【正文】 所有非終結(jié)符 數(shù)組值為真假，為真的條件是 c ∈FIRSTVT (Q) ? 通過構(gòu)造一個二維數(shù)組 F來實現(xiàn) ,該從數(shù)組 F反映任何一個非終結(jié)符 P的 FIRSRVT集中的元素。 ? 的定義 (自底向上 ,可通過樹形結(jié)構(gòu)觀察 ) ① a b,G中有 P...ab...或 P...aQb... (在同一產(chǎn)生式中 ) ② a b,G中有 P...aR...的產(chǎn)生式 ,且 R=b...或R=Qb... (注意 ab相鄰 ) ③ a b,G中有 P...Rb...的產(chǎn)生式 ,且 R=...a或R=...aQ (注意 ab相鄰 ) 算符優(yōu)先文法的定義 + + + + 例： E→E+E | E*E | (E) | i 證明不是算符優(yōu)先文法 。 ? 各種分析方法中處理沖突的技術(shù)不同 算符優(yōu)先分析 ? 算符優(yōu)先分析法的思想源于表達式的分析，即利用相鄰終結(jié)符號之間的關(guān)系來尋找可歸約串。 – 由于總是將句型的最左邊的可歸約串替換成非終結(jié)符，該方法通常得到是最右推導(dǎo)。 ? 2) 歸約 ： 當(dāng)棧頂符號串形成一個可歸約的串（如： 句柄 ）時，直接進行歸約，即用產(chǎn)生式左側(cè)的非終結(jié)符替換棧頂?shù)木浔? – 與最左歸約 (規(guī)范歸約 )對應(yīng)，得規(guī)范句型。第四章 (2) 自下向上語法分析 本章要求 : 1. 掌握自下向上語法分析的基本思想和基本概念 2. 了解算符優(yōu)先語法分析；求 FIRSTVT集和LASTVT集，構(gòu)造算符優(yōu)先關(guān)系表；能運用算符優(yōu)先分析方法進行表達式分析（選學(xué)） 3. 掌握句柄的定義與判定 4. 理解規(guī)范歸約的過程和 LR分析過程中的實現(xiàn) 5. 掌握 LR語法分析的實現(xiàn)過程 回顧 : 歸約和推導(dǎo)的概念 例 S ? aABe A ? Abc | b B ? d 用歸約的方法對句子 abbcde進行語法分析 。 ? 最右推導(dǎo) (Rightmost Derive) – 每次推導(dǎo)都替換當(dāng)前句型的最右邊的非終結(jié)符。 分析器的四種動作 ? 1) 移進 ： 讀入下一個輸入符號并把它下推進棧。 – 若最終能歸約成文法的開始符號，則分析成功（ 接受 ）；否則 出錯 。 ? 2) 歸約 歸約沖突 – 存在兩個可選的句柄，可對棧頂符號進行歸約 – 例如上述第 13)步，可以用 T→F 進行歸約，又可以按 T→T*F 進行歸約。 ? :一個上下無關(guān)文法 G,如果沒有 P?,且沒有 P...QR...(P,Q,R屬于非終結(jié)符 ),則 G是一個 算符文法。 ? a,b之間未必有優(yōu)先關(guān)系 ( , , ) 算符優(yōu)先關(guān)系表的構(gòu)造算法 ? – 定義： 對每個非終結(jié)符 P, FIRSTVT(P)={a|P=a...或 P=Qa...,a為終結(jié)符 ,P， Q為非終結(jié)符 } + + 由優(yōu)先性低于的定義和 FIRSTVT集合的定義可以得出： 若存在某個產(chǎn)生式： …aP… ，對所有： b∈ firstVT(P) 都有： a b。 if Xi為非終結(jié)符 , Xi+1為終結(jié)符 then for lastVT中的每個元素 a do a Xi+1 。 例：下述文法的一個句型： T * F + i 其短語、素短語、最左素短語分別是？ E?T | E+T T?F | T*F F?i | (E) E E + T F i T T * F 短語有： i, T * F, T * F + i 素短語有： i, T * F 最左素短語是： T * F ? 一個算符文法 G的某個句型的最左素短語可描述： 設(shè)句型的一般形式為 (Ni∈V N∪{ ε },ai ∈V T N1a1 N2a2… Nnan 它的 最左素短語 是滿足下列條件的最左子串： Niai Ni+1ai+1… Njaj Nj+1 其中： ai1≮ ai, ai≡ ai+1≡ ….. ≡ aj1≡ aj ， aj≯ aj+1 該定理說明了最左素短語與周圍符號之間的關(guān)系 ? 例 :文法 G ? EE+T|T TT*F|F F(E)|i ? 句型 T+T*F+i的語法樹如圖： E E T + E + T F T T * F P i 根據(jù)語法樹可知： 句型 T+T*F+i的 短語 有： T — 相對非終結(jié)符 E的短語 T*F — 相對非終結(jié)符 T的短語 T+T*F — 相對非終結(jié)符 E的短語 i — 相對非終結(jié)符 P、 F、 T的短語 T+T*F+i —相對非終結(jié)符 E的短語 根據(jù) 素短語 的定義可知： i和 T*F為素短語。 WHILE s[j] a DO BEGIN repeat q:=s[j]。 else error。 (分析過程見呂映芝課本 ) 練習(xí)