【正文】 ① 對(duì)詞法分析器產(chǎn)生的單詞符號(hào)進(jìn)行處理，輸出分析樹 ② 與單詞相關(guān)的信息記錄到符號(hào)表中 ③ 類型檢查 ④ 錯(cuò)誤處理 語(yǔ)法分析器任務(wù) 2022/8/28計(jì)算機(jī)學(xué)院 辛明影 116 相關(guān)約定 一 .符號(hào)的使用約定 1. 終結(jié)符 ① .字母表中比較靠前的小寫字 ,如 a,b,c ② . 操作符，如 +、 等 ③ . 標(biāo)點(diǎn)符號(hào)，如括號(hào)、逗號(hào)等 ④ . 數(shù)字 0、 。 9 ⑤ . 黑體串，如 if 、 id等 2022/8/28計(jì)算機(jī)學(xué)院 辛明影 117 ① .字母表中比較靠前的大寫字 ,如 A、 B、 C ② .字母 S，常用來(lái)表示開始符號(hào) ③ . 小寫斜體名字，如 expr、 stmt 2022/8/28計(jì)算機(jī)學(xué)院 辛明影 118 ，如 X、 Y、Z等，用來(lái)表示 文法符號(hào) ，也就是說(shuō)，可以是終結(jié)符，也可以是非終結(jié)符 ，如 u、v…z 等，表示 終結(jié)符的串聯(lián) α、 β、 γ等表示 文法符號(hào)的串 ，所以一個(gè)產(chǎn)生式可寫作： A → α 2022/8/28計(jì)算機(jī)學(xué)院 辛明影 119 使用的技術(shù)、存在的問題及解決方法 2022/8/28計(jì)算機(jī)學(xué)院 辛明影 120 一、 推導(dǎo) 推導(dǎo)：就是用產(chǎn)生式的右部的串來(lái)代 替左部的非終結(jié)符 事實(shí)上推導(dǎo)給出了自頂向下構(gòu)成分析樹過程的精確描述 例：有描述算術(shù)表達(dá)式的文法 G 字符串 id+id*id 是該文法的句子，其推導(dǎo)過程如下： E → E+E| E*E|（ E） |E|id 2022/8/28計(jì)算機(jī)學(xué)院 辛明影 121 E 幾個(gè)約定： =〉 E+T =E+T*F =E+T*id =〉 E+F*id =〉 E+id*id E=〉 E E推導(dǎo)出 E = 一步或多步推導(dǎo) = 零步或多步推導(dǎo) * + =〉 T+id*id =〉 F+id*id =〉 id+id*id 2022/8/28計(jì)算機(jī)學(xué)院 辛明影 122 最左推導(dǎo)：每一步都堅(jiān)持替換當(dāng)前句型中 最左 非終結(jié)符的推導(dǎo) 最右推導(dǎo)：每一步都堅(jiān)持替換當(dāng)前句型中 最右 非終結(jié)符的推導(dǎo)，也稱為 規(guī)范推導(dǎo) + 句子： S =〉 w 稱終結(jié)符串 w是文法 G句子 + 句型： S =〉 α 稱 α是文法 G的句型 + 語(yǔ)言： L（ G） ={w/S =〉 w } 2022/8/28計(jì)算機(jī)學(xué)院 辛明影 123 二、語(yǔ)法樹 語(yǔ)法描繪了如何從文法的開始符號(hào)推導(dǎo)出一個(gè)句子的過程 語(yǔ)法樹可以看成是推導(dǎo)的圖形表示，但它不能顯示出替代的順序 前面句子 id+id*id推導(dǎo)過程所對(duì)應(yīng)的分析樹如下： 2022/8/28計(jì)算機(jī)學(xué)院 辛明影 124 E E + T T T * F F F id id id 2022/8/28計(jì)算機(jī)學(xué)院 辛明影 125 A是某個(gè)內(nèi)結(jié)點(diǎn)的非終結(jié)符標(biāo)記， A1， A2， …… An是該結(jié)點(diǎn)從左到右排列的所有子結(jié)點(diǎn)的標(biāo)記，則 A→ A1 A2…… An是一個(gè)產(chǎn)生式 ε標(biāo)記 語(yǔ)法具有如下特性的樹： 2022/8/28計(jì)算機(jī)學(xué)院 辛明影 126 語(yǔ)法樹的葉結(jié)點(diǎn)從左到右的排列，剛好是這個(gè)文法所產(chǎn)生的語(yǔ)言的一個(gè)句子 一個(gè)文法生成的語(yǔ)言就是它的某個(gè)分析樹所生成的句子的集合 為給定的終結(jié)符串（句子）構(gòu)造一棵分析樹的過程稱為這個(gè)串（句子）的語(yǔ)法分析（ parsing) 2022/8/28計(jì)算機(jī)學(xué)院 辛明影 127 三、二義性 句子 id+id*id 有兩棵分析樹與之對(duì)應(yīng) E E + E id E * E id id E E * E E + E id id id 2022/8/28計(jì)算機(jī)學(xué)院 辛明影 128 給定一個(gè)文法 G，如果 L（ G）中存在一個(gè)具有兩棵或兩棵以上分析樹的句子， 很顯然，描述算術(shù)表達(dá)式的文法 G E → E+E| E*E|（ E） |E|id 是一個(gè)二義性文法 造成二義性的原因是：文法中沒有體現(xiàn)出結(jié)合率和優(yōu)先級(jí) 我們就稱該文法為 二義性的 ， G也叫 二義性文法 。 2022/8/28計(jì)算機(jī)學(xué)院 辛明影 129 大多數(shù)的語(yǔ)法分析器都要求文法是無(wú)二義性的 消除二義性： 可以通過改寫文法來(lái)消除二義性 例： stmt→if expr then stmt |if expr then stmt else stmt |other 2022/8/28計(jì)算機(jī)學(xué)院 辛明影 130 通過例子 if E1 then if E2 then S2 else S3 很容易證明這是一個(gè)二義性文法 s if E then S else S if E then S 2022/8/28計(jì)算機(jī)學(xué)院 辛明影 131 S if E then S if E then S else S 2022/8/28計(jì)算機(jī)學(xué)院 辛明影 132 在程序設(shè)計(jì)語(yǔ)言中，我們常常采用?最近匹配?原則來(lái)解決這種二義性 文法改寫出為： stmt→ matched_stmt |unmatched_stmt matched_stmt → if expr then matched_stmt else matched_stmt | other unmatched_stmt → if expr then matched_stmt else unmatched_stmt | if expr then _stmt 2022/8/28計(jì)算機(jī)學(xué)院 辛明影 133 四、左遞歸 如果文法 G具有一個(gè)非終結(jié)符 A使得對(duì) 某個(gè)字符串 α存在推導(dǎo) A=A α, 例：下面是描述算術(shù)表達(dá)式的算法 S →E E→E+T|T T→T*F|F F→(E)| id 為句子 id*id+id構(gòu)造分析樹 S E + T E + T E + T ： 則稱文法 G是左遞歸的； 如果 A→A α， 則稱文法 G是直接左遞歸 的 + 2022/8/28計(jì)算機(jī)學(xué)院 辛明影 134 左遞歸會(huì)使分析進(jìn)入到無(wú)限循環(huán)之中 消除簡(jiǎn)單左遞歸的方法： 對(duì)于含有左遞歸的產(chǎn)生式 A→A α| β 可用下面的非左遞歸的產(chǎn)生式 代替： A→ β A? A? → αA?| ε 2022/8/28計(jì)算機(jī)學(xué)院 辛明影 135 例：下面是描述算術(shù)表達(dá)式的算法 E→E+T|T T→T*F|F F→(E)| id 消除 E和 T的直接左遞歸，得到： E→TE‘ E‘ → +TE‘|ε T →FT‘ F→(E)|id T‘→*FT‘| ε 2022/8/28計(jì)算機(jī)學(xué)院 辛明影 136 對(duì)于一般情況而言，若某一文法 G的產(chǎn)生式具有如下形式： 則可用如下方法消除左遞歸 : A→A α1| A α2 |…| A α m| β1| β2|…| β n A→β1A?| β2A? |…| β n A? A? → α1A?| α2A?|… | α mA? | ε 很容易證明改造前后的文法是等價(jià)的 2022/8/28計(jì)算機(jī)學(xué)院 辛明影 137 例：文法 G（ P） ： P → （ Q） |aP|a Q →Q ,P|P 試消除左遞歸 2022/8/28計(jì)算機(jī)學(xué)院 辛明影 138 消除左遞歸后，方法改為： P →（ Q） |aP｜ a Q →PＱ’ Q → ，ＰＱ’｜ ε 2022/8/28計(jì)算機(jī)學(xué)院 辛明影 139 S→Qc|c Q → Rb|b R → Sa|a S 這樣的遞歸無(wú)法用前面的方法消除 對(duì)于含有間接左遞歸的文法： =Qc =Rbc = Sabc 出現(xiàn)了左遞歸 2022/8/28計(jì)算機(jī)學(xué)院 辛明影 140 消除左遞歸的一般算法： 輸入：無(wú)循環(huán)推導(dǎo)和 ε 產(chǎn)生式的方法 G 輸出：與 G等價(jià)的無(wú)左遞歸文法 算法： 2022/8/28計(jì)算機(jī)學(xué)院 辛明影 141 A 1A 2… A n i=1 to n do begin for j=1 to i1 do begin 改寫 A i→ A j γ 規(guī)則，方法如下： 如果 A j→ δ 1| δ 2|…| δ k 則 A i→ δ 1 γ | δ 2 γ |…| δ n γ； end 消除 A i中的所有直接左遞歸 End 2所得文法 2022/8/28計(jì)算機(jī)學(xué)院 辛明影 142 S→Qc|c Q → Rb|b R → Sa|a 對(duì)如下文法消除左遞歸： R、 Q、 S ，將 R代入 Q： Q → Sab|ab|b 3. Q不存在左遞歸，將 Q代入 S S→ Sabc|abc|bc|c ，得文法： 2022/8/28計(jì)算機(jī)學(xué)院 辛明影 143 S→abcS ?| bcS?| cS? S?→abcS ?| ε Q → Rb|b R → Sa|a S→abcS ?| bcS?| cS? S?→abcS ?| ε 2022/8/28計(jì)算機(jī)學(xué)院 辛明影 144 ZA AaB|aC|Ad|Ae BbBC|f Cc 2022/8/28計(jì)算機(jī)學(xué)院 辛明影 145 五、提取左因子 為句子 if E1 then S1 else S2構(gòu)造一棵語(yǔ)法樹 文法： stmt→if expr then stmt |S |if expr then stmt else stmt