構文解析 - bbr-proglang-memo

構文解析

Syntax analysis

文字列で書かれた言語を読んで、その構造を具象構文木や抽象構文木に変換する。

現在は字句解析も同時に行うことが多い。

構文は基本的に以下の構造をとる。

連続 (X := A B C…)

選択 (X := A | B | C…)

優先順序付き選択 (X := A / B / C…) (→PEG)

繰り返し (X := XA や X := AX、または正規表現での繰り返し X := A*　ここから生まれるのは AAAA のような繰り返しになる。)

再帰 (A := B, B := C, C := A)

終端記号: いわゆるこれ以上何かと置き換えることができない記号(いわゆる数値そのもののようなもの)

非終端記号: 何かと置き換えることができる記号(いわゆる代数のようなもの)

自然数(0を含まない)と加算だけが定義されている数式解析の構文の例

code:bnf

Goal := Expr

Expr := Number | Number "+" Expr

Number := 1-90-9*

数値は正規表現で記述する。(この方がトークンとして取り扱いやすい)

この時

非終端符号は Goal,Expr, Number である。

終端符号は "+", [1-9][0-9]* である。

暗黙の文法終端

書かれることはないが、文法には暗黙の終端がある。ここでは EOT (End Of Text) とする。

code:bnf

Goal := 1-90-9*

この時、受け入れられるのは数字の繰り返しの後に終端符号 EOT を受け取った時だけで、それ以外の文字を受け取った場合にはエラーとなる。

いつ、暗黙の文法終端を考えることができるか?

ゴール文法の終端は必ず EOT のはずである。

ゴール文法以外は EOT 以外の文字が引き続く可能性がある。

構文解析には基本的に2つの方法がある。

トップダウン構文解析

ボトムアップ構文解析

現れるべきではない文字が現れた場合、どう振る舞うべきか

そこで解析すべてを打ち切る。

構文をエラーとして、少なくとも区切りと考えられる所までをスキップして、次の構文解析に移る。

構文解析で何が問題となるのか?

構文解析器の構造によっては解釈不能な構文がある。

パターンマッチングをどうするか?

文字の取り込みをどうするか?

実際に使われている構文解析方法

CLR法(Canonical LR, 正準LR)

PEG

左再帰