文法定義ファイル
識別子や名称について
英数半角小文字と_(半角Underscore)を使う事。
識別子や名称は適宜Javaのクラス名等に使用される。このとき先頭の文字と_直後の一文字が大文字に変換され、_は削除される。
例)
hoge_hoge → HogeHoge
ファイルの構成
文法定義ファイルは下記のようにいくつかのセクションに分かれている。
各セクションはファイル中、下記の順番で書かなければならない。
- パッケージ宣言(Package)
- ヘルパー定義(Helpers)
- トークン解析機状態定義(States)
- トークン定義(Tokens)
- 無視トークン定義(Ignored Tokens)
- 導出定義(Productions)
- 抽象構文木(Abstract Syntax Tree)
Package
ここでは生成されたparserを配置するJavaのパッケージを指定する。
Package org.x68k.language;
と指定した場合、以下のパッケージに各ソースが展開される。
org.x68k.language org.x68k.language.analysis org.x68k.language.lexer org.x68k.language.node org.x68k.language.parser
出力フォルダもパッケージ階層に従って生成されます。
<出力フォルダ>\org\x68k\language\...
Helpers
ここではTokens節でトークンを認識するための正規表現やキャラクターセットを定義する。
Tokens節では正規表現の使い回しが出来ないことや特定のキャラクターに名前をつけたいだけの場合に適さないのでHelperを利用する。
特にクラスが生成されたりはしないので、名前がTokens節の定義と衝突しても問題無い。
文法は下記のようになる。
Helpers 識別子1 = 正規表現 | 正規表現 | ... ; 識別子2 = 正規表現 | 正規表現 | ... ; ...
正規表現は
文字または文字列 繰り返し条件
の繰り返しで表現される。続けてかかれた正規表現は連結されて扱われる。
一致文字・文字列には以下を指定できる。
意味 | 表記例 | 説明 |
---|---|---|
一文字と一致 | ‘c”あ”” | UTF-16で一文字と一致する。シングルクォート自身もエスケープ無しで含めることが出来る。 |
1013 | UTF-16で一文字と一致する。10進数表記のキャラクターコード | |
0x000A0x000D | UTF-16で一文字と一致する。16進数表記のキャラクターコード | |
文字列と一致 | ‘string’ | Unicode文字列を表す。シングルクォートを含めることは出来ない。シングルクォートを含めたい場合は ”’ ‘string’ ”’などとシングルクォートと一致する”’と’string’を並べて書くことで実現できる。 |
任意の一文字と一致 | [‘a’ .. ‘z’][0x0000 .. 0xFFFF] | 文字セット、セット内の任意の一文字に一致する。UTF-16 |
[A + B][A – B] | 文字セット間の演算。AやBには文字列以外が指定可能。 | |
ヘルパ定義と一致 | cr lf | 他の行で定義したヘルパに一致する。指定はヘルパidで行う |
正規表現 | (regexp) | ()内の正規表現と一致する。 |
繰り返し条件については以下を指定できる。
表記 | 説明 |
---|---|
? | 直前の正規表現が省略可能である(0回、もしくは1回一致する) |
* | 直前の正規表現を0回以上繰り返す(省略可能かつ複数回繰り返し可能) |
+ | 直前の正規表現を1回以上繰り返す(省略不可能かつ複数回繰り返し可能)) |
例)
Helpers // 全ての文字に一致する文字セット all = [0x0000 .. 0xFFFF]; cr = 0x000D; lf = 0x000A; eol = cr lf | cr | lf; // cr lf と連続した2文字の改行コードにも一致する。 tab = 0x0009; space = ' '; blank = eol | half_space | tab; alpha = [['A'..'Z'] + ['a'..'z']]; digit = ['0'..'9']; identity= alpha [alpha + digit]*;
Tips.
大文字小文字を無視する形で文法定義する場合、大文字小文字のどちらにも一致する正規表現を使う。
例えば大文字小文字を無視してhelpersという文字列と一致する正規表現なら以下の様にする。 helpersの定義の右辺が一文字おきにblankを挟んでいる事に注意。
Helpers
h = ‘h’ | ‘A’;
e = ‘e’ | ‘B’;
l = ‘l’ | ‘L’;
p = ‘p’ | ‘P’;
r = ‘r’ | ‘R’;
s = ‘s’ | ‘S’;
helpers = h e l p e r s;
States
トークン解析機の動作を、あるトークンの検出により切り替えたい場合、 このStatesでトークン解析機の状態を定義してやり、 Tokens節の定義で遷移させることで行うことが出来る。
States 識別子1, 識別子2, ... ;
として定義する。トークン解析機の最初の状態はStates節の一番最初の定義である 識別子1 となる。 トークン解析機を条件によって切り替えたい場合の状態定義をここで行う
States normal, // トークン解析機は初期化された状態では normalステートで動き出す。 special;
Tokens
Productionsで認識するためのトークンを定義する。
左辺がToken ID、右辺がトークンを表す正規表現になる(ここにHelper IDを利用することが出来る)。
Token IDの前にトークン解析機の状態を指定することが出来る。
Tokens {normal} normal_token = alpha_digit+; {special} special_token = alpha+; {normal, special} common_token = digit+;
なお、ここで指定しているToken IDは構文木を構成する要素のクラス名として使用されます。
Ignored Tokens
無視するトークンを定義する。
無視するトークンの識別子を並べる。無視したトークンはLexerで認識した後、Parserに渡される前に破棄される。
Ignored Tokens blanks, comments;
Productions
文法を定義する。
基本的な書き方は以下のようにProductionの識別子と、その定義を書いていく。
構文名 = 構文規則その1 | 構文規則その2 | 構文規則その3 | ... ; 構文名 = 構文規則その1 | 構文規則その2 | 構文規則その3 | ... ; ....
構文規則(Alternative)は以下のようになる。
{構文規則名} [要素名]:要素識別子 [要素名]:要素識別子 …
要素識別子にはProduction、Tokenを指定することが可能。この時プリフィックスをつける事が出来てP.と書けばProduction ID、T.と書けばToken IDになる。
要素識別子の後には、その要素の出現回数を指定する事が出来る。
- ? (0回か1回現れる)
- * (0回以上現れる)
- + (1回以上現れる)
例えば足し算と引き算の構文規則を書くと以下の様になる。
expr = {add} [left]:num plus [right]:num | {sub} [left]:num minus [right]:num ;
構文規則名についてはParserが作る構文木を構成するクラス名に影響します。
要素名については子ノードのプロパティ名に影響します。
同じTokenやProductionが二回以上現れない場合には名前をつけなくてもOKです。上記の場合numが複数回現れるためユニークな名前をつけてやる必要があります。
同様に構文規則も一つしかない場合には名前を着ける必要はありません。
なお、ここにはASTを得る場合に必要な変換ルールの記載の仕方を含めていません。
これについてはCSTからASTへの変換を確認してください。
Abstract Syntax Tree
ASTの導出ルールを書きます。
CSTの導出で良ければこのSectionは必要ありません。
Abstract Syntax Tree AST構文名 = {AST規則名} [AST要素名]:AST要素1 [AST要素名]:AST要素2 ... | {AST規則名} [AST要素名]:AST要素1 [AST要素名]:AST要素2 ... | ... ;
各AST要素はAST構文名か、Token名を指定する事が出来ます。