0

通过遵循这个问题，我能够为我的解析器的语法添加对交替字符（例如ababa或）的支持。baba

我现在希望通过允许重复字符来扩展它。

例如，我希望能够支持abaaabab，aababaaa以及。在我的特殊情况下，只a允许重复，但允许重复的解决方案b也很有用。

鉴于另一个问题的规则：

expr ::= A | B
A ::= "a" B | "a"
B ::= "b" A | "b"

...我尝试将其扩展为支持重复，如下所示：

expr ::= A | B

# support 1 or more "a"
A_one_or_more = A_one_or_more "a" | "a"

A ::= A_one_or_more B | A_one_or_more
B ::= "b" A | "b"

...但是这种语法是模棱两可的。是否有可能明确这一点，如果可以，有人可以帮我消除歧义吗？

我正在使用柠檬解析器，它是一个 LALR(1) 解析器。

4

2 回答 2

1

一般来说，解析的重点是解析; 也就是说，确定输入的句法结构。这与简单地验证输入是否属于一种语言有很大不同。

例如，由 和 的任意重复组成的语言a可以b用正则表达式 来描述(a|b)*，它可以用 BNF 写成

S ::= /* empty */  | S a | S b

但这可能无法捕捉您试图定义的句法结构。另一方面，由于您没有指定该结构，因此很难知道。

这里有更多的可能性，它们构建了不同的解析树：

S ::= E | S E
E ::= A b | E b
A ::= a | A a

S ::= E | S E
E ::= A B
A ::= a | A a
B ::= b | B b

在编写语法来解析语言时，从绘制建议的解析树开始很有用。通常，您可以直接从树的形式编写语法，这表明正式语法主要是一种文档工具，因为它以非正式描述所不能的方式清楚地描述了语言。使用解析器生成器将该语法转换为解析器可确保解析器实现所描述的语言。或者，至少，这是目标。

于 2016-11-22T16:32:04.653 回答
1

这是一个在线检查语法的好工具http://smlweb.cpsc.ucalgary.ca/start.html。它实际上接受您提供的语法作为有效的 LALR(1) 语法。

允许重复 a 的不同 LALR(1) 语法将是：

S ::= "a" S | "a" | "b" A | "b"
A ::= "a" S .
于 2016-11-22T13:00:48.493 回答