構文解析
01cat.strmの構文解析
字句解析の結果、現在streemは以下のトークンのリストを持っています。
- identifier : STDIN
- op_bar
- identifier : STDOUT
構文解析では、与えられたトークンの並びを構文として成立しているかどうかを判定し、以降の処理が可能なようにコンパイル作業を行います。とはいうものの、現在のstreemの実装は、この構文が正しいかどうかの判定までしか行いません（下記はexamples/01cat.strmの実行結果）。
$ bin/streem examples/01cat.strm examples/01cat.strm: Syntax OK
そのため、構文解析の結果のおもしろいところ[6]は、parse.yにはまだ記述されていません。ここでは、先に求めたlex.lによる01cat.strmの字句解析結果が正しい文法であると判定できる理由を示すにとどめましょう。
[6] 構文木の生成や仮想マシン語へのコンパイルなど。
parse.yのソース説明
Makefileを参照するとわかるように、parse.yは、bison -yコマンドを利用してy.tab.cという名前のCのソースファイルに変換されます。bisonは、字句解析結果を使って構文解析を行うコマンドです。bisonの後ろの-yは、yacc互換モードで処理を行うという意味です。
bisonは、構文解析コマンドyaccのGNU版です。lex.lを処理するflexに対してlexというオリジナルのコマンドがあるのと同じ関係です。なお、Windowsで実行可能なbisonはhttp://gnuwin32.sourceforge.net/packages/bison.htmで公開されています。
以下、parse.yから、ここまでの説明に関連する箇所を抜き出したリストを示して、その内容を説明していきます。
次の箇所は、lex.lで利用していたトークンの種類の定義です。bisonが生成したソースではenumに変換されます。また、lex.lをflexを利用して生成したソースファイル（lex.yy.c）のincludeが記述されています。
%token
keyword_if
（略）
op_bar
op_amper
（略）
%token
lit_number
lit_string
identifier
（略）
#include "lex.yy.c"
次に示す箇所が、parse.yの肝の部分です（特に3行目のexpreの行以降）。
%left op_bar
（略）
expr : expr op_plus expr
（略）
| expr op_bar expr
（略）
| primary
（略）
;
primary : lit_number
| lit_string
| identifier
（略）
;
exprはexpressionの略で、式を示します。primaryはそれ以上分解できない単位、lit_numberはリテラル数値、lit_stringはリテラル文字列を示します。op_plus、op_barはそれぞれoperator plusとoeprator barですね。
最初の%left op_barというのは、op_bar（|演算子）は左優先の結合をすることを示します。ほとんどの演算子は左優先の結合なので、逆にソースから右優先の結合を指示している箇所を探してみましょう。すると、それらしい箇所が見つかります。
%right '!' '~'
この定義によって、単項演算子!と単項演算子~が右優先の結合であることが指定されます。
リスト5のexpr :から;までの行は、: で左辺と右辺が結合されている点がMakefileの依存関係の記法に少し似ています。Makefileの場合は左辺は右辺に依存するという意味でしたが、こちらは「左辺は右辺である」という規則を示します[7]。また、最後は「;」で終結させます。
[7] この記法をバッカス・ナウア記法（BNF）と呼びます。トリビアとして、BNFの「B」のバッカスはFORTRANの発明者、ALGOLの開発者の一人、関数型パラダイムの提唱者としても知られています。
|はor結合を意味します。したがって、この部分を読み下すと「exprは、expr op_plus exprまたはexpr op_bar exprまたはprimaryである」となります。
exprはprimaryであるというのですから、expr op_bar exprのexprはprimaryに置き換え可能です。置き換えると次のようになります。
primary op_bar primary
parse.yをさらに読み進むと（リスト5では直下に抜き出してあります）には、primary : lit_number……と定義されています。これを読み下せば「primaryはlit_numberまたはlit_stringまたはidentifierである」です。この規則を、上で求めたprimary op_bar primaryに適用して、primaryをidentifierに置き換えると、次のようになります。
identifier op_bar identifier
これは、先に示した字句解析した結果である、
- identifier : STDIN
- op_bar
- identifier : STDOUT
と合致します。ここから、01cat.strmの字句解析結果のリストが正しい文法であることがわかります。
なお、実際のparse.yの処理では、lex.lから与えられた「identifier op_bar identifier」から、今読んだのと逆の順番に規則を適用していきます。
先ほどは引用しなかったparse.yの文法規則の先頭部分を見てみましょう。
program : compstmt
;
compstmt : stmts opt_terms
;
stmts : /* none */
| stmt
（略）
;
stmt : var '=' expr
（略）
| expr
;
opt_terms : /* none */
| terms
;
先ほど、identifier op_bar identifierからexprが求まりました。次にexprはstmt（ステートメント）に置き換えられます。そのstmtはstmts（ステートメントの集合）と置き換えられます[8]。
[8] lex.lの説明時に、煩雑になることを理由に改行文字を無視しましたが、複数のステートメントを処理するには、ステートメントを区切る
term（ターミネータ）として改行文字または「;」が必要となります。parse.yを読んで確認してみましょう。
リストの最後の規則を見ると、opt_termsは/* none */（無い）で置き換えられることもわかります。すると、stmts opt_termsと置き換えられるため、結局compstmtとなり、一番上の規則から、identifer op_bar identifierは正しくprogramであることが検証できます。
まとめ
この記事では、現在GitHubで公開されてるstreemのlex.lおよびparse.yのソースを元に、プログラミング言語処理系が最初に行う字句解析および構文解析について解説しました。ここで利用されているflex（lex）およびbison（yacc）は、プログラミング言語処理系の作成だけに利用が限定されているわけではありません。そういった実用的な面だけではなく、単純に字句解析や構文解析はプログラムの処理として機械的な置き換えが順に行われていくおもしろさがあります。
現時点のstreemはごくごく小さな仕様しか持たないため、lex.lやparse.yのソースを読み解くのはそれほど難しくはありません。ぜひとも実際のソースを読んでみてください。
