数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学什么是二义性文法？
产生相同句子的左推导（或右推导）不止一种的文法称为二义性文法。
示例 − 验证以下文法是否二义性。
E → E+E|E $\ast$ E|id
解答
对于字符串 id + id * id，存在两棵不同的语法树。
E ⇒lm $\underline{E}$+E
⇒ id+ $\underline{E}$
⇒ id+$\underline{E}$ $\ast$ E
⇒ id+id $\ast$ $\underline{E}$
⇒ id+id $\ast$ id
E ⇒lm $\underline{E}$ $\ast$ E
⇒ $\underline{E}$+E $\ast$ E
⇒ id+ $\underline{E}$ $\ast$ E
⇒ id+id $\ast$ $\underline{E}$
⇒ id+id $\ast$ id
因此，同一个字符串使用了两种不同的左推导生成。每种推导都有不同的语法树。
∴ 字符串 id + id * id 存在两棵不同的语法树。
∴ 文法是二义性的。
将二义性文法转换为非二义性文法
在其右部包含一个给定非终结符多次出现的产生式是二义性产生式。
示例 − E → $\underline{E}$ * $\underline{E}$
它在右部包含两个 E。
可以通过引入一个新的非终结符将这些非终结符中最右边的非终结符移动到语法树的更下方，从而将这些类型的二义性产生式转换为非二义性产生式。
示例1 − 考虑以下文法
E → E+E|E $\ast$ E|(E)| id
将这个二义性文法转换为非二义性文法。
解答
步骤1 − 引入一个非终结符 T（项），它不能再进一步分解为两个项的加法。
E → E+T | T T → E * E | (E) |id
步骤2 − 由于我们有产生式 E → T。用 T 代替 E 得到
T→T∗T
引入另一个非终结符 F（因子），它不能进一步分解，也不能是两个数字的乘积。
用 F 代替 T 得到，
T → T * F | F F → (E) | id
∴ 非二义性文法将是
E → E+T | T T → T * F | F F → (E) | id
示例2 − 证明以下文法对于字符串 if c then if c2 then s1 else s2 是二义性的。
<statement> →if<cond> then<statement> | if<cond> then<statement> else<statement>
|另一个语句
将其转换为非二义性文法。
解答
给定的文法是二义性的，因为对于同一个字符串存在两棵不同的语法树，因为 else 条件可以属于任何 if 语句。
在上图的语法树中，else 属于第二个 if。
在上图的语法树中，else 属于第一个 if。
转换为非二义性文法
非二义性文法将是 −
<statement>→<match−statement>|<Unmatch−statement> <match−statement>→if<cond>then<match−statement>else <match−statement>| other−statement <Unmatch−statement>→if<cond>then<statement>| if<cond>then <match−statement>else<Unmatch Statement>
17K+ 次浏览
