编译原理二义性

‘壹’ 如何消除二义性 编译原理

1、需要在语法设计时就要考虑了，即使是C/C++也存在二义性、不确定性的语法，对于这种情况，各编译器考虑的不同的方案，主要还是看你如何进行文法分析，可以选一种方便分析的一种去做。
2、要判断二义性的存在，可以尝试使用不同的优先顺序解释
假如解释出现歧义，那么一定存在二义性的语法（如经典的++运算）
3、要消除二义性，最简单可行的就是定义优先级，不过不一定适合所有情况。

‘贰’ 编译原理 正则语言 二义文法 急~

这个没有一个好老师，自己咬文嚼字看懂是很累的
二义性文法

【定义】 若文法中存在这样的句型，它具有两棵不同的语法树，则称该文法是二义性文法。

二义性文法会引起歧义，应尽量避免之！
G(E)：E -> E+E | E*E | (E) | i
这两种展开
E E
E + E E * E
i E * E E + E i
i i i i

都可以表示i+i*i

所以;文法具有二义性。

‘叁’ 编译原理文法定型规则

编译原理中的文法定型规则是指将任意上下文无关文法（Context-Free Grammar, CFG）转化为某个特定形式的上下文无关文法的规则。这个特定形式的上下文无关文法通常是Chomsky范式或Greibach范式。
以下是文法定型规则的具体步骤：
1. 消除文法中的ε产生式（epsilon-proction），即产生空串的产生式。
2. 消除文法中的单一产生式（unit-proction），即右侧只有一个非终结符的产生式。
3. 消除文法中的左递归产生式（left-recursive proction）。
4. 将文法转化为无二义性的文法。
上述步骤的具体实现方法如下：
1. 消除文法中的ε产生式：
1. 对于所有含有ε产生式的非终结符，将其ε产生式删除。
2. 对于所有产生式右侧含有已删除非终结符的产生式，将其右侧的已删除非终结符替换为ε。
3. 重复执行上述步骤，直到所有含有ε的产生式都被消除为止。
2. 消除文法中的单一产生式：
1. 对于所有单一产生式A → B，将其删除。
2. 对于所有产生式右侧含有被删除产生式的非终结符的产生式，将其替换为被删除产生式的右侧符号B。
3. 重复执行上述步骤，直到所有单一产生式都被消除为止。
3. 消除文法中的左递归产生式：
1. 对于每个非终结符A，将所有形如A → Aα的产生式改为A → β1A'、A' → β2A' | ε的形式。
2. 其中，β1是所有右侧不含有A的A产生式的右侧符号串，β2是所有右侧含有A的A产生式的右侧符号串，α是所有产生式右侧不含有A的符号串。
3. 重复执行上述步骤，直到所有左递归产生式都被消除为止。
4. 将文法转化为无二义性的文法：
1. 消除文法中的二义性产生式，即产生式右侧存在两个或以上的不同符号串。
2. 引入新的非终结符，将二义性产生式拆分为多个不同的产生式。
3. 对于所有产生式右侧含有多个符号的产生式，使用括号或其他符号进行明确区分。
4. 重复执行上述步骤，直到文法不存在二义性为止。
以上是文法定型规则的具体步骤和实现方法。通过执行这些步骤，可以将任意上下文无关文法转化为某个特定形式的上下文无关文法，从而方便进行语法分析和编译。

‘肆’ 编译原理笔记9：语法分析树、语法树、二义性的消除

语法分析树和语法树不是一种东西 。习惯上，我们把前者叫做“具体语法树”，其能够体现推导的过程；后者叫做“抽象语法树”，其不体现过程，只关心最后的结果。

语法分析树是语言推导过程的图形化表示方法。这种表示方法反映了语言的实质以及语言的推导过程。

定义：对于 CFG G 的句型，分析树被定义为具有下述性质的一棵树：

推导，有最左推导和最右推导，这两种推导方式在推导过程中的分析树可能不同，但因最终得到的句子是相同的，所以最终的分析树是一样的。

分析树能反映句型的推导过程，也能反映句型的结构。然而实际上，我们往往不关心推导的过程，而只关心推导的结果。因此，我们要对 分析树 进行改造，得到 语法树 。语法树中全是终结符，没有非终结符。而且语法树中没有括号

定义：

说白了，语法树这玩意，就一句话： 叶子全是操作数，内部全是操作符 ，树里没有非终结符也不能有括号。

语法树要表达的东西，是操作符（运算）作用于操作数（运算对象）

举俩例子吧：

【例】： -(id+id) 的语法树：

【例】：-id+id 的语法树：

显然，我们从上面这两个语法树中，直接就能观察出来它们的运算顺序。

【例】：句型 if C then s1 else s2

二义性问题：一个句子可能对应多于一棵语法树。

【例】： 设文法 G： E → E+E | E*E | (E) | -E | id

则，句子 id+id*id、id+id+id 可能的分析树有：

在该例中，虽然 id+id+id 的 “+” 的结合性无论左右都不会影响结果。但万一，万一“+”的含义变成了“减法”，那么左结合和右结合就会引起很大的问题了。

我们在这里讲的“二义性”的“义”并非语义——我们现在在学习的内容是“语法分析器”，尚未到需要研究语言背后含义的阶段。

我们现在讲的“二义性”指的是一个句子对应多种分析树。

二义性的体现，是文法对同一句子有不止一棵分析树。这种问题由【句子产生过程中的某些推导有多于一种选择】引起。悬空 else 问题就可以很好地体现这种【超过一种选择】带来的二义性问题，示例如下。

看下面这么个例子。。

（其实，我感觉这个其实比较像是“说话大喘气”带来的理解歧义问题。。。）上面的产生式中并没体现出来该咋算分一块，所以两种完全不同的句子结构都是合法的。

二义性问题是有救的，大概有以下这三种办法：

这些办法的核心，其实都是将优先级和结合性说明白。

核心：把优先级和结合性说明白

既然要说明白，那就不能让一个非终结符可以直接在当次推导中能推出会带来优先级和结合性歧义的东西。（对分析树的一个内部节点，不会有出现在其下面的分支是相同的非终结符的情况。如果有得选，那就有得歧义了。没得选才能确定地一路走到黑）

改写为非二义文法的二义文法大概有下面这几个特点：

改写的关键步骤：

【例】改写下面的二义文法为非二义文法。图右侧是要达成的优先级和结合性

改写的核心其实就两句话：

所以能够得到非终结符与运算的对应关系（因为不同的运算有不同的优先级，我们想要引入多个优先级就要引入多个新的非终结符。这样每个非终结符就可以负责一个优先级的运算符号，也就是说新的非终结符是与运算有关系的了。因此这里搞出来了“对应关系”四个字）如下：

优先级由低到高分别是 +、 、-，而距离开始符号越近，优先级越低。因此在这里的排序也可以+ -顺序。每个符号对应一层的非终结符。根据所需要的结合性，则可确定是左递归还是右递归，以确定新的产生式长什么样子

【例】：规定优先级和结合性，写出改写的非二义文法

我们已经掌握了一种叫做【改写】的工具，能让我们消除二义性。接下来我们就要用这个工具来尝试搞搞悬空 else 问题！

悬空 else 问题出现的原因是 then 数量多于 else，让 else 有多个可以结合的 then。在二义文法中，由于选哪两个 then、else 配对都可以，故会引起出现二义的情况。在这里，我们规定 else 右结合，即与左边最靠近的 then 结合。

为改写此文法，可以将 S 分为完全匹配（MS）和不完全匹配（UMS）两类。在 MS 中体现 then、else 个数相等即匹配且右结合；在UMS 中 then、else 不匹配，体现 else 右结合。

【例】：用改写后的文法写一个条件语句

经过检查，无法再根据文法写出其他分析树，故已经消除了二义性

虽然二义文法会导致二义性，但是其并非一无是处。其有两个显着的优点：

在 Yacc 中，我们可以直接指定优先级、结合性而无需自己重写文法。

left 表示左结合，right 表示右结合。越往下的算符优先级越高。

嗯就这么简单。。。

我们其实可以把语言本身定义成没有优先级和结合性的。。然后所有的优先、结合都交由括号进行控制，哪个先算就加括号。把一个过程的结束用明确的标志标记出来。

比如在 Ada 中：

在 Pascal 中，给表达式加括号：

‘伍’ 编译原理中文法二义性问题

二义性文法

【定义】 若文法中存在这样的句型，它具有两棵不同的语法树，则称该文法是二义性文法。

二义性文法会引起歧义，应尽量避免之！

E E

E + E E * E

i E * E E + E i

i i i i

都可以表示i+i*i

所以G(E)：E -> E+E | E*E | (E) | i ;文法具有二义性。

文法二义性的消除：

【方法1】不改变文法的原有规则,加进一些非形式规定。

加进运算符的优先顺序和结合规则对G(E)，规定*优于+，*和+服从左结合

【方法2】构造一个等价的无二义性文法，将排除 二义性的规则合并到文法中

G(E) -> G´(E) : E -> E+T | T T -> T*F | F F -> (E) | i ;

‘陆’ 如何由文法推导语法树(编译原理)

语法树是一种用于表示句型生成过程的结构，特别是在上下文无关文法中非常有用。它能够帮助我们理解句型是如何通过文法规则逐步构建起来的。在编译原理课程中，构建语法树是语法分析的一项重要任务。为了完成这项任务，我们通常需要应用各种语法分析方法，这些方法在学习过程中会逐渐掌握。

在学习这些方法之前，我们只能依赖直觉和经验，通过猜测和拼凑的方式尝试构建句型的语法树。由于这种方法依赖于经验和直觉，因此适用于较为简单的句型。通过反复练习，可以逐渐积累一些构建语法树的技巧，这些技巧主要是自顶向下的语法分析中的基本原则。

值得注意的是，对于同一文法，可能存在多个结构不同的语法树。如果一个文法能够产生多个不同的语法树，这个文法就被称为二义性文法。二义性文法的存在使得句型的解析变得复杂，因为同一个句型可能存在多种解释。

然而，如果文法是非二义性的，那么对于任何给定的句型，其对应的语法树都是唯一的。这意味着，只要遵循文法中的规则，我们就能确定句型的正确结构。这种特性对于编译器的设计和实现非常重要，因为它确保了解析过程的确定性和唯一性。

总之，理解如何构建语法树以及文法的二义性问题，对于深入学习编译原理至关重要。通过掌握各种语法分析方法，我们可以更准确地解析句型，从而为后续的编译工作奠定坚实的基础。

‘柒’ 【编译原理】第二章：语言和文法

上述文法 表示，该文法由终结符集合 ，非终结符集合 ，产生式集合 ，以及开始符号 构成。
而产生式 表示，一个表达式（Expression） ，可以由一个标识符（Identifier） 、或者两个表达式由加号 或乘号 连接、或者另一个表达式用括号包裹（ ）构成。

约定 ：在不引起歧义的情况下，可以只写产生式。如以上文法可以简写为：

产生式

可以简写为：

如上例中，

可以简写为：

给定文法 ，如果有 ，那么可以将符号串 重写 为 ，记作 ，这个过程称为 推导 。
如上例中， 可以推导出 或 或 等等。

如果 ，
可以记作 ，则称为 经过n步推导出 ，记作 。

推导的反过程称为 归约 。

如果 ，则称 是 的一个 句型（sentential form ）。

由文法 的开始符号 推导出的所有句子构成的集合称为 文法G生成的语言 ，记作 。
即：

例
文法

表示什么呢？
代表小写字母；
代表数字；
表示若干个字母和数字构成的字符串；
说明 是一个字母、或者是字母开头的字符串。
那么这个文法表示的即是，以字母开头的、非空的字符串，即标识符的构成方式。

并、连接、幂、克林闭包、正闭包。
如上例表示为：

中必须包含一个 非终结符 。

产生式一般形式：
即上式中只有当上下文满足 与 时，才能进行从 到 的推导。

上下文有关文法不包含空产生式（ ）。

产生式的一般形式：
即产生式左边都是非终结符。

右线性文法 ：
左线性文法 ：
以上都成为正则文法。
即产生式的右侧只能有一个终结符，且所有终结符只能在同一侧。

例：（右线性文法）

以上文法满足右线性文法。
以上文法生成一个以字母开头的字母数字串（标识符）。
以上文法等价于 上下文无关文法 ：

正则文法能描述程序设计语言中的多数单词。

正则文法能描述程序设计语言中的多数单词，但不能表示句子构造，所以用到最多的是CFG。

根节点 表示文法开始符号S；
内部节点 表示对产生式 的应用；该节点的标号是产生式左部，子节点从左到右表示了产生式的右部；
叶节点 （又称边缘）既可以是非终结符也可以是终结符。

给定一个句型，其分析树的每一棵子树的边缘称为该句型的一个 短语 。
如果子树高度为2，那么这棵子树的边缘称为该句型的一个 直接短语 。

直接短语一定是某产生式的右部，但反之不一定。

如果一个文法可以为某个句子生成 多棵分析树 ，则称这个文法是 二义性的 。

二义性原因：多个if只有一个else；
消岐规则：每个else只与最近的if匹配。

‘捌’ 【编译原理】自顶向下LL（1）分析中，消除左递归和提取左因子的目的是什么

提取左因子---避免程序回溯；
消除左递归---消除死循环。