Chapt5语法分析-自下而上ppt.ppt
《Chapt5语法分析-自下而上ppt.ppt》由会员分享,可在线阅读,更多相关《Chapt5语法分析-自下而上ppt.ppt(173页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、编译原理,第五章 语法分析自下而上分析,编译原理,编译原理,第五章 语法分析自下而上分析,自上而下分析法(Top-down)自下而上分析法(Bottom-up),编译原理,语法分析的方法:自下而上分析法(Bottom-up)自上而下分析法(Top-down)基本思想:它从文法的开始符号出发,反复使用各种产生式,寻找匹配的推导。递归下降分析法:对每一语法变量(非终结符)构造一个相应的子程序,每个子程序识别一定的语法单位,通过子程序间的信息反馈和联合作用实现对输入串的识别。预测分析程序优点:直观、简单和宜于手工实现。,编译原理,语法分析的方法:自下而上分析法(Bottom-up)基本思想:从输入串
2、开始,逐步进行“归约”,直到文法的开始符号。即从树末端开始,构造语法树。所谓归约,是指根据文法的产生式规则,把产生式的右部替换成左部符号。算符优先分析法:按照算符的优先关系和结合性质进行语法分析。适合分析表达式。LR分析法:规范归约,编译原理,G(E): E i| E+E | E-E | E*E | E/E | (E) i*i+i E*i+i E*E+i E+i E+E E,i,+,*,i,i,编译原理,5.1.1 归约,采用“移进归约”思想进行自下而上分析。基本思想:用一个寄存符号的先进后出栈,把输入符号一个一个地移进到栈里,当栈顶形成某个产生式的候选式时,即把栈顶的这一部分替换成(归约为)
3、该产生式的左部符号。,编译原理,例:设文法G(S): (1) S aAcBe (2) A b (3) A Ab (4) B d试对abbcde进行“移进归约”分析。,编译原理,编译原理,b,d,b,a,c,e,分析树和语法树不一定一致。自下而上分析过程:边输入单词符号,边归约。核心问题:识别可归约串,编译原理,5.1.2 规范归约,定义:令G是一个文法,S是文法的开始符号,假定是文法G的一个句型,如果有 且,则称是句型相对于非终结符A的短语。特别是,如果有A,则称是句型相对于规则A 的直接短语。一个句型的最左直接短语称为该句型的句柄。,编译原理,考虑文法G(E): E T | E+T T F
4、| T*F F (E) | i和句型i1*i2+i3:E E+T E+F E+i3 T+i3 T*F+i3 T*i2+i3 F*i2+i3 i1*i2+i3短语: i1,i2,i3, i1*i2, i1*i2+i3直接短语: i1,i2,i3句柄: i1,编译原理,在一个句型对应的语法树中,以某非终结符为根的两代以上的子树的所有末端结点从左到右排列就是相对于该非终结符的一个短语,如果子树只有两代,则该短语就是直接短语。,编译原理,可用句柄来对句子进行归约句型 归约规则abbcde (2) A baAbcde (3) A AbaAcde (4) B daAcBe (1) S aAcBe S,编译
5、原理,定义:假定是文法G的一个句子,我们称序列 n, n-1, ,0 是的一个规范归约,如果此序列满足: 1 n= 2 0为文法的开始符号,即0=S 3 对任何i,0 i n, i-1是从i经把句柄替换成为相应产生式左部符号而得到的。,编译原理,把上例倒过来写,则得到:S aAcBe aAcde aAbcde abbcde 显然这是一个最右推导。规范归约是关于是一个最右推导的逆过程最左归约 规范推导由规范推导推出的句型称为规范句型。,编译原理,编译原理,5.1.3 符号栈的使用和分析树的表示,栈是语法分析的一种基本数据结构。#作为栈底符号考虑文法G(E): E T | E+T T F | T*
6、F F (E) | i输入串为i1*i2+i3 ,分析步骤为:,编译原理,步骤 符号栈输入串动作0 #i1*i2+i3#预备1 #i1*i2+i3#进2 #F*i2+i3#归,用Fi3 #T*i2+i3#归,用TF4 #T*i2+i3#进,G(E): E T | E+T T F | T*F F (E) | i,编译原理,步骤 符号栈输入串动作4 #T*i2+i3#进5 #T*i2+i3#进6 #T*F+i3#归,用Fi7 #T+i3#归,用TT*F8 #E+i3# 归,用ET9 #E+i3# 进,G(E): E T | E+T T F | T*F F (E) | i,编译原理,步骤 符号栈输入
7、串动作9 #E+ i3#进10#E+i3#进11#E+F#归,用Fi12#E+T#归,用TF13#E#归,用EE+T14#E#接受,G(E): E T | E+T T F | T*F F (E) | i,编译原理,语法分析的方法:自下而上分析法(Bottom-up) 基本思想:从输入串开始,逐步进行“归约”,直到文法的开始符号。即从树末端开始,构造语法树。所谓 归约 ,是指根据文法的产生式规则,把产生式的右部替换成左部符号。,回顾,编译原理,归约,采用“移进归约”思想进行自下而上分析。基本思想:用一个寄存符号的先进后出栈,把输入符号一个一个地移进到栈里,当栈顶形成某个产生式的候选式时,即把栈顶
8、的这一部分替换成(归约为)该产生式的左部符号。,编译原理,规范归约,定义:令G是一个文法,S是文法的开始符号,假定是文法G的一个句型,如果有 且,则称是句型相对于非终结符A的短语。特别是,如果有A,则称是句型相对于规则A 的直接短语。一个句型的最左直接短语称为该句型的句柄。,编译原理,定义:假定是文法G的一个句子,我们称序列 n, n-1, ,0 是的一个规范归约,如果此序列满足: 1 n= 2 0为文法的开始符号,即0=S 3 对任何i,0 i n, i-1是从i经把句柄替换成为相应产生式左部符号而得到的。,编译原理,步骤 符号栈输入串动作0 #i1*i2+i3#预备1 #i1*i2+i3#
9、进2 #F*i2+i3#归,用Fi3 #T*i2+i3#归,用TF4 #T*i2+i3#进,G(E): E T | E+T T F | T*F F (E) | i,编译原理,步骤 符号栈输入串动作4 #T*i2+i3#进5 #T*i2+i3#进6 #T*F+i3#归,用Fi7 #T+i3#归,用TT*F8 #E+i3# 归,用ET9 #E+i3# 进,G(E): E T | E+T T F | T*F F (E) | i,编译原理,步骤 符号栈输入串动作9 #E+ i3#进10#E+i3#进11#E+F#归,用Fi12#E+T#归,用TF13#E#归,用EE+T14#E#接受,G(E): E
10、T | E+T T F | T*F F (E) | i,编译原理,5.2 算符优先分析,四则运算的优先规则: 先乘除后加减,同级从左到右考虑二义文法文法G(E):G(E): E i| E+E|E-E|E*E|E/E|(E)它的句子有几种不同的规范规约。归约即计算表达式的值。归约顺序不同,则计算的顺序也不同,结果也不一样。如果规定算符的优先次序,并按这种规定进行归约,则归约过程是唯一的。,编译原理,例如:句子i+i-i*(i+i),编译原理,返回,编译原理,句子i+i-i*(i+i)的归约过程是:(1) i+i-i*(i+i)(2) E+i-i*(i+i)(3) E+E-i*(i+i)(4) E
11、-i*(i+i)(5) E-E*(i+i)(6) E-E*(E+i)(7) E-E*(E+E)(8) E-E*(E)(9) E-E*E(10) E-E(11) E,编译原理,起决定作用的是相邻的两个算符之间的优先关系。所谓算符优先分析法就是定义算符之间的某种优先关系,借助于这种关系寻找“可归约串”和进行归约。,编译原理,首先必须定义任何两个可能相继出现的终结符a与b的优先关系 三种关系a b a的优先级低于ba b a的优先级等于ba b a的优先级高于b注意:与数学上的=不同 + + a b并不意味着b a,如 ( + 和 + (,编译原理,5.2.1 算符优先文法及优先表构造,一个文法,如
12、果它的任一产生式的右部都不含两个相继(并列)的非终结符,即不含如下形式的产生式右部:QR 则我们称该文法为算符文法。约定:a、b代表任意终结符;P、Q、R代表任意非终结符;代表由终结符和非终结符组成的任意序列,包括空字。,编译原理,假定G是一个不含-产生式的算符文法。对于任何一对终结符a、b,我们说:1. ab当且仅当文法G中含有形如Pab或PaQb的产生式;,如果一个算符文法G中的任何终结符对(a,b)至多只满足下述三关系之一:ab,ab, ab 则称G是一个算符优先文法。,2. ab当且仅当G中含有形如PaR的产生式, 而R b或R Qb;,3. ab 当且仅当G中含有形如PRb的产生式,
13、而 R a或R aQ。,编译原理,例:考虑下面的文法G(E): (1) EE+T | T (2) TT*F | F (3) FP F | P (4) P(E) | i由第(4)条规则,有 ();由规则EET和TT*F, 有 *;由(2) TT*F 和(3) FP F ,可得*;由(1)EET和E E+T,可得+;由(3)FPF和F PF,可得。由(4)P(E)和 EE+TT+TT*F+TF*F+TPF*F+TiF*F+T 有 (+、(*、(和(i。,编译原理,优先关系表,编译原理,从算符优先文法G构造优先关系表的算法。通过检查G的每个产生式的每个候选式,可找出所有满足ab的终结符对。,确定满足
14、关系和的所有终结符对:,1. ab当且仅当文法G中含有形如Pab或PaQb的产生式;,编译原理,从算符优先文法G构造优先关系表的算法。通过检查G的每个产生式的每个候选式,可找出所有满足ab的终结符对。确定满足关系和的所有终结符对:首先需要对G的每个非终结符P构造两个集合FIRSTVT(P)和LASTVT(P):,编译原理,从算符优先文法G构造优先关系表的算法。通过检查G的每个产生式的每个候选式,可找出所有满足ab的终结符对。确定满足关系和的所有终结符对:首先需要对G的每个非终结符P构造两个集合FIRSTVT(P)和LASTVT(P):,编译原理,从算符优先文法G构造优先关系表的算法。通过检查G
15、的每个产生式的每个候选式,可找出所有满足ab的终结符对。确定满足关系和的所有终结符对:首先需要对G的每个非终结符P构造两个集合FIRSTVT(P)和LASTVT(P):,比较,比较,编译原理,有了这两个集合之后,就可以通过检查每个产生式的候选式确定满足关系和的所有终结符对。假定有个产生式的一个候选形为aP 那么,对任何bFIRSTVT(P),有 ab。假定有个产生式的一个候选形为Pb 那么,对任何aLASTVT(P),有 ab。,编译原理,首先讨论构造集合FIRSTVT(P)的算法。按其定义,可用下面两条规则来构造集合FIRSTVT(P):1. 若有产生式Pa或PQa,则aFIRSTVT(P)
16、;2. 若aFIRSTVT(Q),且有产生式PQ,则aFIRSTVT(P)。,编译原理,数据结构:布尔数组FP,a,使得FP,a为真的条件是,当且仅当aFIRSTVT(P)。开始时,按上述的规则(1)对每个数组元素FP,a赋初值。栈STACK,把所有初值为真的数组元素FP,a的符号对(P,a)全都放在STACK之中。,编译原理,运算:如果栈STACK不空,就将顶项逐出,记此项为(Q,a)。对于每个形如PQ 的产生式,若FP,a为假,则变其值为真且将(P,a)推进STACK栈。上述过程必须一直重复,直至栈STACK拆空为止。,编译原理,如果把这个算法稍为形式化一点,我们可得如下所示的一个程序(包
17、括一个过程和主程序):PROCEDURE INSERT(P,a);IF NOT FP,a THENBEGIN FP,a:=TRUE; 把(P,a)下推进STACK栈 END;,编译原理,主程序:BEGIN FOR 每个非终结符P和终结符a DO FP,a:=FALSE; FOR 每个形如Pa或PQa的产生式 DO INSERT(P,a); WHILE STACK 非空 DOBEGIN 把STACK的顶项,记为(Q,a),上托出去; FOR 每条形如PQ的产生式 DOINSERT(P,a);END OF WHILE;END,编译原理,这个算法的工作结果得到一个二维数组F,从它可得任何非终结符P的
18、FIRSTVT。FIRSTVT(P)a | FP,a=TRUE同理,可构造计算LASTVT的算法。,编译原理,构造集合LASTVT(P)的算法。按其定义,可用下面两条规则来构造集合LASTVT(P):1. 若有产生式P a或P aQ,则a LASTVT(P);2. 若a LASTVT(Q),且有产生式P Q ,则a LASTVT(P)。,编译原理,使用每个非终结符P的FIRSTVT(P)和LASTVT(P),就能够构造文法G的优先表。构造优先表的算法是:,编译原理,FOR 每条产生式PX1X2Xn DO FOR i:=1 TO n-1 DOBEGIN IF Xi和Xi+1均为终结符 THEN
19、置XiXi+1 IF in-2且Xi和Xi+2都为终结符 但Xi+1为非终结符 THEN 置XiXi+2; IF Xi为终结符而Xi+1为非终结符 THENFOR FIRSTVT(Xi+1)中的每个a DO 置 Xia; IF Xi为非终结符而Xi+1为终结符 THEN FOR LASTVT(Xi)中的每个a DO 置 aXi+1 END,编译原理,例: 考虑下面的文法G(E): (1) EE+T | T (2) TT*F | F (3) FP F | P (4) P(E) | i1. 计算文法G的FIRSTVT和LASTVT;2. 构造优先关系表;3. G是算符优先文法吗?,编译原理,编译原
20、理,结论: G是算符优先文法,G的算符优先关系表,编译原理,回顾,定义任何两个可能相继出现的终结符a与b的优先关系 三种关系a b a的优先级低于ba b a的优先级等于ba b a的优先级高于b注意:与数学上的=不同,a b并不意味着b a,编译原理,假定G是一个不含-产生式的算符文法。对于任何一对终结符a、b,我们说:1. ab当且仅当文法G中含有形如Pab或PaQb的产生式;,如果一个算符文法G中的任何终结符对(a,b)至多只满足下述三关系之一:ab,ab, ab 则称G是一个算符优先文法。,2. ab当且仅当G中含有形如PaR的产生式, 而R b或R Qb;,3. ab 当且仅当G中含
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- chapt5 语法分析 自下而上 ppt
限制150内