Зубцы жевательной резинки 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.

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; 
} 

Answer 1

Bison генерирует bottom-upLALR(1) анализатор. Вы можете представить себе, как это работает:

1. Он читает один лексер из лексера, а именно ID.
2. Он видит, что нет случая, когда за куском с нулевыми терминалами следует ID, поэтому он знает, что он может просто shift этот токен. Теперь он имеет этот терминал ID на стеке.
3. После переключения маркера он считывает еще один токен, который станет концом маркера ввода в вашем случае.
4. Единственная действительная вещь, связанная с ID, - , уменьшая до f. Таким образом, он применяется f → ID и теперь имеет f на стеке.
5. Далее уменьшает с использованием t → f для получения t.
6. Как заглядывая вперёд не TIMES, правило t → t TIMES f не будет применяться, так что уменьшает с помощью e → t для получения e.
7. В качестве внешнего вида тоже нет PLUS. Здесь тоже ничего не менять.
8. Как e является корневым символом, и взгляд вперед - это маркер конца файла, все готово.

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

Я ожидаю, что выход будет: "(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 + ")"; } 
    ; 

[…] 

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