Compiler::Parserの動作解説

ここでは、Compiler::Parserが内部で行っている構文解析の仕組みを解説します。 Compiler::Parserが利用している構文解析器はC++で実装されており、コードは全てsrc以下に配置されています。 解説では、C++で書かれているコードをベースに行います。

はじめに (ここからはC++コードの解説になります)

Parserクラスでは、Compiler::Lexerによって得られたトークンオブジェクトの配列が与えられることを期待しています。 構文解析を始めるには、Parser::parseメソッドをcallするため、まずはparseメソッドの構成から説明します。 Parser::parseの中身は次のようになっています。

AST *Parser::parse(Tokens *tokens)
{
	grouping(tokens);
	prepare(tokens);
	Token *root = parseSyntax(NULL, tokens);//Level1
	parseSpecificStmt(root);//Level2
	setIndent(root, 0);
	size_t block_id = 0;
	setBlockIDWithDepthFirst(root, &block_id);
	Completer completer;
	completer.complete(root);
	Node *last_stmt = _parse(root);
	return new AST(last_stmt->getRoot());
}

それぞれについて解説していきましょう。 groupingメソッドの呼び出しでは、tokensの中にある 'Namespace' '::' 'Method' といった構成を一つにまとめています。 判断基準は、tokenの間にスペースを入れてしまうとsyntax errorになってしまう場合です。 上記の例の他にも、正規表現のオプションなども該当します。

次に最初の構文解析であるparseSyntaxを実行します。このメソッドでは、token列を、 BlockStatement > Statement > Expression > Term > Value　といった構成に変換するものです。 例えば次のようなコードを元に考えてみます。

my $a = 1;
if ($a == 1) {
    print "true\n";
} else {
    print "false\n";
}

上記のようなコードが与えられたとき、parseSyntaxをする前の時点では、

if, (, $a, ==, 1, ), {, print, "true\n", ;, }, else, {, .....

となっているかと思います。これを次のようにまとめます。

|-- if
|-- Expression
|   |-- (
|   |-- $a
|   |-- ==
|   |-- 1
|   |-- )
|-- BlockStatement
|   |-- {
|   |-- Statement
|   |   |-- print
|   |   |-- "true\n"
|   |   |-- ;
|   |-- }
|-- else
|-- BlockStatement
|....

特殊なtoken(BlockStatement, Statement, Expression, Term)を加えて、 その子要素に内包するトークンを追加していきます。 それぞれの特殊要素に内包する場合の判断基準は以下のようになっています。

• BlockStatement Blockの開始を表す '{' 記号だと判断できた場合には、'}'が現れるまで読み進め、 BlockStatmentトークンの子要素に追加する
• Statement ';'のトークンが現れたら、一つ前の文末のトークンまでさかのぼり、間にあるトークンを Statementトークンの子要素に追加する
• Expression 式の開始を表す '(' 記号と判断できた場合には、 ')' が現れるまで読み進め、 　　 Expressionトークンの子要素に追加する
• Term $a[0]や$a{key}など、配列やハッシュの参照は、それひとつで項として判断できるため、 該当するトークンをTermトークンの子要素に追加する

次に、parseSpecificStmtについて説明します。このメソッドでは、ifやforといったStatementとして機能する 特別なものに対して、if, Expr, BlockStatmentをStatementの子要素としてまとめてしまおうというものです。 つまり、上記の結果に対してparseSpecificStmtを実行すると次のような結果になります。

|-- Statement
|   |-- if
|   |-- Expression
|   |   |-- (
|   |   |-- $a
|   |   |-- ==
|   |   |-- 1
|   |   |-- )
|   |-- BlockStatement
|   |   |-- {
|   |   |-- Statement
|   |   |   |-- print
|   |   |   |-- "true\n"
|   |   |   |-- ;
|   |   |-- }
|-- Statement
|   |-- else
|   |-- BlockStatement
|   |....

setIndent(root, 0);やsetBlockIDWithDepthFirst(root, &block_id);は、トークンに対して indentやblock_idを設定するものですので割愛します。

そして次がPerlならではの処理となる、括弧の補完処理です。 括弧の補完はCompleterクラスで行います。