【文章內(nèi)容簡(jiǎn)介】 ’ |? 33 S ? aSbS | bSaS |? 構(gòu)造一個(gè)帶有回溯的遞歸下降分析器 . 問(wèn)能否構(gòu)造一個(gè)預(yù)測(cè)分析器 . procedure match(t:token)。 begin ifkahead = t then end。 procedure S。 begin if match 34 對(duì)于文法 bexpr ? bexpr or bterm | bterm bterm ? bterm and bfactor | bfactor bfactor? not bfactor | (bexpr) | true | false 構(gòu)造一個(gè)預(yù)測(cè)分析器。 1. 消除左遞歸 bexpr ? bterm bexpr’ bexpr’ ? or bterm bexpr’ | ? bterm ? bfactor bterm’ bterm’ ? and bfactor bterm’ | ? bfactor? not bfactor | (bexpr) | true | false 2. First(bexpr) = First(bterm) = First(bfactor) ={not, (, true, false} First(bexpr’) = {or, ?} First(bterm’) = {and, ?} Follow(bexpr) = { $, )} Follow(bexpr’) = { $, )} Follow(bterm) = {or, $, ) } Follow(bterm’) = {or, $, )} Follow(bfactor) = {or, and, $, )} 35 (1) bexpr ? bterm bexpr’ (2) bexpr’ ? or bterm bexpr’ (3) bexpr’ ? ? (4) bterm ? bfactor bterm’ (5) bterm’ ? and bfactor bterm’ (6) bterm’ ? ? (7) bfactor? not bfactor (8) bfactor ? (bexpr) (9) bfactor ? true (10) bfactor ? false First(bexpr) = First(bterm) = First(bfactor) ={not, (, true, false} First(bexpr’) = {or, ?} First(bterm’) = {and, ?} Follow(bexpr) = { $, )} Follow(bexpr’) = { $, )} Follow(bterm) = {or, $, ) } Follow(bterm’) = {or, $, )} Follow(bfactor) = {or, and, $, )} or and not true false ( ) $ bexpr (1) (1) (1) (1) synch synch bexpr’ (2) (3) (3) bterm synch (4) (4) (4) (4) synch synch bterm’ (6) (5) (6) (6) bfactor synch synch (7) (9) (10) (8) synch synch 36 LL(1)的。 (1) 直接左遞歸文法中存在產(chǎn)生式 : A ? A?1 | A?2 |...| A?m | ? 1 | ? 2 |...| ? n, 其中 ? 1 ? 2 ... ? n均不以 A開(kāi)頭 First(A?i) ? First(? j) = First(? j) ? ? 若 ? j ?*?, First(A? i) ? Follow(A) = First(? i) ? ?, ?不是 LL(1)文法 . (2) 間接左遞歸文法中存在產(chǎn)生式集合 : A ? B1 ?1 | ? 1 | ? 2 |...| ? n B1 ? B2 ?2 ... Bm ? A ? First(B1 ?1) = First(A ? ?m ... ?1) First(? j) ? First(B1 ?1) , j=1,...,n First(? j) ? First(B1 ?1) ? ?, j=1,...,n 若 ? j ?*?, First(B1 ?1) ? Follow(A) = First(? ?m ... ?1) ? ?, ?不是 LL(1)文法 . 37 LL(1)文法可以是二義性的。 若有一個(gè) LL(1)文法是二義性的 , 則存在句子 ?w? 有兩種不同的最左推導(dǎo) : S ?* ?A? ? ? ?1 ? ?* ?w? S ?* ?A? ? ? ?2 ? ?* ?w? 對(duì)于文法中的產(chǎn)生式 A ? ?1 | ?2 , 其中 ?1 , ?2 ? ? First(?1) ? First(?2) = First(w) ? ? 與 LL(1)文法矛盾 . 38 文法 S ? (L) | a L ? L, S | S 的算符優(yōu)先關(guān)系由表 。建立與 表相應(yīng)的算符優(yōu)先函數(shù)并用算符優(yōu)先分 析法分析句子 (a, (a, a))及 (a, ((a,a), (a,a)))。 算符優(yōu)先關(guān)系表 a ( ) , $ a ( = ) , $ 算符優(yōu)先函數(shù) a ( ) , $ f 2 0 2 2 0 g 3 3 0 1 0 句子 (a, (a, a))的分析過(guò)程 棧 輸入 動(dòng)作 $ (a,(a,a))$ $( shift $( a,(a,a))$ (a shift $(a ,(a,a))$ a, reduce $(S ,(a,a))$ (, shift $(S, (a,a))$ ,( shift $(S,( a,a))$ (a shift $(S,(a ,a))$ a, reduce $(S,(S ,a))$ (, shift $(S,(S, a))$ ,a shift $(S,(S,a ))$ a) reduce $(S,(S,S ))$ ,) reduce $(S,(L ))$ (=) shift $(S,(L) )$ )) reduce $(S,S )$ ,) reduce $(L )$ (=) shift $(L) $ )$ reduce $S $ accept 39 試為下列各文法建立算符優(yōu)先關(guān)系表。 (a) S ? a S b S | b S a S | ? a b $ a = b = $ acc 設(shè) G是一個(gè)運(yùn)算符文法 , R和 S是 G中任何 兩個(gè)終結(jié)符 , 定義 : (1) R=S當(dāng)且僅當(dāng) G中存在產(chǎn)生式 U ? ...RS... 或 U ? ...RVS... (2) RS當(dāng)且僅當(dāng) G中存在產(chǎn)生式 U ? ...RW..., 其中 W ?+ S... 或 W ?+ VS... (3) RS當(dāng)且僅當(dāng) G中存在產(chǎn)生式 U ? ... W S..., 其中 W ?+ ...R 或 W ?+ ...RV 最左終結(jié)符 : U ? S...或 U ? VS..., S是的 最左終結(jié)符 U ? V..., 則 V的 最左終結(jié)符是 U的 最左終結(jié)符 對(duì)于文法中 U ? RW...的產(chǎn)生式 , R W的 最左終結(jié)符 . 40 (b) bexpr ? bexpr or bterm | bterm bterm ? bterm and bfactor | bfactor bfactor? not bfactor | (bexpr) | true | false or and not ( ) true false $ or and not ( = ) true false $ acc 最左終結(jié)符