第3章 形式语言与语法分析.pptVIP

编译原理与实现 第二章 自动机与词法分析 3.6 LR（0）语法分析 例：假设有文法G（S）：S→aAc [1]，A→Abb [2]，A→b [3] 解：可按如下步骤构造其可归约前缀图： 第二章 自动机与词法分析 3.6 LR（0）语法分析 可归约前缀图的形式化构造方法 定义： 1．设B→X1X2…Xn [P]是产生式P，则称形如X1X2…Xi?Xi+1…Xn [P]的侯选式为LR（0）项目，其中圆点可在X1之前，也可在Xn之后。 2．称形如X1X2…Xn? [P]的项目为归约项目，其它项目为移进项目； 3．设I为项目集，则定义 为项目集I的闭包集； 4．设I为项目集，X∈VN∪VT，则定义 其中 。 最终构造出的可归约前缀图中的状态结点是由项目所构成的集合。 第二章 自动机与词法分析 3.6 LR（0）语法分析 可归约前缀图的构造算法： 1．若文法开始符Z出现于某产生式右部，则首先定义新的文法开始符Z′，并加入新产生式Z′→Z； 2．生成初始项目集I0： 3．若I是新的项目集，则对每个X∈VN∪VT，构造新的项目集Go（I，X），若两个项目集完全相同，则作为一个项目集； 4．重复3，直至不产生新的项目集为止； 5．可归前缀图的结点由上述项目集组成，并且若有Go（Ii，X）＝Ij，则有 第二章 自动机与词法分析 3.6 LR（0）语法分析 例： 假设有文法G（Z）： Z→aAc [1] A→bB [2] A→ba [3] B→dB [4] B→e [5] 依据上述规则构造的可归约前缀图如右图所示： 第二章 自动机与词法分析 3.3 LL（1）语法分析 非LL（1）文法转换为LL（1）文法 1. 提取公共左因子 设文法中存在如下产生式 A→αβ1|αβ2|……|αβn 提取公共左因子后，文法变为 A→α（β1|β2|……|βn） 引入新的非终结符A′，将文法变为 A→αA′ A′→β1|β2|……|βn 2. 消除直接左递归 假定关于A的全部产生式为： A→Aα1|Aα2|……|Aαm|β1|β2|……|βn 其中αi不以A开头，消除直接左递归后文法被改写为： A→β1A′|β2A′|……|βnA′ A′→α1 A′ |α2 A′ |……|αm A′ |ε 3. 消除间接左递归 对于间接左递归的消除需先将间接左递归变为直接左递归，然后再将直接左递归消除。 第二章 自动机与词法分析 3.3 LL（1）语法分析 非LL（1）文法转换为LL（1）文法 例：若文法G的产生式为： S→aSb S→aS S→ε 将文法变为LL（1）文法。 解： 提取公共左因子，将文法变为： S→aS（b| ε） S→ε 进一步变为： S→aSA A→b A→ε S→ε 第二章 自动机与词法分析 3.3 LL（1）语法分析 非LL（1）文法转换为LL（1）文法 例：设文法G为： A→aB A →Bb B →Ac B→d 将该文法变为LL（1）文法。 解： 用A对应产生式的右部代替B对应产生式中的非终结符A，得到右部中不含A的B的产生式： B→aBc B→Bbc B→d 消除左递归后可得： B →aBc B′|d B′ B′→bcB′|ε 再把原来其余的产生式A→aB，A →Bb加入，最终文法为： A→aB A→Bb B→aBc B′|d B′ B′→bcB′|ε 该文法即为LL（1）文法。 第二章 自动机与词法分析 3.3 LL（1）语法分析 进行LL（1）文法分析时，需同时考虑两个串X1X2……Xn，Y1Y2……Ym，记为（X1X2……Xn，Y1Y2……Ym）。 其中左部是句型的后端部分，由非终极符和终极符以及＃