構文解析
Syntax analysis
文字列で書かれた言語を読んで、その構造を具象構文木や抽象構文木に変換する。 構文は基本的に以下の構造をとる。
連続 (X := A B C…)
選択 (X := A | B | C…)
優先順序付き選択 (X := A / B / C…) (→PEG) 繰り返し (AAAA, ABBB…)
再帰 (A := B, B := C, C := A)
終端記号 いわゆるこれ以上何かと置き換えることができない記号(いわゆる数値そのもののようなもの)
非終端記号 何かと置き換えることができる記号(いわゆる代数のようなもの)
自然数(0を含まない)と加算だけが定義されている数式解析の構文の例
code:bnf
Goal := Expr
Expr := Number | Number "+" Expr
数値は正規表現で記述する。(この方がトークンとして取り扱いやすい) この時
非終端符号は Goal,Expr, Number である。
終端符号は "+", [1-9][0-9]* である。
暗黙の文法終端
書かれることはないが、文法には暗黙の終端がある。ここでは EOT (End Of Text) とする。
code:bnf
この時、受け入れられるのは数字の繰り返しの後に終端符号 EOT を受け取った時だけで、それ以外の文字を受け取った場合にはエラーとなる。
いつ、暗黙の文法終端を考えることができるか?
ゴール文法の終端は必ず EOT のはずである。
ゴール文法以外は EOT 以外の文字が引き続く可能性がある。
構文解析には基本的に2つの方法がある。
現れるべきではない文字が現れた場合、どう振る舞うべきか
そこで解析すべてを打ち切る。
構文をエラーとして、少なくとも区切りと考えられる所までをスキップして、次の構文解析に移る。
構文解析で何が問題となるのか?
構文解析器の構造によっては解釈不能な構文がある。
パターンマッチングをどうするか?
文字の取り込みをどうするか?
実際に使われている構文解析方法
LL法
SLR法
LALR法
LR法
CLR法(Canonical LR, 正準LR)
左再帰
関連