cha自上而下语法分析PPT课件

1、2022-7-61第1页/共92页2022-7-62 句型、句子和语言的定义 句型 有文法GSGS，若S =S =* *，且* *, , 则称是是文法G G的一个句型 句子 有文法GSGS，若S =S =* *，且T T* * , ,则称是是文法G G的一个句子 语言 由文法 G G 产生的所有句子的集合 L(G)=|S=L(G)=|S=+ +,且VVT T* * 第2页/共92页2022-7-63 最左(最右)推导 在推导的任何一步=*(其中和是句型)， 都对中的最左(最右)非终结符进行替换 句型分析(句子分析) 识别一个符号串是否为某文法的句型(句子)的过程 也就是某文法的某个推导的构造过

2、程第3页/共92页2022-7-64 任务 分析并判定输入的单词符 号串是否符合该语言的语 法规则(上下文无关文法) 实质 就是按照文法的产生式， 识别输入符号串是否为一 个句子(合法程序，语句， 表达式等)第4页/共92页2022-7-65 设计思想 判断是否能从文法的开始符号出发推导出这个输入串 或者,判断能否建立一棵与输入串匹配的语法分析树 输入 单词符号串 输出 语法分析树 格式化的程序 合法的表达式、语句、函数 出错处理要求 尽快发现错误，准确定位 可能时进行恢复处理，继续语法分析第5页/共92页2022-7-66 语法分析算法可分为两大类: 自上而下分析法 从文法的开始符号出发，反

3、复使用各种产生式向 下推导，寻找与输入符号串匹配的推导 自下而上分析法 从输入串开始，逐步进行归约，直至归约到文法 的开始符号 两种方法反映了两种不同的语法树的构造过程 自上而下从树根推导到树叶 自下而上从树叶归约到树根第6页/共92页2022-7-67 编程语言的语法大都可用2型文法来描述没有一种方法能够有效地分析所有上下文 无关文法 存在无法处理的2型文法 每种方法能够处理一部分上下文无关文法 每种方法都有适用范围第7页/共92页2022-7-684.2 自上而下分析面临的问题 p67 基本方法 对任何输入串,试图从文法的开始符号出发， 自上而下地为输入串建立一棵语法树，或者说为输入串寻找

4、一个最左推导。 过程本质 是一种试探过程，是反复使用不同产生式谋求匹配输入串的过程如何选择哪个产生式进行推导?第8页/共92页2022-7-69 例 文法GS SxAy Aab|a 判断输入串 w = x a y是否为该文法的句子？第9页/共92页2022-7-610 公共左因子产生回溯 例 文法G: S xAy A ab|a 无法确定非终结符A面临输入符 号a时选用哪个关于A的候选式 左递归无限循环 例 文法G: S Sa|aba第10页/共92页2022-7-611为了构造不带回溯的自上而下分析算法n消除文法的左递归消除文法的左递归n消除回溯、提取左因子消除回溯、提取左因子nLL(1)分析

5、条件分析条件uLL(1)文法文法第11页/共92页2022-7-612关于非终结符P P的规则 直接左递归定义：若P PP P 、 * * 例如 E E E E + T + TT T（含有E E的左递归） T T T T * * F FF F（含有T T的左递归） F ( E )F ( E )i i 第12页/共92页2022-7-613 间接左递归定义： 若P P =+ + P P * * 例如 间接左递归 S S Aa Aa A A S Sb|bb|b S S =Aa= =Aa=S Sba ba 即S S=+=+S Sb b 用S S的产生式右部替换A A右部的S S得： A A A Aa

6、b|bab|b 变成A A的产生式含有直接左递归第13页/共92页2022-7-614改写为等价的右递归 形如：P P 非，不以P开始 改写为：PP（P为新增加的非终结符） PP 改写前产生式可产生短语 P=P= 改写后产生式可产生短语 P= P = P = 第14页/共92页2022-7-615 E E E E + T + TT T T T T T * * F FF F F ( E )F ( E )i inE E T T EE EE + T + T EEnT T F F TT T T * * F F TTnF F ( E ) ( E )i i第15页/共92页2022-7-616第16页/共

7、92页2022-7-617消除直接左递归课堂练习 例如有文法： KKKKa a | K | Kb b| K| Kc c | | d d | | e eBEGINBEGIN第17页/共92页2022-7-618间接左递归消除举例 p70 S QcS Qcc c Q Q Rb Rbb b R R Sa Saa aS=Qc=Rbc=Sabc S=Qc=Rbc=Sabc 是间接左递归消除方法1 1： 将非终结符排序： R Q SR Q S 将R R的右部代入Q Q，S S：Q Q SaSab ba ab bb b S Qc S Qcc c （不变）n 将Q Q的右部代入S S：S S SabSabc

8、cababc cb bc cc cn 消除S S的直接左递归： S abcSS abcSbcS|cSbcS|cS SabcS| SabcS| Q Sab Q Sabab|bab|b R Sa R Saa an 整理化简：删除Q Q，R R（无用）n 消除左递归后得： S abcSS abcSbcS|cSbcS|cS SabcS| SabcS| 第18页/共92页2022-7-619间接左递归消除举例（续） p70 S S Qc Qcc c Q Q Rb Rbb b R Sa R Saa a消除方法2 2： 将非终结符排序： S Q RS Q R 将S S的右部代入Q Q，R R：Q RbQ R

9、bb b（不变） R R QcQca ac ca|aa|a第19页/共92页2022-7-620消除左递归算法 p701.1.以某种顺序将文法的非终结符排列 P P1 1，P P2 2，,P,Pn n 2.FOR i:=1 TO n DO2.FOR i:=1 TO n DO BEGIN BEGIN FOR j:=1 TO i-1 DO FOR j:=1 TO i-1 DO 把形如P Pi iPPj j的规则改写成 P Pi i1 1|2 2|k k,其中 P Pj j1 1|2 2|k k是关于P Pj j的所有规则; ; 消除P Pi i的直接左递归 ENDEND3.3.化简由2 2所得的文

10、法，即去除那些从开始符号 出发永远无法到达的非终结符的产生式n 当非终结符的排列顺序不 同时，变换后的文法形式 可能不同，但是它们都和 原文法是等价的 第20页/共92页2022-7-621 消除回溯目的 对文法的任何非终结符，当它去匹配输入串 时，能够根据输入符号，准确地选择合适的候选式去匹配 若需要非终结符A A去匹配输入串，A A的候选式 为AA1 1| | 2 2 | | n n ， A A所面临的第一个输入符号为a a时，A A能准确地选择i i去执行匹配任务，则无需回溯第21页/共92页2022-7-622 对于所有形如 AA1 12 2.n n的规则 其中，为左因子，不以开头 改

11、写为 AAAA 其中AA为新增加的非终结符 AA1 12 2.n n 例如 S xAyS xAy A A a ab|b|a a第22页/共92页2022-7-6234.3.3 LL(1)分析条件 p71FIRSTFIRST集合的定义与计算FOLLOWFOLLOW集合的定义与计算LL(1)LL(1)文法的定义LL(1)LL(1)分析第23页/共92页2022-7-624FIRST()集合的定义 p71 设G=(G=(T T，N N，S S，P P） * * FIRST(FIRST()=)=a a| |=* * a a ，a aT T 若=* * ，则FIRST(FIRST() ) FIRST(F

12、IRST() )是的所有可能推导的首遇终结符号或，是选择产生式的依据a a E T E E T E E + T EE + T ET F T T F T T T * * F T F T F ( E )F ( E )i inFIRST(FIRST(E)(E) = ) = ( ( （E E）=0 0 （E E） nFIRSTFIRST（TETE） =（，i i TETE=FTE=FTE=（E E）TETETETE=FTE=FTE=i iTETE第24页/共92页2022-7-625 FIRST()= FIRST()= a a = =* * a a ，aaT T 若 = =* * ，则 FIRST()

13、 FIRST() 计算文法符号X X的FIRSTFIRST（X X） 计算文法符号串=X=X1 1X X2 2XXn n的FIRST()FIRST()第25页/共92页2022-7-626重复以下计算，直到FIRSTFIRST（X X）不再增大为止: :1) 1) 若 XXT T，则 FIRST( X ) = FIRST( X ) = X X 。 例 FIRSTFIRST（+ +）=+ FIRST=+ FIRST（i i）=i=i2) 2) 若 XXN N，若有XXa a，则将 a a 加入FIRST(X)FIRST(X)； 例 E+TE +FIRSTE+TE +FIRST（EE） FF（E

14、E）|i |i （，iFIRSTiFIRST（F F）若有X X ，则将加入FIRST( X )FIRST( X )。 例 E FIRSTE FIRST（EE）第26页/共92页2022-7-627第27页/共92页2022-7-628若有文法G G为： X YX Y1 1 Y Y2 2 Y Y3 3 Y Y4 4 Y Y5 5 Y1 a Y1 a Y2 b Y2 b Y3 c Y3 c Y4 d Y4 d Y5 e Y5 ef f第28页/共92页2022-7-629文法G G为：E T EE T EE+ T EE+ T ET F T T F T TT* * F T F T F ( E )F

15、 ( E )i i第29页/共92页2022-7-630第30页/共92页2022-7-631第31页/共92页2022-7-632候选式的FIRSTFIRST集FIRST(FIRST(TETE)=FIRST()=FIRST(T T)=)=( (, ,i i FIRST(FIRST(+TE+TE)=)=+ + FIRST(FIRST(FTFT)=FIRST()=FIRST(F F)=)=( (, ,i i FIRST(FIRST(* *FTFT)=)=* * FIRST(FIRST(E)(E)=)=( ( FIRST(FIRST(i i)=)=i i FIRST(FIRST()=)= 第32页

16、/共92页2022-7-633候选式的FIRSTFIRST集FIRST(FIRST(ApAp)=FIRST()=FIRST(A A)=a,)=a,ccFIRST(FIRST(BqBq)=FIRST()=FIRST(B B)-)- FIRST( FIRST(q q) ) =d,q =d,qFIRST(FIRST(a a)=a)=aFIRST(FIRST(cAcA)=c)=cFIRST(FIRST(dBdB)=d)=dFIRST(FIRST()=)=第33页/共92页2022-7-634FOLLOW(A)集合的定义 p73 A AN N FOLLOW(FOLLOW(A A)= )= a aS S=

17、* *A Aa a，a aT T 若S S=* *A A，则# #FOLLOWFOLLOW（A A） #输入串的结束符 也可看作是句子的括号 #S#S# FOLLOW(FOLLOW(A A) )表示了句型中可能紧跟在A A后面的终结符号S SA Aa aE T E E T E E + T EE + T E T F T T F T T T * * F T F T F ( E )F ( E )i in ） FOLLOW FOLLOW（E E）S S = TE = FTE = TE = FTE =（E E）TE TE n + + FOLLOW FOLLOW（T T）S S = TE = = TE =

18、 T T+ +TE TE n # # FOLLOW FOLLOW（E E）S S =0 0 E E 第34页/共92页2022-7-635 FOLLOW(FOLLOW(A A)= )= a aS=S=* *AaAa，aaT T 若S=S=* *A A，则# #FOLLOWFOLLOW（A A）重复以下计算，直到每个FOLLOW(A)FOLLOW(A)不再增大为止： 1)1)将 # # 加入到 FOLLOW( FOLLOW( S S ) )中 例 # FOLLOW( E )# FOLLOW( E ) 2)2)若AAB B, , 则将FIRST()-FIRST()-加入FOLLOW(B)FOLLO

19、W(B) 第35页/共92页2022-7-636 3) 3) 若 A A B B ，或 A A B B， 且 =* *，即 FIRST() FIRST()，ABAB 则将FOLLOW(A)FOLLOW(A)所有元素加入FOLLOW(B)FOLLOW(B) 第36页/共92页2022-7-637第37页/共92页2022-7-638第38页/共92页2022-7-639第39页/共92页2022-7-640 输入输出 输入：符号串(有序的) 输出：结构化的符号串(树结构) 产生式的选择 根据当前符号（单词） 语法分析树的表示 按照使用序列排列的产生式序列第40页/共92页2022-7-641 非

20、终结符A A的所有候选首符集两两不相交， 即A A的任何两个不同候选和，满足： FIRST(FIRST() FIRST() FIRST() = ) = 当要求 A A 匹配输入串时，A A就能根据它所面 临的第一个输入符号 a a，准确地指派某一个 候选去执行任务，这个候选就是那个终结首 符集含 a a 的第41页/共92页2022-7-642 当非终结符 A A 面临输入符号a a，但a a不属于A A的任何候选首符集，如果A A有候选式AA(A(A的某个候选首符集包含)，可以让A A自动得到匹配，即A A匹配于空字，但输入符号不读进 要想让A A自动匹配成功，需要考察FOLLOW(A)FO

21、LLOW(A) 第42页/共92页2022-7-643 文法不含左递归 对于文法的每个非终结符 A A 的任何两 个不同的产生式 A|A|1) FIRST()FIRST() = 1) FIRST()FIRST() = 2) =2) = =* * 和= =* * 不能同时成立3) 3) 如果=* * ，则 FISRT()FOLLOW(A)= FISRT()FOLLOW(A)= 满足以上条件的文法称为LL(1)LL(1)文法第43页/共92页2022-7-644满足条件（3 3）： E FIRST(+TE)=+ FOLLOW(E)=),# E FIRST(+TE)=+ FOLLOW(E)=),#

22、T FIRST( T FIRST(* *FT)=FT)=* * FOLLOW(T)=+,),# FOLLOW(T)=+,),# 文法G G是LLLL（1 1）文法第44页/共92页2022-7-645 含义 第一个 L 表示从左向右扫描输入符号串 第二个 L 表示生成最左推导 1 表示读入一个符号可确定下一步推导 LL(1)文法能够对输入串进行有效的 无回溯的自上而下分析第45页/共92页2022-7-646 对于文法G G，当面临的输入符号为a a，要用 非终结符A A进行匹配时，假设A A的所有产生 式为 AA1 1| | 2 2 | | n n1)1)若aFIRST(aFIRST(i i

23、 ) )，则指派i i去执行任务2)2)若a a不属于任何候选首符集，则： 若属于某个FIRST(FIRST(i i ) )且 aFOLLOW(A)aFOLLOW(A)，则让A A与自动匹配 否则，a a的出现是一种语法错误第46页/共92页2022-7-647 不带回溯的自上而下分析程序第47页/共92页2022-7-648第48页/共92页2022-7-649C C语言 E E（ ） T T; ; EE; ; 第49页/共92页2022-7-650E()E() if (c=if (c=+ +) p+; p+; T T; ; EE; ; 第50页/共92页2022-7-651C C语言练习T

24、( )T( ) F F; ; TT; ; 第51页/共92页2022-7-652第52页/共92页2022-7-653procedure F; procedure F; begin begin if sym= if sym=( ( then then begin advance; begin advance; E E; ; if sym= if sym= ) ) then advance then advance else error else error 括号不匹配 end end else if sym= else if sym= i i then advance then advance

25、 else else errorerror FF面临非（，i i输入符号，语法错误 end end第53页/共92页2022-7-654第54页/共92页2022-7-655i+i的递归下降分析过程 i ii i生成语法分析树i + i #i + i #匹配成功返回，指针下移自动匹配，返回自动匹配，返回自动匹配，返回匹配成功继续，指针下移匹配成功返回，指针下移分析成功结束第55页/共92页2022-7-656 优点： 1）直观、简单、可读性好 2）便于扩充 缺点： 1) 递归算法的实现效率低 2) 处理能力相对有限 3) 通用性差，难以自动生成第56页/共92页2022-7-657 第57页/

26、共92页2022-7-658 第58页/共92页2022-7-659 第59页/共92页2022-7-660简介预测分析程序的工作过程预测分析表的构造综合练习第60页/共92页2022-7-661实现LL(1)分析的另一种有效方法使用一张二维分析表（预测分析表）和一个分析栈（文法符号栈）联合进行控制来实现自上而下分析技术第61页/共92页2022-7-662 第62页/共92页2022-7-663第63页/共92页2022-7-664 分析栈用于存放分析过程中的文法符号第64页/共92页2022-7-665 第65页/共92页2022-7-666对于任何（X X，a a） X X是栈顶符号 a

27、 a是面临输入符号(1)(1)XXT T 且 X Xa a#， 分析成功结束，输入串是一个合法句子(2) X(2) XT T 且 X Xa#a#， X X出栈，输入指针指向下一输入符号(3) (3) XXN N ，查分析表 M XM X，aa 若 M XM X，a= a= XXi i， X X出栈，i i逆序入栈，输入指针不动 若 M XM X，a= a= 空， 则调用errorerror程序，进行错误处理第66页/共92页2022-7-667 栈 输入缓冲区 所用产生式0 #0 #E E i i* *i+i# E TE ETi+i# E TE ET入栈1 #E1 #ET T i i* *i+

28、i# T FT i+i# T FT 2 #ET2 #ETF F i i* *i+i# F ii+i# F i3 #ET3 #ETi i i i* *i+i# ii+i# i出栈，a a下移4 #E4 #ETT * *i+i# Ti+i# T* *FT FT 5 #ETF5 #ETF* * * *i+i# i+i# * *出栈，a a下移6 #ET6 #ETF F i i+i# F i +i# F i 7 #ET7 #ETi i i i+i# i+i# i出栈，a a下移第67页/共92页2022-7-668 栈 输入缓冲区 所用产生式8 #E8 #ETT + +i# T i# T 9 #9 #

29、EE + +i# E +TEi# E +TE10 #ET10 #ET+ + + +i# i# 11 #E11 #ET T i i# T FT# T FT12 #ET12 #ETF F i i# F i# F i13 #ET13 #ETi i i i# # 14 #E14 #ETT # # T T 15 #15 #EE # # E E 16 16 # # # # # = # # = #分析成功结束第68页/共92页2022-7-669栈 输入缓冲区 所用产生式 BEGINBEGIN0 #0 #E E i i+i# E TE+i# E TE1 #E1 #ET T i i+i# T FT+i# T

30、FT2 #ET2 #ETF F i i+i# F i +i# F i 3 #ET3 #ETi i i i+i# +i# 4 #E4 #ETT + +i# T i# T 5 #5 #EE + +i# E +TEi# E +TE6 #ET6 #ET+ + + +i# i# 7 #E7 #ET T i i# T FT# T FT 第69页/共92页2022-7-670i+i 分析过程续栈 输入缓冲区 所用产生式8 #ET8 #ETF F i i# F i# F i9 #ET9 #ETi i i i# # 10 #E10 #ETT # # T T 11 #11 #EE # # E E 12 12 #

31、# # # # = # # = #分析成功第70页/共92页2022-7-671栈 输入缓冲区 所用产生式0 #0 #E E i i+i+i* *i# E TEi# E TE1 #E1 #ET T i i+i+i* *i# i# T FT T FT2 #ET2 #ETF F i i+i+i* *i# F ii# F i3 #ET3 #ETi i i i+i+i* *i# i# 4 #E4 #ETT + +i i* *i# T i# T 5 #5 #EE + +i i* *i# E i# E +TE+TE6 #ET6 #ET+ + + +i i* *i#i#7 #E7 #ET T i i* *i

32、# T FTi# T FT 第71页/共92页2022-7-672栈 输入缓冲区 所用产生式8 #ET8 #ETF F i i* *i# F i i# F i 9 #ET9 #ETi i i i* *i# i# 10 #E10 #ETT * *i# T i# T * *FTFT11 #ETF11 #ETF* * * *i# i# 12 #ET12 #ETF F i i# F i# F i13 #ET13 #ETi i i i# # 14 #E14 #ETT # # T T 15 #15 #EE # # E E 16 16 # # # # 分析成功结束第72页/共92页2022-7-673BEG

33、INBEGIN PUSH(STACK,#) PUSH(STACK,#)；PUSH(STACK,PUSH(STACK,开始符号);); a= a=第一个输入符号； FLAG:=TRUEFLAG:=TRUE； WHILE FLAG DOWHILE FLAG DO BEGIN BEGIN X=POP(STACK); X=POP(STACK); IF X IF XT T THEN THEN IF X=a THEN a= IF X=a THEN a=下一个符号 终结符匹配 ELSE ERROR ELSE ERROR与当前输入符号不匹配 第73页/共92页2022-7-674ELSE IF X=# THE

34、N ELSE IF X=# THEN IF X=a FLAG:=FALSE ELSE IF X=a FLAG:=FALSE ELSE ERRORERROR第74页/共92页2022-7-6754.5.2 预测分析表的构造 p78设有文法G G，预测分析表构造过程： 计算所有候选式的首符集 FIRSTFIRST（） 计算所有非终结符A A的后继符集 FOLLOWFOLLOW（A A） 构造预测分析表 M M第75页/共92页2022-7-676 FIRST()= FIRST()= a a = =* * a a ，aaT T 若 = =* * ，则 FIRST() FIRST() 计算文法符号X

35、X的FIRSTFIRST（X X） 计算文法符号串=X=X1 1X X2 2XXn n的FIRST()FIRST()第76页/共92页2022-7-677 FOLLOW(FOLLOW(A A)= )= a aS=S=* *AaAa，aaT T 若S=S=* *A A，则# #FOLLOWFOLLOW（A A）第77页/共92页2022-7-678(4)(4)把所有无定义的 MA,aMA,a标上“出错标志”第78页/共92页2022-7-679预测分析表的构造算法举例第79页/共92页2022-7-680 1) 编写文法，消除二义性； 2) 消除左递归、提取左因子； 3) 求 FIRST 集合和

36、 FOLLOW 集合 4）检查是不是 LL(1) 文法 若不是 LL(1),说明文法的复杂性超过自上 而下方法的分析能力 5）按照 LL(1) 文法构造预测分析表 6）实现预测分析器第80页/共92页2022-7-681第81页/共92页2022-7-682第82页/共92页2022-7-683 符号栈 输入缓冲区 所用产生式0 #S0 #S baabbb# SbAB baabbb# SbAB1 #BAb baabbb# 1 #BAb baabbb# 移进b b 2 #BA aabbb# AaAb2 #BA aabbb# AaAb3 #BbAa aabbb# 3 #BbAa aabbb# 移进

37、a a4 #BbA abbb# AaAb4 #BbA abbb# AaAb5 #BbbAa abbb# 5 #BbbAa abbb# 移进a a 6 #BbbA bbb# Ab 6 #BbbA bbb# Ab 7 #Bbbb bbb# 7 #Bbbb bbb# 移进b b8 #Bbb bb# 8 #Bbb bb# 移进b b9 #Bb b# 9 #Bb b# 移进b b10#B # B10#B # B11# # 11# # 分析成功结束 4.4.b ba aa ab bb bb b分析过程第83页/共92页2022-7-684 语法错误： 栈顶终结符与当前输入符不匹配 栈顶非终结符A A面临输入符a a，但分析表M M中MA,aMA,a为空 解决方法： 弹出栈顶终结符 利用“同步符号”进行略过或恢复: : (1)FOLLOW(A) (1)FOLLOW(A)略过输入串中的符号 (2)FIRST(A)(2)FIRST(A)根据A A恢复语法分析第84页/共92页2022-7-685加入同步符号的LL(1)LL(1)分析表 p80p80第85页/共92页2022-7-686对)i)i* *+i+i的语法分析与错误处理 p81p81栈 输入缓冲区 所用产生式0 #0 #E