Skip to content
Published on

[コンパイラ] 07. 構文解析 (2) - Bottom-UpパーシングとLRパーサ

🇰🇷KO🇺🇸EN🇯🇵JA
Split View
Authors

構文解析 (2) - Bottom-UpパーシングとLRパーサ

Bottom-Upパーシングは入力文字列から出発して開始記号に還元していく方式です。LLパーサより広い範囲の文法を処理でき、実際のコンパイラで広く使用されています。

1. Bottom-Upパーシングの概要

基本アイデア

Bottom-Upパーシングは**還元（reduction）**を繰り返して入力文字列を開始記号にします。

入力: id * id + id

還元過程（最右導出の逆順）:
  id * id + id
  F  * id + id     (F -> id)
  T  * id + id     (T -> F)
  T  * F  + id     (F -> id)
  T     + id       (T -> T * F)
  E     + id       (E -> T)
  E     + F        (F -> id)
  E     + T        (T -> F)
  E                (E -> E + T)

これは最右導出を逆順に追跡したものです。

ハンドル（Handle）

ハンドルは還元可能な部分文字列と該当する生成規則の組み合わせです。正しいハンドルを見つけて還元すると開始記号に到達します。

文形式: T * F + id
ハンドル: T * F（生成規則: T -> T * F）
還元結果: T + id

間違ったハンドルを選ぶと開始記号に到達できません。ハンドル選択がBottom-Upパーシングの核心課題です。

2. シフト-還元パーシング（Shift-Reduce Parsing）

シフト-還元パーサはスタックと入力バッファを使用します。

4つの動作

  1. シフト（Shift）: 入力の次のトークンをスタックにpushします。
  2. 還元（Reduce）: スタック頂上のハンドルを生成規則の左辺の非終端記号に置き換えます。
  3. 受理（Accept）: パーシング成功です。
  4. エラー（Error）: 構文エラーが発見されました。

パーシングの例: id * id + id

スタック        入力              動作
$            id * id + id $   シフト
$ id         * id + id $      還元 (F -> id)
$ F          * id + id $      還元 (T -> F)
$ T          * id + id $      シフト
$ T *        id + id $        シフト
$ T * id     + id $           還元 (F -> id)
$ T * F      + id $           還元 (T -> T * F)
$ T          + id $           還元 (E -> T)
$ E          + id $           シフト
$ E +        id $             シフト
$ E + id     $                還元 (F -> id)
$ E + F      $                還元 (T -> F)
$ E + T      $                還元 (E -> E + T)
$ E          $                受理！

シフト-還元の衝突

パーサがシフトするか還元するか決定できない状況が発生することがあります。

  • シフト-還元衝突（Shift-Reduce Conflict）: シフトと還元の両方が可能な場合
  • 還元-還元衝突（Reduce-Reduce Conflict）: 複数の生成規則で還元が可能な場合

これらの衝突を解決することがLRパーシング技法の核心です。

3. LRパーシングの概要

LRパーサは最も強力なシフト-還元パーサです。

LR(k)の意味

  • L: 入力を左から右にスキャン
  • R: 最右導出を逆順に生成
  • (k): k個の先読みトークンを見て決定

LRパーサの構成要素

入力: a1 a2 ... an $

        +---+---+---+---+
スタック: | s0| X1| s1| X2| s2 ...
        +---+---+---+---+

パーシングテーブル:
  ACTION[s, a] = シフト/還元/受理/エラー
  GOTO[s, A]   = 次の状態
  • スタック: 状態と文法記号が交互に積まれます。
  • ACTIONテーブル: 現在の状態と入力トークンに基づいて動作を決定します。
  • GOTOテーブル: 還元後に遷移する状態を決定します。

LRパーシングアルゴリズム

スタックに初期状態s0をpush

loop:
  s = スタック頂上の状態
  a = 現在の入力記号

  case ACTION[s, a]:
    シフト sn:
      aと状態snをスタックにpush
      次の入力記号に進む

    還元 (A -> beta):
      スタックから2*|beta|個の記号をpop
      s' = 新しいスタック頂上の状態
      AとGOTO[s', A]をスタックにpush

    受理:
      パーシング成功、終了

    エラー:
      エラー処理ルーチンを呼び出す

4. LR(0)項目とオートマトン

LR(0)項目（Item）

LR(0)項目は生成規則に**ドット（dot）**を追加したもので、パーシングの進行状態を表します。

生成規則: A -> X Y Z

可能なLR(0)項目:
  A -> . X Y Z    （まだ何も見ていない）
  A -> X . Y Z    （Xを見た状態）
  A -> X Y . Z    （X Yを見た状態）
  A -> X Y Z .    （還元可能！）

クロージャ（Closure）演算

項目集合のクロージャを計算します。

closure(I):
  Iの全項目を結果に追加
  結果にA -> alpha . B beta形式の項目がある場合:
    B -> gammaの全生成規則に対して
    B -> . gammaを結果に追加（まだなければ）
  変化がなくなるまで繰り返す

GOTO演算

goto(I, X):
  Iの中のA -> alpha . X beta形式の項目に対して
  A -> alpha X . betaを集めた集合のclosure

LR(0)オートマトンの構成例

文法:
  E' -> E       （増補文法の開始）
  E  -> E + T
  E  -> T
  T  -> T * F
  T  -> F
  F  -> ( E )
  F  -> id

I0 = closure({E' -> . E}):
  E' -> . E
  E  -> . E + T
  E  -> . T
  T  -> . T * F
  T  -> . F
  F  -> . ( E )
  F  -> . id

goto(I0, E) = I1:
  E' -> E .
  E  -> E . + T

goto(I0, T) = I2:
  E  -> T .
  T  -> T . * F

goto(I0, F) = I3:
  T  -> F .

goto(I0, '(') = I4:
  F  -> ( . E )
  E  -> . E + T
  E  -> . T
  ...

goto(I0, id) = I5:
  F  -> id .

5. SLRパーシングテーブルの構成

**SLR（Simple LR）**パーシングはLR(0)項目とFOLLOW集合を使用します。

SLRパーシングテーブルの構成アルゴリズム

1. 増補文法のLR(0)項目集合Cを構成

2. 項目集合Iiに対して:
   a) A -> alpha . a betaがIiにあり、goto(Ii, a) = Ijの場合:
      ACTION[i, a] = shift j

   b) A -> alpha .がIiにある場合（A != S'）:
      FOLLOW(A)の全aに対して:
      ACTION[i, a] = reduce (A -> alpha)

   c) S' -> S .がIiにある場合:
      ACTION[i, $] = accept

3. goto(Ii, A) = Ijの場合: GOTO[i, A] = j

SLRパーシングテーブルの例

       ACTION                          GOTO
状態 | id  | +   | *   | (   | )   | $ | E | T | F
-----+-----+-----+-----+-----+-----+---+---+---+---
  0  | s5  |     |     | s4  |     |   | 1 | 2 | 3
  1  |     | s6  |     |     |     | acc|   |   |
  2  |     | r2  | s7  |     | r2  | r2|   |   |
  3  |     | r4  | r4  |     | r4  | r4|   |   |
  4  | s5  |     |     | s4  |     |   | 8 | 2 | 3
  5  |     | r6  | r6  |     | r6  | r6|   |   |
  6  | s5  |     |     | s4  |     |   |   | 9 | 3
  7  | s5  |     |     | s4  |     |   |   |   | 10
  8  |     | s6  |     |     | s11 |   |   |   |
  9  |     | r1  | s7  |     | r1  | r1|   |   |
  10 |     | r3  | r3  |     | r3  | r3|   |   |
  11 |     | r5  | r5  |     | r5  | r5|   |   |

ここで s5 はshift 5、r2 はreduce by production 2、acc はacceptです。

6. 正規LR(1)項目

SLRパーサでは処理できない文法があります。正規LR(1)項目は**先読み記号（lookahead）**を追加してより強力なパーシングが可能です。

LR(1)項目の形式

[A -> alpha . beta, a]

- A -> alpha . beta: LR(0)項目と同じ
- a: 先読み記号（この項目で還元する時に参照）

LR(1)クロージャ

closure(I):
  [A -> alpha . B beta, a]がIにある場合:
    B -> gammaの全生成規則に対して
    FIRST(beta a)の全bに対して
    [B -> . gamma, b]を追加

正規LR(1)パーシングの長所と短所

長所: SLRより多くの文法を処理可能
短所: 状態数が非常に多くなる可能性あり
      （LR(0)の数十〜数百倍）

7. LALRパーシング

**LALR（Look-Ahead LR）**は正規LR(1)の強力さとSLRの効率性を折衷した方法です。

核心アイデア

LR(1)項目で**コア（core）**が同じ項目集合を統合します。

LR(1)状態:
  I4: {[C -> .c C, c], [C -> .c C, d], [C -> .d, c], [C -> .d, d]}
  I7: {[C -> .c C, $], [C -> .d, $]}

コアが同じなので統合:
  I47: {[C -> .c C, c/d/$], [C -> .d, c/d/$]}

LALRパーサの特徴

  • 正規LR(1)と同じ数の状態を持つSLRと同じサイズのテーブル
  • SLRより強力で、正規LR(1)より若干弱い
  • ほとんどのプログラミング言語を処理可能
  • YaccとBisonがLALRパーサを生成

SLR、LR(1)、LALRの関係

LR(0)文法 < SLR文法 < LALR文法 < LR(1)文法

実用的な選択:
- 簡単な文法: SLR
- ほとんどのプログラミング言語: LALR (Yacc/Bison)
- 複雑な文法: 正規LR(1)

8. Yaccパーサ生成器

Yacc（Yet Another Compiler Compiler）はLALR(1)パーサを自動生成するツールです。GNU版のBisonが広く使用されています。

Yaccプログラムの構造

宣言部（declarations）
%%
文法規則と動作（grammar rules and actions）
%%
補助C関数（supporting C functions）

Yaccプログラムの例: 電卓

%{
#include <stdio.h>
#include <ctype.h>
int yylex();
void yyerror(const char *s);
%}

%token NUM

%%

line   : expr '\n'          { printf("Result: %d\n", $1); }
       ;

expr   : expr '+' term      { $$ = $1 + $3; }
       | expr '-' term      { $$ = $1 - $3; }
       | term               { $$ = $1; }
       ;

term   : term '*' factor    { $$ = $1 * $3; }
       | term '/' factor    { $$ = $1 / $3; }
       | factor             { $$ = $1; }
       ;

factor : '(' expr ')'       { $$ = $2; }
       | NUM                 { $$ = $1; }
       ;

%%

int yylex() {
    int c = getchar();
    if (isdigit(c)) {
        yylval = c - '0';
        while (isdigit(c = getchar()))
            yylval = yylval * 10 + c - '0';
        ungetc(c, stdin);
        return NUM;
    }
    return c;
}

void yyerror(const char *s) {
    fprintf(stderr, "Error: %s\n", s);
}

int main() {
    return yyparse();
}

Yaccの衝突解決規則

LALRパーシングテーブルに衝突がある場合、Yaccは以下の規則を適用します。

  1. シフト-還元衝突: デフォルトでシフトを選択します（ぶら下がりelse問題を解決）。
  2. 還元-還元衝突: 先に記述された規則で還元します。

Yaccの優先順位指示子

%left '+' '-'       // 左結合、低い優先順位
%left '*' '/'       // 左結合、高い優先順位
%right UMINUS       // 右結合、単項マイナス

これらの指示子を使用すると曖昧な文法も衝突なく処理できます。

9. LRパーサのエラー回復

パニックモード回復

1. スタックからAを処理できる状態が見つかるまでpop
2. 入力からFOLLOW(A)に属するトークンが見つかるまでスキップ
3. GOTO[s, A]をpushしてパーシングを続行

Yaccのエラー回復: errorトークン

stmt : expr ';'
     | error ';'   { yyerrok; printf("Skipping bad statement\n"); }
     ;

error はYaccの特殊トークンで、エラー状況で自動的にマッチします。yyerrok はエラー回復が完了したことを宣言します。

まとめ

概念核心内容
Bottom-Upパーシング入力から出発して開始記号に還元
ハンドル還元する部分文字列と生成規則の組み合わせ
シフト-還元スタックベースの4つの動作（シフト、還元、受理、エラー）
LR(0)項目ドットでパーシング進行状態を表現
SLRLR(0)項目 + FOLLOW集合を使用
正規LR(1)先読み記号を含む項目、最も強力
LALRコアが同じLR(1)状態を統合、実用的
Yacc/BisonLALR(1)パーサ自動生成ツール

LRパーシングはほとんどのプログラミング言語を効率的に処理できる強力な技法です。次の記事では、パーシング結果を活用して意味のある翻訳を行う構文指示翻訳を扱います。

Discuss on Twitter • View on GitHub