Получение конфликта с лимонным парсером

Question

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

Конфликт между грамматикой для:

{x = 10;} 

и

{x:10}; 

Первое утверждение блок, содержащий оператор присваивания, а второй является выражением утверждение определении объекта.

Грамматика для анализа обоих из них приводит к конфликту. Минимальный код выглядит следующим образом:

rMod ::= rStmt. 

rStmt ::= rStmtList RCURLY. {leaveScope();} 
rStmtList ::= rStmtList rStmt. 
rStmtList ::= LCURLY. {enterScope();} 

rStmt ::= rExpr SEMI. 

rExpr ::= rObj. 
rObj ::= LCURLY rObjItemList RCURLY. 
rObjItemList ::= rObjItemList COMMA rObjItem. 
rObjItemList ::= rObjItem. 
rObjItem ::= ID COLON rExpr. 

rExpr ::= ID. 
rExpr ::= NUM. 

из файла показывает следующее:

State 4: 
    (3) rStmtList ::= LCURLY * 
     rObj ::= LCURLY * rObjItemList RCURLY 
     rObjItemList ::= * rObjItemList COMMA rObjItem 
     rObjItemList ::= * rObjItem 
     rObjItem ::= * ID COLON rExpr 

         ID shift  8  
         ID reduce  3  ** Parsing conflict ** 
       rObjItemList shift  6  
        rObjItem shift-reduce 8  rObjItemList ::= rObjItem 
       {default} reduce  3  rStmtList ::= LCURLY 

Любые предложения о том, как я могу решить эту проблему будет с благодарностью принято. Благодарю.

Answer 1

Сердце проблемы состоит в том, что вы хотите выполнить enterScope() после скобки, которая инициирует блок оператора. Однако, если за фигурной скобкой следуют два токена VAR и :, тогда он начинает литерал объекта, а не блок. Таким образом, невозможно узнать, следует ли выполнять действие enterScope без двухзначного вида, а лимон не создает грамматики LR (2). В этой связи вы правы, что проблема неразрешима. Но, конечно, есть решения.

Вероятно, худшее решение с любой точки зрения (читаемость, сложность verificability) заключается в создании (1) грамматики LR с использованием обычного LR (2) → LR (1) преобразование, которое позволит вам вызвать enterScope(); действия в точке, где ясно, что область введена. Это означает задержку сокращения на один токен. Это, в свою очередь, означает разделение expr на два непересекающихся нетерминала: те expr, которые могут начинаться с VAR, и те, которые не могут. Для тех expr, которые могут начинаться с VAR, вам также необходимо предоставить механизм, который по существу позволяет склеить вместе VAR и остальную часть expr; в случае выражений, что особенно уродливо (но все же возможно). Цель состоит в том, чтобы иметь возможность написать:

block(A)  ::= blockPrefix(B) RCURLY .     { closeScope(); A = B;} 
blockPrefix(A) ::= lcurlyOpen exprNotStartingVAR(E) .  { A = E; } 
blockPrefix(A) ::= lcurlyVAR(V) restOfExprStartingVar(R) . { A = makeExpr(V, R); } 
blockPrefix(A) ::= blockPrefix(B) SEMI expr(E) .   { A = appendExpr(B, E); } 
lcurlyOpen  ::= LCURLY .        { openScope(); } 
lcurlyVAR(A) ::= LCURLY VAR(V) .       { openScope(); A = V; } 

В качестве альтернативы, который также является некрасивым, но, вероятно, менее некрасиво в данном конкретном случае, это признать имя переменного с последующим двоеточием в качестве одного лексических маркеров (VAR_COLON) , Хотя это усложняет lexer (особенно, поскольку вам нужно распознать конструкции, где между именем переменной и двоеточием появляются пробелы или даже комментарии), это делает грамматику намного проще. С этим изменением конфликта нет, потому что литерал объекта должен начинаться с VAR_COLON, в то время как expr может начинаться только с VAR (или других несвязанных токенов).

Проще простого решения не пытаться создать область inherited attribute.Если мы делаем разрешение области синтетически, то проблема более или менее исчезает:

stmt  ::= expr SEMI | block . 
stmtList ::= stmt . 
stmtList ::= stmtList stmt . 
block(A) ::= LCURLY stmtList(B) RCURLY . { A = applyScope(newScope(), B); } 
objLiteral ::= LCURLY itemList RCURLY . 
objLiteral ::= LCURLY RCURLY . 
itemList ::= item . 
itemList ::= itemList COMMA item . 
item  ::= VAR COLON expr . 
expr  ::= VAR . 
expr  ::= objLiteral . 
... 

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

Однако я бы сказал, что для большинства языков (в том числе Javascript) на самом деле удобнее делать обзор в конце блока или даже после прохода по АСТ. Javascript, в отличие от C, позволяет объявлять локальные переменные после их первого упоминания. Локальные функции могут даже использоваться до их объявления. (Это тонко отличается от Python, где объявление функции является исполняемым присваиванием, но правила обзора аналогичны.)

В качестве другого примера, C++ позволяет объявлять члены класса в любом месте декларации класса, даже если член уже упоминался внутри другой функции класса.

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