解析语法交替和重复

Question

我能够通过跟随此问题来为我的解析器的语法增加支持（例如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"

...但是语法是模棱两可的。是否有可能使它变得明确，如果有人可以帮助我消除它？

我正在使用柠檬解析器（1）解析器。

Answer 1

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

例如，可以用正则表达式(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

在写语法以解析一种语言时，首先要绘制提议的解析树是有用的。通常，您可以直接从树的形式中编写语法，这表明形式的语法主要是文档工具，因为它以非正式的描述不能清楚地描述语言。使用解析器发电机将语法变成解析器可确保解析器实现所描述的语言。或者，至少这是目标。

Answer 2

这是一个不错的工具，可以在线检查您的语法http://smlweb.cpsc.ucalgary.ca/start.html。它实际上接受您作为有效LALR（1）语法提供的语法。

允许Reapeata A的不同LALR（1）语法是：

S ::= "a" S | "a" | "b" A | "b"
A ::= "a" S .