yacc

ほげほげ

ちょっとメモしますよ

定義

%%
add:
    mul 
  | add '+' mul 
  | add '-' mul 
  ;
mul:
    una 
  | mul '*' una 
  | mul '/' una 
  ;
una:
    pri 
  | '+' una 
  | '-' una 
  ;
pri:
    '1' 
  | '(' add ')' 
  ;

ルール

ルールには $accept: add $end が追加される。（%start がないから、最初の非終端が $accept と $end で挟まれる。）

$accept: add $end
add: mul
add: add '+' mul
add: add '-' mul
mul: una
add: mul '*' una
add: mul '/' una
una: pri
una: '+' una
una: '-' una
pri: '1'
pri: '(' add ')'

終端

終端は、以下の 8 個

$end '(' ')' '*' '+' '-' '/' '1'

非終端

非終端は、以下の 5 個

$accept add mul una pri

非終端の最初に出現する非終端をまとめる

たとえば、 add のルールは三つあり、その先頭に出てくる非終端は mul と add の二つ。

$accept: add
add: mul add
mul: una mul
una:pri 
pri: 

これの推移閉包を求める。推移閉包は、a→b、 b→c という情報があるときに a→b 、 b→c、 a→c のようにを求めるようなこと。詳しくは wikipedia:推移閉包 を。

$accept: add mul una pri
add: add  mul una pri
mul: mul una pri
una: pri 
pri:

ルールを網羅的にしたようなもの（？）を作る

$accept:
    add $end
  | mul
  | add '+' mul
  | add '-' mul
  | una
  | mul '*' una
  | mul '/' una
  | pri
  | '+' una
  | '-' una
  | '1'
  | '(' add ')'
  ;

add:
    mul
  | add '+' mul
  | add '-' mul
  | una
  | mul '*' una
  | mul '/' una
  | pri
  | '+' una
  | '-' una
  | '1'
  | '(' add ')'
  ;

mul:
    una
  | mul '*' una
  | mul '/' una
  | pri
  | '+' una
  | '-' una
  | '1'
  | '(' add ')'
  ;

una:
    pri
  | '+' una
  | '-' una
  | '1'
  | '(' add ')'
  ;

pri:
    '1'
  | '(' add ')'
  ;

パーサの最初の状態を考える

読み込んでる場所は ドットで書く
まず最初

. add $end

つまりこれは

. add $end
. mul
. add '+' mul
. add '-' mul
. una
. mul '*' una
. mul '/' una
. pri
. '+' una
. '-' una
. '1'
. '(' add ')'

でもある
ここから次の状態を考える
例えば '+' が来た場合は、

'+' . una

つまり

'+' . una
. pri
. '+' una
. '-' una
. '1'
. '(' add ')'

add が来た場合は

add . $end
add . '+' mul
add . '-' mul

という感じで、求められるだけ求める。
この場合は 22 個の状態ができた。

先読みをしなければならない場所を考える

パーサは、状態遷移の過程をスタックに push しながら、終端を読んでは状態遷移して、ドットが最後にあるルールが一つだけある状態になったらスタックをポップして状態を戻して、今度はそのルールの非終端を使って状態遷移をするということを繰り返す。
最後にドットがあるルールと他のルールが組み合わされている場合は、コンフリクトするので先読みをしなければならない。
たとえば、以下のような状態の場合（reduce/reduce conflict）

hoge piyo .
fuga piyo .

または（shift/reduce conflict）

hoge piyo .
piyo . hoge

先読みの情報は、ルールと終端のセットになる。

hoge piyo . ('+', '-')
fuga piyo . ('*', '/')

のような感じだ
先読みは、状態を走査して非終端をシフトするところを探せばいい。

概念はこんな感じか。

でも、表にする意味を感じないな。
この状態遷移情報をオブジェクトにするだけでいいんじゃないかな。

あれちょっと違うな

状態を作るところが違うっぽいな
あ。やっぱあってるか。
状態には、元々のアイテムと追加されたアイテムが含まれるってところがポイントか
（つづく）