什么是歧义语法？

• Z时代
• 2024-01-10
• 分类：综合

对相似句子进行多个最左推导（或最右推导）的语法称为歧义语法。

示例- 验证以下语法是否模棱两可。

E → E+E|E $\ast$E|id

解决方案

对于字符串 id + id * id，存在两个解析树。

E ⇒ ^lm  $\下划线{E}$+E

 ⇒ id+ $\下划线{E}$

⇒ id+$\下划线{E}$$\ast$E

⇒ id+id $\ast$$\下划线{E}$

⇒ id+id $\ast$id

E ⇒ ^lm  $\下划线{E}$$\ast$E

⇒ $\下划线{E}$+E $\ast$E

⇒ id+ $\下划线{E}$$\ast$E

⇒ id+id $\ast$$\下划线{E}$

⇒ id+id $\ast$id

因此，使用两个不同的最左侧推导生成相同的字符串。每个都有不同的解析树。

∴ 字符串 id + id * id 存在两种不同的解析树。

∴ 语法是模棱两可的。

歧义到明确语法的转换

在其右侧包含多次出现的给定非终结符的产生式是模棱两可的产生式。

示例- E → $\underline{E}$* $\underline{E}$

它在 RHS 上包含两个 E

它可以通过引入一个新的非终结符将这些非终结符中的大部分向右移动到解析树的下方，将这些类型的歧义产生式转换为明确的产生式。

Example1 - 考虑语法

E → E+E|E $\ast$E|(E)| ID

将此歧义语法转换为明确语法。

解决方案

Step1 - 介绍一个不能进一步添加两个术语的非终结 T（术语）。

E → E+T | T
T → E * E | (E) |id

Step2 - 因为我们有生产 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 语句。

在上面的 Parse 树中，else 属于第二个 if。

在上面的 Parse 树中，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>

以上是 什么是歧义语法？ 的全部内容， 来源链接： utcz.com/z/363293.html