ch5自底向下语法分析.ppt

1,第五章 语法分析,该讲语法分析了！ 这可是很重要的章节,2,主要内容：,本章将重点介绍典型的语法分析方法及相关的概念和实现技术,语法分析分为：,自上而下:,自下而上：,递归下降分析法,LL（1）预测分析法,推导,算符优先分析法,LR分析法,归约,从根向叶的方向建立语法树,从叶向根的方向建立分析树,3,5.1语法分析器的功能,词法分析器,语法分析器,语义分析,符号表,源程序,单词符号,语法树,中间表示,完成的任务：, 对词法分析器产生的单词符号进行处理，输出语法树,与单词相关的信息记录到符号表中,类型检查,错误处理,5.1.1 语法分析器任务,4,5.1.2 相关约定,一.符号的使用约定,1. 终结符,.字母表中比较靠前的小写字,如a,b,c,. 操作符，如+、-等,. 标点符号，如括号、逗号等,. 数字0、1、。9,. 黑体串，如if 、i等,5,2.下列符号是非终结符,.字母表中比较靠前的大写字,如A、B、C,.字母S，常用来表示开始符号,. 小写斜体名字，如expr、stmt,6,3.字母表中比较靠后的大写字母，如X、Y、Z等，用来表示文法符号，也就是说，可以是终结符，也可以是非终结符,4.字母表中比较靠后的小写字母，如u、vz等，表示终结符的串联,5.小写希腊字母、等表示 文法符号的串，所以一个产生式可写作：,A ,7,5.2自顶向下分析法,5.2.1 使用的技术、存在的问题及解决方法,8,一、 推导,推导：就是用产生式的右部的串来代 替左部的非终结符,事实上推导给出了自顶向下构成分析树过程的精确描述,例：有描述算术表达式的文法G,字符串-(i+i) 是该文法的句子，其推导过程如下：,E E+E| E*E|（E）|-E|i,9,E,几个约定：,=-E,=-（E）,=-（E+E）,=-（i+E),=-(i+i),E=-E E推导出-E,10,最左推导：每一步都坚持替换当前句型中 最左非终结符的推导,最右推导：每一步都坚持替换当前句型中 最右非终结符的推导，也称为 规范推导,+ 句子：S =w 称终结符串w是文法G句子,+ 句型：S = 称是文法G的句型,+ 语言：L（G）=w/S =w ,11,二、语法树,语法描绘了如何从文法的开始符号推导出一个句子的过程,语法树可以看成是推导的图形表示，但它不能显示出替代的顺序,前面句子-(i+i)推导过程所对应的分析树如下：,12,=,E,E,=,E,-,E,(,E,E,),=,-,E,(,E,),=,=,E,-,E,(,E,),E,+,E,i,E,-,E,(,E,),E,+,E,E,+,E,i,i,-,E,13,4.如果A是某个内结点的非终结符标记，A1， A2， An是该结点从左到右排列的所有子结点的标记，则A A1 A2 An是一个产生式,3.每个内结点由一个非终结符标记,1.树根标记为开始符号,2.每个叶结点由终结符或者标记,语法具有如下特性的树：,14,语法树的叶结点从左到右的排列，刚好是这个文法所产生的语言的一个句子,一个文法生成的语言就是它的某个分析树所生成的句子的集合,为给定的终结符串（句子）构造一棵语法树的过程称为这个串（句子）的语法分析（parsing),15,三、二义性,句子i+i*i 有两棵分析树与之对应,E E + E i E * E i i,E E * E E + E i i i,16,给定一个文法G，如果L（G）中存在一个具有两棵或两棵以上分析树的句子，,很显然，描述算术表达式的文法G E E+E| E*E|（E）|-E|i 是一个二义性文法,造成二义性的原因是：文法中没有体现出结合律和优先级,我们就称该文法为二义性的，G也叫二义性文法。,17,大多数的语法分析器都要求文法是无二义性的,消除二义性：,可以通过改写文法来消除二义性,例：stmtif expr then stmt |if expr then stmt else stmt |other,18,通过例子 if E1 then if E2 then S2 else S3 很容易证明这是一个二义性文法,19,S,if,E,then,S,if,E,then,S,else,S,20,在程序设计语言中，我们常常采用“最近匹配”原则来解决这种二义性,文法改写出为：,stmt matched_stmt |unmatched_stmt matched_stmt if expr then matched_stmt else matched_stmt | other unmatched_stmt if expr then matched_stmt else unmatched_stmt | if expr then _stmt,21,四、消除左递归,例：下面是描述算术表达式的算法 S E EE+T|T TT*F|F F(E)|i,则称文法G是左递归的；,如果AA ，则称文法G是直接左递归的,22,左递归会使分析进入到无限循环之中,消除简单左递归的方法： 对于含有左递归的产生式 AA | ,可用下面的非左递归的产生式 代替： A A A A| ,23,例：下面是描述算术表达式的算法 S E EE+T|T TT*F|F F(E)|i,消除E和T的直接左递归，得到： S E,ETE,E +TE|,T FT,F(E)|i,T*FT| ,24,对于一般情况而言，若某一文法G的产生式具有如下形式：,则可用如下方法消除左递归:,AA 1| A 2 | A m| 1| 2| n,A1A| 2A | n A,A 1A| 2A| | mA | ,很容易证明改造前后的文法是等价的,25,例：文法G（P）： P （Q）|aP|a Q Q ,P|P 试消除左递归,26,消除左递归后，方法改为：,P （Q）|aPa Q P Q ，,27,SQc|c Q Rb|b R Sa|a,S,这样的递归无法用前面的方法消除,对于含有间接左递归的文法：,=Qc,=Rbc,= Sabc,出现了左递归,28,消除左递归的一般算法：,输入：无循环推导和产生式的文法G,输出：与G等价的无左递归文法,算法：,29,1.以某种顺序排列非终结符A 1A 2A n 2.for i=1 to n do begin for j=1 to i-1 do begin 改写A i A j 规则，方法如下： 如果A j 1| 2| k 则A i 1 | 2 | n ； end 消除A i中的所有直接左递归 End 3.化简由2所得文法,30,SQc|c Q Rb|b R Sa|a,对如下文法消除左递归：,1.将非终结符排序为R、Q、S,2.R不存在左递归，将R代入Q： Q Sab|ab|b,3. Q不存在左递归，将Q代入S S Sabc|abc|bc|c,4.消除直接左递归后，得文法：,31,SabcS| bcS| cS SabcS| Q Rb|b R Sa|a,5.化简文法,SabcS| bcS| cS SabcS| ,32,32,例：已知符号串S=cad 文法GZ: ZcAd Aab|a 求解 SL(GZ),分析过程 是设法建立一棵语法树, 使语法树的末端结点与 给定符号串相匹配.,2.用Z的右部,符号串去匹配输入串,完成一步推导ZcAd 检查 c-c匹配 A是非终结符,将匹配任务交给A,33,33,3. 选用A的右部符号串匹配输入串 A有两个右部,选第一个,完成进一步推导Aab 检查,a-a匹配,b-d不匹配(失败) 但是还不能冒然宣布SL(GZ),4. 回溯 即砍掉A的子树 改选A的第二右部,Aa 检查 a-a匹配 d-d匹配,建立语法树,末端结点为cad与输入cad相匹配, 建立了推导序列 ZcAdcad cadL(G(Z),S=cad GZ: ZcAd Aab|a,分析工作要部分地或全部地退回去重做叫回溯,34,五、回溯、提取左因子,为句子if E1 then S1 else S2构造一棵语法树,文法： stmtif expr then stmt |S |if expr then stmt else stmt,回溯,35,造成这种情况的原因是产生式具有相同的首符号，从而导致不清楚该用哪个来替换非终结符,可通过改写产生式来推迟这种决定，直到看见足够多的输入符号，可以作出正确选择为止,上例可改为： stmtif expr then stmt S |S S else stmt | ,36,stmt if expr then stmt S E1 else stmt,提取左因子算法：,输入：文法G,输出：一个等价的提取了左因子的文法,方法：对于A 1| 2 | n| ,可改写为： A A| ,A 1| 2 | n,37,例：EE+T EE-T TT*F TT/F Fi F（E）,EEE E +T|-T T TT T *F|/F Fi F（E）,定义： FIRST() = a | * a， a Vt ， , V* 若 * ，则规定 FIRST() 该集合称为的头符号集合,设有文法GZ:,六、FIRST与FOLLOW、SELECT集,39,39,设=X1X2.Xn, XiVn Vt 求FIRST()=? 首先求出组成的每一个符号Xi的FIRST集合,若XiVt，则 FIRST(Xi) = Xi,(2) 若Xi Vn 且Xia|， a Vt 则 FIRST(Xi)=a，,() 集合FIRST的算法,40,40,41,例1：有文法G（S） S BA A BS A d B aA B bS B c 试写出其FIRST集,First(B)=a,First(B)=b,First(B)=c,First(S)=First(BA)=a,b,c,First(A)=First(BS)=a,b,c,First(A)=d,42,42,() 构造集合FOLLOW的算法,若S为识别(开始)符号,则把“#”加入FOLLOW(S)中,(2)若AB (),则把FIRST()-加入FOLLOW(B),(3)若AB 或AB， 且*则把FOLLOW(A)加 入FOLLOW(B),注：FOLLOW集合中不能有,设S, A, BVn , 算法：连续使用以下规则，直至FOLLOW集合不再扩大,43,43,解：1）求FIRST： FIRST(F)= (，i FIRST(T)=*, FIRST(T)=FIRST(F)-= (，i FIRST(E)=+, FIRST(E)= FIRST(T)-=(，i,例2：有文法GE ETE E+TE| TFT T*FT| F(E)|i,1）求FIRST： 2）求FOLLOW,44,44,ETE E+TE| TFT T*FT| F(E)|i,2）求FOLLOW,FIRST(F)=(,i FIRST(T)=*, FIRST(T)=(,i FIRST(E)=+, FIRST(E)=(,i,45,45,注： SELECT集合中不能有,由定义可见，SELECT(Ax)实际上是指在推导过程中，若采用规则Ax进行推导时，可能推导出的下一个终结符号组成的集合。,() SELECT集,46,46,ETE E+TE| TFT T*FT| F(E)|i,求SELECT,FIRST(F)=(,i FIRST(T)=*, FIRST(T)=(,i FIRST(E)=+, FIRST(E)=(,i,SELECT(ETE)= (,i SELECT(E+TE)= + SELECT(E )= ),# SELECT(TFT)= (,i SELECT(T*FT)=* SELECT(T)= +,),# SELECT (F(E)= ( SELECT (Fi)= i ,FOLLOW(F)=*,+,),# FOLLOW(T)=+,),# FOLLOW(T)=+,),# FOLLOW(E)=#,) FOLLOW(E)=#,),FIRST(TE)=FIRST(T)=(，i FIRST(+TE)=+ FIRST()= FIRST(FT)= FIRST(F)=(，i FIRST(（E）)=( FIRST(i)=i,47,七、LL（1）文法,一个上下文无关文法若满足下列条件， 我们就称它为LL（1）文法,文法不含左递归,文法中每个非终结符A的各个产生 式的首终结符集两两不相交，即 A 1| 2 | n 则 FIRST（ i ）FIRST（ j ）=,文法中每个非终结符A若其首字符 集中含有，则 FIRST（ i ）FOLLOW（A）= ,48,这里LL（1）中的,只有LL（1）文法，才可以实现确定的自顶向下语法分析,第一个L表示从左 到右扫描输入串，,第二个L表示最左 推导，,1表示分析时每步 只需向前查看一 个符号,49,5.2.2 递归下降法,为每一个非终结符编制一个递 归下降过程，,方法：,过程的名字就产生 式左部的非终结符，,过程体则是 按产生式的右部符号顺序编写的，,每匹配一个终结符，则再读入下 一个输入符号；,对于产生式右部 的每个非终结符，则递归调用相 应过程,50,例：对于文法G ETE E +TE| T FT T*FT| F(E)|i 其递归下降分析程 序编写如下：,PROCEDURE E BEGIN T； E； END,PROCEDURE T BEGIN F； T； END,51,PROCEDURE E IF SYM=+ THEN ADVANCE； T； E； END,PROCEDURE T IF SYM=* THEN ADVANCE； F； T； END,这一步实际上就匹配了一个输入符号,52,PROCEDURE F IF SYM=i THEN ADVANCE； ELSE IF SYM=（ THEN BEGIN ADVANCE； E； IF SYM=） THEN ADVANCE； ELSE ERROR END ELSE ERROR；,当调用一个过程的时候，就相当于进行了一步推导,53,5.2.3 LL（1）预测分析法,一、特征 根据当前输入符号，为当前要处 理的非终结符选择产生式,二、表驱动的预测分析器包含： 一个输入缓冲区 一个栈 一张分析表 一个输出流,要求文法是LL(1)的,54,三、预测分析器模型：, a + b #,预测分析程序,X Y Z #,分析表M,输出,#是输入串的结 束标记，也是栈 底符号,55,四、预测分析表M,预测分析表是一个MA，a形式的矩阵,其中： A为非终结符，a为终结符或#,MA，a中存放着一条关于A的产生式，指出当A面临a时所应采取的候选；,MA，a中也可能存放一条“出错标志”，指出不应该面临a,56,非终结符,输入符号,E,E,T,T,F,i,*,(,),#,+,TE,TE,+TE, , ,FT,FT, , , ,*FT,(E),i,预测分析表,57,预测分析表的构造,for i:A do for a= FIRST（ ） begin MA,a= A; end if FIRST（ ） for bFOLLOW（ A） MA,b= A; 将M的空白处均置为error,即A ,58,五、预测分析器的工作方式,1、如果X=a=#,分析成功,2、如果X=a#，则POP，advance,3、如果X Vn,查MX，a表 若MX，a=XUVW,则用WVU替换栈顶； 若MX，a=error,则调用错误恢复程序,当前栈顶符号X和当前输入符号为a，则语法分析器的动作为：,59,预测分析程序的算法：,输入：串w和文法G的分析表M 输出：如果w属于L（G），则输出w的最左推导，否则报错,方法：开始时，#S在栈里 w#在输入缓冲区,令ip指向w#的第一个符号 令X是栈顶符号，a是ip指向的符号,60,Repeat If X Vt, then if X=a then pop X，ip指向下一个符号 else error() Else if MX,a= X Y1 Y2 Yk then pop X; push Yk Yk-1 Y1; 输出 X Y1 Y2 Yk Until X= # if X=a=# 接收 else error,61,句子i+i*i的分析过程,栈,输入,输出,#E,#ET,#ETF,#ET,#E,#ETi,#ET+,#ET,#ETF,#ETi,#ET,#,#ETF,#ETi,#ET,#E,#ETF*,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#,#,#,#,ETE,TFT,Fi,T ,E+TE,TFT,Fi,T*FT,Fi,T ,E ,62,练习：文法G（S） SS*aT|aT T +aT| 消去左递归，求FIRST和FOLLOW 写出句子a*a*a+a的分析过程,解：S aTS S *aTS| T +aT| ,63,FIRST(S)=a FIRST(S)=*, FIRST(T)=+ , FOLLOW(S)=# FOLLOW(S)=# FOLLOW(T)=*,#,64,* + a # S aTS S *aTS T +aT ,65,句子a*a*a+a的分析过程,栈,输入,输出,#S,#STa,#ST,#STa*,#ST,#S,#S,# STa*,# ST,#ST a+,#ST,#S,a*a*a+a#,a*a*a+a#,*a*a+a#,*a*a+a#,*a*a+a#,*a+a#,*a+a#,+a#,+a#,+a#,#,#,SaT S,T ,T ,T +aT,T ,S *aTS,S *aTS,S ,#,#,end,66,七、预测分析的错误恢复,1、发现错误 栈顶的终结符与当前输入符不匹配 非终结符A位于栈顶，面临的输入符为a，但分析表M的MA,a为空,2、“应急”恢复策略 跳过输入串中的一些符号直至遇到“同步符号”为止。,67,3、同步符号的选择,把FOLLOW(A)中的所有符号作为A的同步符号。跳过输入串中的一些符号直至遇到这些“同步符号”，把A从栈中弹出，可使分析继续,把FIRST(A)中的符号加到A的同步符号集，当FIRST(A)中的符号在输入中出现时，可根据A恢复分析,68,可以把表示语句开