[编译原理第3讲.上..ppt

CompilerPrinciples 第三讲 语法分析 语法分析概述 自上而下语法分析 自下而上语法分析 基本思想：从文法的开始符号出发，推 导出句子 回溯→避免条件 First(x), Follow(u) 基本问题 无限循环→消除左递归 递归子程序法 分析方法 LL(1)分析法 基本思想：从输入串开始逐步归约 基本问题：归约的问题 简单优先 优先分析法 算符优先 优先函数的构造 分析方法 规范句型活前缀 基础知识 LR(0)项目及项目集 LR(1)项目及项目集 LR分析法 LR分析器 分析栈、分析表 分析方法 LR分析表的构造 二义性文法的分析 实现技术——移进归约 §1.语法分析概述 一、语法分析器的功能 1.语法分析器在编译程序中的地位： 2.功能：在单词符号的基础上，分析给定语言的句子（程序）的语法结构，看其是否符合语法规则。 二、分析方法 1.针对程序的单词符号串构造语法树——依据程序语言的语法规则，即文法描述。 ☉若能构造出一棵语法树则正确，否则程 序有错 2.根据语法树的建立方法，分为两种： ●自上而下分析法：从文法开始符号出 发，自上而下地构造语法树； ●自下而上分析法：从单词符号串形式的 源程序开始，自下而上地构造语法树； §2.自上而下的语法分析 一、方法、问题及其解决 1.方法概述：对任意输入的（单词符号）串，试着从开始符号出发，自上而下地建立起一棵语法分析树，使得该树的叶结点自左而右地排列起来，刚好就是所给的输入串。 ☉显然，这种建立语法树的过程应遵照某种规范——通常应与最左推导相对应，即自左向右进行匹配。 例 G[S]: S→aAb 输入串 a*b A→**∣* 2.问题： ·这是一种自上而下的试探法，有时免不了要走回头路——回溯。 ·自左向右建立子树—左递归文法会造成死循环。 3.解决办法： (1)左递归问题：改写产生式，变左递归为右递归。 ①直接左递归：直接见诸于产生式的左递归，如 P→Pα,P∈VN, α∈(VT∪VN)* 这种直接左递归可以通过直接扫描产生式发现，也容易解决——改写产生式即可。 如： P→Pα1∣Pα2∣…∣Pαm∣β1∣β2∣…∣βn 其中P∈VN,αi,βj ∈(VT∪VN)* 且α≠?, β不以P开头 改写成 P→β1 P ∣β2 P ∣…∣βn P P →α1 P ∣α2 P ∣…∣αm P∣ε 例：文法G[E]: E →E+T∣T 改写成 E→TE E→+TE∣ε T →T*F ∣ F 改写成 T→FT T→*FT∣ε ②消除左递归：通过改写产生式我们可以消除直接左递归，但不能完全消除左递归，因为还存在着间接左递归的问题。 例如文法G[P]: P→Qc∣c Q→Rb∣b R→Pa∣a 表面上并看不出它的左递归性，但是仔细观察时不难发现P,Q,R都是左递归的，因为 P? Qc? Rbc? Pabc，即P ?+Pabc； Q ?+Qcab,R ?+Rbca亦然。 对这种左递归的消除就稍微麻烦一些。首先，从产生式中找这种形式的左递归。其思想也就是通过推导来寻找左递归、并进一步修改产生式。为此