将含糊不清的语法转换为明确的语法

Question

我不明白一个明确的语法是如何从一个含糊不清的语法中得出的？考虑现场示例:示例.如何得出的语法让我感到困惑.

有人可以指导我吗？

Answer 1

该示例有两个语法:

暧昧:

E ? E + E | E ? E | (E) | a

明确:

E ? E + T | T
T ? T ? F | F
F ? (E) | a

明确的语法来自使用模糊语法中未指定的信息的模糊语法:

• 运算符'*'比运算符'+'更紧密.
• 运算符'*'和'+'都是左关联的.

没有外部信息,就无法进行转换.

有了外部信息,我们可以说:

a * a + b * b

按如下编写分组:

(a * a) + (b * b)

而不是:

a * ((a + b) * b)

第二个假设'+'比'*'更紧密,并且运算符从右到左而不是从左到右绑定.

评论

对于以下示例,关联性如何进入图片:

    S ? aA | Ba
    A ? BA | a
    B ? aB | epsilon

这是一个含糊不清的语法,那么如何将其转换为明确的？

我想知道'epsilon'是ε,空字符串; 让我们两种方式分析语法.

ε是空字符串

B的规则表示B是空字符串或a后跟有效B,这相当于0或更多a的无限长字符串.

A的规则是A是a或B后跟a.所以,一个无限长串的a也可能是A.因此,语法无法选择a的字符串是A还是B.

S的规则没有帮助; S是一个a后跟一个无限长的一串或一个无限长的a后跟一个a.它需要至少一个a,但是从一个向上的任何数量的a都可以,但语法没有依据在左右选择之间做出决定.

所以,这个语法本质上是模棱两可的,在我的估计中,不能明确地说出来; 如果没有我们掌握的其他信息,它肯定不能毫不含糊.

ε不是空字符串

如果ε不是空字符串怎么办？

• B是ε或aε.
• A是a或B后跟a(所以a或aε或aaε).
• 要么:S是a后跟A(因此aa,aaε或aaaε)
• 或者:S是B后跟a(因此εa或aεa).

在这种情况下,语法是明确的(尽管不一定是LR(1)).很明显,很多都取决于评论/问题中"epsilon"的含义.

关联性

我不认为关联性会影响这种语法.它通常与中缀运算符一起发挥作用(例如'a + b'中的'+').

Answer 2

来自维基百科(关于识别歧义语法):

一些模糊的语法可以转换成明确的语法,但是没有一般的程序可以做到这一点,就像没有用于检测模糊语法的算法一样.

为了得出第二个语法,你必须找到一个语法

1. 相当于第一个:两者都生成相同的语言
2. 明确:对于语言的每个句子,解析树都是唯一的