前回の(1)はこちらから。
字句解析器の作り方
(2)では、一般に字句解析器や構文解析器に利用されるパーサジェネレータツール(Yacc/Bison)を利用せずに、自分の手で字句解析器を作成する際に気をつけなければいけない点や設計方針について、Compiler::Lexerを開発した際に得られた知見をもとに解説します。
正規表現で処理するのは正解?
字句解析器や構文解析器を開発するときによく利用するものとして正規表現があります。正規表現は文字列処理を行ううえでとても有益ですが、言語処理系の場合はそうとも限りません。正規表現で表現できないシンタックスが存在する場合や同じ文字を何度も探索しなければならない場合は、正規表現ではなく、後述する1文字ずつ処理する方法をお勧めします。
正規表現で表現できないシンタックスが存在する場合
当然ながら、Perl 5のような複雑なシンタックスの場合、すべてを正規表現で処理することは難しいです。たとえば#があったら、それ以降は行末までコメントと判断してよいでしょうか。答えはノーで、正規表現のデリミタ(区切り文字)の場合や、文字列やヒアドキュメントの中に記述されている場合は無視しなければいけません。Perl 5にはほかにも、正規表現で記述することを考えるとぞっとするシンタックスが多く存在します。
もちろん、1つの正規表現で表現しきれない場合は、いったんスペースなどでソースを分解したあとに個別に適用するなど、段階的に正規表現を適用していく方法が考えられますが、次第にソースコードが複雑化し、保守しにくくなる原因となります。このため、正規表現を用いたパターンマッチによってトークンに切り出す方法は、あまりお勧めできません(PPIでも初めは正規表現で実装されていたそうですが、途中でパターンマッチによる解析に限界を感じ、書き直すことになったそうです)。
同じ文字を何度も探索しなければならない場合
1つの正規表現で表現できない場合、段階的に正規表現を適用する方法も考えられると説明しましたが、この方法だと同じ文字を何度も正規表現の適用対象にしてしまうことになり、実行パフォーマンスの観点から望ましくありません。パフォーマンスの面からも正規表現は避けるべきでしょう。
字句解析器の基本構成
本項では、字句解析器を構成する主なコンポーネントや用語について説明します。字句解析器の説明でよく登場する用語は次のようなものです。
- トークン(Token)
- 字句解析器によって切り出された文字列
- カーソル(Cursor)
- 現在処理している文字の位置を表す
- スキャナ(Scanner)
- デリミタの開始位置から終了位置までカーソルを進める(また、その間の文字列をトークンとして切り出す)
- アノテータ(Annotator)
- 切り出したトークンに解析情報を付加する
これらの用語を用いて字句解析器のテンプレートを表現すると、次のような擬似コードになります(擬似コードはC++言語をベースとして書かれています)。
前項で説明したように、正規表現ではなくカーソルを1文字ずつ進めながら解析することで、何度も同じ文字が解析対象にならず、ソースコードの見通しも良くなります。Compiler::Lexerは、まさに上記に近い構成で実装されています。
本項からは、字句解析器をスムーズに開発するための勘どころを解説します。
「デリミタ」の判断がすべて
字句解析器の目的は文字列から文字列を切り出すことです。文字列を切り出すためには、どの位置からどの位置までを切り出し対象とするか、つまりある文字がデリミタかどうかの判断が重要となります((1)で示した擬似コードの中では、スキャナがこの役目を担っています)。
上記を踏まえ字句解析器が内部で行う処理を整理すると、
- ソースコードを1文字ずつ読み進めながら、その文字があるトークンの開始デリミタかどうかを判断し、開始デリミタだと判断できた場合には、スキャナに開始デリミタとカーソル位置を渡して、終了デリミタまで読み進めてもらう
- 読み進める際には、文字をすべてバッファに貯めておき、終了デリミタに到着した際にトークンに切り出す
となります。これをそのままコードにすることで、シンプルなシンタックスであれば簡単に字句解析器を作成できます。
状態をできる限り持たない
「必要以上に状態を持たないようにする」というプログラミングの鉄則は、字句解析器を作成するうえでも重要です。具体的には、「デリミタかどうかを判断するために、状態変数をなるべく使わないようにする」ことが重要となります。たとえば文字列や空白の終了デリミタを探す際に状態変数を使う必要はないでしょう。
しかし、Perl 5では次に示すヒアドキュメントの処理などが状態を持たざるをえないので、複雑になりがちです。
上記のヒアドキュメントを処理する場合、<<HERE_DOCUMENT
を解析した際に、ヒアドキュメントの開始フラグを保持しつつ、以降の解析を続けなければなりません。そのうえで、改行文字が現れた際に保持しておいたフラグと照らし合わせ、それ以降をヒアドキュメントと判断するという処理になります。
このようなやむを得ない場合を除き、なるべく状態変数を使うことは避けましょう。
先読みをしない
ある文字がデリミタかどうか判断するために、その文字より先の文字を読んで判断してはいけません。次のコード例を見てみましょう。
両者の違いはsplit
関数か$b
というスカラ変数かの違いだけですが、そのあとにある/の文字の処理のしかたは違います。
先読みでは判断できないケースがある
字句解析器で先頭から文字列を探索していき、カーソルが初めに現れた/
の位置にあり、/
が除算演算子なのか、正規表現のデリミタなのかを判断しようとしているとします。このとき、先の文字を読むことで/
の判定をしようとすると、正規表現であるとした場合の終了デリミタである/
の存在を確認するまで先読みをしなければなりません。①の例ではそれでもうまくいきますが、②の例では間違った範囲を正規表現として切り出してしまいます。では②の例を正しく判断しようとして、/
のあとの1が登場した時点で除算演算子と判断するとしましょう。すると今度は①の例が正しく切り出せなくなってしまいます。つまり、ある文字がデリミタかどうか判断するために、その先にある文字を読んで判断しようとすると、うまくいかないケースがあり得るのです。
前のトークンを読むことで判断する
以上を踏まえデリミタの判断は、1つ前、場合によっては2つ前のトークンを読むことで判断します。上記の例では、①ではsplit
関数が第一引数に正規表現を指定できることが自明なので、split
、/
ときた時点で/
を正規表現の開始デリミタと判断できます。同様に②では、$b
というスカラ変数のあとに正規表現を続けて記述できないため、$b
、/
ときた時点で除算演算子だと判断できます。
基本的には上記で示したように、先読みではなく、1つもしくは2つ前のトークンを読むことでデリミタの判断は可能です。
前のトークンを読んでも判断できないケースがある
しかし、Perl 5では前のトークンを読んでも正確に判断できない場合があります。次のケースを見てみましょう。
func
は別packageで定義してあり、exportして利用している関数とします。このとき、func
の次の/
は正規表現の開始デリミタでしょうか、それとも除算演算子でしょうか。実はこれを正しく判断するためにはfunc
のプロトタイプ定義を知る必要があり、これがPerl 5の構文解析器を作ることが難しい理由の一つでもあります。
たとえばfunc
の定義が次のようになっていたとしましょう。
重要なのは、func
キーワードのあとのプロトタイプ定義です。ここでは空が指定してあるため、引数を受け取らないタイプの関数だとわかります。ここで先ほどの③のコード例を見ると、func
は引数をとらないため、/
は正規表現の開始デリミタではなく、除算演算子だとわかります。
それではfunc
の定義が次のようになっていたらどうでしょうか。
今度はプロトタイプ定義が($)
となっているため、スカラ値を1つ取るタイプの関数だとわかります。ここでもう一度③のコードを見ると、func
は引数をとるため、/
は正規表現の開始デリミタだと判断できます。
Perlはビルトイン関数やプロトタイプ定義のある関数に関して括弧を省略できる仕様になっており、正確に解析するためには、プロトタイプ定義を見るほかありません。C言語などの静的型付け言語においても関数のシグネチャ判断は必要になりますが、字句解析の時点でシグネチャを参照しないと正しく解析できない言語はそう多くはないと思います。
PPI、Compiler::Lexerともに、いまだシグネチャを見て字句解析する機能がありません。そのため、上記のように自ら定義した関数を括弧なしで利用している場合には誤動作する可能性があります(実際にPPIを使って③の例を試すと、func
の定義によらず、解析パターンが一通りになってしまうことがわかります)。
しかし、Compiler::Lexerは前節で述べたとおり、Perl5のコンパイラとして動作することを目標としているため、今後プロトタイプ定義を見たうえでの解析もサポートしようと考えています。
<続きの(3)はこちら。>