本节书摘来自华章出版社《编译与反编译技术》一书中的第3章，第3.6节本章小结，作者庞建民，陶红伟，刘晓楠，岳峰，更多章节内容可以访问云栖社区“华章计算机”公众号查看。
3.6 本章小结
语法分析是编译的核心部分，其任务是检查由词法分析器所产生的单词符号串是否符合源语言的语法规则。要分析源程序的语法规则，必须对编写源语言的语法结构进行描述，因此本章首先介绍了描述语法结构的上下文无关文法的相关概念。接下来，讨论了编译器常用的两种语法分析方法，即自上而下的语法分析方法和自下而上的语法分析方法，前者是为输入串寻找一个最左推导，后者是为输入串寻找一个最左归约，它们的共同点是从左向右逐个地扫描输入。
自上而下的语法分析会遇到左递归问题、回溯问题，因此本章又分别介绍了消除左递归和回溯的方法。此外，介绍了一类可以进行确定的自上而下的语法分析的文法，即LL(1)文法。讨论了如何利用FIRST集和FOLLOW集来判定某个上下文无关文法是否为LL(1)文法。探讨了如何利用LL(1)分析法对LL(1)文法进行不带回溯的非递归自上而下的语法分析，并给出了LL(1)分析法的表驱动方式的实现，也即LL(1)分析器。
自下而上语法分析法是一种“移进–归约”法。这一部分首先介绍了移进–归约的基本思想和表驱动方式的实现：移进–归约分析程序。接下来，介绍一种有效的自下而上的语法分析方法，即LR分析法。讨论了几种常用的LR分析方法，包括LR(0)分析方法、SLR(1)分析方法、LR(1)分析方法和LALR(1)分析方法，并对它们进行了比较。最后，介绍了LALR(1)语法分析器的自动生成工具YACC软件。
习题
- 考虑文法 bexpr → bexpr or bterm | bterm
bterm → bterm and bfactor | bfactor
bfactor → not bfactor | ( bexpr) | true | false
（1）请指出该文法的终结符号、非终结符号和文法开始符号。
（2）为句子not ( true or false )构造一棵语法分析树。
（3）给出句子not ( true or false )的最左推导和最右推导。
（4）试求该文法所产生的语言。
- 给出产生下面语言的上下文无关文法
（1）L1 = {wcwT}，其中wT是w的逆
（2）L2 = {aibncn | n≥1，i≥0}
（3）L3 = {anbnambm | n，m≥0}
（4）L4 = {1n0m1m0n | n，m≥0}
-
对于文法G(S)：S→(L)∣aS∣a
L→L，S∣S（1）画出句型(S，(a))的语法树。
（2）写出上述句型的所有短语、直接短语、句柄。
- 已知文法G(S)：S→aSb∣Sb∣b，试证明文法G(S)为二义文法。
- 已知文法G(S)：S→SaS∣ε，试证明文法G(S)为二义文法。
- 试证明：左递归的文法不是LL(1)文法。
- 试证明：LL(1)文法不是二义的。
- 考虑下面文法G(S)： S→(T)∣^∣a
T→T，S∣S
（1）消去G(S)的左递归。
（2）经改写后的文法是否是LL(1)文法？如果是，给出它的预测分析表。
- 已知文法G(A)： A→aABc∣a
B→Bb∣d
（1）试给出与G(A)等价的LL(1)文法G'(A)。
（2）构造G'(A)的LL(1)分析表。
（3）给出输入串“aadc#”的预测分析过程。
- 已知文法G(V)： V→N∣N[E]
E→V∣V+E
N→i
判断该文法是否为LL(1)文法？如果不是，其是否可以改造为LL(1)文法？
- 构造下面文法G(D)的LL(1)分析表。
D→TL
T→int | real
L→id R
R→，id R | ε
- 考虑如下文法G(E)：
E→(L) | a
L→L，E | E
（1）构造该文法的LR(0)项目集规范族及识别其所有活前缀的DFA。
（2）构造该文法的SLR(1)分析表。
（3）给出对输入符号串“((a)，a，(a，a))”的移进–归约分析动作。
（4）该文法是LR(0)文法吗？如果是，请构造其LR(0)分析表；如果不是，请说明理由。
- 考虑习题12中的文法：
（1）构造该文法的LR(1)项目集规范族及识别其所有活前缀的DFA。
（2）构造该文法的LR(1)分析表。
（3）构造该文法的LALR(1)项目集规范族及识别其所有活前缀的DFA。
（4）构造该文法的LALR(1)分析表。
- 试构造下述文法的SLR(1)分析表。
S→bASB | bA
A→dSa | e
B→cAa∣c
- 考虑文法
E→E + T | T
T→TF | F
F→F * | a | b
（1）为该文法构造SLR(1)分析表。
（2）构造其LALR(1)分析表。
- 考虑文法
S→A
A→BA |ε
B→aB | b
（1）证明该文法是LR(1)文法。
（2）构造该文法的LR(1)分析表。
（3）给出对于输入符号串“abab”的LR(1)分析过程。
- 证明下面文法是SLR(1)文法，但不是LR(0)文法。
S→A
A→Ab | bBa
B→aAc | a | aAb
- 证明下面文法是SLR(1)文法，但不是LL(1)文法。
S→SA | A
A→a
- 证明下面的文法是LL(1)文法，但不是SLR(1)文法。
S→AaAb | BbBa
A→ε
B→ε
- 证明所有LL(1)文法都是LR(1)文法。
- 证明下面的文法是LALR(1)文法，但不是SLR(1)文法。
S→Aa | bAc | dc | bda
A→d
- 证明每个SLR(1)文法都是LALR(1)文法。
- 证明下面的文法是LR(1)文法，但不是LALR(1)文法。
S→Aa | bAc | Bc | bBa
A→d
B→d
- LR(0)、SLR(1)、LR(1)及LALR(1)分析方法有何共同特征？它们的本质区别是什么？
- 一个非LR(1)的文法如下：
L→MLb | a
M→ε
请给出所有有移进–归约冲突的LR(1)项目集，以说明该文法确实不是LR(1)文法。
