本節書摘來自華章出版社《編譯與反編譯技術》一書中的第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
（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)文法。
（3）給出對于輸入符号串“abab”的lr(1)分析過程。
證明下面文法是slr(1)文法，但不是lr(0)文法。
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
b→d
lr(0)、slr(1)、lr(1)及lalr(1)分析方法有何共同特征？它們的本質差別是什麼？
一個非lr(1)的文法如下：
l→mlb | a
m→ε
請給出所有有移進–歸約沖突的lr(1)項目集，以說明該文法确實不是lr(1)文法。