1、溫故而知新溫故而知新1A 1 | 2A+Aa 本講綱要本講綱要v語(yǔ)法分析方法語(yǔ)法分析方法v自上而下分析自上而下分析vFIRSTFIRST集和集和FOLLOWFOLLOW集集2v給定一個(gè)句子給定一個(gè)句子id+idid+id* *ididv語(yǔ)法分析的目標(biāo)語(yǔ)法分析的目標(biāo) 分析句子的語(yǔ)法結(jié)構(gòu)，確分析句子的語(yǔ)法結(jié)構(gòu)，確定該句子是否符合表達(dá)式定該句子是否符合表達(dá)式文法文法v怎么做？怎么做？v分析的途徑分析的途徑 自上而下自上而下 自下而上自下而上3Eid+id*id？本講綱要本講綱要v語(yǔ)法分析方法語(yǔ)法分析方法v自上而下分析自上而下分析vFIRSTFIRST集和集和FOLLOWFOLLOW集集4自上而下分析

2、自上而下分析v自上而下分析方法自上而下分析方法 從根部開始構(gòu)建語(yǔ)法樹從根部開始構(gòu)建語(yǔ)法樹v存在的問(wèn)題存在的問(wèn)題 文法存在左遞歸怎么辦？文法存在左遞歸怎么辦？5自上而下分析中的問(wèn)題自上而下分析中的問(wèn)題vE=E+E=E+E+E=E+E+E+E=E=E+E=E+E+E=E+E+E+E=6自上而下分析中的問(wèn)題自上而下分析中的問(wèn)題v自上而下分析方法自上而下分析方法 從根部開始構(gòu)建語(yǔ)法樹從根部開始構(gòu)建語(yǔ)法樹v存在的問(wèn)題存在的問(wèn)題 文法存在左遞歸怎么辦？文法存在左遞歸怎么辦？ 文法中一步推導(dǎo)可能存在多個(gè)產(chǎn)生式選文法中一步推導(dǎo)可能存在多個(gè)產(chǎn)生式選擇時(shí)，怎么辦？擇時(shí)，怎么辦？7自上而下分析中的問(wèn)題自上而下分析中

3、的問(wèn)題8如何避免問(wèn)題如何避免問(wèn)題v如果要用自上而下的方法進(jìn)行分析，就必如果要用自上而下的方法進(jìn)行分析，就必須避免例子中出現(xiàn)的問(wèn)題須避免例子中出現(xiàn)的問(wèn)題 每一步推導(dǎo)，不能因?yàn)樽筮f歸的存在而使得推每一步推導(dǎo)，不能因?yàn)樽筮f歸的存在而使得推導(dǎo)過(guò)程陷入死循環(huán)導(dǎo)過(guò)程陷入死循環(huán) 每一步推導(dǎo)，可以選擇的產(chǎn)生式必須是唯一的每一步推導(dǎo)，可以選擇的產(chǎn)生式必須是唯一的v消除左遞歸消除左遞歸 文法中存在左遞歸時(shí)，為了采用自上而下的分文法中存在左遞歸時(shí)，為了采用自上而下的分析方法，必須采取方法消除左遞歸析方法，必須采取方法消除左遞歸9 串的特點(diǎn)串的特點(diǎn) . . . . . . A A A A A A A A | | 10

4、 E E TE TE E E + + TE TE | | T T FT FT T T * * F T F T | | F F ( ( E E ) | id ) | id11id + id id + id * * id id的最左推導(dǎo)再現(xiàn)的最左推導(dǎo)再現(xiàn)12最左推導(dǎo)與語(yǔ)法樹的生成ETidT E FidT F*FT id1, E TE 2, T FT 3, F id4, T 5, E + TE 6, T FT 7, F id8, T * F T 9, F id10, T 11, E +TE E TE E + TE | T FT T * F T | F ( E ) | id 13例：例： 間接左遞歸的

5、消除間接左遞歸的消除SAc|c SAc|c ABb|b ABb|b BSa|aBSa|av將將B B的定義代入的定義代入A A產(chǎn)生式得產(chǎn)生式得: ASab|ab|b: ASab|ab|bv將將A A的定義代入的定義代入S S產(chǎn)生式得產(chǎn)生式得: : SSabc|abc|bc|cSSabc|abc|bc|cv消除直接左遞歸：消除直接左遞歸：SabcS|bcS|cSSabcS|bcS|cS SabcS|SabcS|v刪除刪除“多余的多余的”產(chǎn)生式：產(chǎn)生式：ASab|ab|bASab|ab|b和和BSa|a BSa|a v結(jié)果：結(jié)果： SabcS|bcS|cSSabcS|bcS|cSSabcS|Sab

6、cS|14消除左遞歸的一般方法消除左遞歸的一般方法v對(duì)產(chǎn)生式組對(duì)產(chǎn)生式組AAAA1 1|A|A2 2|A|An n| | 1 1 | | 2 2 | | m m v用如下產(chǎn)生式組替換用如下產(chǎn)生式組替換A A 1 1B | B | 2 2B | B | m mB BB B 1 1B| B| 2 2B |B |n nB |B |其中：其中：B B為新變量，相當(dāng)于為新變量，相當(dāng)于AAv消除左遞歸的算法消除左遞歸的算法 為非終結(jié)符編號(hào)，再采用代入法將間接左遞歸為非終結(jié)符編號(hào)，再采用代入法將間接左遞歸變?yōu)橹苯幼筮f歸，消除直接左遞歸變?yōu)橹苯幼筮f歸，消除直接左遞歸15提取左因子提取左因子v例：例：ifif語(yǔ)

7、句的原始文法語(yǔ)句的原始文法vS S if E then Sif E then S | | if E then Sif E then S else S else S | other | otherv遇到遇到 if if 時(shí)難以判斷用哪一個(gè)產(chǎn)生式時(shí)難以判斷用哪一個(gè)產(chǎn)生式進(jìn)行匹配（推導(dǎo)）進(jìn)行匹配（推導(dǎo)）v存在左因子存在左因子 if E then Sif E then S16提取左因子提取左因子v當(dāng)存在某一步推導(dǎo)可能有多種選擇的產(chǎn)生當(dāng)存在某一步推導(dǎo)可能有多種選擇的產(chǎn)生式的時(shí)候，可通過(guò)提取左因子的方法修改式的時(shí)候，可通過(guò)提取左因子的方法修改文法文法17提取左因子提取左因子 18提取左因子提取左因子stm

8、tstmt if if exprexpr then then stmtstmt else else stmtstmt | if | if exprexpr then then stmtstmt | other | otherstmt if expr then stmt optional_else_part| otheroptional_else_part else stmt | 19提取左因子提取左因子v將形如 A 1| 2| m | 1 | 2 | | p 的規(guī)則改寫為 A A | 1 | 2 | | p A 1 | 2| m20自上而下分析方法自上而下分析方法v基本思想基本思想 尋找輸入符

9、號(hào)串的最左推導(dǎo)尋找輸入符號(hào)串的最左推導(dǎo) 試圖根據(jù)當(dāng)前輸入單詞確定使用哪個(gè)產(chǎn)生式試圖根據(jù)當(dāng)前輸入單詞確定使用哪個(gè)產(chǎn)生式v基本過(guò)程基本過(guò)程 從從S S出發(fā)，構(gòu)造輸入符號(hào)串出發(fā)，構(gòu)造輸入符號(hào)串(Token)(Token)的最左推導(dǎo)的最左推導(dǎo) 從根開始，按與最左推導(dǎo)相對(duì)應(yīng)的順序，構(gòu)造從根開始，按與最左推導(dǎo)相對(duì)應(yīng)的順序，構(gòu)造輸入符號(hào)串輸入符號(hào)串(Token)(Token)的語(yǔ)法分析樹的語(yǔ)法分析樹21本講綱要本講綱要語(yǔ)法分析方法語(yǔ)法分析方法自上而下分析自上而下分析FIRSTFIRST集和集和FOLLOWFOLLOW集集22232022-2-21 242022-2-21 詞法分析詞法分析語(yǔ)法分析語(yǔ)法分析語(yǔ)義

10、語(yǔ)義分析分析中間代碼生成中間代碼生成252022-2-21 自上而下的自上而下的語(yǔ)法分析語(yǔ)法分析自下而自下而上上的的語(yǔ)法分析語(yǔ)法分析FirstFirst集合、集合、FollowFollow集合集合LLLL（1 1）文法）文法自上而下的預(yù)測(cè)分析方法自上而下的預(yù)測(cè)分析方法構(gòu)造非遞歸預(yù)測(cè)分析表構(gòu)造非遞歸預(yù)測(cè)分析表語(yǔ)法分析語(yǔ)法分析262022-2-21 句子句子主語(yǔ)主語(yǔ) 謂語(yǔ)謂語(yǔ) 名詞名詞 動(dòng)詞動(dòng)詞 空調(diào)空調(diào) 設(shè)為設(shè)為數(shù)詞數(shù)詞2525度度賓語(yǔ)賓語(yǔ)句子句子 主語(yǔ)謂語(yǔ)賓語(yǔ)主語(yǔ)謂語(yǔ)賓語(yǔ)主語(yǔ)主語(yǔ) 名詞名詞謂語(yǔ)謂語(yǔ) 動(dòng)詞動(dòng)詞 賓語(yǔ)賓語(yǔ) 數(shù)詞數(shù)詞 | | 名詞名詞 空調(diào)空調(diào) | | 導(dǎo)航導(dǎo)航動(dòng)詞動(dòng)詞 設(shè)為設(shè)為 |

11、 | 開開數(shù)詞數(shù)詞 25 25度度 | | 272022-2-21 自上而下的自上而下的語(yǔ)法分析語(yǔ)法分析FirstFirst集合、集合、FollowFollow集合集合LLLL（1 1）文法）文法自上而下的預(yù)測(cè)分析方法自上而下的預(yù)測(cè)分析方法構(gòu)造非遞歸預(yù)測(cè)分析表構(gòu)造非遞歸預(yù)測(cè)分析表語(yǔ)法分析語(yǔ)法分析282022-2-21 句子句子 主語(yǔ)謂語(yǔ)賓語(yǔ)主語(yǔ)謂語(yǔ)賓語(yǔ)主語(yǔ)主語(yǔ) 名詞名詞謂語(yǔ)謂語(yǔ) 動(dòng)詞動(dòng)詞 賓語(yǔ)賓語(yǔ) 數(shù)詞數(shù)詞 | | 名詞名詞 空調(diào)空調(diào) | | 導(dǎo)航導(dǎo)航動(dòng)詞動(dòng)詞 設(shè)為設(shè)為 | | 開開數(shù)詞數(shù)詞 25 25度度 | | FIRST(FIRST(句子句子)=)= 空調(diào)，導(dǎo)航空調(diào)，導(dǎo)航 FIRST(F

12、IRST(主語(yǔ)主語(yǔ))=)=FIRSTFIRST( (謂語(yǔ)謂語(yǔ))=)= 空調(diào)，導(dǎo)航空調(diào)，導(dǎo)航 FIRSTFIRST( (賓語(yǔ)賓語(yǔ))=)=FIRSTFIRST( (名詞名詞)=)=FIRSTFIRST( (動(dòng)詞動(dòng)詞)=)=FIRSTFIRST( (數(shù)詞數(shù)詞)=)= 設(shè)為，開設(shè)為，開 2525度，度， 空調(diào)，導(dǎo)航空調(diào)，導(dǎo)航 設(shè)為，開設(shè)為，開 2525度，度， 1.29SBAABS|dBaA|bS|cFIRST(S)=FIRST(B)FIRST(A)=FIRST(B) dFIRST(B)=a,b,c30312022-2-21 句子句子 主語(yǔ)謂語(yǔ)賓語(yǔ)主語(yǔ)謂語(yǔ)賓語(yǔ)主語(yǔ)主語(yǔ) 名詞名詞謂語(yǔ)謂語(yǔ) 動(dòng)詞動(dòng)詞 賓語(yǔ)

13、賓語(yǔ) 數(shù)詞數(shù)詞 | | 名詞名詞 空調(diào)空調(diào) | | 導(dǎo)航導(dǎo)航動(dòng)詞動(dòng)詞 設(shè)為設(shè)為 | | 開開數(shù)詞數(shù)詞 25 25度度 | | FOLLOWFOLLOW( (句子句子)=)=$FOLLOWFOLLOW( (主語(yǔ)主語(yǔ))=)=FOLLOWFOLLOW( (謂語(yǔ)謂語(yǔ))=)= 設(shè)為，開設(shè)為，開 FOLLOWFOLLOW( (賓語(yǔ)賓語(yǔ))=)=FOLLOWFOLLOW( (名詞名詞)=)=FOLLOWFOLLOW( (動(dòng)詞動(dòng)詞)=)=FOLLOWFOLLOW( (數(shù)詞數(shù)詞)=)= 2525度，度，$ $ $ 設(shè)為，開設(shè)為，開 2525度，度，$ $ $1.32SBAABS|dBaA|bS|cFIRST(B)

14、=a,b,c FIRST(A)=a,b,c,d FIRST(S)=a,b,cFOLLOW(S)=?FOLLOW(A)=?FOLLOW(B)=?FOLLOWFOLLOW集計(jì)算集計(jì)算v文法文法33SBAABS|dBaA|bS|cFIRST(B)=a,b,c FIRST(A)=a,b,c,d FIRST(S)=a,b,cFOLLOWFOLLOW集計(jì)算集計(jì)算v文法文法34SBAABS|dBaA|bS|cFIRST(B)=a,b,c FIRST(A)=a,b,c,d FIRST(S)=a,b,cFOLLOWFOLLOW集計(jì)算集計(jì)算v文法文法35SBAABS|dBaA|bS|cFIRST(B)=a,b,c FIRST(A)=a,b,c,d FIRST(S)=a,b,cFOLLOWFOLLOW集計(jì)算集計(jì)算v文法文法36SBAABS|dBaA|bS|cFIRST(B)=a,b,c FIRST(A)=a,b,c,d FIRST(S)=a,b,cFOLLOWFOLLOW集計(jì)算集計(jì)算v文法文法37SBAABS|dBaA|bS|cF