Избегание левой рекурсии при разборе определений объектов LiveScript

Я работаю над парсером для языка 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Я получаю ошибки об использовании левой рекурсии. Какой (правильный) способ сделать это?

2 ответа

Решение

Размещенный вами фрагмент грамматики уже рекурсивен слева, то есть даже без добавления (+|-)boolprop, нетерминальное "Выражение" получает форму, в которой "Выражение" вновь появляется как крайний левый символ:

Expression -> PropDefExpression -> Expression COLON Expression

И это не просто левая рекурсия, это неоднозначно. Например

Expression COLON Expression COLON Expression

может быть получен двумя различными способами (грубо говоря, левоассоциативный или правосторонний).

Вы можете устранить обе эти проблемы, используя что-то более ограниченное слева от толстой кишки, например:

PropDefExpression ::= Identifier COLON Expression

Кроме того, еще одна неоднозначность: выражение получает PropDefExpression двумя различными способами, напрямую и через ObjDefExpression. Я думаю, вы можете отказаться от прямого вывода.

После того, как вы позаботились об этих вещах, мне кажется, вы сможете добавить (+ | -) boolprop без ошибок (если только он не конфликтует с одним из других видов выражений, которые вы не показывали).

Имейте в виду, глядя на примеры на http://livescript.net/, я сомневаюсь, сколько из этого вы сможете уловить в обычной грамматике. Но если вы просто собираетесь на подмножество, вы можете быть в порядке.

Я не знаю, насколько это поможет, потому что я ничего не знаю о GrammarKit и не намного больше о языке, который вы пытаетесь разобрать.

Тем не менее, мне кажется, что

PropDefExpression ::= Expression COLON Expression

не совсем точно, и это создает двусмысленность, когда вы добавляете производство логических свойств, потому что выражение может начинаться с унарного оператора. Однако в реальной грамматике свойство не может начинаться с произвольного выражения. Существует два типа определений свойств ключа:

name : expression
parenthesized_expression : expression

(То есть выражения должны начинаться с().

Это означает, что определение логического свойства, начинающееся с+ или -, можно узнать по первому токену, что является условием, необходимым для успешного разбора рекурсивного спуска. Есть несколько других синтаксисов определения свойств, включая имена и выражения в скобках, за которыми не следует :

С парсером LR(1) легко разобраться, как тот, который создает Jison, но для парсера с парсером рекурсивного спуска вам нужно оставить левую факторную. (Между прочим, возможно, что GrammarKit может сделать это за вас.) По сути, вам нужно что-то вроде (это не завершено):

PropertyDefinition ::= PropertyPrefix PropertySuffix? | BooleanProperty
PropertyPrefix ::= NAME | ParenthesizedExpression
PropertySuffix ::= COLON Expression | DOT NAME 
Другие вопросы по тегам