1 系列説明
GitHub のアドレス 各段階のソースコード 各段階の説明集合
2 構文解析の説明
構文：単語を組み合わせて句または文を形成する方法。
字句解析を経て、入力テキストを単語ごとに識別することができるようになりました。この段階の目標は、これらの単語を文として識別し、単語の組み合わせが定義した構文に合致するかどうかを判断することです。
2.1 文法を使って構文を定義する
構文解析には、再帰によって得られる追加の表現能力が必要です。明らかに、正規表現では要件を満たすことができません。
実際、文法は字句単語の構造を記述するためにも使用できますが、正規表現は要件を満たすことができるため、正規表現の方が簡潔です。
2.2 LR (1) 解析法
@%……￥&%#￥複雑すぎて言いたくない
とにかく、LR (1) は非常に非常に強力な解析アルゴリズムであり、多くの削減 - 削減の衝突を解決することができます。ほとんどの文脈自由文法でその構文を記述するプログラミング言語には、LR (1) 文法があります。
2.3 Yacc を使用して構文解析器を生成する
LR (1) 解析表を構築するアルゴリズムは、計算機で自動的に実行するのに十分単純であり、手動で構築するのは非常に面倒で退屈です。そのため、Yacc を使用することは賢明な決定です。
Lex と同様に、Yacc の仕様は 3 つの部分に分かれています。
%{
...
%}
...
%%
...最初の部分は Lex と同じで、include と宣言を含みます。
2 番目の部分では、字句解析から受け取る終端記号、開始記号、優先度などを定義します。
3 番目の部分では、文法と意味アクションを定義します。構文解析段階では文法のみを定義し、意味解析の段階で意味アクションを完了します。
2.3.1 衝突
Yacc はシフト - 削減の衝突を解決するためにシフトを選択し、削減 - 削減の衝突を解決するために文法で最初に出現する規則を選択します。
2.3.2 優先度ガイド
優先度を定義することで曖昧さを解決するため、文法を書く際にははるかに便利です。
Yacc では、2 番目の部分に優先度ガイドコマンドを追加できます。
%left COMMA %right PLUSASSIGN MINUSASSIGN TIMESASSIGN DIVIDEASSIGN ASSIGN %left OR %left AND %left EQ NEQ %left LE GE LT GT %left PLUS MINUS %left TIMES DIVIDE MOD %right INC DEC NOT %left LPAREN RPAREN LBRACK RBRACK
上から下への優先度の低下、left right は単語が左結合か右結合かを示します。
3 具体的な実装
構文解析器と改良された字句解析器のソースコードは記事の冒頭にあります。
この段階まで進むと、コンパイラは 4 つのモジュールに分かれます：
1. エラーハンドリングモジュール（errormsg.c errormsg.h）：ファイル名と行番号を含むエラーメッセージを生成するために使用されます。
2. 一般的なユーティリティモジュール（util.c util.h）：いくつかの一般的な関数を定義します。
3. 字句解析モジュール（simplec.lex）：Lex を使用して字句解析を行います。
4. 構文解析モジュール（simplec.yacc）：Yacc を使用して構文解析を行います。
以前の段階での token.h は不要になりましたが、その代わりに、Yacc は私たちが書いた文法に基づいて単語に関連するヘッダーファイル y.tab.h を自動的に生成します。parsetest.c はドライバープログラムであり、通常は Parsing successful! と出力されます。
付録：ANSI C grammar (Lex) ANSI C grammar (Yacc)
構文解析完了。