Ruby開発者・まつもとゆきひろ氏の新言語「Streem」のソースコードを読んでみよう！ ～ 文法と構造を規定する「lex.l」と「parse.y」

字句解析

サンプルプログラムの自然言語による字句解析

　まずは、Streemのサンプルプログラムを例に、字句解析でどのような処理が行われるかを考えてみましょう。

　次に示す01cat.strmは、リポジトリのexamplesディレクトリにあるStreemのサンプルプログラムです。

リスト1：examples/01cat.strm

# most fundamental Streem program

# build pipeline from STDIN to STDOUT
STDIN | STDOUT
# actual stream processing will happen in the event loop
# that starts after all program execution.

　最初の行のコメント（#で始まる行はコメントです）によれば、これは「最も基本的なStreemプログラム」です。実行したときの動作は、標準入力に入力された文字列を標準出力へ出力するだけ^[2]です。コードも、標準入力（STDIN）を標準出力（STDOUT）へパイプ（|）でつないだだけと、いたってシンプルです。したがって、字句解析のゴールは、STDIN、|、STDOUTという3つのトークンの取得です。それ以外はコメントなので、有効なトークンとはみなしません。

[2]　streemが未完成なので、実際にこの結果を得ることはまだできませんが。

　では、streemになったつもりで、01cat.strmを読んでみましょう。

　なお、#以降改行までがコメント、STDINとSTDOUTは定数または変数、|は演算子ということを前提します。このあたりは、「Rubyと同じだなぁ（さらに遡ればUnix流儀だなぁ）」と思えばそう外れることはなく、実際、正しいです。

1行目：1文字目を読むと#なので、コメントの開始ということがわかります。以降改行まで読み飛ばします。

2行目：改行コードしかないので、これも読み飛ばします。

3行目：1文字目を読むと#が見つかるので、再度コメントの開始です。1行目のときと同様に改行まで読み飛ばします。

4行目：読み始めると先頭はSです。これは識別子の始まりです。以降順にTDINと読み進めると空白が見つかります。空白はトークンの区切りなので、ここまで読み込んだ「STDIN」を最初のトークンとしてリストへ保持します。次に|があるので同様にトークンの先頭と認識します。その次は空白なので「|」を2番目のトークンとして保持します（もし「|」に続けて「|」が読まれれば「||」というトークンとなります）。同様にして「STDOUT」を3番目のトークンとして取り出します。

5行目：1行目同様にコメントとして読み飛ばされます。

図2：01cat.strmの字句

 

　ここで示したように字句解析というのは、何らかの入力ストリームから文字を読み込み、現在の状態を切り替えながらトークンを切り出す処理です。

lex.lのソース説明

【お断り】 本記事では、2015年1月10日にgithubからcloneしたソースファイルを元に説明を行っています。streemは活動中のリポジトリなので、現在のものとは内容が異なっている可能性があります。

　それではlex.lのソースの肝となる部分、字句解析のルールの定義を見てみましょう。

リスト2：src/lex.l（抜粋）

TRAIL  ([\t \n]|"#"[^\n]*"\n")*
%%
"+"{TRAIL}  LEX_RETURN(op_plus);
(略)
"||"{TRAIL} LEX_RETURN(op_or);
"|"{TRAIL}  LEX_RETURN(op_bar);
"&"{TRAIL}  LEX_RETURN(op_amper);

if{TRAIL}           LEX_RETURN(keyword_if);
{TRAIL}else{TRAIL}  LEX_RETURN(keyword_else);
(略)
[A-Za-z_][A-Za-z0-9_]* {
  yylval->str = strdup0(yytext);
  LEX_RETURN(identifier);
};

　最初にTRAILとして終端を示す正規表現が定義されています。この正規表現を読解すると、

となります。

　次の行にある「%%」は領域の区切りで、上で示したTRAILを定義している「定義領域」から「規則領域」に切り替わったことを示します。つまり、引用部の「"+"{TRAIL}……」という行からは字句解析の規則です。

　最初に、引用部の規則領域の3番目について読解します。これは最初に示した01cat.strmで利用した規則です。

　ここでTRAILは先の上の定義から0個以上という点が重要です。サンプルプログラムでは「| STDOUT」となっているため、「|」の直後にTRAIL（空白1文字）が続いていますが、仮に「|STDOUT」となっていても、次のトークンの開始となるため、op_barが認識されます。

　最後の引用部は、やはり01cat.strmの読み取りで利用したSTDINやSTDOUTの切り出しルールです。

　なお、yylvalは次に説明するparse.yで利用する変数、yytextは最後に切り出したトークンを保持する変数です。

　つまり、STDIN | STDOUTを字句解析した結果は、次のトークンのリストとなります。

• identifier : STDIN
• op_bar
• identifier : STDOUT

　また、ここまでに説明した定義やルールを利用して図1を書き直すと、図2となります^[3]。

図3：lex.lによる01cat.cstrmの処理結果

 

[3]　lex.lのルールをさらに読むと、LEX_RETURN('\n')によって改行文字もトークンとして扱われていることがわかります。改行をトークンとして構文解析時に利用すれば、現在処理しているファイルの行番号を得られます。行番号は文法エラーの表示には必須となるため、これは不可欠です。ただし、本文では煩雑になるので改行コードについては無視しています。

　ここでは%%という記法やyytextという変数について事前の説明なしに利用しましたが、これらはlexというツールによって規定されています。lexは「字句解析を行うCプログラム」を生成してくれるジェネレータで、lex.lはlex用のソースファイルなのです。