检查语法歧义 [英] Check grammar ambiguity
问题描述
以下是一段语法的摘录,我正在尝试查看它是否模棱两可.
The following is the extract of a piece of grammar that I'm trying to see whether it is ambiguous or not.
Y->b
Y->Z
Z->bW
W->d
W->ϵ
当我计算第一组语法时,我偶然发现Y的第一个不规则性.
When I compute the first set of the grammar I stumble upon this irregularity for first of Y.
First(Y) = {b,First(Z)}
First of Z = b so I have the set First(Y)={b,b}.
我想知道的是,足以证明给定该证据的语法是否模棱两可.还是应该将其设置为First(Y) = {b}
.
What I want to know is that sufficient enough to prove that the grammar given this evidence is ambigious or not. Or should the set be First(Y) = {b}
.
推荐答案
要证明语法是模棱两可的,您只需要证明至少有两种方法可以得出结果.
To prove a grammar is ambiguous, you simply need to prove that there's at least two different ways to reach a result.
考虑示例并考虑修改,您确实有一个模棱两可的语法,因为您可以通过以下方式导出表达式b
:
Considering your example, and considering your edit, you do have an ambiguous grammar, since you're be able to derive the expression b
by:
Y -> b
Y -> Z
Z -> bW
Y -> d
W -> ϵ
第一种方式:
Y -> b
第二种方式:
Y -> Z
Y -> Z -> bW
Y -> Z -> bW -> bϵ
Y -> Z -> bW -> bϵ -> b
这是一个模棱两可的语法.
This is an ambiguous grammar.
这篇关于检查语法歧义的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!