當前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

语法分析：自上而下分析

發布時間：2023/12/14 编程问答 26 豆豆

生活随笔收集整理的這篇文章主要介紹了语法分析：自上而下分析小編覺得挺不錯的,現在分享給大家,幫大家做個參考.

概述

本節將介紹編譯程序構造中的一些典型的語法分析方法。語法分析器的功能，自上而下分析面臨的問題，LL（1）分析法

語法分析器的功能

語法分析是編譯過程的核心部分。它的任務是在詞法分析識別出單詞符號串的基礎上，分析并判定程序的語法結構是否符合語法規則。

語言的語法結構是用上下文無關文法描述的。因此，語法分析器的工作本質上就是按文法的產生式，識別輸入符號串是否為一個句子。這里所說的輸入串是指由單詞符號（文法的終結符）組成的有限序列。對一個文法，當給你一串（終結）符號時，怎樣知道它是不是該文法的一個句子（“程序”）呢？這就要判斷，看是否能從文法的開始符號出發推導出這個輸入串，或者，從概念上講，就是要建立一棵與輸入串相匹配的語法分析樹。
按照語法分析樹的建立方法，我們可以粗略地把語法分析辦法分成兩類，一類是自上而下分析法，另一類是自下而上分析法。本章主要介紹自上而下分析法，下一章我們將介紹自下而上分析法。

自上而下分析面臨的問題

現在來討論自上而下的語法分析方法。顧名思義，自上而下就是從文法的開始符號出發，向下推導，推出句子。我們首先將簡單地介紹自上而下分析的一般方法。這種方法是帶“回溯”的。下一節，將著重討論一種廣為使用的不帶回溯的遞歸子程序（遞歸下降）分析方法。
自上而下分析的主旨是，對任何輸入串，試圖用一切可能的辦法，從文法開始符號（根結）出發，自上而下地為輸入串建立一棵語法樹。或者說，為輸入串尋找一個最左推導。這種分析過程本質上是一種試探過程，是反復使用不同產生式謀求匹配輸入串的過程。
實現這種自上而下的帶回溯試探法的一個簡單途徑是讓每個非終結符對應一個遞歸子程序。每個這種子程序可作為一個布爾過程。一旦發現它的某個候選與輸入串相匹配，就用這個候選去擴展語法樹，并返回“真”值；否則，保持原來的語法樹和IP值不變，并返回“假”值。
上述這種自上而下分析法存在許多困難和缺點。
首先是文法的左遞歸性問題。一個文法是含有左遞歸的，如果存在非終結符P
PPa
含有左遞歸的文法將使上述的自上而下的分析過程陷入無限循環。即，當試圖用P去匹配輸入串時，我們會發現，在沒有識別任何輸入符號的情況下，又得重新要求P去進行新的匹配。因此，使用自上而下分析法必須消除文法的左遞歸性。
其次，由于回溯，就碰到一大堆麻煩事情。如果我們走了一大段錯路，最后必須回頭，那么，就應把已經做的一大堆語義工作（指中間代碼產生工作和各種表格的簿記工作）推倒重來。這些事情既麻煩又費時間，所以，最好應設法消除回溯。
第三，在上述的自上而下分析過程中，當一個非終結符用某一候選匹配成功時，這種成功可能僅是暫時的。例如，就文法（4.1）而言，考慮輸入串x**y。若對A首先使用第二個候選式，A將成功地把它的唯一子結匹配于輸入串的第二個符號。但S的第三個子結y與第三個輸入符號不匹配。因而，導致了無法識別輸入串x**y是一個句子的事實。然而，若A首先使用它的第一個候選**，則整個輸入串即可獲得成功分析。這意味著，A首先使用第二個候選所得的成功匹配是虛假的。由于這種虛假現象，我們需要更復雜的回溯技術。一般說，要消除虛假匹配是很困難的。但若從最長的候選開始匹配，虛假匹配的現象就會減少一些。
第四，當最終報告分析不成功時，我們難于知道輸入串中出錯的確切位置。
最后，由于帶回溯的自上而下分析實際上采用了一種窮盡一切可能的試探法，因此，效率很低，代價極高。嚴重的低效使得這種分析法只有理論意義，而在實踐上價值不大。
后面，我們將集中討論不帶回溯的自上而下分析法。

LL(1)分析法

左遞歸消除

直接消除見諸于產生式中的左遞歸是比較容易的。假定關于非終結符P的規則為

P→Pa | b

其中b不以P開頭。那么，我們可以把P的規則改寫為如下的非直接左遞歸形式：

P→bP￠
P￠→aP￠|e ,e為空字）

這種形式和原來的形式是等價的，也就是說，從P推出的符號串是相同的。
如何消除一個文法的一切左遞歸呢？雖然困難不少，但仍有可能。如果一個文法不含回路（形如PP的推導），也不含以e為右部的產生式，那么，執行下述算法將保證消除左遞歸（但改寫后的文法可能含有以e為右部的產生式）。
消除左遞歸算法：

把文法G的所有非終結符按任一種順序排列成P1，P2，…，Pn；按此順序執行；

FOR i:=1 TO n DO
BEGIN
FOR j:=1 TO i-1 DO
把形如Pi→Pjg的規則改寫成
Pi→d1g|d2g|…|dkg。其中Pj→d1|d2|…|dk是關于Pj的所有規則；
消除關于Pi規則的直接左遞歸性
END

化簡由2所得的文法。即去除那些從開始符號出發永遠無法到達的非終結符的產生規則。

消除回溯、提左因子

欲構造行之有效的自上而下分析器，必須消除回溯。為了消除回溯就必須保證：對文法的任何非終結符，當要它去匹配輸入串時，能夠根據它所面臨的輸入符號準確地指派它的一個候選去執行任務，并且此候選的工作結果應是確信無疑的。也就是說，若此候選獲得成功匹配，那么，這種匹配決不會是虛假的；若此候選無法完成匹配任務，則任何其它候選也肯定無法完成。換句話說，假定現在輪到非終結符A去執行匹配（或稱識別）任務，A共有n個候選a1，a2，…，an，即A→a1 | a2 | … |an。A所面臨的第一個輸入符號為a，如果A能夠根據不同的輸入符號指派相應的候選ai作為全權代表去執行任務，那就肯定無需回溯了。在這里A已不再是讓某個候選去試探性地執行任務，而是根據所面臨的輸入符號a準確地指派唯一的一個候選。其次，被指派候選的工作成敗完全代表了A。

前面已經說過，欲實行自上而下分析，文法不得含有左遞歸。令G是一個不含左遞歸的文法，對G的所有非終結符的每個候選a定義它的終結首符集FIRST（a）為：

FIRST（a）＝{a | aa…, a?V T}

特別是，若ae，則規定e?FIRST（a）。換句話說，FIRST（a）是a的所有可能推導的開頭終結符或可能的e。如果非終結符A的所有候選首符集兩兩不相交，即A的任何兩個不同候選a i和a j

FIRST（ai）∩FIRST（a j）＝f
那么，當要求A匹配輸入串時，A就能根據它所面臨的第一個輸入符號a，準確地指派某一個候選前去執行任務。這個候選就是那個終結首符集含a的a。
應該指出，許多文法都存在那樣的非終結符，它的所有候選的終結首符集并非兩兩不相交的。例如，通常關于條件句的產生式

語句?if 條件 then 語句 else 語句| if 條件 then 語句

就是這樣一種情形。

如何把一個文法改造成任何非終結符的所有候選首符集兩兩不相交呢？其辦法是，提取公共左因子。例如，假定關于A的規則是

A→db 1 | db 2 | …| db n | g 1 | g 2 | … g m （其中，每個g 不以d開頭）

那么，可以把這些規則改寫成

A→dA￠ | g 1 | g 2 | … | g m
A￠→b 1 | b 2 | … | b n
經過反復提取左因子，就能夠把每個非終結符（包括新引進者）的所有候選首符集變成為兩兩不相交。我們為此付出的代價是，大量引進新的非終結符和e-產生式。

LL(1)分析條件

當一個文法不含左遞歸，并且滿足每個非終結的所有候選首符集兩兩不相交的條件，我們可以找出滿足構造不帶回溯的自上而下分析的文法條件：

文法不含左遞歸，

對于文法中每一個非終結符A的各個產生式的候選首符集兩兩不相交。即，若A→a 1|a 2|…|an
則FIRST（a i）∩FIRST（a j）＝f（i1j）

對文法中的每個非終結符A，若它存在某個候選首符集包含e，則
FIRST（A）∩FOLLOW（A）=f
如果一個文法G滿足以上條件，則稱該文法G為LL（1）文法。

這里，LL（1）中的第一個L表示從左到右掃描輸入串，第二個L表示最左推導，1表示分析時每一步只需向前查看一個符號。
對于一個LL（1）文法，可以對其輸入串進行有效的無回溯的自上而下分析。假設要用非終結符A進行匹配，面臨的輸入符號為a，A的所有產生式為

A→a 1 | a 2 | … | an
1. 若a?FIRST（a i），則指派a i去執行匹配任務；
2. 若a不屬于任何一個候選首符集，則：
(1) 若e屬于某個FIRST（ai ）且a?FOLLOW（A），則讓A與e自動匹配。
(2) 否則，a的出現是一種語法錯誤。
根據LL（1）文法的條件，每一步這樣的工作都是確信無疑的。

遞歸下降分析程序構造

當一個文法滿足LL（1）條件時，我們就可以為它構造一個不帶回溯的自上而下分析程序，這個分析程序是由一組遞歸過程組成的，每個過程對應文法的一個非終結符。這樣的一個分析程序稱為遞歸下降分析器。如果用某種高級語言寫出所有遞歸過程，那就可以用這個語言的編譯系統來產生整個的分析程序。例如，考慮文法，它的每個非終結符所對應的遞歸過程列于如下圖1。其中，ADVANCE是指把輸入串指示器IP調至指向下一個輸入符號；SYM是指IP當前所指的那個輸入符號；ERROR為出錯診察處理程序。
對于圖1的遞歸子程序，我們假定在開始工作前，輸入串指示器IP指向第一個輸入符號。當每個子程序工作完畢之后，IP總是指向下一個未處理的符號。請注意遞歸子程序E￠，我們知道，關于E￠的規則是

E￠→+TE￠|e
即E￠只有兩個候選。第一個候選的開頭終結符為＋，第二個候選為e。這就是說，當E￠面臨輸入符號＋時就令第一個候選進入工作，當面臨任何其它輸入符號時，E￠就自動認為獲得了匹配（這時，更精確的做法是判斷該輸入符號是否屬于FOLLOW（E￠））。遞歸過程E￠就是根據這一原則設計的。同理，關于T￠的過程也是如此。

PROCEDURE E； PROCEDURE T；BEGIN BEGINT；E￠ F；T￠END； ENDPROCEDURE E￠； PROCEDURE T￠；IF SYM=‘+’ THEN IF SYM=‘*’ THENBEGIN BEGINADVANCE； ADVANCE；T；E￠ F；T￠END END；PROCEDURE F；IF SYM=‘i’ THEN ADVANCEELSEIF SYM=‘(’ THENBEGINADVANCE;E；IF SYM=‘)’ THEN ADVANCEELSE ERRORENDELSE ERROR;

圖1 遞歸子程序

在前面的上下文無關文法產生式（或稱巴科斯范式）中我們只用到了兩個元符號“→”和“|”。下面我們擴充幾個元語言符號：

用花括號{a}表示閉包運算a*。

用表示a可任意重復0次至n次，。

用方括號{a}_1^0表示，即表示a的出現可有可無（等價于a|e）。

引入上述元符號的文法亦稱擴充的巴科斯范式。
例如，通常的“實數”可定義為：

decimal→ [sign]integer.{digit}[exponent]exponent→E[sign]integerinteger→digit{digit}sign→+|-

用這種定義系統來描述語法的好處是，直觀易懂，便于表示左遞歸消去和因子提取。對于構造自上而下分析器來說，采用這種定義系統描述文法顯然是非常可取的。

預測分析程序

預測分析程序工作過程

預測分析表是一個M[A，a]形式的矩陣。其中，A為非終結符，a是終結符或‘＃’（注意，‘＃’不是文法的終結符，我們總把它當成輸入串的結束符。雖然它不是文法的一部分，但假定它的存在將有助于簡化分析算法的描述）。矩陣元素M[A，a]中存放著一條關于A的產生式，指出當A面臨輸入符號a時所應采用的候選。M[A，a]中也可能存放一個“出錯標志”，指出A根本不該面臨輸入符號a。

棧STACK用于存放文法符號。分析開始時，棧底先放一個‘＃’，然后，放進文法開始符號。同時，假定輸入串之后也總有一個‘＃’，標志輸入串結束。
預測分析程序的總控程序在任何時候都是按STACK棧頂符號X和當前的輸入符號a行事的,如圖4.4。對于任何（X，a），總控程序每次都執行下述三種可能的動作之一：
1. 若X＝a＝‘＃’，則宣布分析成功，停止分析過程。
2. 若X＝a 1‘＃’，則把X從STACK棧頂逐出，讓a指向下一個輸入符號。
3. 若X是一個非終結符，則查看分析表M。若M[A，a]中存放著關于X的一個產生式，那么，首先把X逐出STACK棧頂，然后，把產生式的右部符號串按反序一一推進STACK棧（若右部符號為e，則意味不推什么東西進棧）。在把產生式的右部符號推進棧的同時應做這個產生式相應的語義動作（目前暫且不管）。若M[A，a]中存放著“出錯標志”，則調用出錯診察程序ERROR。

預測分析程序的總控程序略微形式一點的描述是：
BEGIN
首先把‘＃’然后把文法開始符號推進STACK棧；
把第一個輸入符號讀進a；
FLAG:=TRUE;
WHILE FLAG DO
BEGIN
把STACK棧頂符號上托出去并放在X中；
IF X?VT THEN
IF X= a THEN 把下一輸入符號讀進a
ELSE ERROR
ELSE IF X=‘#’ THEN
IF X=a THEN FLAG:=FALSE ELSE ERROR
ELSE IF M[A，a]={X→X1X2…Xk}THEN
把Xk,Xk-1,…,X1一一推進STACK棧
/* 若X1X2…Xk=e，不推什么進棧 */
ELSE ERROR
END OF WHILE;
STOP /分析成功，過程完畢/
END

預測分析表的構造

下面，我們介紹對于任給的文法G，如何構造它的預測分析表M[A，a]。為了構造預測分析表M，我們需要先構造與文法G有關的集合FIRST和FOLLOW。

首先，我們來討論如何對每一個文法符號X?VT∪VN構造FIRST（X）。其辦法是，連續使用下面的規則，直至每個集合FIRST不再增大為止：
1. 若X?VT，則FIRST（X）＝{X}。
2. 若X?VN，且有產生式X→a…，則把a加入到FIRST（X）中；若X→e也是一條產生式，則把e也加到FIRST（X）中。
3. 若X→Y…是一個產生式且Y?VN，則把FIRST（Y）中的所有非e-元素都加到FIRST（X）中；若X→Y1Y2…Yk是一個產生式，Y1，…，Yi-1都是非終結符，而且，對于任何j，1￡j￡i-1，FIRST（Yj）都含有e（即Y1…Yi-1e），則把FIRST（Yi）中的所有非e-元素都加到FIRST（X）中；特別是，若所有的FIRST（Yj）均含有e，j＝1，2，…，k，則把e加到FIRST（X）中。

現在，我們能夠對文法G的任何符號串a=X1X2…Xn構造集合FIRST（a）。首先，置FIRST（a）＝FIRST（X1）{e}；若對任何1￡j￡i-1，e?FIRST（Xj），則把FIRST（Xi）{e}加至FIRST（a）中；特別是，若所有的FIRST（Xj）均含有e，1￡j￡n，則把e也加至FIRST（a）中。顯然，若a＝e則FIRST（a）＝{e}。

對于文法G的每個非終結符A構造FOLLOW（A）的辦法是，連續使用下面的規則，直至每個FOLLOW不再增大為止：

對于文法的開始符號S，置＃于FOLLOW（S）中；

若A→aBb是一個產生式，則把FIRST（b）{e}加至FOLLOW（B）中；

若A→aB是一個產生式，或A?aBb是一個產生式而be（即e?FIRST（b）），則把FOLLOW（A）加至FOLLOW（B）中。

在對文法G的每個非終結符A及其任意候選a都構造出FIRST（a）和FOLLOW（A）之后，我們現在可以用它們來構造G的分析表M[A，a]。構造分析表算法的思想背景是很簡單的。例如，假定A→a是一個產生式，a ?FIRST（a）。那么，當A呈現于STACK棧之頂且a是當前的輸入符號時，a應被當作是A唯一合適的全權代表。因此，M[A，a]中應放進產生式A→a。當a＝e或ae時，如果當前面臨的輸入符號a（可能是終結符或‘＃’）屬于FOLLOW（A），那么，A→a就認為已自動得到匹配，因而，應把A?a放在M[A，a]中。根據這個思想背景，構造分析表M的算法是：

對文法G的每個產生式A→a執行第2步和第3步；

對每個終結符a ?FIRST（a），把A→a加至M[A，a]中；

若e?FIRST（a），則對任何b?FOLLOW（A）把A→a加至M[A，b]中。

把所有無定義的M[A，a]標上“出錯標志”。

上述算法可應用于任何文法G以構造它的分析表M。但對于某些文法，有些M[A，a]可能持有若干個產生式，或者說有些M[A，a]可能是多重定義的。如果G是左遞歸或二義的，那么，M至少含有一個多重定義入口。因此，消除左遞歸和提取左因子將有助于獲得無多重定義的分析表M。
可以證明，一個文法G的預測分析表M不含多重定義入口，當且僅當該文法為LL（1）的

小結

通過這一章的學習，我們了解了自上而下分析法的基本思想，學習了遞歸下降分析法的基本方法：如消除左遞歸、消除回溯、構造遞歸下降子程序。學習了預測分析方法，掌握了預測分析表的構造方法、LL（1）文法的定義。在下一章中，我們將討論自下而上語法分析方法。

典型題解

例題1按照喬姆斯基(Chomsky)對文法的分類，指出下述文法的所屬類型，并給出所描述的語言。
(a) S → Be
B → eC | Af
A → Ae | e
C → Cf
D → fDA

(b) A → ε| aB
B → Ab | a

解題思路：這類問題主要是考察考生對Chomsky形式語言體系的掌握情況，因此，首先應當理解各種類型文法的特征，注意各種類型文法對產生式形式上的限制。本題的另一個考察的知識點是文法的一些基本概念，如推導、句子、語言等。解答： (a) 該文法是上下文無關文法(2型)，從D → fDA可以看出該文法不是正規文法。它所描述的語言是L={eife | i≥1}∪{ efie | i≥1} (b) 該文法是上下文無關文法(2型)，從兩個產生式可以看出，該文法既不是右線性文法，也不是左線性文法。它所描述的語言是L={anbm | n,m≥0且 (n=m 或 n-m=2)} (c) 該文法是上下文有關文法(1型)，從產生式Aa → Sa可以看出，該文法不是上下文無關文法。它所描述的語言是L={(abc)m | n>0}注意：(a)文法描述的語言是文法推導的句子的全體，該文法推導的句子的過程中不會引用非終結符D。

例題2給出文法G(S)
S → aSb | P
P → bPc | bQc
Q → Qa | a
1) 它是Chomsky哪一型文法？
2) 它生成的語言是什么?

解題思路：
注意到S推出的串的形式是aiPbi(i≥0)，而P推出的串的形式是bjQcj(j≥1), Q推出的串的形式是ak(k≥1)。

解答：
1）該文法是Chomsky2型文法，即上下文無關文法。
2）它生成的語言是L={aibjakcjbi | i≥0，j≥1，k≥1}

例題3寫一個文法G，使得L(G)={ anbman|n，m30}。

解題思路：
寫出語言的文法是檢查考生形式抽象的能力。解答這類問題，首先應當仔細研究語言的結構特點，通常這些語言具有形式上的對稱性和字符數目上的相關性等特點，這些特性可以用文法的遞歸定義來實現。

解答：所求文法是：
G(S)：
S ? aSa | B
B ? bB| e

例題4 將文法G(S)改寫成等價的正規文法。
G(S):
S → dAB
A → aA | a
B → Bb |ε

解題思路：
對于這類題目，首先求出文法描述的正規語言，寫出相應的正規式，在此基礎上構造相應的DFA，最后把DFA的狀態轉換成文法的非終結符，就能夠寫出等價的正規文法了。

解答：該文法描述的語言是daibj(i>0，j≥0)，對應的DFA是：

相應的正規文法是：
G(S):
S → dA
A → aB
B → aB | bC |ε
C → bC |ε

注意: 把DFA的轉換成正規文法時，終態對應的非終結符應當有ε候選式(如B,C)。

例題5 按指定類型，給出語言的文法
(a) L={aibj|j>i≥1} 的上下文無關文法
(b) 字母表Σ={a,b}上的同時只有奇數個a和奇數個b的所有串的集合的正規文法
(c) 有相同個數的a和b組成的句子的無二義文法

解題思路：
給出語言的文法可以從多個角度進行思考，如分解語言的結構，利用有限自動機，找出語言的遞歸或遞推特性等。
語言(a) L={aibj|j>i≥1}，實際上可以看成aibibj-i的形式，而aibi可以由A → aAb | ab規則來描述，bj-i可以由B → bB | b規則來描述。

語言(b)的描述可以借助有限自動機的思想，非終結符A、B、C、S分別表示下面四種狀態：

識別了偶數個a和偶數個b的狀態
識別了奇數個a和偶數個b的狀態
識別了偶數個a和奇數個b的狀態
識別了奇數個a和奇數個b的狀態
文法規則只需要描述這些非終結符之間的推導關系，即狀態之間的轉換關系。
語言(c)的描述可以采用遞歸的思想，寫出相應的無二義文法。

例題6 寫一個上下文無關文法，使其語言是能被5整除且不以0開頭的無符號整數的集合。(如{5，10，15，…})

解題思路：
能被5整除的數從形式上看，是以0，5結尾的數字串。題目要求的不以0開頭，注意0不是該語言的句子。

解答：所求文法為：
G(S):
S → M F | 5
F → 5 | 0
N → 1 |2 | 3 | 4 | 5 | 6 | 7 | 8｜ 9
D → N | 0
M → M D | N
其中， S代表能被5整除且不以0開頭的無符號整數；
F代表可以出現在個位上的數字；
D代表所有數字；
N代表所有非零數字；
M代表所有不以零開頭的數字串；

例題7
寫一個文法使其語言為L(G)={ anbm| 2n>m≥n≥1}
解題思路:
b的個數大于或等于a的個數，但又比a的個數的2倍要少。這是一種類型的問題，一般在兩個或多個字符的數量上做文章，對于這類問題，有一種固定的問題求解方法。以本題為例，b的個數在a的個數的一倍和兩倍之間，那么就存在兩個邊界：一倍和兩倍，我們就分別為它們寫出兩個產生式：
1．S —> aSb
2．S —> aSbb
此時可以看到，用產生式1擴展時所產生的a和b的個數相等，而用產生式2擴展時所產生的b的個數是a的個數的兩倍，如果同時使用兩個產生式進行擴展，那b的個數將在a的個數的一倍和兩倍之間，滿足了這個前提之后，再用另一個產生式（S —> ab）來保證邊界條件（2n>m、m≥n和n≥1）就可以了。如果邊界條件是2n≥m>n≥1，則可以用產生式S —> abb來滿足。

解答: S —> aSb | aSbb | ab

例題8試簡述二義性概念。
解答：如果一個文法存在某個句子對應兩顆不同的語法樹，則說這個文法是二義的。如果一個語言是二義的，當且僅當它不存在無二義性的文法。文法的二義性與語言的二義性是兩個不同的概念。例如，對于某種語言L來說，可能存在兩個文法G和G’，有L(G)=L(G’)=L，但文法G是二義的，而G’是無二義的，這時，語言L并不是二義的。

例題9文法G的產生式集為{S → S+S |S*S | i | (S)}，對于輸入串i+i*i：
1) 給出一個推導；
2) 畫出一棵語法樹；
3) 文法G是否是二義性的，請證明你的結論？

解題思路：
這類題目，重點考察推導、語法樹和二義性等基本概念。要證明一個文法是二義性的，只要找出該文法的一個句子，說明該句子有兩種不同的最左推導或最右推導，或者有兩棵不同的語法樹。
解答：
1) STS+STi+ST i+S*S T i+i*S T i+i*i
2) i+i*i 的語法樹
3) 文法G是二義性的。考慮句子i+i*i，除了語法樹外，還有另一棵語法樹，所以文法G是二義性的。

例題10已知文法G=({S}，{a}，{S → SaS, S →ε}，S)
1) 該文法是否是二義性文法，為什么？
2) 該文法是否是OPG(算符優先文法)文法，為什么？
3) 該文法是否是LL(1)文法，為什么？
4) 該文法是否是SLR(1)文法，為什么？

解題思路：
本題和核心是判斷文法的二義性，同時必須掌握OPG(算符優先文法)文法、 LL(1)文法和SLR(1)文法和二義性文法的關系，并根據它們之間的關系判斷文法的性質。
解答：考慮該文法的句子aa，我們有下面兩個不同的最左推導：
STSaSTSaSaSTaSaSTaaSTaa
STSaSTaSTaSaSTaaSTaa
所以該文法是二義性的。因為OPG(算符優先文法)文法， LL(1)文法和SLR(1)文法一定不是二義性文法，所以，該文法不是OPG(算符優先文法)文法、 LL(1)文法和SLR(1)文法。

例題11 生成L={ albmclanbn| l30，m31，n32}這種語言的文法是什么？它是Chomsky哪一型文法？

解答：所求文法是G(S)
S → AC
A → aAc | B
B → bB | b
C → aCb | ab
它是Chomsky 2型文法，即上下文無關文法。

例題12文法G(S)：
S → aSPQ | abQ
QP → PQ
bP → bb
bQ → bc
cQ → cc
它是Chomsky哪一型文法？它生成的語言是什么？

解答：從規則形式上可以看出，文法G是Chomsky 1型文法，即上下文有關文法。它生成的語言是L={ anbncn | n31}

例題13給出下列術語的嚴格定義：
1) 上下文無關文法 2) LL(1)文法

解答：
上下文無關文法的定義：
形式上說，一個上下文無關文法G是一個四元式（VT，VN，S，P），其中
VT是一個非空有限集，它的每個元素稱為終結符號；
VN是一個非空有限集，它的每個元素稱為非終結符號，VT∩VN＝f；
S是一個非終結符號，稱為開始符號；
P是一個產生式集合（有限），每個產生式的形式是P?a，其中，P?VN， a?（VT∪VN）*。開始符號S至少必須在某個產生式的左部出現一次。

LL（1）文法的定義：
如果一個文法G滿足下面的條件，則稱該文法G為LL（1）文法：
1. 文法不含左遞歸，
2. 對于文法中每一個非終結符A的各個產生式的候選首符集兩兩不相交。即，若A→a1|a2|…|an
則 FIRST（ai）∩FIRST（aj）＝f （i1j）
3. 對文法中的每個非終結符A，若它存在某個候選首符集包含e，則
FIRST（A）∩FOLLOW（A）=f

例題14給出文法G1(S)
S → aSb | P
P → bPc | bQc
Q → Qa | a
消除文法的左遞歸、提取左公共因子后是不是LL(1)文法？請證實。

本章練習

考慮下面文法G1：
S→a | ù | (T)
T→T, S | S
(1) 消去G1的左遞歸。然后，對每個非終結符，寫出不帶回溯的遞歸子程序。
(2) 經改寫后的文法是否是LL（1）的？給出它的預測分析表。

對下面的文法G
E→TE￠
E￠→+E | e
T→FT￠
T￠→T | e
F→PF￠
F￠→*F￠ | e
P→ (E) | a | b | ù
(1) 計算這個文法的每個非終結符的FIRST和FOLLOW。
(2) 證明這個文法是LL（1）的。
(3) 構造它的預測分析表。
(4) 構造它的遞歸下降分析程序。

下面文法中，哪些是LL（1）的，說明理由。

(1) S→Abc
A→a | e
B→b | e

(2) S→Ab
A→a | B | e

(3) S→ABBA
A→a | e
B→b | e

(4) S→aSe | B
B→bBe | C
C→cCe | d

對下面文法
Expr→-Expr
Expr→ (Expr)|Var ExprTail
ExprTail→-Expr | e
Var→id VarTail
VarTail→ (Expr) | e
(1) 構造LL（1）分析表。
(2) 給出對句子id–id((id))的分析過程。

參考文獻

［1］Alfred V.Aho, Ravi Sethi, Jeffrey D. Ullman. Compilers: Principles, Techniques, and Tools. Acldison-Wesley Publishing Company, 1986.
［2］A.V.Aho, J.D. Ullman. Principles of Compiler Descign, Addison=Wesley, 1977.
［3］Arthur B.Pyster. Compiler Design and Constuction. Van Nostrand Reihold Company, 1980.
［4］陳火旺，錢家驊，孫永強. 程序設計語言編譯原理. 北京：國防工業出版社，1984.
［5］王兵山，吳兵，形式語言. 國防科技大學出版社，1988.
［6］霍普克羅夫特，厄爾曼. 形式語言及其與自動機的關系. 科學出版社，1979.

總結

以上是生活随笔為你收集整理的语法分析：自上而下分析的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。