在解析 LiveScript 对象定义时避免左递归

Question

我正在为 LiveScript 语言开发解析器，但在同时解析对象属性定义形式 — key: value 和 (+|-)key 时遇到了问题。例如：

prop: "val"
+boolProp
-boolProp
prop2: val2

我有 key: value 表格来处理这个：

Expression ::= TestExpression
    | ParenExpression
    | OpExpression
    | ObjDefExpression
    | PropDefExpression
    | LiteralExpression
    | ReferenceExpression

PropDefExpression ::= Expression COLON Expression

ObjDefExpression ::= PropDefExpression (NEWLINE PropDefExpression)*

// ... other expressions

但是我尝试将 ("+"|"-") IDENTIFIER 添加到 PropDefExpression 或 ObjDefExpression，但我得到有关使用左递归的错误。执行此操作的（正确）方法是什么？

Answer 1

您发布的语法片段已经是左递归的，即甚至没有添加 (+|-)boolprop，非终结符 'Expression' 派生出一种形式，其中 'Expression' 重新出现在最左边符号：

Expression -> PropDefExpression -> Expression COLON Expression

而且它不仅是左递归的，而且是模棱两可的。例如

Expression COLON Expression COLON Expression

可以用两种不同的方式推导出来（大致上，左结合与右结合）。

您可以通过在冒号左侧使用更受限制的内容来消除这两个问题，例如：

PropDefExpression ::= Identifier COLON Expression

此外，还有另一个歧义：Expression 以两种不同的方式派生 PropDefExpression，直接派生和通过 ObjDefExpression 派生。我的猜测是，您可以放弃直接推导。

一旦你处理了这些事情，在我看来你应该能够添加 (+|-)boolprop 而不会出错（除非它与你没有的其他类型的表达式之一冲突显示).

请注意，查看 http://livescript.net 中的示例，我怀疑您能否用常规语法捕捉其中的多少。但如果你只是想要一个子集，你可能没问题。

Answer 2

我不知道这会有多大帮助，因为我对 GrammarKit 一无所知，对您尝试解析的语言也不了解。

不过，在我看来

PropDefExpression ::= Expression COLON Expression

不是很准确，当您添加布尔属性产生式时它会产生歧义，因为表达式可能以一元 - 运算符开头。但是，在实际语法中，属性不能以任意表达式开头。有两种key-属性定义：

name : expression
parenthesized_expression : expression

(也就是说，表达式需要以()开头。

这意味着布尔值属性定义，以 + 或 - 开头的第一个标记是可识别的，它正是成功进行递归下降解析所需的条件。还有其他几种属性定义语法，包括名称和 parenthesized_expressions 后面没有 :

这很容易用 LR(1) 解析器解析，就像 Jison 生成的解析器一样，但是要用递归下降解析器解析它，你需要左因子。（顺便说一下，GrammarKit 可能会为你做这件事。）基本上，你需要类似的东西（这还不完整）：

PropertyDefinition ::= PropertyPrefix PropertySuffix? | BooleanProperty
PropertyPrefix ::= NAME | ParenthesizedExpression
PropertySuffix ::= COLON Expression | DOT NAME

在解析 LiveScript 对象定义时避免左递归

Avoiding left recursion in parsing LiveScript object definitions

recursion

context-free-grammar

ebnf

livescript

grammar-kit