Использование правил смежности в Lemon для интерпретации выражения «let»

Question

Я пытаюсь написать интерпретатор «игрушек» с использованием Flex + Lemon, который поддерживает очень простой синтаксис let, где переменная X временно привязана к выражению. Например, «Пусть X 3 + 4 в х + 8» следует оценивать до 15.

В сущности, то, что я «как» правило сказать:

expr(E) ::= LETX expr(N) IN expr(O). { 
             environment->X = N; 
             E = O; 
            } 

Но это не будет работа с O оценивается до назначения X = N.

Я понимаю, что обычное решение для этого было бы действием среднего правила. Lemon явно не поддерживает это, но я читал в другом месте, что в любом случае будет syntactic sugar.

Так что я попытался собрать в середине правила действий, которые могли бы сделать мое назначение X = N перед интерпретацией O:

midruleaction ::= /* mid rule */.     { environment->X = N; }  
expr(E) ::= LETX expr(N) IN midruleaction expr(O). { E = O; } 

Но это не будет работать, потому что нет никакого способа для midruleaction правила к доступ N, или, по крайней мере, нет, я вижу в лимонных документах/примерах.

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

Любые предложения?

Answer 1

Это действительно не очень масштабируемое решение для оценки сразу в синтаксическом анализаторе. Смотри ниже.

Это правда, что действия среднего уровня (в основном) синтаксического сахара. Однако в большинстве случаев они не являются синтаксическим сахаром для «маркеров» (без терминалов с пустыми правыми сторонами), а скорее для нетерминалов, представляющих производственные префиксы. Например, вы могли бы написать letx правило так:

expr(E)  ::= letx_prefix IN expr(O). { E = O; } 
letx_prefix ::= LETX expr(N).   { environment->X = N; } 

Или вы могли бы сделать это:

expr(E)  ::= LETX assigned_expr IN expr(O). { E = O; } 
assigned_expr ::= expr(N).      { environment->X = N; } 

Первый префикс desugaring; второй - тот, который я буду использовать, потому что я чувствую, что это лучше отделяет проблемы. Важным моментом является то, что действие environment->X = N; требует доступа к семантическим значениям префикса RHS, поэтому оно должно быть частью префиксного правила (которое включает в себя, по крайней мере, символы, для которых нужны семантические значения), а не маркер, который вообще не имеет семантических значений.

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

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

В целом, вам лучше построить легко оцененный АСТ во время анализа и оценить АСТ при успешном завершении анализа.