💏 👩🏼‍🔧 🤽🏼 コンパイル。 3：バイソン 👩‍⚖️ 🎽 👏🏿

これは、オールドビリーバーバイソンバッファローに焦点を当てたシリーズの唯一の投稿で、一部の人には退屈しています。 Cで書かない人にとっては、原理的には動作するLRパーサージェネレーターが非常に多くの言語に存在するため、この記事はまだ興味深いはずです。イデオロギー的にLRパーサーを受け入れない人は、私が今日引き付けるものは何もありません。

さらに投稿：

文法編集
2ステージパーサー
中身は何ですか？
文法の矛盾
どのように機能しますか？

これまで何をしてきましたか？
前回、算術式の文法をコンパイルしました：

 EXPR：TERM |  EXPR「+」ターム|  EXPR '-' TERM;
期間：NUM |  TERM '*' NUM |  TERM '/' NUM;
 NUM：DIGIT |  NUM DIGIT;
 DIGIT： '0' |  '1' |  '2' |  '3' |  '4' |  '5' |  '6' |  '7' |  '8' |  '9';

結局、それを解析するマシンを見つめてしまいました。
私たち自身は、高騰する機械を発明する方法を知りませんし、必要もありません-バイソンは私たちのためにそれらを構築する方法を知っているからです！
バイソンの助けを借りて、パーサーをコンパイルし、それが実際にどのように機能するかを見ることができます。

文法編集

一般的な原則は、最初の部分の flexと同じです。文法規則をリストし、各規則の反対側に、規則の折りたたみ中に実行されるコードを記述します。

前回、畳み込み中にスタックから文字セット（文字列または変数）を取り出し、その値を確認し、カールされた変数の値を設定し、削除された変数の代わりにスタックに配置することについて言及しました。

%{
#include <stdio.h>
int yylex() { return getc( stdin ); }
void yyerror( char *s) {
fprintf ( stderr , " %s \n " , s);
}
%}

%%

EVALUATE: EXPR '\n' { printf( " %d \n " , $$ ) } ;

EXPR: TERM
| EXPR '+' TERM { $$ = $1 + $3 ; }
| EXPR '-' TERM { $$ = $1 - $3 ; }
;

TERM: NUM
| TERM '*' NUM { $$ = $1 * $3 ; }
| TERM '/' NUM { $$ = $1 / $3 ; }
;

NUM: DIGIT
| NUM DIGIT { $$ = $1 * 10 + $2 ; }
;

DIGIT: '0' { $$ = 0 ; } | '1' { $$ = 1 ; } | '2' { $$ = 2 ; } | '3' { $$ = 3 ; }
| '4' { $$ = 4 ; } | '5' { $$ = 5 ; } | '6' { $$ = 6 ; } | '7' { $$ = 7 ; }
| '8' { $$ = 8 ; } | '9' { $$ = 9 ; }
;

%%

コード解析

lexファイルと同様に、 ％{％}タグ内のコードはパーサーに変更されずにコピーされます。定義する必要がある関数は2つありますint yylex()は次の入力文字を返し、 void yyerror(char *s)はエラーメッセージを出力します。古典的なyaccは、必要に応じて再宣言できるyyerror既製の実装が含まれていました。しかし、彼のGNUクローンのbisonは、プログラマーによる明示的な実装が必要です。

lexファイルの場合のように、 %%は宣言領域と文法規則領域を分離します。ルールは、以前と同じ形式でリストされています。ルールの最後に畳み込みコードを追加します。畳み込みコードでは、パーサースタック上の文字の値を参照するために、 $ -tagsを使用します。 $$は折りたたみ可能な変数（ルールの左側）、 $1はルールの右側の一番左の文字（パーサースタックの最も深い文字）、 $2は左から2番目などを指します。ルールの右側にN個の文字がある場合、 $1 $N値を使用できます$N
畳み込みコードが指定されておらず、ルールの右側に1文字ある場合、バイソンはデフォルトでその値を「継承」します： $$=$1

最初に宣言された変数は、文法の「ルート」と見なされます。すべての入力は、最終的にそのルートまで丸くなるはずです。 EXPRはルートとして適切ですが、計算された式のシールはEXPRの畳み込みに押し込まれなければなりません。つまり、道路に沿った各部分式の意味も印刷されます。印刷の便宜上、ルートとしてのみ使用される新しい変数EVALUATE作成しましょう。これにより、式の最後の改行を読み取ることができます-印刷の利便性に加えて、入力の利便性が得られます。

パーサーのコンパイル時には、標準のbison main()を含むlibyライブラリを指定する必要があります。

[tyomitch@home ~]$ bison 2.y
[tyomitch@home ~]$ cc -ly 2.tab.c
[tyomitch@home ~]$ ./a.out
22+3*4-5
=29
[tyomitch@home ~]$ ./a.out
2 + 2
syntax error

スペースやコメントを無視する方法を知っていたマーケットトレーダー電卓とは異なり、バイソン電卓は厳密に定義された構文を理解します：数字、操作記号、最後の改行。たとえば、文字のペア間にスペースを提供するには、それらを文法に明示的に追加する必要があります。

EXPR: TERM | EXPR WS '+' WS TERM | EXPR WS '-' WS TERM ;
TERM: NUM | TERM WS '*' WS NUM | TERM WS '/' WS NUM ;
NUM: DIGIT | NUM DIGIT ;
DIGIT: '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9' ;
WS: | WS ' ' ;

明らかに、これは不便です。はい。数字の認識に関する10の異なるルールを書くのは不便です。変数名などにラテン文字が必要な場合、52のルールを設定しますか？！

flexとbison利点を組み合わせることはどれほど素晴らしいことでしょう！簡単な式（数字、スペース）を認識しやすくし 、複雑な式を可能にします。

2ステージパーサー

数値を正常に認識し、コメントとスペースを削除するflexパーサーが既にある場合は、入力テキストをそこから導き出します。そして何が起こるか、高度なバイソンパーサーを駆使してみましょう。実際、中間結果を保存する必要はありません。1つのパスで両方のステップを実行できます。 flexは、入力テキストを文字ごとに、トークンをバイソン「up」に渡す場合があります-ターミナル文法文字。トークンflex自体の値。

そのような共生を可能にするために、 flexはバイソン文法の終端文字を何らかの方法で認識しなければなりません。 -dスイッチを指定してbisonを実行すると、すべての端末をリストする.hファイルが生成されます。これを行うには、文法ファイルで端末を宣言（ %token示す）する必要があり、残りは.lexファイルで生成された.hファイルを参照する.lexです。

%{
#include <stdio.h>
void yyerror( char *s) {
fprintf ( stderr , " %s \n " , s);
}
%}

%token NUM

%%

EVALUATE: EXPR { printf( "= %d \n " , $$ ); } ;

EXPR: TERM
| EXPR '+' TERM { $$ = $1 + $3 ; }
| EXPR '-' TERM { $$ = $1 - $3 ; }
;

TERM: NUM
| TERM '*' NUM { $$ = $1 * $3 ; }
| TERM '/' NUM { $$ = $1 / $3 ; }
;

%%

yylex関数は不要になりyylexた。入力文字はstdinではなくflexからyylexされるようになりました。
さらに、 EXPR （ flexそれを飲み込む） '\n'後に'\n'を消去し、 NUMおよびDIGITに関するすべてのルールを削除しました。

対応する.lexファイル：

%{
#include "3.tab.h"
%}

%option yylineno
%option noyywrap

%%

[/][/] .*\n ; // comment
[0-9] + { yylval = atoi(yytext);
return NUM;
}
[ \t\r\n] ; // whitespace
. { return * yytext ; }

%%

トークン定義ファイルは接尾辞.tab.h取得します
唯一のものは#define NUM 258
すべてのトークンは、「通常の」文字とは異なる256より大きい数値を受け取ります。

バイソンにトークンを渡すために、その値はグローバル（ああ、ホラー！） yylvalに書き込まれ、トークンコードを返します。
通常の文字を通常の方法で送信します（文字コードを返します）。

noyywrapオプションは、入力テキストが1つであることを示しますnoyywrap後、次のテキストに移動する必要はありません。このオプションは、 stdinからの読み取りを設定する%option mainを使用している間に自動的に設定されました。これでmain()にバイソンがflex標準のmain() flexに要求したり、独自に記述する必要はありません。

2段階のパーサーをコンパイルします。

[tyomitch@home ~]$ lex 3.lex
[tyomitch@home ~]$ bison -d 3.y
[tyomitch@home ~]$ cc -ly lex.yy.c 3.tab.c
[tyomitch@home ~]$ ./a.out
22+ // hello
3*4 - 5
=29
[tyomitch@home ~]$ ./a.out
22+x
syntax error

用語に関して：このような2段階モデルでは、トークンを認識する下位のパーサーは伝統的に字句解析器 （「字句解析器」）と呼ばれ、トークンからの構成を認識する上位のパーサーは解析器と呼ばれます。これは、デバイスではなく、パーサーの役割を示しています。他の解析システムでは、たとえば、両方の段階でストア自動パーサーを使用できます。

中身は何ですか？

生成されたオートマトンを見るために、システムコードの深sに飛び込む必要はありません。バイソンには、文法をデバッグするための強力なツールがあります。 -vスイッチを指定して、拡張子が.outputファイルを確認します。
数値の解析をレクサーに転送した後、マシンには14の状態が残っており、次のように記述されています。

 ...

状態7

     4 EXPR：EXPR '-'。 期間

     NUMシフトし、状態1に移動します

    期間は状態11になります


状態8

     6 TERM：TERM '*'。 数

     NUMシフト、状態12に移動


状態9

     7 TERM：TERM '/'。 数

     NUMシフトし、状態13に進みます


状態10

     3 EXPR：EXPR「+」ターム。
     6期間：期間。  「*」NUM
     7 | 期間。  「/」NUM

     「*」シフト、状態8へ
     「/」シフトし、状態9に進みます

     $ルール3（EXPR）を使用したデフォルトの削減

 ...

各状態について、この状態で認識されるルール（文法の番号と一緒に）が示され、各入力文字に対して実行されるアクションがリストされます。次の条件は、折りたたみ後は表示されません。代わりに、オートマトンはスタックから読み取られた状態に戻り、その中で、新たに最小化された非ターミナルに対応する「go to」ルールを検索します。したがって、オートマトンの遷移表は2次元です。各状態では、 アクションは入力シンボルのみに依存し、スタックの内容には依存しません。（ただし、折りたたみ後の次の状態はスタックから取得されます。）

マシンのプリントアウトで鉛筆でクロールしないように、シンボルをシンボルごとに置き換えて、解析中に状態から状態へのすべての遷移を印刷するようバイソンに依頼できます。これを行うには、 -tスイッチを使用して文法をコンパイルすると、 yydebugグローバルフラグがパーサーに表示されます。 main()などで1に設定する必要があります。
さらに、シンボル値を印刷する場合は、 YYPRINTマクロを定義する必要があります。

%{
#include <stdio.h>
void yyerror( char *s) {
fprintf ( stderr , " %s \n " , s);
}
#define YYPRINT(file, type, value) fprintf(file, " %d " , value);
%}

%token NUM

%%

EVALUATE: EXPR { printf( "= %d \n " , $$ ); } ;

EXPR: TERM
| EXPR '+' TERM { $$ = $1 + $3 ; }
| EXPR '-' TERM { $$ = $1 - $3 ; }
;

TERM: NUM
| TERM '*' NUM { $$ = $1 * $3 ; }
| TERM '/' NUM { $$ = $1 / $3 ; }
;

%%
int main () { yydebug= 1 ; return yyparse(); }

2番目のタグ%%の後のコードは、 ％{％}にあるかのように、パーサーに変更されずにコピーされます。
さて、 main()自分で定義したliby 、コンパイル時にlibyを接続する必要がなくなりました。

[tyomitch@home ~]$ lex 3.lex
[tyomitch@home ~]$ bison -dt 3.y
[tyomitch@home ~]$ cc lex.yy.c 3.tab.c
[tyomitch@home ~]$ ./a.out
Starting parse
Entering state 0
Reading a token: 22+3*4-5
Next token is token NUM (22)
Shifting token NUM, Entering state 1
Reducing stack by rule 5 (line 20), NUM -> TERM
Stack now 0
Entering state 4
Reading a token: Next token is token '+' (22)
Reducing stack by rule 2 (line 15), TERM -> EXPR
Stack now 0
Entering state 3
Next token is token '+' (22)
Shifting token '+', Entering state 6
Reading a token: Next token is token NUM (3)
Shifting token NUM, Entering state 1
Reducing stack by rule 5 (line 20), NUM -> TERM
Stack now 0 3 6
Entering state 10
Reading a token: Next token is token '*' (3)
Shifting token '*', Entering state 8
Reading a token: Next token is token NUM (4)
Shifting token NUM, Entering state 12
Reducing stack by rule 6 (line 21), TERM '*' NUM -> TERM
Stack now 0 3 6
Entering state 10
Reading a token: Next token is token '-' (4)
Reducing stack by rule 3 (line 16), EXPR '+' TERM -> EXPR
Stack now 0
Entering state 3
Next token is token '-' (4)
Shifting token '-', Entering state 7
Reading a token: Next token is token NUM (5)
Shifting token NUM, Entering state 1
Reducing stack by rule 5 (line 20), NUM -> TERM
Stack now 0 3 7
Entering state 11
Reading a token: Now at end of input.
Reducing stack by rule 4 (line 17), EXPR '-' TERM -> EXPR
Stack now 0
Entering state 3
Now at end of input.
Reducing stack by rule 1 (line 13), EXPR -> EVALUATE
=29
Stack now 0
Entering state 2
Now at end of input.

スタックから状態のみが出力されます。スタック上の文字のタイプとその値は、コンテキストから推測する必要があります。
YYPRINTマクロYYPRINT設定されていない場合、読み取りトークンの値を推測する必要があります。バイソンは空の括弧のみを印刷します。

文法の矛盾

前回、あいまいな文法が言及され、1つの式を解析するためのいくつかのオプションが許可されました。
曖昧な文法をコンパイルしようとすると、バイソンは何を言うでしょうか？

%{
#include <stdio.h>
void yyerror( char *s) {
fprintf ( stderr , " %s \n " , s);
}
%}

%token NUM

%%

EVALUATE: EXPR { printf( "= %d \n " , $$ ) } ;

EXPR: NUM
| EXPR '+' EXPR { $$ = $1 + $3 ; }
| EXPR '-' EXPR { $$ = $1 - $3 ; }
| EXPR '*' EXPR { $$ = $1 * $3 ; }
| EXPR '/' EXPR { $$ = $1 / $3 ; }
;

%%

[tyomitch@home ~]$ bison 4.y
4.y: conflicts: 16 shift/reduce

文法が1つの状態から複数の継続を許可する場合、バイソンは何を実行するかを正確に理解しません。私たちの場合、それはシフトと畳み込みの間で変動します。前回と同様に、文法を修正できます。また、バイソンを正しい方向に「プッシュ」し、競合が発生した場合の対処方法を示唆できます。これを簡単なハックとして扱う必要があります。パーサーは動作を開始しますが、「ヒント付き文法」のデバッグはより困難になります。

算術式は競合の典型的な原因であるため、ヒントは、演算子の優先度（加算の前に乗算を実行する）とその結合性（優先度が同じで、先に実行する演算子から）を示す形式でも提供されます。リスト内の演算子が低いほど、優先度が高くなります。リストの同じ行のオペレーターは同じ優先度を受け取ります。

%{
#include <stdio.h>
void yyerror( char *s) {
fprintf ( stderr , " %s \n " , s);
}
%}

%token NUM

%left '+' '-'
%left '*' '/'

%%

EVALUATE: EXPR { printf( "= %d \n " , $$ ) } ;

EXPR: NUM
| EXPR '+' EXPR { $$ = $1 + $3 ; }
| EXPR '-' EXPR { $$ = $1 - $3 ; }
| EXPR '*' EXPR { $$ = $1 * $3 ; }
| EXPR '/' EXPR { $$ = $1 / $3 ; }
;

%%

連想演算子には、 %rightディレクティブがあります。
優先順位を持つハックの不自然さは、 if (1) if (2) foo(); else bar();のあいまいさの例によって評価できますif (1) if (2) foo(); else bar(); if (1) if (2) foo(); else bar();
通常の方法で解析するように-if if (1) { if (2) foo(); else bar(); } if (1) { if (2) foo(); else bar(); } if (1) { if (2) foo(); else bar(); } else優先度が')'より高い必要がある
これらの端末はどちらもオペレーターを呼び出すのが難しく、「自然な」優先順位を設定するのがさらに困難です。
しかし、それは機能します！

「ヒント付き文法」は、元の形式（短く2回）とオートマトンの形式（1つの状態が保存された）の両方で、明確なものよりもコンパクトです。

明確な文法であっても、ストアオートマトンの動作原理に関連して競合が発生する可能性があります。各アクションの実行中、次の入力文字が1つだけ表示されます。たとえば、文法

 WORD：S1 'a' 'i' 'l' |  S2 'a' 'l' 'e';
 S1： 's';
 S2： 's';

-明確であり、帆とセールの2つの単語に対応しています。パーサーが最初の文字 's'をシフトし、その後に 'a'を見ると、選択を行うことができず、 S1またはS2折り畳みます。しかし、彼女のマシンはまだ見えません。
これが、パーサーが2段階になっている2番目の理由です：字句解析プログラムが行をトークンに圧縮し、トークン間の不要な文字を破棄するという事実により、LRパーサーは、「1文字ではなく1トークン前方」を管理します。

どのように機能しますか？

flexに、パーサーコアにはジャンプテーブルと小さなループがあります。 yyssa状態yyssaとyyvsa値yyvsa 2つの並列スタックが使用されyyvsaすべて同じで、状態とシンボルは常にペアでスタックに出入りします。

前回同様、パーサーの観点からは同一のシンボルがクラスに結合されます。この場合、7つのクラスがあり、それらは.outputファイルにリストされて.outputます。配列static const unsigned char yytranslate[259]は、クラスをすべての端末にマップします。（0〜255は通常の文字、258は発表したNUM端末です）。

遷移表は巧妙に組み合わされています。アクションの説明はメインテーブルに保存されます。シフト（正の数）の場合-移行する状態。畳み込み（負）のために-どのルールによって崩壊するか。

 static const unsigned char yytable [] =
 {
        6、7、5、8、9、10、11、1、12、13
 };

テーブルが1次元であるだけでなく、状態よりも要素が少ないことも驚くべきことです（14個あります）。
トリックは、各状態の最初のアクションのインデックスが別のテーブルに保存されることです。

 #define YYPACT_NINF -5
 static const yysigned_char yypact [] =
 {
        4、-5、2、-4、-3、-5、4、4、5、6、
       -3、-3、-5、-5
 };

YYPACT_NINFはyytable要素がないことを意味します。つまり、実行されるアクションは入力文字とは無関係です。
各状態のデフォルトのアクションは、別の別のテーブルに保存されます。

 static const unsigned char yydefact [] =
 {
        0、6、0、2、3、1、0、0、0、0、0
        4、5、7、8
 };

畳み込みのみが入力文字に依存しないため、 yydefactの値は、 yydefact必要のある文法規則の番号です。

yypact[n]のインデックスには、状態nと文字クラス0のアクションが格納されyytable[yypact[n]+k]文字クラスkのアクションは、 yytable[yypact[n]+k]格納されます。したがって、 yypactは負のインデックスyypactする可能yypactます。これはクラス番号が追加される「ベース」にすぎません。

yytable各アクションがyytableするシンボルを確認するには、別のテーブルがあります。

 static const unsigned char yycheck [] =
 {
        4、5、0、6、7、6、7、7、3、3、3
 };

何が見えますか？ yytable[0]はクラス4の文字、 yytable[1]はクラス5の文字などを指します。
上記のようなアクションを見つけてみましょう。

 ...

状態7

     4 EXPR：EXPR '-'。 期間

     NUMシフトし、状態1に移動します

    期間は状態11になります


状態8

     6 TERM：TERM '*'。 数

     NUMシフト、状態12に移動

 ...

端末クラスNUMは3です。
最初のシフトを探しています： yytable[yypact[7]+3]==yytable[4+3]==1 （そして実際、 yycheck[yypact[7]+3]==3 ）
2番目のシフト： yytable[yypact[8]+3]==yytable[5+3]==12 （そして実際、 yycheck[yypact[7]+3]==3 ）

「go to」テーブルは同じ方法で3つの配列に分割され、折りたたみ後にどの状態に切り替える必要があるかが決まります。

パーサーコード自体：（興味のない部分は切り取られ、興味深い部分はコメント化されます）

yynewstate :
*++yyssp = yystate; //

yyn = yypact[yystate]; //
if (yyn == YYPACT_NINF)
goto yydefault; //

yychar = yylex(); //
yytoken = yytranslate[yychar]; //
yyn += yytoken; // yytable
if (yyn < 0 || YYLAST < yyn || yycheck[yyn] != yytoken)
goto yydefault; //
yyn = yytable[yyn];

if (yyn <= 0 ) {
yyn = -yyn;
goto yyreduce;
}

*++yyvsp = yylval; //
yystate = yyn; //
goto yynewstate;

yydefault :
yyn = yydefact[yystate];
if (yyn == 0 ) // :
goto yyerrlab; // ,
//
yyreduce :
yylen = yyr2[yyn]; //

yyval = yyvsp[ 1 -yylen]; // : $1

// :
// $- yyval yyvsp[]

switch (yyn) {
case 2 :
{ printf( "= %d \n " , yyval); }
break ;

case 4 :
{ yyval = yyvsp[- 2 ] + yyvsp[ 0 ]; }
break ;

case 5 :
{ yyval = yyvsp[- 2 ] - yyvsp[ 0 ]; }
break ;

case 7 :
{ yyval = yyvsp[- 2 ] * yyvsp[ 0 ]; }
break ;

case 8 :
{ yyval = yyvsp[- 2 ] / yyvsp[ 0 ]; }
break ;
}

yyvsp -= yylen; //
yyssp -= yylen;

*++yyvsp = yyval; //

yyn = yyr1[yyn]; //

//
yystate = yypgoto[yyn - YYNTOKENS] + *yyssp;
if ( 0 <= yystate && yystate <= YYLAST && yycheck[yystate] == *yyssp)
yystate = yytable[yystate];
else
yystate = yydefgoto[yyn - YYNTOKENS];

goto yynewstate;

繰り返しますが、パーサー全体が式の計算とともに数ページのコードに収まります。その場合でも、彼の3番目は圧縮テーブルでの高度な検索です。

次回は、おもちゃのプログラミング言語の解析に取り組みます。
バイソンとその同類の利点は、 .yファイルからコピーされた.yアクションを持つテーブルとスイッチのみが、パーサーの言語の複雑さから成長することです。
パーサーコードの残りの部分は普遍的です。スパゲッティも、トリッキーな組み合わせでお互いを呼び出す再帰関数もありません。文法規則は実際にコンパイルされており、高級言語の構文に組み込まれていません。

コンパイル。 3：バイソン