[理學]第四章2 自下而上語法分析-預覽頁
【正文】 號串 ? 如果有 S=xAy, 且有 A=β ,則 β 是句型 xβ y相對于非終結符 A的 短語 ? 如果有 S=xAy, 且有 Aβ ,則 β 是句型 xβ y相對于Aβ 的 直接短語 ? 位于 一個 句型最左邊的直接短語稱為 句柄 . ? 句型 短語 直接短語 句柄 * * + * 注 : 每次歸約的部分就是分析為 句柄 的字符串 (最右推導 )。 ? 2) 歸約 歸約沖突 – 存在兩個可選的句柄，可對棧頂符號進行歸約 – 例如上述第 13)步，可以用 T→F 進行歸約，又可以按 T→T*F 進行歸約。 (2) a優(yōu)先性高于 b， 記作 a b。 ? :一個上下無關文法 G,如果沒有 P?,且沒有 P...QR...(P,Q,R屬于非終結符 ),則 G是一個 算符文法。 算符優(yōu)先關系表 的構造 ? 用表格形式來表示各終結符號的優(yōu)先關系，這種表稱為優(yōu)先表。 ? a,b之間未必有優(yōu)先關系 ( , , ) 算符優(yōu)先關系表的構造算法 ? – 定義： 對每個非終結符 P, FIRSTVT(P)={a|P=a...或 P=Qa...,a為終結符 ,P， Q為非終結符 } + + 由優(yōu)先性低于的定義和 FIRSTVT集合的定義可以得出： 若存在某個產(chǎn)生式： …aP… ，對所有： b∈ firstVT(P) 都有： a b。 IF not F[P,a] then begin f[p,a] = true。 if Xi為非終結符 , Xi+1為終結符 then for lastVT中的每個元素 a do a Xi+1 。各種優(yōu)先關系已經(jīng)存于優(yōu)先關系表中。 例：下述文法的一個句型： 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的某個句型的最左素短語可描述： 設句型的一般形式為 (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 該定理說明了最左素短語與周圍符號之間的關系 ? 例 :文法 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 — 相對非終結符 E的短語 T*F — 相對非終結符 T的短語 T+T*F — 相對非終結符 E的短語 i — 相對非終結符 P、 F、 T的短語 T+T*F+i —相對非終結符 E的短語 根據(jù) 素短語 的定義可知： i和 T*F為素短語。 – 分析過程的結束 ：分析棧中為 S，輸入串為 ? 例 : EE+T|T TT*F|F F(E)|i ? 把 入棧 ,讀一符號 i, 因為 i, 所以把 i入棧 ? 因為 i + ,所以歸約 :Fi ? 因 + , 所以 +入棧 ? 因 + i , 所以 i入棧 ? 因 i * , 所以歸約 :Fi ? 因 + * , 所以 *入棧 ? 因 * i , 所以 i入棧 ? 因 i , 所以歸約 :Fi ? 因 * , 所以歸約 :TF*F ? 因 + , 所以歸約 :ET+F ? 分析成功 求 i+i*i的算符優(yōu)先分析過程 棧 輸入緩沖區(qū) i+i*i i +i*i F +i*i F+ i*i F+i *i F+F *i F+F* i F+F*i F+F*F F+T E k:=1。 WHILE s[j] a DO BEGIN repeat q:=s[j]。 s[k] := N。 else error。 ? 算符優(yōu)先分析比規(guī)范歸約過程要快，跳過了所有的單非產(chǎn)生式。 (分析過程見呂映芝課本 ) 練習
教學課件相關推薦
鄂ICP備17016276號-1