编译第五章08本cp.ppt

第五章 自下而上 语法分析 语法分析 推导： —自上而下的语法分析过程 —预测分析程序，递归下降分析法（最左推导） —注：要求文法是LL(1)文法 归约： —自下而上的语法分析过程 —简单优先分析法，算符优先分析法、LR分析法 5.1 自下而上分析的基本问题 自下而上的语法分析过程 1.自下而上的语法分析过程思想 —自下而上的语法分析过程是一个最左归约的过程，从输入串开始。朝着文法的开始符号进行归约，直到到达文法的开始符号为止的过程 注意：输入串在这里是指从词法分析器送来的单词符号组成的二元式的有限序列 2.自下而上分析的PDA 一、自下而上的语法分析过程 注：1）初态时栈内仅有栈底符“#”，读头指在最左边的单词符号上 . 2）语法分析程序执行的动作： a)移进：读入一个单词并压入栈内，读头后移； b)归约：检查栈顶若干个符号能否进行归约，若能，就以产生式左部替代该符号串，同时输出产生式编号. c)识别成功：移进—归约的结局是栈内只剩下栈底符号和文法开始符号，读头也指向语句的结束符. d)识别失败. 自下而上分析的中心问题: 怎样判断栈顶的符号串的可归约性，以及如何归约。这是5.2节(算符优先分析)和5.3节(LR分析法)将讨论的问题。 举例 例如：有文法如下： (1) S aAcBe (2) A b (3) A Ab (4) B d 问语句abbcde是否是该文法的合法语句? 5.1.2 规范规约简述 令G是一个文法，S是文法的开始符号，假定αβδ是文法G的一个句型，如果有 S αAδ且A β 则称β是句型αβδ相对于非终结符A的短语。 特别是，如果有 A β 则称β是句型αβδ相对于规则A→β的直接短语，一个句型的最左直接短语称为该句型的句柄。 规范归约是关于α的一个最右推导的逆过程。 因此，规范归约也称最左归约。 S aAcBe aAcde aAbcde abbcde 注：文法是无二义的 句柄与归约 二、自下而上语法分析方法 1.优先分析器（Precedence Parser) 简单优先分析法 算符优先分析法 2.LR分析器 一、简单优先分析法 基本思想 1.确定相邻文法符号之间的优先关系 在句型中，句柄内各相邻符号之间具有相同的优先级，相同优先级用“ ” 由于句柄要先归约,所以规定句柄两端符号的优先级要比位于句柄之外的相邻符号的优先级高,优先级低于表示为“﹤”,优先级高于表示为“ ＞” 某句型中:N1…..Ni-1 Ni …… Nj ＞ Nj+1…..Nn 二、简单优先文法 1.定义：一个文法G，如果它不含e产生式，也不含任何右部相 同的不同产生式，并且它的任何符号对（X，Y） X，Y是终结符或非终结符 ——或者没有关系， ——或者存在优先级相同或低于、高于等关系之一， 则这是一个简单优先文法。 四、简单优先分析法实现过程 PDA读入一个单词后，比较栈顶符号和该单词的优先级，若栈顶符号优先级低于该单词，继续读入；若栈顶符号优先级高于或等于读入符号，则找句柄进行归约，找不到句柄就继续读入，直到最后栈内只剩下开始符号，输入串读到“#”为止，此时识别正确。 5.2 算符优先分析法一、什么是算符优先分析法 1.算符优先分析法： 所谓算符优先分析法是仿效四则运算的计算过程而构造的一种语法分析方法. 2.算符优先分析法的特点： 简单直观，特别方便于表达式分析，易于手工实现，是自下而上的归约过程，但未必按照句柄归约. 3.算符优先分析法的关键： 规定算符（终结符）的优先级及结合性质 例如：8+7-6*5/3的运算 5.2 算符优先分析法 例：表达式文法： E E+E|E-E|E*E|E/E|(E)|i 对这个二义文法可能会有好几个规范推导和归约，真正运算时也有几种不同结果，但若按算符优先顺序和结合规则的规定进行归约，句子的归约过程就是唯一的，运算结果也唯一. 5.2 算符优先分析法 直观算符分析法 5.2 算符优先分析法 直观算符分析法 1）直观算符分析法使用两个工作栈：一个算符栈（OPTR）存放运算符和括号，一个算量栈（OPND)用于存放操作数和运算结果；OPTR的栈顶符号用Q表示，OPND的栈顶符号用p表示 2）初态时，OPND为空，OPTR只有”#“ {SYM入OPND栈；advance；} else if