交替和重复解析语法

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"

...但是语法有歧义。是否可以将其明确化，如果可以，谁能帮我消除歧义？

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

Answer 1

这是一个很好的在线检查语法的工具http://smlweb.cpsc.ucalgary.ca/start.html. It actually accepts the grammar you provided作为有效的 LALR(1) 语法。

另一种允许重复 a 的 LALR(1) 语法是：

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

Answer 2

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

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

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

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

Parse grammar alternating and repeating