PHPで構文解析器をスクラッチで作ろうかな？
高木です。おはようございます。
たまには技術情報らしい技術情報を書いておかないと、私を事務か営業の人と勘違いされてしまうといけません。
というわけで、今回はタイトルのとおり、PHPで構文解析器をスクラッチで実装する話です。
といっても、まだ計画だけで成果物は影も形もありません。
でも最初は構想から入らないといけませんからね。
このブログはいろいろな方に読まれています。
ですので、まずは「構文解析器」とは何なのかを簡単に説明することにしましょう。
「構文解析器」というのは、テキストファイルの内容を調べて言語としての構造を解釈するためのプログラムです。
プログラミング言語だけでなく自然言語に対しても構文解析器を作ることができます。
具体例として、「This is a pen.」という英文を構文解析してみましょう。
S+V+Cの第2文型であることは見た瞬間にわかりますが、それ以上に詳細まで解析します。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | [ '主部' => [ [ 'This', 'this', '指示代名詞', '主格' ] ], '述部' => [ [ 'is', 'be', 'be動詞', '三人称単数現在' ], ], '補部' => [ [ 'a', 'a', '不定冠詞' ], [ 'pen', 'pen', '名詞', '主格' ], ], '句読点' => [ [ '.', '.', 'ピリオド' ] ], ] |
上記は単なるイメージですが、構文解析した結果をPHPの配列にするとこんな感じかなと思って書いてみました。
プログラミング言語を解析するときも、大体こんな感じで解析することになります。
多くの場合、構文解析を行う前に字句解析を行うことが多いようです。
簡単にいうと、最初に単語に分解してしまうんですね。
そして、以降は単語の並びとして考えたほうが処理が簡単になります。
自然言語の場合は、活用形とか変化形のようなものもあるので、単純な字句解析より形態素解析を行うほうが現実的かと思いますが、話が横道にそれすぎるので今回はこれ以上触れません。
PHPでは、構文解析や字句解析を行うためのライブラリがPEARの一部として提供されています。
PHP_LexerGeneratorが字句解析、PHP_ParserGeneratorが構文解析を行うためのもののようです。
今回、PHPで構文解析器を作ろうと考えた動機は、PCP: C++ Preprocessorに使おうと考えたからです。
PCPでは、型や宣言をPHPの配列として記述する必要があるのですが、これが非常に非人間的です。
そのため、普通にCやC++のコードと同じように書けば、それをPCP内部で構文解析してPHPの配列を組み立ててやれば便利になるだろうと考えたのです。
しかし、C++の構文解析をまともにやろうとすると、字句解析が文脈依存になったりします。
なので、今回はPHP_LexerGeneratorとPHP_ParserGeneratorをあえて使わず、スクラッチで実装しようと考えたのです。
もっとも、本当に真面目に構文解析を行う必要があるかはかなり疑問です。
最初の段階では、たとえば定数式として指定できるのは識別子だけとかに制限してもよいかもしれません。
それであれば、ずいぶん実装が楽になると思います。
その制約を前提にすれば、PHP_LexerGeneratorとPHP_ParserGeneratorでも作れる気もしますが、将来の拡張を考慮してスクラッチで頑張りたいと思います。
今回は本当にさわりだけになってしまいましたが、折を見て続きを書きたいと思います。