Bison / Flex обрабатывает токены в обратном порядке

Question

Bison / Flex обрабатывает токены в обратном порядке

Поэтому я пытаюсь понять Бизона и Флекса (и как они идут вместе). Пример грамматики, который мне дали, очень прост,

e → e plus t
e → t
t → t TIMES f
t → f
f → LPAREN e RPAREN
f → ID

Мой тестовый ввод просто «х», и я ожидаю, что результат будет:

"(e (t (f (ID x))))"

Фактический результат, который я получаю:

ID x f t

Мне интересно, почему мой вывод обратный (я еще не добавил скобки). Вот мои файлы Flex и Bison.

Бизон:

%{
#include "expr-parse-defs.h"#include <iostream>

std::string AST;
%}

%union {
char *sval;
}

%token <sval> ID PLUS TIMES LPAREN RPAREN

%%e :
| e PLUS t          { AST += std::string("e ") + $2 + "t "; }
| t                 { AST += "t "; }
;

t :
| t TIMES f         { AST += std::string("t ") + $2 + "f "; }
| f                 { AST += "f "; }
;

f :
| LPAREN e RPAREN   { AST += $1 + std::string("e ") + $3; }
| ID                { AST += std::string("ID ") + $1 + " " ; }
;

%%int main() {
yyparse();
std::cout << AST;
return 0;
}

Flex:

%{
#include <cstring>
#include <string>
#include <sstream>
#include <cstdlib>
#include <iostream>
#include "expr-parse.tab.h"#include "expr-parse-defs.h"

using namespace std;
int tokenpos = 0;

char * process_token(const char* token){
// we have to copy because we can't rely on yytext not changing underneath us:
char *res = new char[strlen(yytext) + 3];
strcpy(res, yytext);
yylval.sval = res;
}

%}

ID [a-zA-Z][a-zA-Z0-9_]*

%%
"+"   { yylval.sval = process_token("PLUS"); return PLUS; }
"*"   { yylval.sval = process_token("TIMES"); return TIMES; }
"("   { yylval.sval = process_token("LPAREN"); return LPAREN; }
")"   { yylval.sval = process_token("RPAREN"); return RPAREN; }
{ID}  { yylval.sval = process_token("ID"); return ID; }
[\n]

%%

int yyerror(const char *s) {
cerr << "this is a bad error message and needs to be changed eventually" << endl;
return 0;
}

2

bison c++flex-lexer lex

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

Бизон генерирует вверх дном LALR (1) синтаксический анализатор. Вы можете представить его работу следующим образом:

Он читает один токен от лексера, а именно ID,
Он видит, что нет ни одного случая, когда за частью с нулевыми клеммами следует IDтак что он знает, что может просто сдвиг этот токен. Теперь это имеет то ID терминал на своем стеке.
После смещения токена он считывает еще один токен, который будет концом входного маркера в вашем случае.
Единственное действительное, что можно сделать с ID является сокращение это к f, Так что это относится f → ID и теперь имеет f на своем стеке.
Далее это уменьшает с помощью t → f чтобы получить t,
Так как прогноз не TIMES, правило t → t TIMES f не будет применяться, так что уменьшает с помощью e → t чтобы получить e,
Так как прогноз не PLUS здесь тоже нечего сдвигать.
Как e является корневым символом, а предварительный просмотр является маркером конца файла, все готово.

Эта операция «снизу вверх» может показаться вам странной, но в целом она более мощная и может также привести к более описательным сообщениям об ошибках, чем анализ «сверху вниз». Вы можете видеть, в какое время он использует предварительный просмотр, чтобы решить следующий шаг. Вы также можете себе представить, что если бы у вас были реальные цифры и вы использовали какой-то игрушечный калькулятор, этот подход снизу вверх позволил бы вам оценить части выражения, прежде чем вы проанализируете все выражение. Руководство имеет подробности об алгоритме.

Я ожидаю, что результат будет: "(e (t (f (ID x))))"

Тогда напишите это так. В качестве примера возьмем это:

%{
#include "expr-parse-defs.h"#include <iostream>

#define YYSTYPE std::string;
%}

%token ID PLUS TIMES LPAREN RPAREN

%%

e :
| e PLUS t          { $$ = std::string("(e ") + $1 + " " + $3 + ")"; }
| t                 { $$ = std::string("(e ") + $1 + ")"; }
;

[…]

Это использует строки как семантические значения ваших нетерминалов. Заметьте что вы не может использовать C ++ с не POD-типами лайк std::string, Теперь выражения ожидаемой формы собираются «наизнанку», а синтаксический анализатор выполняет свои правила. Подход с единой AST переменная будет работать для вашего простого примера, но правило с двумя нетерминальными детьми, такими как e → e plus t должен объединить две строки. Для этого лучше всего использовать семантические значения. Вы можете определить свой собственный тип C ++ для хранения различной информации, например, например. текстовое представление термина, числовое значение и места в источнике, где он был определен.

3