自底向上优先分析法资料.ppt

武汉理工大学计算机科学系陈天煌 第6章 自底向上优先分析法 【预习思考】 ◇ 什么是自底向上语法分析的策略？ ◇ 什么是移进-归约分析？ ◇ 移进-归约过程和自顶向下最右推导有何关系？ ◇ 自下而上语法分析成功的标志是什么？ ◇ 什么是可归约串？ ◇ 移进-归约过程的关键问题是什么？ ◇ 如何确定可归约串？ ◇ 如何决定什么时候移进，什么时候归约？ ◇ 什么是简单优先文法？什么是算符优先文法？ ◇ 简单优先分析是如何识别可归约串的？ ◇ 简单优先分析法的优缺点和局限性有哪些？ 【学习目标】 简单优先分析法是自下而上（自底向上）语法分析的一种，特别适合于表达式的语法分析，由于它的算法简单直观易于理解，因此，也是学习其它自下而上语法分析的基础。 通过本章学习大家应掌握： ◇ 对给定的文法能够判断该文法是否是简单优先文法 ◇ 对给定的简单优先文法能够判断该文法是否是简单优先文法 ◇ 对给定的简单优先文法能构造简单优先关系表，并能利用简单优先优先关系表判断该文法是否是简单优先文法。 ◇ 能应用简单优先分析算法对给定的输入串进行移进-归约分析，在分析的每一步能确定当前应移进还是归约，并能判断所给的输入串是否是该文法的句子。 ◇ 了解简单优先分析法的优缺点和实际应用中的局限性。 【学习指南】 简单优先分析法是自下而上语法分析的一种，它的算法简单、直观、易于理解，所以通常作为学习其它自下而上语法分析的基础。 为学好本章内容，同学们应复习有关语法分析的知识，如：什么是语言、文法、句子、句型、短语、简单短语、句柄、最右推导、规范归约基本概念。 【重难点】 ◇ 通过本章学习后，同学们应该能知道简单优先文法的形式。 ◇ 对一个给定的简单优先文法能构造简单优先关系分析表，并能判别所给文法是否为简单优先文法。 ◇ 分清规范句型的句柄和最左素短语的区别，进而分清算符优先归约和规范归约的区别。 6.1 概述 原理:在采用自左向右扫描，自底向上分析的前提下，该类 分析方法是从输入符号串入手，通过反复查找当前句 　　 型的句柄（最左简单短语），并使用文法的产生式把 句柄归约成相应的非终极符来一步步地进行分析的。 最终把输入串归约成文法的开始符号，表明分析成功。 自底向上分析方法的关键就是要找出当前句型的句柄（或是它的变型），然后根据产生式判别将它归约成什么样的非终极符号。 下面，我们结合具体的实现方法，介绍在分析过程中如何来识别句柄的。我们首先介绍自底向上分析的一般过程，再介绍两种常用的分析技术：简单优先分析法和LR分析方法。 第6章 自底向上优先分析法 一、自底向上分析的一般过程： 先设置一个寄存符号的栈（寄存句型前端），称为分析栈。其作用是用来记录分析的历史和指示分析的下一步动作。 分析进行时，把输入符号一个一个地按扫描顺序移进栈中，当栈顶符号形成一个句柄（即为某产生式的右部）时，就进行一次归约，即把栈顶构成句柄的那个符号子串用相应的产生式左部符号来替换。 接着再检查在栈顶是否又出现了新的句柄，则再进行归约，直至整个输入符号串处理完。 最终如果栈顶为文法的开始符号，则所分析的输入符号串为合法的符号串，报告分析成功。 否则，是不合格的符号串，报告错误。 例：给定文法G(E)：E→E +T |T T→T*F | F F→i| (E)并假定输入串为（i+i)*i，考察自底向上的分析过程。 二、分析过程图表： 为了具体实现上的方便，我们仍统一约定以“#”作为输入串的左右分界符（开始和结束标志）。作为初始状态，先将符号串的开始标志“#”压入分析栈中，作为栈底符号，则分析过程为： 步骤 分析栈 输入串 动作 # (i+i)*i# 移进 #( i+i)*i# 移进 #(i +i)*i# 归约 #(F +i)*i# 归约 #(T +i)*i# 归约 #(E +i)*i# 移进 #(E+ i)*i# 移进 #(E+i )*i# 归约 #(E+F )*i# 归约 E→E +T |T T→T*F | F F→i| (E