構文解析とは（全体像）
構文解析（パーシング）は、文字の並びを「文法の組み立て図（構文木）」に変える処理のこと。プログラムを機械語に翻訳するコンパイラは、まず文を単語に切り分け（字句解析）、次にその単語の並びが文法どおりかを調べて木の形に組み立てる——この後半が構文解析だ。
つまり順番は「字句解析（単語に切る）→構文解析（文法の形に組み立てる）」。この2つは別の段階なので、混同しないことが大事だ。
組み立て方には2つの方向がある。
- LL（トップダウン） … 文法のルールを上から下へ展開していく。
- LR（ボトムアップ） … 単語を下から上へ組み上げていく。
詳しく：このLLとLRの違いだけ覚えれば戦える
ここが記事の心臓部。2つのやり方を比べる。
LLとLRの違い
| LL（トップダウン） | LR（ボトムアップ） | |
|---|---|---|
| 向き | 上から下へ展開 | 下から上へ組み上げ |
| 対応できる文法 | せまめ | 広い（より強力） |
| 作りやすさ | 手書きしやすい（再帰下降） | ツールで生成（yacc等） |
いちばん大事なのが、対応できる文法の広さはLRのほうが上だということ。LLは「上から素直に展開できる文法」しか扱えないが、LRは下から組み上げるぶん、もっと複雑な文法まで扱える。ここが試験の狙い目で、「広いのはLR」と正しく押さえれば確実な得点源になる。
一方、作りやすさ・読みやすさはLLが上。LLは再帰下降パーサという形で手書きしやすく、動きも追いやすい。だから「LL＝書きやすい／LR＝広い文法に強い」と整理する。
なお、LL(k)・LR(k)のkは「何個先まで単語を読んでから判断するか（先読みの数）」を表す。
そして、構文解析の成果物が構文木（抽象構文木・AST）。これは、文の構造を木の形にしたもので、このあとの翻訳・最適化の入力になる。
わかりやすく言い換えると
要するに、構文解析は「文を文法の組み立て図にする」ことだ。
LLとLRは、プラモデルの作り方の違いにたとえられる。
①LL（トップダウン） … 完成図（全体）を見ながら、上から順に部品を当てはめていく
②LR（ボトムアップ） … 手元の小さな部品から、下から順に組み上げていく
つまり、組み上げ式のLRのほうが、変わった形（複雑な文法）にも柔軟に対応できる——というイメージだ。
試験のツボ
🔴 一番出る：LLとLRの向きと表現力
①LL＝トップダウン（上から展開）
②LR＝ボトムアップ（下から組み上げ）
③対応できる文法はLRのほうが広い（強力）
🔴 次に出る：段階と成果物
①字句解析（単語に切る）→構文解析（文法に組み立てる）の順
②成果物は構文木（抽象構文木・AST）
🟡 押さえると安定：先読みと作りやすさ
①LL(k)・LR(k)のkは先読みする単語の数
②LLは手書きしやすい（再帰下降）、LRはツールで生成
よくある間違い
①「LLのほうがLRより広い文法に対応できる」→ ✗ 逆。広い文法に対応できるのはLR（ボトムアップ）。
②「構文解析は単語に切り分ける処理である」→ ✗ 単語に切るのは字句解析。構文解析はその後、文法の形に組み立てる段階。
③「LL(k)のkは構文木の深さを表す」→ ✗ kは先読みする単語の数。深さではない。
試験での出題パターン
実際の問題でたしかめてみよう。
オリジナル問題1（LLとLRの表現力）
構文解析のLL法とLR法に関する次の記述のうち、正しいものはどれか。
- LL法は下から上へ組み上げる方式で、LR法より広い文法に対応できるとされる
- LL法もLR法も対応できる文法の範囲はまったく同じで、違いは存在しない
- LR法は下から上へ組み上げる方式で、LL法より広い文法に対応できる方式だ
- LR法は上から下へ展開する方式で、手書きの再帰下降に最も向いている方式だ
解答は 3 だぜ。
LR法は下から上へ組み上げる方式で、LLより広い文法に対応できる（より強力）。LLは上から展開する手書きしやすい方式だ。
選択肢1はLLを「下から・LRより広い」とする誤り。選択肢2は「違いがない」が誤り。選択肢4はLRを「上から・再帰下降向き」としているが、それはLLの特徴だぜ。
| 選択肢 | 判定 | 理由 |
|---|---|---|
| 1 | ✗ | LLは上から、広いのはLR |
| 2 | ✗ | 対応範囲に違いがある |
| 3 | ✓ | LRは下から組み上げ・より広い文法に対応 |
| 4 | ✗ | 上から・再帰下降はLLの特徴 |
オリジナル問題2（段階）
字句解析と構文解析の関係に関する次の記述のうち、正しいものはどれか。
- 字句解析で単語に切り分けたあと、構文解析で文法の形（構文木）に組み立てる
- 構文解析で単語に切り分けたあと、字句解析で文字を1つずつ読み込んでいく
- 字句解析と構文解析はまったく同じ処理で、呼び名が二つあるだけのものである
- 構文解析は機械語を生成する最終段階で、文法の確認とは関係のない処理である
解答は 1 だぜ。
順番は「字句解析（単語に切る）→構文解析（文法の形に組み立てる）」だ。構文解析の成果物が構文木（AST）になる。
選択肢2は字句解析と構文解析が逆。選択肢3は「同じ処理」が誤り。選択肢4は「機械語を生成する最終段階」が誤りで、構文解析は文法を組み立てる段階だぜ。
| 選択肢 | 判定 | 理由 |
|---|---|---|
| 1 | ✓ | 字句解析→構文解析の順で正しい |
| 2 | ✗ | 役割が逆 |
| 3 | ✗ | 別々の段階である |
| 4 | ✗ | 構文解析は文法を組み立てる段階 |
オリジナル問題3（先読みと成果物）
構文解析の用語に関する次の記述のうち、正しいものはどれか。
- LL(k)のkは生成される構文木の深さを表し、深いほど高速に解析できるとする
- 構文解析の成果物は単語の一覧表だけで、構文木は作られることがないとされる
- LR(k)のkは扱える演算子の種類の数を表し、多いほど文法が単純になるとする
- LL(k)やLR(k)のkは先読みする単語の数で、成果物は構文木（AST）だ
解答は 4 だぜ。
LL(k)・LR(k)のkは「何個先まで単語を読んでから判断するか（先読みの数）」、そして構文解析の成果物は構文木（AST）だ。
選択肢1はkを「構文木の深さ」とする誤り。選択肢2は「構文木は作られない」が誤り。選択肢3はkを「演算子の種類」とする誤りだぜ。
| 選択肢 | 判定 | 理由 |
|---|---|---|
| 1 | ✗ | kは先読み数で深さではない |
| 2 | ✗ | 成果物は構文木 |
| 3 | ✗ | kは先読み数 |
| 4 | ✓ | kは先読み数・成果物は構文木 |
まとめ
押さえどころ
- 🔴 LLとLR ＝ LLは上から展開（手書きしやすい）、LRは下から組み上げ（広い文法に強い）。
- 🔴 段階と成果物 ＝ 字句解析→構文解析の順。成果物は構文木（AST）。
- 🟡 先読み ＝ LL(k)・LR(k)のkは先読みする単語の数。
次に学ぶ
- BNF記法・EBNF ── 構文解析が読み取る「文法そのもの」を表す記法。BNFで書いた文法を、構文解析が木に変える、という流れでつながる。
- 正規表現 ── 構文解析の前段（字句解析）で単語を切り出すのに使われる。解析の全体像が見えてくる。
執筆: SikakuQuest編集部