parsing - 具有关联性和自指产生式的 LL 语法

Question

我正在尝试编写一个解析器语法，并且目前有以下 LL 语法（在 Antlr 中）的产生，并且我正在尝试解析一个或多个（数字或字符串），它由正确的关联的“#”分隔。如何修改产品，以便它可以解析一个或多个用“#”分隔的字符串，而不仅仅是一个？

A ::= B
    | Number
    | String

B ::= C "->" A

C ::= Number
    | String

此语法的语言示例：

ABC # 123
123 # ABC
ABC # DEF # 123
ABC # DEF # (123 # 456)
ABC # (DEF # 123) # 456

我尝试使用 EBNF 表格

A ::= B
    | Number
    | String
    | "(" A ")"

B ::= C ("#" A)?

C ::= Number
    | String

但这导致我的语法模棱两可。我将如何解决这种歧义？

score 0 · Accepted Answer

歧义来自这样一个事实，您可以通过两种方式得出 - 直接->或Number- > -> -> （类似地 for ）。显而易见的解决方法是摆脱直接制作：StringANumberABCNumberString

A ::= B
    | "(" A ")"

B ::= C ("#" A)?

C ::= Number
    | String

score 0 · Accepted Answer

我认为你正在寻找的是相当简单的：

A ::= B ( "#" B )*
B ::= Number | String | "(" A ")"

不是 ANTLR 专业人士，我不确定您将如何将其标记#为右关联，但该规则的目的是生成一个Bs 列表，因此您可能可以将它们与语义规则中的右侧相关联。

将带括号的表达式规则放在层次结构的底部很重要（可以这么说）；否则，您将无法解析( first # second ) # third.

2 回答 2