パース（構文解析）
入力を形式文法に従って解析し、AST（抽象構文木）を組み立てる処理。コンパイラ、クエリ解析、JSON/XMLの読み込み、正規表現エンジンの土台になる。
処理は三層に分かれる。文字をトークンにする字句解析（レキサ）、トークンからASTを作るパーサ、型チェックなどを行う意味解析だ。代表的な方式は、手書きで現代では主流の再帰下降、トップダウンのLL(k)、ボトムアップのLR(k)（yacc/bison）、ANTLRなどのPEG、演算子優先順位に強いPrattパーサである。近年のツールにはtree-sitter（増分パーサ。Neovim、Atom、GitHubが採用）、Rustのnom、PythonのLarkなどがある。LLMの時代になって、出力をパースすること自体が一つの技術分野になった（JSONモード、関数呼び出し、BNFで制約した生成）。