编译5语法分析－金锄头文库

资源描述

《编译5语法分析》由会员分享，可在线阅读，更多相关《编译5语法分析（60页珍藏版）》请在金锄头文库上搜索。

1、编译原理(第三版)陈火旺等编著（20122012年年9 9月月-12-12月）月）主讲：朱世松主讲：朱世松计算机学院计算机学院2*第五章语法分析自下而上分析n自上而下分析法(Top-down)n自下而上分析法(Bottom-up)3*n语法分析的方法：自上而下分析法(Top-down)n基本思想：它从文法的开始符号出发，反复使用各种产生式，寻找“匹配“的推导。n递归下降分析法：对每一语法变量(非终结符)构造一个相应的子程序，每个子程序识别一定的语法单位，通过子程序间的信息反馈和联合作用实现对输入串的识别。n预测分析程序F优点：直观、简单和宜于手工实现。4*n语法分析的方法：自下而上

2、分析法(Bottom-up)n基本思想：从输入串开始，逐步进行“归约” ，直到文法的开始符号。即从树末端开始，构造语法树。所谓归约，是指根据文法的产生式规则，把产生式的右部替换成左部符号。n算符优先分析法：按照算符的优先关系和结合性质进行语法分析。适合分析表达式。nLR分析法：规范归约5*5 5若若Z Z S S 则则 S S L(GZ) L(GZ) 否则否则 S S L(GZ) L(GZ) + +GZGZ存在主要问题存在主要问题: : 左递归问题左递归问题回溯问题回溯问题主要方法主要方法: : 递归子程序法递归子程序法 LLLL分析法分析法自上而下分析算法的基本思想为：自上而下分析

3、算法的基本思想为：若若Z Z S S 则则 S S L(GZ) L(GZ) 否则否则 S S L(GZ) L(GZ) + +GZGZ自下而上分析算法的基本思想为：自下而上分析算法的基本思想为：存在主要问题存在主要问题: : 句柄的识别问题句柄的识别问题主要方法主要方法: : 算法优先分析法算法优先分析法 LRLR分析法分析法存在主要问题存在主要问题: : 左递归问题左递归问题回溯问题回溯问题主要方法主要方法: : 递归子程序法递归子程序法 LLLL分析法分析法存在主要问题存在主要问题: : 句柄的识别问题句柄的识别问题存在主要问题存在主要问题: : 左递归问题左递归问题回溯问题回溯问题

4、主要方法主要方法: : 递归子程序法递归子程序法 LLLL分析法分析法主要方法主要方法: : 算法优先分析法算法优先分析法 LRLR分析法分析法存在主要问题存在主要问题: : 句柄句柄的识别问题的识别问题存在主要问题存在主要问题: : 左递归问题左递归问题回溯问题回溯问题主要方法主要方法: : 递归子程序法递归子程序法 LLLL分析法分析法6*例：G(E)： E i| E+E | E-E | E*E | E/E | (E)i*i+iE*i+iE*E+iE+iE+EEi+*EiiEEEE7*5.1.1 归约n采用“移进归约”思想进行自下而上分析。n基本思想：用一个寄存符号的后进先出栈，把输

5、入符号一个一个地移进到栈里，当栈顶形成某个产生式的候选式时，即把栈顶的这一部分替换成(归约为)该产生式的左部符号。8*n例：设文法G(S)：(1) S aAcBe(2) A b(3) A Ab(4) B d 试对abbcde进行“移进归约”分析。abbcdeb abcdeA abcdeb A acdeA acdec A aded c A aeabbcdee B c A aSB c A ae9*10*bdbaceSABA最终的语法分析树自下而上分析过程：边输入单词符号，边归约。核心问题：如何识别可归约串11*5.1.2 规范归约n定义：令G是一个文法，S是文法的开始符号，假定是文法G的

6、一个句型，如果有且则称是句型相对于非终结符A的短语。特别是，如果有A,则称是句型相对于规则A 的直接短语。一个句型的最左直接短语称为该句型的句柄。三个重要概念12*考虑文法G(E)： E T | E+TT F | T*FF (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+i3n短语： i1，i2，i3， i1*i2， i1*i2+i3n直接短语： i1，i2，i3n句柄： i113*n在一个句型对应的语法树中，以某非终结符为根的两代以上的子树的所有末端结点从左到右排列就是相对于该非

7、终结符的一个短语，如果子树只有两代，则该短语就是直接短语。EFFTTTi1+*EFi3i214*n可用句柄来对句子进行归约句型归约规则 abbcde (2) A b aAbcde (3) A Ab aAcde (4) B d aAcBe (1) S aAcBeSbdbaceSABA15*bdbaceSABAdbaceSABAdaceSABaceSABS16*n定义：假定是文法G的一个句子，我们称序列n， n-1，，0是的一个规范归约，如果此序列满足：1 n= ；2 0为文法的开始符号，即0=S；3 对任何i，0 i n， i-1是从i经把句柄替换成为相应产生式左部符号而得到的。

8、17*把上例倒过来写，则得到： S aAcBe aAcde aAbcde abbcde 显然这是一个最右推导。规范归约是关于的一个最右推导的逆过程最左归约规范推导由规范推导推出的句型称为规范句型。18*5.1.3 符号栈的使用和分析树的表示n栈是语法分析的一种基本数据结构。首先将 # 作为栈底符号n考虑文法G(E)： E T | E+TT F | T*FF (E) | i 输入串为i1*i2+i3 ，分析步骤为：19*步骤符号栈输入串动作 0 #i1*i2+i3#预备 1 #i1*i2+i3#进 2 #F*i2+i3#归，用Fi 3 #T*i2+i3#归，用TF 4 #T*i2+i3#

10、算的优先规则：先乘除后加减，同级从左到右n考虑二义文法G(E)： G(E)： E i| E+E|E-E|E*E|E/E|(E)n它的句子有几种不同的规范规约。n归约即计算表达式的值。归约顺序不同，则计算的顺序也不同，结果也不一样。n如果规定算符的优先次序，并按这种规定进行归约，则归约过程是唯一的。23*例如：句子i+i-i*(i+i)Ei()i*EiEE+EEE-ii+EEE24*Ei()i*EiEE+EEE-ii +EEE返回例如：句子i+i-i*(i+i)25*句子i+i-i*(i+i)的归约过程是： (1) i+i-i*(i+i) (2) E+i-i*(i+i) (3) E+E-i

11、*(i+i) (4) E-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) E26*n起决定作用的是相邻的两个算符之间的优先关系。n所谓算符优先分析法就是定义算符之间的某种优先关系，借助于这种关系寻找“可归约串”和进行归约。27*n首先必须定义任何两个可能相继出现的终结符a与b的优先关系三种关系 a b a的优先级高于bn注意：与数学上的 “”、“=” 不同a aa b 并不意味着 b a28*5.2.1 算符优先文法及优先表构造n一个文法，如果它的任一产生式的右部

12、都不含两个相继(并列)的非终结符，即不含如下形式的产生式右部： QR则我们称该文法为算符文法。n约定： a、b代表任意终结符；P、Q、R代表任意非终结符；代表由终结符和非终结符组成的任意序列，包括空字。29*n假定G是一个不含-产生式的算符文法。对于任何一对终结符a、b，我们说： 1. a b当且仅当文法G中含有形如 Pab或PaQb的产生式；n如果一个算符文法G中的任何终结符对(a， b)至多只满足下述三关系之一： a b，a b则称G是一个算符优先文法。2. a b 当且仅当G中含有形如PRb的产生式，而 R a或R aQ。30*n例:考虑下面的文法G(E)：(1) EE+T |

13、T(2) TT*F | F(3) FP F | P(4) P(E) | in由第(4)条规则，有 ( )；n由规则EET和TT*F，有 +；n由(3)FPF 和 F PF，可得 b当且仅当G中含有形如PRb的产生式，而 R a或R aQ。n确定满足关系的所有终结符对：1. a b当且仅当文法G中含有形如 Pab或PaQb的产生式；33*n确定满足关系的所有终结符对：首先需要对G的每个非终结符P构造两个集合 FIRSTVT(P)和LASTVT(P)：a b 当且仅当G中含有形如PRb的产生式，而 R a或R aQ。34*比较比较35*q有了这两个集合之后，就可以通过检查每个产生式的候选式确定满足关系的所有终结符对。假定有个产生式的一个候选形为 aP那么，对任何bFIRSTVT(P)，有 a b。36*n首先讨论构造集合FIRSTVT(P)的算法。n按其定义，可用下面两条规则来构造集合 FIRSTVT(P)：1. 若有产生式Pa或PQa，则 aFIRSTVT(P)；2. 若aFIRSTVT(Q)，且有产生式PQ，则aFIRSTVT(P)。37*n数据结构：布尔数组 FP，a，使得 FP，a为真的条件是，当且仅当aFIRSTVT(P)。开始时，按上述的规则(1)对每个数组元素FP，a赋初值。栈STACK，把所有初值为真的数组元素FP ，a

展开阅读全文

编译5语法分析

最新文档