歧义和无歧义语法之间的区别

语法是指自然语言中的句法规则。 1956 年，计算机科学家引入了一种用于编写计算机语言的语法数学模型。如果可以使用某种语法导出一种语言的所有字符串，那么就说该语言是从该语法中生成的。上下文无关文法是一种文法。该语法生成上下文无关语言。上下文无关文法可以是歧义的或无歧义的。对于特定的字符串，如果有两个或多个派生词，则称该文法不明确。对于一个特定的字符串，如果只有一个唯一的最左派生，则该文法被称为无歧义文法。

歧义语法，明确语法

什么是歧义语法

如果一个字符串存在两个或多个派生，则称该文法是二义性的。

图 1：歧义语法

假设有如下定义的语法。

G= ({S}, {a+b, +, *}, P, S}. 产生规则如下. S -> S+S | S*S | a | b. 假设要求生成字符串 a+ a*b。

考虑，S -> S+S

用“a”代替最左边的 S 将给出以下结果。

S-> a +S

用 S*S 代替 S 如下。

S-> a + S*S

用“a”代替最左边的 S 将得到以下输出。

S -> a+ a*S

用“b”代替 S 将得到以下输出。

S -> a + a * b

这是生成所需的字符串。

当使用其他产生式规则时，它会给出

S -> S* S

将 S+S 应用到最左边的 S 将给出以下内容。

S -> S+S * S

用‘a’代替最左边的S，

S -> a + S*S

用‘a’代替最左边的S，

S -> a + a * S

用“b”代替 S 将得到以下输出。

S -> a + a*b

同样，它生成了所需的字符串。因此，生成字符串的派生方法不止一种。因此，它是一个二义性语法。

什么是无歧义语法

在二义性文法中，某个字符串具有唯一的最左派生。请参考以下生产规则。

S -> L | a, L -> LS |秒

考虑 S -> L 规则。用 LS 代替 L。

S -> LS

用 S 代替第一个 L。

S -> S S

用“a”代替最左边的 S 将得到以下输出。

S -> 一个 S

用“a”代替 S 将得到以下结果。

S -> a a

因此，字符串具有唯一的最左派生。所以，它是一个明确的语法。