ltmpc:Parserの解説

Parserは、LR(1)法もどきの手法によりトークン列を抽象構文木に変換しています。 まずは、LR(1)法のおさらいからします。

LR(1)法

LR(1)法を使うと、（文法を適切に書いたとき）あらゆる決定性文脈自由言語を認識することができることが知られています。 また、完全に同様の方法で構文解析（出力がyes/noではなくて、抽象構文木も作らないといけない問題）も行うことができ、こちらもLR(1)法と呼びます。 LR(1)法を用いた構文解析は、仮想的に構文木が置けるスタックを使うプッシュダウンオートマトンとして理解することができます （ただし、プッシュダウンオートマトンからは、ノード構築子の種類が何であるかしかアクセスできず、その先のノードが何であるかはわからない）。

ところで、多くのLRオートマトンでは、認識の時だけでなく構文解析の時でも「現在の状態」と「現在までの状態のスタック」を使います。 Reduceする前の部分抽象構文木が置いてあるスタックのスタックトップ付近を眺めると、現在のLRオートマトンの状態はほとんど復元できるので、 これは単に何度もスタックを見返さなくて済むようにするためのメモであるということです。

（注：一般に、スタックに積まれている情報だけから現在のLRオートマトンの状態を復元できます。 ただし、一般の言語の場合はスタックトップだけではなくスタック全体が、特定の正規言語にマッチしているかを確認する必要があり、メモなしにいちいち確認していては線形時間で構文解析することができなくなります。）

LR法を手で書き下すのは困難なので、通常はパーサージェネレータを利用します。 しかし、今回のように手で書く場合にはLRオートマトンの状態を列挙するのが非常に面倒な上、どのLRオートマトンの状態がどのスタックトップ付近の状態に対応しているかを一目で判断することができなくなります。 そのため、今回はスタックトップ付近を何度も眺める方法を採用しました。

Parser

前提知識として、C++11TMPによるコンパイル時コンパイラltmpcを支えるテンプレートメタプログラミングテクニック - Qiitaの暗黙変換の項を理解しているものとします。

ソースコードの上から解説していきます。

CRTP型クラスの基底クラス

lr_element<T>はここでいうAny<T>に相当するもので、CRTP型クラスのうち必要なものはこれを継承しています。 lr_postfix_posはどうやら何にも使われていないようです……orz。 lr_suffix_pos<T>は、次に前置の単項演算子が登場しうる部分構文木を表すCRTP型クラスになっています。 例えば、if(expr)の直後には前置の単項演算子が登場し得ますが、3+(expr)の後ろには登場しません。 このため、if(expr)の次の'+'は単項演算子、3+(expr)の次の'+'は二項演算子であると判断することができます。

Statement

Statement<T>は、文(Statement)である部分構文木を表すCRTP型クラスになっています。

IfStatement_Nodeは、IfStatement_Node<>、IfStatement_Node<Cond>、IfStatement_Node<Cond, St>、IfStatement_Node<Cond, St1, St2>の四種類の形態を取り得ます。 これは、単なる濫用です。本来は別のクラスを作るべきです。また、IfStatement_Node<>とIfStatement_Node<Cond>は文法が正しい限り、出力には現れません。 これは、文法（参考）を以下の

<selection-statement> ::= if ( <expression> ) <statement> | ...

から

<selection-statement> ::= <if-begin> <expression> ) <statement> | ...
<if-begin> :: if (

のようにReduceするのを早める文法変換を行っているためです（本質的な効果はありませんが、スタックトップ付近を眺めないといけない個数が減り、また文法違反を早期に検出しやすくなります）。

また、BraceStatement_Node<T...>やDeclareStatement_Node<T...>は、真に可変長なテンプレート引数を持っています。 このため、「まだ後ろに足せる（閉じられていない）BraceStatement_Node」と「閉じられたBraceStatement_Node」を区別する必要があります。 これに使うのがStatement_Node<T>で、閉じるときはこれで囲うことにしています。紛らわしい……。別のクラスを作ればよかったですね……。

Expr

Expr<T>は、式(Expression)である部分構文木を表すCRTP型クラスになっています。 以下、演算子に対応する構文木のノードをたくさん定義しています。抽象構文木に一本道の部分を残さないようにするために、一つ優先順位が低い演算子のノードを継承 しています。 Term_Nodeは、識別子やリテラル、かっこでかこまれた式を表すノードです。

識別子とリテラルの定義

Nameは識別子、IntLiteralとCharLiteralとStringLiteralはリテラルです。

Func_Node

これも引数が可変長なので、「まだ後ろに足せるもの」と「閉じられたもの」を区別する必要があります。 このとき、閉じられたものはTerm_Node<T>で囲うことによって区別することにしています。

Type

ところで、C言語の単純な型は全てC++の型で表せるわけですが、さすがにそれはセコいかな、と思いちゃんとtype_int等と定義しています。 DeclareSpecifier、Declare、DirectDeclaratorなどは参考にした文法のそれを意味します。 NullDeclaratorは、型宣言のうち識別子が出現しないものの場合に使うプレースホルダーです。 識別子が出現しない型宣言は、典型的には関数の仮引数ですが、文法が同じなのでキャスト式の時にも使われます。

ropとトークン、traits

a+b&cをLR(1)法でパースするとき、'a'をスタックに積み、'+'をスタックに積み、'b'をスタックに積み、'&'を先読みした時点でa+bにReduceします。 a+b*cをパースするときには、'*'を先読みした段階ではa+bをReduceすることはありません。 このように、スタックの二番目の演算子によってReduceするべきかShiftするべきかが変化します。 lr_mult_ropは、乗算系の演算子（'*'、'/'、'%'）を先読みしたときにReduceするべき演算子を表すCRTP型クラスになっています。ropは、reduce_operatorを略したものです。

その他、lr_ifなど、Lexerの出力したトークンをParser独自の定義に変換するための定義が並んでいます。

C言語の型宣言は複雑で、構文木の上の方に出現するのは、使った時に得られる型です。 重要なのはその変数の使い方（これはポインタなのか配列なのか関数なのか？）なのですが、その情報は構文木の最下層に出現します。 そのため、再帰的に情報を収集する必要がありますが、それを実現するのがHasNameなどのtraits手法です。

Reduce

(下)...LRStack B Op A (上)のようなスタック状況でOp2を読み込んだ時、演算子の優先順位的にOpをReduceするべきだとわかったとします（これの判定にはCRTP型クラスが用いられます）。 このような時、Reduce<Op>::operator()( A B LRStack... )を呼び出すことでReduceを行います（Opは関数の引数には渡していない点に注意します）。 この時、AとBは暗黙変換せず、直接同じ型で渡します。なぜなら先読みしたOp2だけの情報からでは、Aをどこまで暗黙変換するべきかが分からないからです。 Aをどこまで暗黙変換するべきかはOpを見ればわかるのですが、それはOp2によらないのでそこだけ抽出しているのがReduceになります。

さらに、ほとんどの二項演算子は同じ構造を持っているので、テンプレートテンプレートパラメータによる抽象化が行われています。 ただし、代入演算子は他のものと異なる右結合であるので別に書かれています。

tuple expand

関数の返り型にパラメータパックを書くことができません。そのため型タプルを返すことになるのですが、それをパターンマッチしても暗黙変換は行われません。 暗黙変換を発動させるためには、関数の引数で受け取ることが必要です。そのため、タプルの中身を展開して関数の引数に渡す関数を作っています。

ReduceToken

これを継承することでReduceを行う定義をいちいち書かなくて済むようになります。

ReduceStatement

if(a)if(b)if(c)x=y;のようなものをパースすることを考えると、最後のセミコロン一つで合計四つの文(Statement)を完成させる必要があります。 これにはいろいろな方法がありますが、次のトークンを先読みした段階でスタックトップがCRTP型クラスStatement<T>を満たしていればReduceするという方法で行っています。 ReduceStatementは、本来は先読みなしでも完成させることができます。 しかし、そのような場合、一つのトークンを読み込んだ時にやる仕事が「Reduceを何回か、Shiftを一回、Reduceを何回か」のようになり、複雑になります。 ReduceStatementを次のトークンを先読みした段階で行うことにより、「Reduceを何回かしたのち、Shiftを一回やって完了」のように簡単になります。 このため、トークン列をすべて処理した後にfinalizeという関数で一度Reduceする必要があります。

reduceDeclare

';'、','、)を読んだ時に共通に行われる、DeclareへのReduceをまとめたものです。

SuffixPosReduceStatement

スタックトップがlr_suffix_pos<T>に該当するCRTP型クラスであったとき、

  • reduceStatementが行えるなら行ってから、行った後のスタックの状態で再度判断を行う
  • reduceStatementが行えないなら、lrElem...をスタックに積む

のどちらかを行います。lr_suffix_pos<U>で受ける上のオーバーロード関数は優先順位が低いため、Statement<U>にマッチしない場合のみ選ばれます。

それ以外のタイプのReduceの選択肢がある場合、SuffixPosReduceStatementを継承したうえで追加のオーバーロード関数を定義しています。

ReduceType

intなどの型を示すトークンが登場したときは、三通りのパターンが存在します。

  • 変数・関数宣言。前置単項演算子が登場し得るところ（の一部）に出現する。ReduceStatementする必要があるかもしれない。
  • 関数の仮引数宣言。開きかっこの後ろなら、仮引数リストの始まりで、コンマの後ろなら仮引数リストの続きである
  • キャスト。開きかっこの後ろに出現する

厄介なのは直前のトークンだけの情報では三つのうちどれが該当するのかわからない点です。幸い、文脈、つまりスタックのトップの方をもう少しだけ見れば区別がつきます。

Token<Lexer::Symbol<'('>>

開きかっこトークンに関する、Reduce/Shiftルールです。五通りのパターンが存在します。

  • 優先順位かキャストのかっこ。前置単項演算子が登場し得るところに出現する
  • 関数適用のかっこ。後置演算子が登場し得るところに出現する。後置演算子は一番優先順位が高いので、スタックトップがTerm_Node<T>であるパターンのみ
  • 構文のかっこ。if(、for(、while(のように出現する
  • 型宣言の時の優先順位のかっこ。型名のあとにポインタの'*'を0個以上伴った後に出現する
  • 型宣言の時の関数仮引数のかっこ。DirectDeclaratorのあと（簡単に言ってセミコロンが来れるところ）に出現する

Token<Lexer::Symbol<')'>>

閉じかっこトークンに関する、Reduce/Shiftルールです。開きかっこに対応する六通りのパターンが存在しますが、空のかっこ対が許されるためにイレギュラーが多いです。

  • 優先順位のかっこ。lr_commma_rop<T>に該当する演算子をReduceし切ってから閉じる
  • キャストのかっこ。reduceDeclareし切ってから閉じる
  • 関数適用のかっこ。直前に'('があれば空の実引数リストであり、そうでなければlr_commma_rop<T>に該当する演算子をReduceし切ってから閉じる
  • 構文のかっこ。for(;;)、for(;;e)、if(e)、while(e)のようになるのでlr_commma_rop<T>に該当する演算子をReduceし切ってから閉じる
  • 型宣言の時の優先順位のかっこ。reduceDeclareし切ってから閉じる
  • 型宣言の時の関数仮引数のかっこ。直前に'('があれば空の仮引数リストであり、そうでなければreduceDeclareし切ってから閉じる

今見ていたら、

template<class... LRStack, std::size_t M> 
static auto move_to( Pointer<0>, lr_open_paren, Pointer<M>, LRStack... ) 
    -> type_stack<DirectDeclarator<Function<NullDeclarator, ParameterList<>>, Pointer<0>>, Pointer<M>, LRStack...>;

は名前のない関数の宣言か仮引数宣言かキャストかしかありえないけれど、いずれも文法違反だからこの行は必要ない気がしますね……。

Token<Lexer::Symbol<'['>>

開き角かっこトークンに関する、Reduce/Shiftルールです。二通りのパターンがあります。

  • 配列アクセスの角かっこ。後置演算子が登場し得るところに出現する
  • 配列型宣言の角かっこ。型名のあとにポインタの'*'を0個以上伴った後に出現すれば識別子なしの宣言であり、そうでなければ普通の宣言

Token<Lexer::Symbol<']'>>

閉じ角かっこトークンに関する、Reduce/Shiftルールです。開きかっこトークンに対応する二通りのパターンがあります。

Error_multidimensional_array_must_have_sizeは正しくない気がしますね……。 int (*a[])[]がパースできなさそうです。そもそもこんなことはTypeAnalysisでやるべきです。

Token<Lexer::Symbol<'{'>>

開き中かっこトークンに関する、Reduce/Shiftルールです。いずれにしてもBraceStatement_Nodeをスタックに積みます。 ここで、スタックトップだけ見る方法でdo;while(e){のようなものをパースするとき、最終的に失敗するとしても一見正常にパースが進んでしまいます。 そのため、このパターンを検出してエラーにするということを行っています（これをしないと非常にわかりづらいSFINAEエラーで落ちてしまいます）。 また、関数宣言の直後に来た場合には関数定義の中かっこになるのですが、「関数宣言かどうか」はC言語の複雑な型宣言の仕様により構文木の最下層を見ないとわかりません。 そのためtraitsで関数宣言か判定しています。これはSFINAEにならないパターンですね。ちゃんと継承を使って書かないといけないのでした。直し忘れていました。

Token<Lexer::Symbol<'}'>>

閉じ中かっこに関する、Rebuceルールです。BraceStatement_NodeにReduceする前に{if(a)if(b)if(c)x=y;}のような多段になっているものをReduceしていきます。

Token<Lexer::Symbol<'?'>> Token<Lexer::Symbol<':'>>

条件演算子に関する、Rebuce/Shiftルールです。他の二項演算子と結合法則が異なるため、直書きしています。

AssignTokenRule

右結合の代入演算子に関するReduce/Shiftルールをまとめたものです。 Cond_Node<T>, lr_element<U>で受けるのは、T, lr_assign_rop<U>で受けるよりも優先順位を下げないといけないことによります。 他の部分でも、lr_element<U>と出現している箇所はこれと同じ理由によります。

BinaryTokenRule MultiBinaryRule

左結合の二項演算子に関するReduce/Shiftルールをまとめたものです。 And_Node<class...>とPlus_Node<PlusOpType, class...>等は別の形になっていて一つのテンプレートテンプレートパラメターにマッチしないためMultiBinaryRuleが存在します。

UnaryTokenRule

前置単項演算子に関するReduce/Shiftルールをまとめたものですが、単にSuffixPosReduceStatementを継承するだけになっています。

UnaryMultiBinaryTokenRule

'*'、'+'、'-'の三種類の、前置単項演算子としても二項演算子としても使える演算子に関するReduce/Shiftルールをまとめたものです。 多重継承する場合はusing宣言しないとオーバーロード解決されません。

以下、これらのルールをまとめたものを継承した具体的なルール定義が並びます。

Token<lexer::Symbol<','>>

コンマに関するReduce/Shiftルールです。以下の三通りが存在します。

  • 関数の引数の区切り記号（lr_comma_rop<T>に該当する演算子をReduceし切ってから）
  • 順次演算子（lr_comma_rop<T>に該当する演算子をReduceし切ってから）
  • 関数宣言の仮引数の区切り記号（reduceDeclareし切ってから）

Token<lexer::Symbol<';'>>

セミコロンに関するReduce/Shiftルールです。以下の四種類が存在します。

  • ;（セミコロンだけ）、break;、continue;、return;の形の文
  • expr;かreturn expr;のような式文の終わり（lr_comma_rop<T>に該当する演算子をReduceし切ってから）
  • 変数宣言の終わり（reduceDeclareし切ってから）
  • int;のような意味のない文

parse

二分再帰により、トークン列をLR(1)法で順次パースしていきます。 ただ、散々Lexerのところで空間計算量Ο(NlogN)にこだわってきたというのにこの方法は、"後ろに渡す情報量"がΘ(N)あるので、空間計算量がΘ(N2)になっています。 LR法で構文解析する限り、TMPの制約のもとでは空間計算量Ω(N2)の壁は破れなさそうに思っています。

finalize

「トークン列の終端」を先読みした時にReduceStatementが必要であれば行う関数です。

Parserを書いてみて

Parser.hppは、千行を超える長大なファイルになっています。 C言語ほどの文法をLR(1)法により構文解析するプログラムを一から書きあげるのはそれなりに大変でしたが、それなりに現実的に書き下すことができました。 LR(1)法といってもスタックトップ付近を見ながらパターンマッチで「今の状態」を導出する、という方法はC++TMPのパターンマッチング機能が優秀なこともありますが、大域的なことを考えずにかけるので楽でした。 言語処理系論の授業で習った時はいまいち理解が深まらなかったLR法でしたが、yaccのようなパーサージェネレータに頼るのではなく、自分の手で書くとさすがに理解が深まったと思います。