バイソンのシンプルな電卓

Question

私は構文解析が初めてです。

Parser.y：：私は入力文字列10 - 3 * 2 + 6が/解析された演算子の優先順位に付着して処理されるかを理解するために苦労しています

%{ 
#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); 
} 

バイソンでのパーサーのコードスニペットを以下に示します。誰でも解析メカニズムを段階的に記述できますか？例えば、

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

助けてください。

ありがとうございました。

Answer 1

バイソンのtrace facilityを使用して、バイソンのパーサーは、尋ねた場合、彼らが行っていることを喜んであなたに伝えます。次のトレースを取得するには

は、私は最小限の変更で、あなたの入力ファイルを使用：

• をノーリターン値（mainとyyerror）でプロトタイプを固定し、yylexとyyerrorの宣言を前方に追加しました。

• にcalclistを固定して、値のないcalclist自体ではなく、式（$2）の値を出力しました。

• は私は些細なレクサーを添加スキャナ

• を簡単にするために、実際の単一文字（'+'、-、等）への単一文字トークン（ADD、SUB、等）を変更しました。

• 最後に、-tフラグでバイソンをmain関数にyydebug = 1;を添加して呼び出すことによって、トレースを可能にしました。

結果は、次のとおりです。状態遷移を理解するには、状態遷移表を出力する必要があります。 bisonには-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()