[理學(xué)]第5章自頂向下語法分析方法-資料下載頁(yè)
2025-10-10 00:54本頁(yè)面
【正文】 ={ + , ) , } ST(F → ( E )) ={ ( } ST(F → i) ={ i } 預(yù)測(cè)分析方法 分析算法 :首先把 ’ ‘,文法開始符號(hào)入棧 。讀第一個(gè)輸入符號(hào)到 b中 FLAG=TRUE WHILE FLAG DO BEGIN 上托棧頂符號(hào) 到 Ｘ 中； IF X?Vt THEN IF X=b THEN 讀 下一 個(gè)輸入符號(hào) 到 b中 ELSE ERROR ELSE IF X=‘’ THEN IF b=‘’ THEN FLAG:=FALSE ELSE ERROR ELSE IF ?[X,b]={X?X1X2..XK} THEN 把 XK， XK1,..,X1 一一推進(jìn)棧 ELSE ERROR END OF WHILE 預(yù)測(cè)分析方法 ?預(yù)測(cè)分析過程 i + * ( ) E TE39。 TE39。 E39。 +TE39。 ε ε T FT39。 FT39。 T39。 ε *FT39。 ε ε F i (E) 分析棧 剩余串 產(chǎn)生式 E E39。T E39。T39。F E39。T39。i E39。T39。 E39。 E39。T+ E39。T E39。T39。F E39。T39。i E39。T39。 E39。T39。F* E39。T39。F E39。T39。i E39。T39。 E39。 i+i*i i+i*i i+i*i i+i*i +i*i +i*i +i*i i*i i*i i*i *i *i i i E→TE39。 T→FT39。 F → i i 匹配 T39。 → ε E39。 → +TE39。 + 匹配 T →FT39。 F → i i 匹配 T → *FT39。 * 匹配 F → i i 匹配 T39。 → ε E39。 → ε 接受 最左推導(dǎo)： E?TE’ ?FT’E’ ?iT’E’ ?iE’ ?i+TE’ ?i+FT’E’ ?i+iT’E’ ?i+i*FT’E’ ?i+i*iT’E’ ?i+i*iE’ ?i+i*i 遞歸子程序法 ?遞歸子程序法是比較簡(jiǎn)單直觀易于構(gòu)造的一種語法分析方法。它要求文法滿足 LL(1)文法。它的 實(shí)現(xiàn)思想是 對(duì)應(yīng)文法中每個(gè)非終結(jié)符編寫一個(gè)遞歸過程，每個(gè)過程的功能是識(shí)別由該非終結(jié)符推出的串。 ?缺點(diǎn)：遞歸調(diào)用多，速度慢，占用空間多。 遞歸子程序法 G’[E] E →TE39。 E39。 → +TE39。 |ε T →FT39。 T39。 → *FT39。 |ε F → i | ( E ) E() { T()。 E’()。 } T() { F()。 T’()。 } E’() { if sym=‘+’ { getsym。 T()。 E’()。 } else if sym( ‘)’or ‘’ ) error。 } T’() { If sym=‘*’ { getsym。 F()。 T’()。 } Else if sym( ‘+’or ‘)’ or ‘’) error。 } F() { if sym=i getsym。 else if sym=‘(‘ { getsym。 E()。 if sym=‘)’ getsym。 else error } else error。 } 遞歸子程序法 ?G[E]： E→ E+T ｜ ET｜ T T→ T*F ｜ T／ F｜ F F→ i ｜ n｜ (E) 注： i為 ident， n為 number。 ?可改寫為表達(dá)式的 EBNF: E∷ = T{(+|)T} T∷ = F{(*|/)F} F∷ = i|n|(E) 遞歸子程序法 例：遞歸子程序?qū)崿F(xiàn)表達(dá)式的語法分析 E( ) { T( )。 while (sym=‘+’ or ‘’) { getsym。 T( )。 } } T( ) { F( )。 while(sym=‘*’ or ‘/‘) { getsym。 F( )。 } } F( ) { if(sym = i) getsym。 else { if(sym = n) getsym。 else { if (sym = lparen) { getsym。 E( )。 if ( sym = rparen) getsym。 else error( )。 } else error( ) } } 分析以下串的執(zhí)行過程 i， i+i， n+n*i， i*(i+i) E∷ = T{ (+|)T } T∷ = F{ (*|/)F } F∷ = i|n|(E) 遞歸子程序法 E( ) {sym=i1 T sym=+ getsym=i2 T Sym= } F( ) {sym=i1 getsym=+ } T( ) {sym=i1 F sym=+ } T( ) {sym=i2 F sym= } F( ) {sym=i2 getsym= } i1+i2的遞歸調(diào)用過程 遞歸子程序法 E( ) {sym=n1 T sym=+ getsym=n2 T Sym= } F( ) {sym=n1 getsym=+ } T( ) {sym=n1 F sym=+ } T( ) {sym=n2 F sym=* getsym=i F Sym= } F( ) {sym=n2 getsym=* } n1+n2*i的遞歸調(diào)用過程 F( ) {sym=i getsym= } 遞歸子程序法 E( ) { sym=i1 T sym= } T( ) {sym=i3 F Sym=) } F( ) {sym=i3 getsym=) } F( ) {sym=i2 getsym=+ } T( ) {sym=i2 F } E( ) {sym=i2 T Sym=+ getSym=i3 T Sym=) } F( ) {sym=( getsym=i2 E Sym=) getsym= } F( ) {sym=i1 getsym=* } T( ) {sym=i1 F Sym=* getSym=( F Sym= } i1*(i2+i3)的遞歸調(diào)用過程 第 5章小結(jié) ?確定的與不確定的自頂向下分析思想 ?LL(1)文法的判別 ? 求非終結(jié)符的 FIRST集 ? 求非終結(jié)符的 FOLLOW集 ? 求產(chǎn)生式的 SELECT集 ? 判別文法是否為 LL(1) ?兩種將非 LL(1)文法轉(zhuǎn)換為 LL(1)文法的方法 ? 提取左公共因子 ? 消除左遞歸 ?確定的自頂向下分析方法 ? 遞歸子程序法。構(gòu)造遞歸下降函數(shù) ? 預(yù)測(cè)分析方法。構(gòu)造預(yù)測(cè)分析表并進(jìn)行分析
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1