先打一发广告，我这个博客一开始就是用于记录算法的学习过程的，后来干脆想着把课堂笔记也整理整理放上来。想想这学期快结束了，下学期开始又要开始学习算法啦。我是准备从0开始学习的，借助于高中生信息学竞赛的平台。欢迎各位各类同学加进来，笑着问我为什么刷那么慢，或者跟我一起从0开始。欢迎对照对边导航栏，对准“算法向”的“洛谷”查看进度，刷完这个之后会继续刷USACO。

群号是⑥⑥①⑨②2025，这是我设置的一道很低的门槛用来阻止广告的。入群的验证暗号是：我爱编译原理

---

语法分析——自上而下分析

语法分析器的功能

语法分析的前提

• 对语言的语法结构进行描述
  
  • 采用正规式和有限自动机可以描述和识别语言的单词符号(其实就是上一次复习材料里面的东西)
  • 用上下文无关文法来描述语法规则

上下文无关文法

语法分析的任务

分析一个文法的句子结构

语法分析器的功能

按照文法的产生式（语言的语法规则），识别输入符号串是否为一个句子（合式程序）

自上而下分析面临的问题

回溯

左递归

LL(1)分析法

消除左递归

消除左递归，这个以前整理过。

消除回溯

为了消除回溯必须保证：

当对文法的任何非终结符，当要它去匹配输入串时，能够根据它所面临的输入符号准确地指派它的一个候选去执行任务，并且此候选的工作结果应该是确信无疑的。

假设有A→α1|α2|⋯|αn

令G 是一个不含左递归的文法，对G 的所有非终结符的每个候选α 定义它的终结首符集FIRST(α) 为：

First(α)={a|α⇒∗a⋯,a∈VT}

特别的，若α⇒∗ϵ ，则规定ϵ∈FIRST(α)

如果非终结符A的所有候选首符集两两不相交，即A的任何两个不同候选αi 和αj ，FIRST(αi)⋂FIRST(αj)=∅

当要求A输入匹配输入串时，A就能根据它所面临的第一个输入符号a，准确地指派某一个候选前去执行任务。这个候选就是那个终结首符集含a的α 。

为了消除回溯，我们必须提取最左公共子表达式

假设要用非终结符A进行匹配，面临的输入符号为a，A的所有产生式为A→α1|α2|⋯|αn

1. 若a∈FIRST(αi) ，则指派αi 执行匹配任务；
2. 若a 不属于任何一个候选首符集，则“
   
   1. 若ϵ 属于某个FIRST(αi) 且a∈FOLLOW(A) ，则让A与ϵ 自动匹配
   2. 否则，a的出现是一种语法错误

FIRST和FOLLOW集合

FIRST(α)={a|α⇒∗a⋯,a∈VT}

FOLLOW(A)={a|S⇒∗⋯Aa⋯,a∈VT}

递归下降分析程序构造

预测分析程序