0

我正在开发 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

但是，无论我尝试添加("+"|"-") IDENTIFIERor PropDefExpression，ObjDefExpression我都会收到有关使用左递归的错误。这样做的（正确）方法是什么？

4

2 回答 2

0

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

Expression -> PropDefExpression -> Expression COLON Expression

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

Expression COLON Expression COLON Expression

可以通过两种不同的方式派生（粗略地说，左关联与右关联）。

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

PropDefExpression ::= Identifier COLON Expression

此外，另一个模糊之处：Expression 以两种不同的方式派生 PropDefExpression，直接和通过 ObjDefExpression。我的猜测是，你可以放弃直接推导。

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

请注意，查看http://livescript.net上的示例，我怀疑您能够在传统语法中捕捉到多少。但是，如果您只是想要一个子集，您可能会没事。

于 2015-03-02T23:57:01.783 回答
0

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

然而，在我看来

PropDefExpression ::= Expression COLON Expression

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

name : expression
parenthesized_expression : expression

（也就是说，表达式需要以 a 开头(）。

这意味着一个布尔属性定义，从+或-从第一个标记开始是可识别的，这正是成功递归下降解析所需的条件。还有其他几种属性定义语法，包括名称和括号表达式，后面不跟:

使用 LR(1) 解析器很容易解析，就像 Jison 生成的那样，但是要使用递归下降解析器解析它，您需要左因子。（顺便说一句，GrammarKit 可能会为您执行此操作。）基本上，您需要类似的东西（这不完整）：

PropertyDefinition ::= PropertyPrefix PropertySuffix? | BooleanProperty
PropertyPrefix ::= NAME | ParenthesizedExpression
PropertySuffix ::= COLON Expression | DOT NAME
于 2015-03-03T04:54:24.603 回答