Токен END OF FILE с flex и bison (работает только без него)

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

  • Переменная
  • постоянный
  • (выражение выражение)
  • (лямбда-переменная. выражение)

Как видите, в последних двух выражениях есть выражения. Я пытался определить общее выражение, чтобы я мог сообщить, какой это тип. Так, например, выражение ((lambda x. (F1 x)) 100) представляет собой комбинацию в целом. Моя идея заключалась в том, чтобы вернуть токен END из flex, когда он достигнет конца файла. Мой код выглядит так:

overallexpr: combo END { printf(" The overall expression is a combination\n"); } |
         constant END { printf(" The overall expression is a constant\n"); } |
         VARIABLE END { printf(" The overall expression is a variable\n"); } |
         l_expr END { printf(" The overall expression is a lambda expression\n"); }
;

expr: combo | constant | VARIABLE | l_expr
;

combo: LPARENS expr expr RPARENS
;

constant: FUNCTION | NUMBER
;

l_expr: LPARENS LAMBDA VARIABLE DOT expr RPARENS
;

Если я помещу этот токен END после четырех возможных вариантов в overallexpr, например, combo END, а не просто combo, он не сработает. Но токен END принимается парсером. Если я распечатаю каждый токен по мере его чтения (с переменной, функцией и числовыми значениями), он будет выглядеть так:

LPARENS  LPARENS  LAMBDA  VARIABLE x  DOT  LPARENS  FUNCTION f1  VARIABLE x  RPARENS  RPARENS  NUMBER 100  RPARENS  END Sorry, Charlie

Трудно сказать, но это должно сработать. Комбинация заканчивается RPARENS, и сразу после нее идет жетон END. Но это не оценивается как общее выражение. Однако, если я вынимаю токены END, кажется, что каждый раз он работает. Я всегда получаю общее сообщение, даже если продукция overallexpr и expr абсолютно одинакова. Вывод идентичен предыдущему, за исключением того, что перед токеном END написано: «Общее выражение представляет собой комбинацию». Итак, мой вопрос: почему? Бизон всегда сначала пробует более ранние постановки? И почему он работал бы без END, а не с ним? Тем более, что вы можете увидеть токен END сразу после того, как он говорит, что это комбинация. Я просто пытаюсь лучше понять, как работает Bison.


lambda flex-lexer eof lambda-calculus bison
person user1040854    schedule 02.11.2012    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Немного сложно сказать, что здесь происходит, не видя вашего кода (и я действительно не хочу углубляться в него), но я рискну предположить: я предполагаю, что вы заменяете стандартный yylex EOF индикация (т.е. возврат 0) с вашим токеном END. Если синтаксический анализатор bison никогда не видит EOF, он никогда не завершает синтаксический анализ.

По сути, бизон сам создает особую продукцию:

__parse__: __start__ $;

parse - это (фактически безымянное) производство, а __start__ - это то, что вы объявили как %start (или первое нетерминальное, если вы не объявили это явно). В вашем случае, я полагаю, это overallexpr. $ - это символ, обычно используемый для обозначения знака EOF.

Теперь, когда происходят действия парсера bison? Хотя в некоторых случаях они могут произойти там, где вы думаете, что они произойдут (то есть сразу после последнего токена в производстве), они обычно не происходят, пока синтаксический анализатор не взглянет на следующий токен. Это разрешено; поэтому он называется LALR(1) парсером: 1 - это количество будущих токенов, на которые ему разрешено смотреть, прежде чем точно решить, что делать с уже имеющимися. Ему почти всегда нужна эта информация, и он часто работает так, как если бы он нуждался, даже если вам и мне кажется, что это не так.

Таким образом, по всей вероятности, синтаксический анализатор на самом деле не будет выполнять overallexpr сокращение - или, другими словами, он не будет выполнять действие, связанное с правилом overallexpr, - до тех пор, пока не убедится, что маркер конца файла является следующий токен.

Теперь, если вы оставите свой END токен вне правила и лексер фактически вернет EOF, тогда bison выполнит сокращение, когда увидит EOF.

person rici    schedule 02.11.2012