構文解析 とは？

一般的なコンパイラの説明ではそうだよ。字句解析が識別子や数値、記号などのトークンを切り出し、構文解析がその並びを文法に照らして読み取る。入力から式や文の構造を見つける役割なんだ。

代入を許す言語の例として「x = 3 + 5;」を考えよう。左側のxに、右側の3と5を足した式を代入する構造だね。「代入」の下にxと「加算」、加算の下に3と5を置いた木で表せるよ。図はその構造を簡略化したASTなんだ。

構文木は文法による組み立てを表す木で、ASTは後の処理に必要な構造を中心に表す木だよ。図のASTではセミコロンなどの記号を省いている。実際のノード名や省く情報は言語や実装による。LLVMの入門例でも、式の種類ごとのノードを後のコード生成に使っているよ。

どちらも入力を左から読むよ。LLは左端導出で、開始記号から展開し、木を上から下へたどる方法。LRは右端導出を逆順にたどり、読んだトークンを規則に従って還元する下からの方法だよ。右端導出という名前でも、入力を右から読むわけではない。BisonはLR系などのパーサーを生成できるんだ。

構文が正しくても、変数が見つからないなど、別の確認でエラーになることがあるよ。構文エラーから回復して次の誤りを調べる仕組みもあるけれど、対応はパーサー次第。Tree-sitterは編集のたびに木を更新し、構文エラーがあっても有用な結果を得ることを目指すツールだね。