[编译原理5.3.1-LR分析器.pptVIP

第五章 语法分析 5.1 自下而上分析基本问题 5.2 算符优先分析 5.3 LR分析 5.4 YACC 5.3 LR分析 5.3.1 LR分析器 5.3.2 LR(0)项目集族＆LR(0)分析表的构造 5.3.3 SLR分析表的构造 5.3.4 规范LR分析表的构造 5.3.5 LALR分析表的构造 5.3.6 二义文法的应用 课前思考 自下而上分析是一种___________过程 自下而上分析法的关键问题是在分析过程中___________________。 算符优先分析法如何确定可归约串？ 什么是规范推导和规范归约？ 它们之间有什么关系？ 规范归约过程是当分析的栈顶符号串形成_______时就采取归约动作 LR(K) L : 自左向右扫描 R : 逆向完成最右推导 (规范归约) K : 向右查看输入串符号的个数 (K省略时, 表示K等于1) 四种LR分析器 LR(0) SLR(1) LR(1) LALR(1) LR方法的基本思想 LR方法的关键: 确定句柄 历史: 已移进和归约出的整个符号串 展望: 根据所用的产生式推测未来可能 碰到的输入符号 现实: 当前的输入符号 LR分析器的每一步工作都是由栈顶状态和 现行输入符号所唯一决定的。 一个LR分析器实质上是一个DFA 5.3.1 LR分析器 P100 例： p101 G: (1) E ? E+T (2) E ? T (3) T ? T*F (4) T ? F (5) F ? (E) (6) F ? i 将LR分析器的工作过程看成三元式的变化过程 状态栈 符号栈 输入串 分析开始时的初始三元式为: (s0 , ＃， ala2...an＃） 分析过程每步的结果可表示为 (s0s1...sm， ＃X1X2...Xm， aiai+1…an＃） 分析器的下一步动作由sm和 ai所唯一决定 Action[sm,ai]: 4种可能动作 (1) 移进 – sj (2) 归约 – rm (3) 接受 – acc (4) 报错 – 空白 / ‘出错’ / ‘error’ (1) 移进 – sj push s ; push ai; (2) 归约 - rm pop 文法符号栈 r次 pop 状态栈 r次 push A 查表 s = GOTO[sm-r , A] push s 补充：LR分析算法 * 状态栈中放入状态0 ; 文法符号栈中放入＃ ip指向输入串w的第一个符号 Sm为栈顶状态 ; a是ip指向的符号 Repeat … //见下页 end . Repeat if ACTION[Sm,a]=Sj begin PUSH j, a 　　　 ip 前进  end else if ACTION[Sm,a]=rj // A→β begin pop |β| 项 //当前栈顶状态为Sk push GOTO[Sk, A] , A end else if ACTION[Sm, a]=acc return (成功） else error end . LR分析器小结 总控程序 - 对所有的LR分析器都是相同的。 根据当前栈顶的状态号和输入符号，去查LR分析表，决定采取什么动作，移进还是归约等。 分析表 - 规定了动作和状态的转换。 不同的文法，分析表将不同 同一个文法采用不同的LR分析器，分析表也将不同。 分析栈 - 文法符号栈和状态栈 它们在移进和归约的过程中是同步的，栈中元素一样多,栈指针用同一个。 在一般的移进－归约过程中也有文法符号栈，但没有状态栈。 几个概念 LR文法: 对于一个文法，如果能够构造一张分析表，使得它的每个入口均是唯一确定的，则我们将把这个文法称为LR文法。 LR(k)文法: 一个文法如果能用一个每步最多向前检查k个输入符号的LR分析器进行分析，则这个文法就称为LR(k)文法。 非LR结构 * * Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. Evaluation only