Избегание левой рекурсии при разборе определения объектов 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 -> PropDefExpression -> Expression COLON Expression 

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

Expression COLON Expression COLON Expression 

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

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

PropDefExpression ::= Identifier COLON Expression 

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

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

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

Answer 2

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

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

PropDefExpression ::= Expression COLON Expression 

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

name : expression 
parenthesized_expression : expression 

(Который должен сказать, выражения должны начинаться с ()

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

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

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