優先順位付け LR(k) 構文解析表

LR(0) の状態集合から LALR(1) の先読み集合を求めることができるので、それらを組み合わせて LALR(1) オートマトンのための構文解析表を作るのは、衝突さえ生じないなら簡単にできます。還元-還元衝突は致命的なエラーとして扱うとし、LALR(1) 文法でシフト-還元衝突を避ける生成規則を作り込むのは、労多いだけの面倒ごとなので、Yacc 以来の伝統で優先順位付け構文解析を組み合わせるのが当たり前になっています。

%token N
%left '+'
%left '*'
%%

e : e '+' e   %prec '+'
  | e '*' e   %prec '*'
  | '(' e ')'
  | N
  ;


優先順位付け構文解析では、終端記号に優先順位と左右の結合性の属性を持たせて、生成規則ごとに優先順を与えた終端記号を設定しておきます。これまた Yacc 以来の伝統で、生成規則ごとの優先順を指定する終端記号の修飾子は省略することができて、そのときは生成規則に現れる最後の終端記号を使います。上の場合なら、%prec '+' 等を省略するのが慣例になっています。

さて、この構文で優先順位がついていないならば、 LALR(1) 構文解析表を作ろうとすると、次のように状態 7 と 8 でシフト-還元衝突が生じます。

state 0 {[start->.e], [e->.e+e], [e->.e*e], [e->.(e)], [e->.N]}
  '(' => SHIFT 2
   N  => SHIFT 3
   e  => GOTO 1

state 1 {[start->e.], [e->e.+e], [e->e.*e]}
  '+' => SHIFT 4
  '*' => SHIFT 5
   $  => ACCEPT

state 2 {[e->(.e)], [e->.e+e], [e->.e*e], [e->.(e)], [e->.N]}
  '(' => SHIFT 2
   N  => SHIFT 3
   e  => GOTO 6

state 3 {[e->N.,+/*/)/$]}
  '+' => REDUCE E->x
  '*' => RECUDE E->x
  ')' => REDUCE E->x
   $  => REDUCE E->x

state 4 {[e->e+.e], [e->.e+e], [e->.e*e], [e->.(e)], [e->.N]}
  '(' => SHIFT 2
   N  => SHIFT 3
   e  => GOTO 7

state 5 {[e->e*.e], [e->.e+e], [e->.e*e], [e->.(e)], [e->.N]}
  '(' => SHIFT 2
   N  => SHIFT 3
   e  => GOTO 8

state 6 {[e->(e.)], [e->e.+e], [e->e.*e]}
  ')' => SHIFT 9
  '+' => SHIFT 4
  '*' => SHIFT 5

state 7 {[e->e+e.,+/*/)/$], [e->e.+e], [e->e.*e]}
  '+' => SHIFT 4 / REDUCE e->e+e CONFLICT
  '*' => SHIFT 5 / REDUCE e->e+e CONFLICT
  ')' => REDUCE e->e+e
   $  => REDUCE e->e+e

state 8 {[e->e*e.,+/*/)/$], [e->e.+e], [e->e.*e]}
  '+' => SHIFT 4 / REDUCE e->e*e CONFLICT
  '*' => SHIFT 5 / REDUCE e->e*e CONFLICT
  ')' => REDUCE e->e*e
   $  => REDUCE e->e*e

state 9 {[e->(e).,+/*/)/$]}
  '+' => REDUCE e->(e)
  '*' => REDUCE e->(e)
  ')' => REDUCE e->(e)
   $  => REDUCE e->(e)

衝突がおきている状態 7 と 8 では、動作決定用の終端記号 a と、還元で使う生成規則の終端記号 r の両方に優先順位が付いているので、衝突を解決することができます。

state 7 {[e->e+e.,+/*/)/$], [e->e.+e], [e->e.*e]}
  a=(%left '+' 1) => SHIFT 4 / REDUCE e->e+e %prec r=(%left '+' 1) CONFLICT
  a=(%left '*' 2) => SHIFT 5 / REDUCE e->e+e %prec r=(%left '+' 1) CONFLICT

state 8 {[e->e*e.,+/*/)/$], [e->e.+e], [e->e.*e]}
  a=(%left '+' 1) => SHIFT 4 / REDUCE e->e*e %prec r=(%left '*' 2) CONFLICT
  a=(%left '*' 2) => SHIFT 5 / REDUCE e->e*e %prec r=(%left '*' 2) CONFLICT

2 つの終端記号 a と r を比較して、シフトか、還元か、もしくはエラーかの選択は、演算子優先順位構文解析法と同じ方法でおこなえます。a に優先順位がついていないか、または、r についてないときは、Yacc のデフォルト動作に合わせて、シフトを選択した上で警告メッセージを出力するようにすれば良いでしょう。エラーのときは、シフトも還元もせずに、エラー処理をおこなうようにします。それ以外のときは、シフトか還元のいずれか一方を選びます。

Precedence = Struct.new(:assoc, :score)
PREC = {'+' => Precedence[:left, 1], '*' => Precedence[:left, 2]}

def resolve_shift_reduce_conflict(a, r)
  return :default if not PREC.key?(a) or not r  or not PREC.key?(r)
  if PREC[a].score < PREC[r].score
    :reduce
  elsif PREC[a].score > PREC[r].score
    :shift
  elsif PREC[r].assoc == :left
    :reduce
  elsif PREC[r].assoc == :right
    :shift
  else
    :error
  end
end

これで選択すると、 状態 7 の * 記号だけシフトになり、他は還元を選びます。

state 7 {[e->e+e.,+/*/)/$], [e->e.+e], [e->e.*e]}
  '+' => REDUCE e->e+e
  '*' => SHIFT 5

state 8 {[e->e*e.,+/*/)/$], [e->e.+e], [e->e.*e]}
  '+' => REDUCE e->e*e
  '*' => REDUCE e->e*e