Простой калькулятор в Bison

Question

Я новичок в разборе. Ниже приведен фрагмент кода для синтаксического анализатора в Bison:

Parser.y:

%{ 
#include <stdio.h> 
%} 
/* declare tokens */ 
%token NUMBER 
%token ADD SUB MUL DIV ABS 
%token EOL 

%% 

calclist: /* nothing */ 
| calclist exp EOL { printf("= %d\n", $1); } 
; 
exp: factor  
| exp ADD factor { $$ = $1 + $3; } 
| exp SUB factor { $$ = $1 - $3; } 
; 
factor: term 
| factor MUL term { $$ = $1 * $3; } 
| factor DIV term { $$ = $1/$3; } 
; 
term: NUMBER 
| ABS term { $$ = $2 >= 0? $2 : - $2; } 
; 

%% 

main(int argc, char **argv) 
{ yyparse(); 
} 
yyerror(char *s) 
{ fprintf(stderr, "error: %s\n", s); 
} 

Я изо всех сил, чтобы понять, как строка ввода 10 - 3 * 2 + 6 будет анализироваться/обрабатывается придерживаясь оператора старшинства. Может кто-нибудь описать механизм разбора шаг за шагом? Напр.

Step1: 10 is read and token NUMBER is returned 
Step2: etc.... 

Любая помощь приветствуется.

Спасибо.

Answer 1

Анализаторы бизонов с радостью расскажут вам, что они делают, если вы попросите их, используя bison's trace facility.

Чтобы получить следующий след, я использовал входной файл с минимальными изменениями:

• Я установил прототипы без возвращаемого значения (main и yyerror) и добавил вперед заявления yylex и yyerror.

• Я установил printf в calclist, чтобы напечатать значение выражения ($2), а не сам calclist, который не имеет значения.

• Я изменил отдельные маркера символов (ADD, SUB и т.д.) с фактическими одиночными символами ('+', - и т.д.) для того, чтобы упростить сканер

• я добавил тривиальный лексер.

• Наконец, я включил отслеживание, добавив yydebug = 1; в функцию main и вызывая бизон с флагом -t.

Результат, используя предоставленное вами выражение, приведен ниже. Чтобы понять переходы состояния, вам нужно распечатать таблицу перехода состояния. Используйте опцию -v для бизонов.

$ ./trace <<< '10 - 3 * 2 + 6' 
Starting parse 
Entering state 0 
Reducing stack by rule 1 (line 13): 
-> $$ = nterm calclist() 
Stack now 0 
Entering state 1 
Reading a token: Next token is token NUMBER() 
Shifting token NUMBER() 
Entering state 3 
Reducing stack by rule 10 (line 22): 
    $1 = token NUMBER() 
-> $$ = nterm term() 
Stack now 0 1 
Entering state 9 
Reducing stack by rule 7 (line 19): 
    $1 = nterm term() 
-> $$ = nterm factor() 
Stack now 0 1 
Entering state 8 
Reading a token: Next token is token '-'() 
Reducing stack by rule 4 (line 16): 
    $1 = nterm factor() 
-> $$ = nterm exp() 
Stack now 0 1 
Entering state 7 
Next token is token '-'() 
Shifting token '-'() 
Entering state 14 
Reading a token: Next token is token NUMBER() 
Shifting token NUMBER() 
Entering state 3 
Reducing stack by rule 10 (line 22): 
    $1 = token NUMBER() 
-> $$ = nterm term() 
Stack now 0 1 7 14 
Entering state 9 
Reducing stack by rule 7 (line 19): 
    $1 = nterm term() 
-> $$ = nterm factor() 
Stack now 0 1 7 14 
Entering state 18 
Reading a token: Next token is token '*'() 
Shifting token '*'() 
Entering state 15 
Reading a token: Next token is token NUMBER() 
Shifting token NUMBER() 
Entering state 3 
Reducing stack by rule 10 (line 22): 
    $1 = token NUMBER() 
-> $$ = nterm term() 
Stack now 0 1 7 14 18 15 
Entering state 19 
Reducing stack by rule 8 (line 20): 
    $1 = nterm factor() 
    $2 = token '*'() 
    $3 = nterm term() 
-> $$ = nterm factor() 
Stack now 0 1 7 14 
Entering state 18 
Reading a token: Next token is token '+'() 
Reducing stack by rule 6 (line 18): 
    $1 = nterm exp() 
    $2 = token '-'() 
    $3 = nterm factor() 
-> $$ = nterm exp() 
Stack now 0 1 
Entering state 7 
Next token is token '+'() 
Shifting token '+'() 
Entering state 13 
Reading a token: Next token is token NUMBER() 
Shifting token NUMBER() 
Entering state 3 
Reducing stack by rule 10 (line 22): 
    $1 = token NUMBER() 
-> $$ = nterm term() 
Stack now 0 1 7 13 
Entering state 9 
Reducing stack by rule 7 (line 19): 
    $1 = nterm term() 
-> $$ = nterm factor() 
Stack now 0 1 7 13 
Entering state 17 
Reading a token: Next token is token '\n'() 
Reducing stack by rule 5 (line 17): 
    $1 = nterm exp() 
    $2 = token '+'() 
    $3 = nterm factor() 
-> $$ = nterm exp() 
Stack now 0 1 
Entering state 7 
Next token is token '\n'() 
Shifting token '\n'() 
Entering state 12 
Reducing stack by rule 3 (line 15): 
    $1 = nterm calclist() 
    $2 = nterm exp() 
    $3 = token '\n'() 
= 10 
-> $$ = nterm calclist() 
Stack now 0 
Entering state 1 
Reading a token: Now at end of input. 
Shifting token $end() 
Entering state 2 
Stack now 0 1 2 
Cleanup: popping token $end() 
Cleanup: popping nterm calclist()