您所在位置：网站首页 > IT计算机/网络 > 计算机原理编译原理语法分析器设计从下至上

编译原理语法分析器设计从下至上

99页

卖家[上传人]：xzh****18

文档编号：56627470

上传时间：2018-10-14

文档格式：PPT

文档大小：709.50KB

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 金贝

/ 99 举报版权申诉马上下载

文本预览

下载提示

常见问题

1、1,编译方法,中国人民大学信息学院陈文萍,2,第五章语法分析自下而上分析,5.1 自下而上分析基本问题 5.2算符优先分析 5.3 LR 分析法 5.4 语法分析器的自动产生工具 YACC,3,5.1 自下而上分析基本问题,自下而上语法分析试图将一个字符串反向归约至开始符号比自上而下语法分析更有效率，对语法的限制更少移进归约过程移进：将一个终结符推进栈归约：当栈顶形成某个产生式的候选式时，把这些符号从栈中弹出，把产生式的左部符号压入栈,4,文法GS： (1) S aAcBe (2) A b (3) A Ab (4) B d,b,b,c,d,e,A,3） #ab bcde# 归约(Ab),A,5） #aAb cde# 归约(AAb),B,8） # aAcd e# 归约(Bd),S,10） #aAcBe # 归约(SaAcBe),分析符号串abbcde是否GS的句子,步骤,符号栈,输入符号串,动作,1） # abbcde# 移进,2） #a bbcde# 移进,4） #aA bcde# 移进,6） #aA cde# 移进,7） #aAc de# 移进,9） #aAcB e#

2、移进,11） #S # 接受,对输入串abbcde#的移进-规约分析过程,a,5,规范归约,短语、直接短语、句柄的定义：文法GS，S A，且A 则称是句型相对于非终结符A的短语。若有A ，则称是句型相对于该规则A 的直接短语。一个句型的最左直接短语称为该句型的句柄。规范归约: 设是文法G的一个句子，称序列n ,n-1, 0 是的一个规范规约，如果此序列满足： n 0 为文法的开始符，即0 S 对任何i,0i=b,24,文法GE： (0) E#E# (1) EE+T (2) ET (3) TT*F (4) TF (5) FPF|P (6) P(E) (7) Pi,FIRSTVT(E)=# FIRSTVT(E)=+,*,(,i FIRSTVT(T)=*,(,i FIRSTVT(F)=,(,i FIRSTVT(P)=(,i LASTVT(E)=# LASTVT(E)=+,*,),i LASTVT(T)=*,),i LASTVT(F)=,),i LASTVT(P)=),i,1)=关系由产生式(0)和(6),得 #=#，（=） 2）关系找形如：AaB的产生式 #E：则#FIRSTVT(

3、E) +T: 则+FIRSTVT(T) *F: 则*FIRSTVT(F) F:则 FIRSTVT(F) (E: 则 (关系找形如：ABb的产生式 E# ,则 LASTVT(E)# E+ ,则 LASTVT(E)+ T* ,则 LASTVT(T)* P ,则 LASTVT(P) E) ,则 LASTVT(E),25,算符优先分析算法,归约过程中，只考虑终结符之间的优先关系来确定可归约串，而与非终结符无关不存在单个非终结符组成的可归约串，用算符优先分析法的归约过程与规范归约是不同的为解决在算符优先分析过程中如何寻找可归约串，引进最左素短语的概念,26,算符优先分析算法,算符文法的任一句型有如下形式： #N1a1N2a2NnanNn+1#, 对于算符优先文法，如果aNb(或ab)出现在句型r中若ab，则在r中必有含有a而不含b的短语存在若a=b，则在r中含有a的短语必含有b，反之亦然句型的素短语是一个短语，它至少包含一个终结符，且除自身外不再包含更小的素短语。处于句型最左边的素短语为最左素短语定理：一个算符优先文法G的任何句型的最左素短语是满足下列条件的最左子串NjajNiai

4、Ni+1 aj-1 ai+1,27,算符优先分析算法,文法GE： (1) EE+T (2) ET (3) TT*F (4) TF (5) FPF|P (6) P(E) (7) Pi,句型#T+T*F+i# 其短语有： T+T*F+i T+T*F T T*F i,最左素短语为：T*F,28,算符优先分析算法,K:=1; Sk:=#; Repeata：下一个输入符号；IF Sk VT THEN j:=k ELSE j:=k-1;WHILE Sja DOBEGINREPEATQ:=Sj;IF Sj-1 VT THEN j:=j-1 ELSE j:=j-2UNTIL Sj Q;把sj+1sk 归约为某个N;k:=k+1;Sk:=N;END OF WHILE;IF Sj a OR Sj=a THENBEGIN k:=k+1; Sk:=a ENDELSE ERROR /*调用出错诊察程序*/ UNTIL a=#,29,算符优先文法的错误处理,错误种类栈顶的终结符与下一个输入符之间没有优先关系栈顶出现了素短语,但没有一个产生式的右部为此素短语错误处理改变,插入,删除符号给出错误信息,30,

5、LR分析法,能力强大部分上下文无关文法都能用LR分析识别效率高，准确发现输入串错误难点手工编写LR分析器工作量大现实有LR分析器的生成器，如YACC,31,LR分析法,LR含义 L：从左到右扫描输入串， R：构造最右推导LR分析特征栈顶状态为S, 当前输入符号是a时做什么-? 四种技术 LR(0) SLR 规范LR LALR,32,LR分析器,LR分析器模型,33,LR分析器,核心：分析表动作（ACTION）表: ACTIONS,a告诉分析器状态为S, 当前输入符号是a时做什麽状态转换（GOTO）表: GOTOS,A规定状态S面对文法符号为A时，下一状态是什么工作过程：栈的状态序列，已归约串和输入串所构成的三元式的变化过程。初始状态：（s0, #, a1a2an# ）分析过程：（ s0 s1 sm, # X0 X1 Xm, aiai+1an# ）,34,LR分析算法,分析器动作：由栈顶状态sm和当前输入符号ai决定，即执行 ACTION sm, ai 的动作。三元式的变化 1. 若ACTIONsm, ai为移进，且s= GOTOsm, ai：（ s0 s1 sms, # X1 Xmai, ai+1an# ） 2.若ACTIONsm, ai为按产生式A归约, 的长度为r，且s= GOTOsm-r, A：（ s0 s1 sm-rs, # X1 Xm-rA, aiai+1an# ） 3.若ACTIONsm, ai为接受，则终止分析，宣布成功。 4.若ACTIONsm, ai为报错，则终止分析，报告错误。,

《编译原理语法分析器设计从下至上》由会员xzh****18分享，可在线阅读，更多相关《编译原理语法分析器设计从下至上》请在金锄头文库上搜索。

点击阅读更多内容

TA的资源