javacc入門 - yappyの日記

今日はちょっとコンパイラな気分なのでjavaccをいじりました。
パーザジェネレータはjavaccしか使ったことがありません。
なんか日本語の情報が少ないです。yaccに押されてます。
Eclipseのプラグインはあまり入れないのですが、それもあんまりよくないかな、と思ってjavacc プラグインが入ってます。
今日触るのはこれで2回目です。

ではまだほとんど全く使い方がわからないので慣れるために、
Cコンパイラを作成します。

初めての作業のため、10進数の数値リテラルトークンや識別子トークンを定義するのにもたもたする。
初めは型はやらない方がいいというアドバイスと、そこらへんのミニC処理系でもintしかないのを踏まえ、

// Reserved
TOKEN :
{
	< INT: "int" >
|	< CHAR: "char" >
|	< SHORT: "short" >
|	< LONG: "long" >
|	< FLOAT: "float" >
|	< DOUBLE: "double" >
}
// Number Literal
TOKEN :
{
	< NUMBER: <NUMBER10> >
|	< #NUMBER10: <NUMBER10_PRE> (<NUMBER10_SUC>)* >
|	< #NUMBER10_PRE: ["1"-"9"] >
|	< #NUMBER10_SUC: ["0"-"9"] >
}
// Identifier
TOKEN :
{
	< IDENTIFIER: <IDENTIFIER_PRE> (<IDENTIFIER_SUC>)* >
|	< #IDENTIFIER_PRE: ["a"-"z", "A"-"Z", "_"] >
|	< #IDENTIFIER_SUC: ["a"-"z", "A"-"Z", "_", "0"-"9"] >
}

思いっきりいろんな型を定義してますが当分intしか使いません。
voidさえない。

さて次はプログラム全体の定義です。
グローバル変数宣言、定義、グローバル関数宣言、定義が0個以上といえそうです。

// Root
ASTProgram Program():
{}
{
	(GlobalDifinition())* <EOF> { return jjtThis;}
}

Difinitionって定義のような気がしますが気にしてはいけません。名前って結構困る・・・。

で、まずは変数宣言です。

int a;
int *a;
int a[10];
int *a[10]; /* int *(a[10]); */
int (*a)[10];

int a, *b, c[10], *d[10], (*e)[10];

復習

int *a[10];

はaから優先順位の高い順に英語で呼んで
a is array(10) of pointer to int.
(aはintへのポインタの10個の配列である)
最後の行からわかるように、
基本となる型ポインタ修飾→識別子←配列修飾
となります。
さらにカンマで区切ると「基本となる型」を共有できます。
Cが怖くなってきたぞ・・・！！

なぜそこまでやった

ここって*とかの優先順位のために()使えるから
int (a);
とかもOKなんだよね・・・。
今日Effective STLにあった・・・。
なんとなく書いてみたら
Left recursion detected.
これが噂に聞く左再帰か！！
[10]とかの後置が・・・。

ここでid:atomonadからD言語のBNFの情報。
http://www.kmonos.net/alang/d/2.0/declaration.html
これからも役に立ちそうです。

void Declarator():
{}
{
	"(" Declarator() ")" (DeclaratorSuffix())*
|	"*" Declarator()
|	<IDENTIFIER> (DeclaratorSuffix())*
}

後置でくる修飾をDeclaratorSuffixと定義し、まあ頭の中で一部を正規表現に置き換え、写しました。

次は関数です。

int a;
int a(int a);
int a, *b, c[10], d(int, int);

今までの類推で関数の返り値は変数宣言の基本型と類推できます。
・・・gccで通りました。やめたくなってきた。
これ以上は仕様書なしでやるのは危険なんじゃ・・・。
ごちゃごちゃやってjavaccがコンパイルエラーになるコードを吐いたりして大変でしたが、前述のD言語のを見て、[]と同じく(パラメータリスト)もサフィックスに含めればいいことがわかりました。
へんてこなコードが通ってしまうことを懸念しましたが、それはこの後の意味解析でエラーとするものなのでしょう。きっと。

パラメータリストの定義でまた変数宣言っぽいものがでてきますが、今度は識別子が省略可能です。gccでは

int; //warning
int (void); //error

よくわかんなかったので、パラメータリストの宣言はいつもののコピペで識別子を正規表現?したものにしておきました。もう仕様書なんて知ったことじゃありません。
ちなみに識別子を常に省略可能にしたら

int (int a, int b){}

無名関数ができたよ！！

警告lookaheadの使用を考えてください→検索 javacc lookahead
な感じでLOOKAHEAD(n)も覚えました。まとまった資料がなく絶望感が漂っていましたが、なんだかんだで結構わかってきた感じがします。

今日読んだ東工大の先生のコンパイラの本全然わかんなかったしなあ。我ながら今日はかなり無茶をやってしまった。
ここまで解析してターゲットコード吐けるのかこれ！？
こんなことやるまえにifとかwhileとかつくれや・・・。

今日の成果

/**
 * JavaCC file
 */

options {
	JDK_VERSION = "1.6";
	MULTI = true;
	VISITOR = true;
}

PARSER_BEGIN(CParser)
public class CParser {
	public static void main(String[] args) throws Exception {
		CParser p = new CParser(System.in);
		p.Program();
		System.out.println("OK!");
	}
}
PARSER_END(CParser)

SKIP :
{
 	" "
|	"\t"
|	"\r"
|	"\n"
}

// Reserved
TOKEN :
{
	< INT: "int" >
|	< CHAR: "char" >
|	< SHORT: "short" >
|	< LONG: "long" >
|	< FLOAT: "float" >
|	< DOUBLE: "double" >
}
// Number Literal
TOKEN :
{
	< NUMBER: <NUMBER10> >
|	< #NUMBER10: <NUMBER10_PRE> (<NUMBER10_SUC>)* >
|	< #NUMBER10_PRE: ["1"-"9"] >
|	< #NUMBER10_SUC: ["0"-"9"] >
}
// Identifier
TOKEN :
{
	< IDENTIFIER: <IDENTIFIER_PRE> (<IDENTIFIER_SUC>)* >
|	< #IDENTIFIER_PRE: ["a"-"z", "A"-"Z", "_"] >
|	< #IDENTIFIER_SUC: ["a"-"z", "A"-"Z", "_", "0"-"9"] >
}

// Root
ASTProgram Program():
{}
{
	(GlobalDifinition())* <EOF> { return jjtThis;}
}

void GlobalDifinition():
{}
{
	Type() Declarator()
	(
		("," Declarator())* ";"
|		"{" "}"
	)
}

void Type():
{}
{
	<INT>
}

void Declarator():
{}
{
	"(" Declarator() ")" (DeclaratorSuffix())*
|	"*" Declarator()
|	<IDENTIFIER> (DeclaratorSuffix())*
}

void IdentifierFreeDeclarator():
{}
{
	LOOKAHEAD(2)
	"(" Declarator() ")" (DeclaratorSuffix())*
|	"*" Declarator()
|	(<IDENTIFIER>)? (DeclaratorSuffix())*
}

void DeclaratorSuffix():
{}
{
	LOOKAHEAD(2)
	"[" "]"
|	"[" <NUMBER> "]"
|	"(" ParameterList() ")"
}

void ParameterList():
{}
{
	(Parameter() ("," Parameter())*)?
}

void Parameter():
{}
{
	Type() IdentifierFreeDeclarator()
}