《编译原理自底向上的语法分析》由会员分享，可在线阅读，更多相关《编译原理自底向上的语法分析（20页珍藏版）》请在金锄头文库上搜索。
1、语法分析部分知识关系图开发语法分析程序语法定义基于上下文无关文法使用实现自顶向下自底向上第五章 自底向上的语法分析l5.1 自底向上的语法分析方法概述l5.2 LR(0)分析的有限自动机l5.3 LR(0) 分析l5.4 SLR(1) 分析l5.5 LR(1) 分析l5.6 LALR(1) 分析l5.7 LALR(1) 语法分析器的自动生成器 (YACC)5.1 自底向上语法分析概述l自顶向下语法分析回顾l自底向上语法分析的例子l自底向上语法分析的主要思想l自底向上语法分析的关键问题l一些相关概念自顶向下分析例P: (1) Z aBeA (2) A Bc (3) B d (4) B bB (5
2、) B a b e c自顶向下分析过程是从文法开始符出发，为所给输入串构造 最左推导的过程。句型输入动作Zabec推导(1)abecaBeA匹配(a)becBeA推导(4)becbBeA匹配(b) ecBeA推导(5) eceA匹配(e) cA推导(2) cBc推导(5)匹配(c)c c 成功自底向上语法分析的例子P: (1) Z ABb (2) A a (3) A b (4) B b (5) B c (6) B bBa b c b输入符号栈动作abcb移入abcb归约(2)Abcb移入Abcb移入 Abcb归约(5) AbBb归约(6) ABb移入归约(1)ABbZ成功自底向上分析过程是从所
3、给输入串出发，对其进行最左归约 的过程。自底向上归约的过程也是自底向上构建语法树的过程a b c bBBZ归约过程Z rm ABb rm AbBb rm Abcbrm abcbAabcb - Abcb - AbBb - ABb - Z自底向上分析中归约过程的逆过程就是该句子 的最右推导;5.1 自底向上语法分析方法概述l主要思想:从输入串出发;尽可能地找到可归约子串并将其归约成一个非终极符;直到归约成文法的开始符或发现语法错误;l分析动作:移入(shift),归约(reduce)l包含以下方法: LR 类的方法; 简单优先法; 算符优先法l关键问题:什么时候进行归约，按照哪条产生式进行归约;一
4、些相关概念 l短语 一个句型形如, 如果存在一个句型A,而且 A+, 则称为句型的短语; 例如句型AbBb，则bB,AbBb是它的短语，因为l存在句型ABb，ABb AbBb， = A， = b；l存在句型Z，Z ABb AbBb ， = ， = ；l简单短语 一个句型形如, 如果存在一个句型A,而且 A , 则称为句型的简单短语; 例如句型AbBb，bB是它的简单短语，AbBb不是 它的简单短语(1) Z ABb (2) A a (3) A b (4) B d (5) B c (6) B bB一些相关概念l句柄:一个句型的简单短语可能有多个，称最 左简单短语为句柄(handler);例如：句
5、型abBb，简单短语有两个：a,bBlZ ABb aBb abBb最左简单短语a是句柄l句柄的唯一性: 如果一个CFG无二义性,则它的任意一个句型都 有唯一的句柄;短语、简单短语、句柄的例子P: (1) E T (2) E E + T (3) T F (4) T T * F (5) F (E) (6) F i (7) F n句型: T+ (E+T)*i简单短语: T, E+T, i句柄: T通过为所给句型建立语法分析树，可以很容易地识别出该句 型的所有短语、简单短语和句柄。句型的一个推导: (该句型没有最右推导) E E + T E + T*FE+T*i E+F*i E+(E)*i E+(E+
6、T)*i T+(E+T)*i 短语: T +(E+T)*i, T, E+T, i, (E+T),(E+T)*i由语法分析树识别短语、简单短语和 句柄EE+TTT* FF（ E ）E+ Ti语法分析树的叶子节点构成句型: T+ (E+T)*i每棵子树的叶子节点构成短语： T+ (E+T)*i 、T、(E+T)*i、(E+T)、E+T、i每棵简单子树(只有一层的子树)的叶子节 点构成简单短语：T、E+T、i最左简单子树的叶子节点构成句柄： T一些相关概念l自顶向下的语法分析方法中曾介绍过：l推导：对句型中的非终极符用产生式右部替换l规范推导：一个句型的最右推导称为该句型的 规范推导;l规范句型(右
7、句型)：从开始符通过规范推导得到 的句型;推导的逆过程称为归约规范推导的逆过程称为规范归约(最左归约 )规范归约过程中产生的句型仍是规范句型 规范归约的过程也是对规范句型的最左简 单短语(句柄)进行归约的过程一些相关概念Z ABb 规范前缀为 AB, ABdZ + Acb 规范前缀为 A, Ac, Acbl规范前缀:一个规范句型的一个前缀称为规范前缀, 如 果该前缀后面的符号串不包含非终极符;规范句型规范前缀或者终极符串一些相关概念Z ABb 规范前缀为 AB, ABb规范活前缀: AB(不包含简单短语) , ABb(包含一个简单短语且在最后) l规范活前缀:满足如下条件之一的规范前缀称为规范
8、 活前缀: 该规范前缀不包含简单短语; 该规范前缀只包含一个简单短语,而且是在该规范前缀的最 后(这个简单短语就是句柄);Z + abcb 规范前缀为 a, ab, abc, abcb 规范活前缀: a (包含一个简单短语且在最后) abc是不是规范活前缀？(不是，包含两个简单短语a和c)自底向上语法分析的例子P: (1) Z ABb (2) A a (3) A b (4) B b (5) B c (6) B bBa b c b输入符号栈动作abcb移入abcb归约(2)Abcb移入Abcb移入 Abcb归约(5) AbBb归约(6) ABb移入归约(1)ABbZ成功自底向上分析过程是从所给输
9、入串出发，对其进行最左归约 的过程。规范活前缀或者 终极符串规范句型一些相关概念l规范活前缀决定分析动作移入:规范活前缀不包含简单短语;移入型规范活前缀归约:规范活前缀只包含一个简单短语,而且是在该规范 活前缀的最后;可归约规范活前缀 ：归约规范活前缀Z ABb 规范前缀为 AB, ABb规范活前缀: AB(不包含简单短语) - 移入型规范活前缀ABb(包含一个简单短语) - 归约规范活前缀自底向上分析知识关系图规范归约推导(*)最右推导句型(S *) 短语(A +)简单短语(A )句柄(最左)规范推导规范句型(S rm*)特例特例规范前缀规范活前缀包含0 或1个归约规范活前缀应用互逆最右包
10、含1个自底向上 分析5.1 自底向上语法分析方法概述lLR 方法主要思想lL表示从左至右读入输入串;lR表示构造一个最右推导的逆过程，即每次找到句柄 (归约规范活前缀)来进行归约;l归约直到得到开始符或报告语法错误; 关键问题: 对于一个CFG, 如何判定归约规范活 前缀?l构造一个判定归约规范活前缀的自动机 - LR自动机l由LR自动机构造LR分析表指导LR分析LR 分析机制分析栈输入#aLR驱动程序:- shift(移入) :移入型规范活前缀- reduce(归约):可归约规范活前缀LR分析表规范 活前 缀5.1 自底向上语法分析方法概述lLR 方法不同的 LR 方法lLR(0)lSLR(1)lLR(1)lLALR(1)不同的LR方法对CFG的要求不一样, 能够分析的 CFG多少也不一样, LR(0) SLR(1) LALR(1) LR(1)
