構文解析 — 知識ノート

トークン列から木構造を組み立てる。 parsing。

文脈自由文法#

言語の構造を生成規則で表す。

expr   → expr + term | term
term   → term * factor | factor
factor → NUM | ( expr )

この書き方で「* が + より優先される」ことを 文法の階層として表現している。

手法#

方式	方向	例
LL(k)	上から下（下降型）	再帰下降、ANTLR
LR(k)	下から上（上昇型）	yacc、bison
LALR(1)	LR の実用版	yacc の既定
PEG	順序付き選択	packrat

再帰下降#

各非終端記号に対応する関数を書き、再帰で降りていく。

parseExpr():
    left = parseTerm()
    while 次が '+' or '-':
        op = 読む
        right = parseTerm()
        left = Node(op, left, right)
    return left

手書きでき、エラーメッセージを作り込めるので、実用的なコンパイラの多くは自動生成でなく手書きの再帰下降を使う（GCC、Clang、Rust など）。

左再帰（expr → expr + term）をそのまま書くと無限再帰になるので、上のようにループに書き換える。

曖昧さ#

if a then if b then x else y

else がどちらの if に付くか（dangling else）。文法が曖昧だと解析木が一意に決まらない。

対処は文法の書き換えか、「最も近い if に付ける」といった規則の追加。

参考文献#

Alfred V. Aho, Monica S. Lam, Ravi Sethi, Jeffrey D. Ullman. Compilers: Principles, Techniques, and Tools, 2nd ed. Pearson, 2006.
Robert Nystrom. Crafting Interpreters. Genever Benning, 2021.（全文公開） https://craftinginterpreters.com/
Bryan Ford. Parsing Expression Grammars: A Recognition-Based Syntactic Foundation. POPL, 2004. https://doi.org/10.1145/964001.964011