Open2024/03/04にコメント追加22

PHPでのパーサー、パーサージェネレータについて

PHPで利用出来るパーサー、パーサージェネレータでアクティブにメンテナンスされているものが少ない気がし、
独自の構文を持った式をパースする処理を実装する場合どのようなロジックが考えられるか調査しようと思います。

候補としては、自前でLexer,Compilerを実装しているテンプレートエンジンのTwigと、
LaravelのテンプレートエンジンであるBlade。Bladeは内部でどんな風にパースしているかまだ見たことがありません。

PHP製のパーサー、パーサージェネレータの状況について

TODO: 後で追記する

Project	調査結果
nikic/php-parser	PHPの構文に対するパーサー。今回はPHPの構文とは異なるものをパースしたいため候補になりません。パーサーをPHPで実装しているので、パーサーを実装する方法としては参考になるかも。

最初に注目するのはCompiler。

パラメータとしてはNodeを受け取っている。
NodeはBlockNode, ForNodeなどがあり、compileメソッドを持っている。
compileメソッドはcompiler->writeを呼び出してPHPコードを出力する実装になっているので、
トークン分割された後の粒度のものに対しcompileメソッドを呼び出すことでPHPへの変換を行っていると思われる。
(トークン分割はもっと前段で行われている)

初心に戻って以下のドキュメントを見ると、

\Twig\Environment 経由で手に入れたインスタンスを以下のように扱うことを想定していそう。
この辺りを調べてみる。

echo $twig->render('index.html', ['the' => 'variables', 'go' => 'here']);

最初にEnvironment::loadの中でEnvironment::loadTemplateが呼ばれており、以下が関係ありそう。

getLoader()->getSourceContext($name) と compileSource($source) を見てみる

getSourceContextは以下。Sourceはテンプレートファイルの内容そのものと、対応するテンプレートファイルのパスなどを持つデータオブジェクト的なもの。

compileSourceは以下のようになっていて、tokenize, parse, compileの順に実行されているのがわかる。

Twigのトークン分割

以下がスタート。

Lexerクラスは以下のようなものが定義されており、このクラスで「{% と %} で括られた範囲をブロックとする」ような定義がされている。
(オプションで変更可能なので定数にはなっていない)
スタートから終端でを抜き出す正規表現も定義されていて、正規表現は「whitespace_trim」を行うかどうかも含めているためか複雑になっている。

最初にpreg_match_allで、 $this->regexes['lex_tokens_start'] に合致するものを全部抜き出している。

$this->regexes['lex_tokens_start'] は以下のようになっていて、各種タグの開始とマッチする内容。

この部分は「TwigはPHPのテンプレートエンジン」ということを前提にしていて、テンプレートの大半の部分はそのままで良く、
Twigのディレクティブが埋め込まれた部分を効率よく抜き出すために書かれている気がする。
({% のようなケースは考慮されていない...?こういうのはそもそも利用側の問題...?)

そういう訳で、汎用的なパーサーを考える場合はこの点は採用出来なそう。

preg_match_allで分割した後は、各タグの開始位置をpositionsに格納した状態で以下のループを行う。

$this->stateに「今ただのテキストを処理しているのか、Blockを処理しているのか」などの状態を格納する
- テキストの処理中はlexData()を呼び出し、Blockの処理中はlexBlock()を呼び出すように、ステートマシンになっている
- カッコの出現はスタック上に積み上げられていて、最後につじつまが合わなければエラーとしている
- 処理結果はTokenStreamとして返される

moveCursorは、受け取ったテキストの長さ分カーソルを進めるのと、
行番号を「間にある\nの数だけ進める」という内容。
行番号の管理が意外な方法だった。

lexData()の場合、preg_match_allで手に入れたpositionの情報を利用して一気にToken::TEXT_TYPEを作ろうとしている。
その後、以下で次にどの状態に遷移するかを判定している。
状態遷移後は1つ前の状態に戻る必要があるのでpushStateで積み上げる形になっている。

lexBlockの場合、基本的にはすぐlexExpressionを呼び出して式をパースしている。
この部分で正規表現を使いながらスペースやオペレータ(記号)、名前、数字などにトークン分割している。
括弧は「punctuation」というトークンとして処理されている。

この辺りが、式をパースするにあたって必要な考え方になりそう。

Twigのparse()

parse()はLexerにより分割されたTokenStreamを受け取って処理する。
準備段階としてget_object_vars()やunset($vars['stack'], $vars['env'], ...)が呼ばれているので、
テンプレートエンジンの変数もこの辺りに展開されていそう。
ネストしたテンプレート内で名前の衝突が起きないようにするためか、getVarName()というメソッドが変数名の接頭辞を返すようになっている。

ForTokenParserは以下のような実装になっていて、Parser経由でtokenStreamの現在位置を取得したり解析を進められるので、
Parserとやりとりしながらfor文用にtokenの解析を進めている。
式に相当する部分のパースはさらにExpressionParserクラスで行われていて、このクラスもParserを通してtokenStreamにアクセスして解析を行っている。

ForNodeは以下のようになっていて、Nodeが持っている情報を使ってcompileメソッドの中で実際のPHPコードを生成する実装になっている。

TwigのExpressionParserについて

TODO: ExpressionParserの中で演算子の優先順位なども考慮しつつNodeの生成が行われているはずなので、そのあたりをもう少し見てみる。