単純なマーク付けがなされた文字列の解析 #6

bisonはLR項の集合をノードとするGOTOグラフをDOT形式で出力するオプション-gを持っている。
例えば#3のparser.yからGOTOグラフを出力し、そのままdotコマンドで画像化すると結構大きいサイズになる。
GOTOグラフのノードの中にLR項の集合の全要素、つまり属するLR項全てが書かれており、
LR項の文字表現での長さは生成規則の文字表現での長さを反映するので、
文法記号の文字表現が無駄に長いparser.yからの出力では、やたら横に伸びた図となるからだ。
内容が見えなくなることを承知で縮小すると、

$ bison -y -gparser.gv -o/dev/null parser.y
$ dot -Gsize=9.597,3.048 -T png -o parser_shrink.png parser.gv

のような感じで楕円ノードの離心率が大きい。
このDOTファイルのノードは、

parser.gv

digraph Automaton {
  0 [label="0\n$accept -> . text $end"]
  0 -> 1 [style=solid label="STRING_EXCEPT_PARENTHESIS"]
...snip

のように、name属性が0から割り振られた状態番号で、
label属性は最初に状態番号、その後に属しているLR項が\n区切りで列挙されている。
とりあえず、gvprでノードのラベルを状態番号だけに整形する。

shrink.g

N {
  label = gsub(label, '\\\\n', '\n    ');
  printf(2, '%s\n', label);
  label = name;
}

このgvprプログラムは、標準出力に整形したグラフを出力するとともに、
標準エラーに各状態に属するLR項をコンソールにリストアップするフィルタとして使う。

$ gvpr -cf shrink.g parser.gv | dot -T png -o parser.png
0
    $accept -> . text $end
1
    string_headed -> STRING_EXCEPT_PARENTHESIS .
    string_headed -> STRING_EXCEPT_PARENTHESIS . $@1 marked_string_headed
2
    marked_string -> '(' . STRING_EXCEPT_PARENTHESIS ')'
3
    $accept -> text . $end
4
    text -> string_headed .
5
    text -> marked_string_headed .
6
    marked_string_headed -> marked_string .
    marked_string_headed -> marked_string . marked_string_headed
    marked_string_headed -> marked_string . string_headed
7
    string_headed -> STRING_EXCEPT_PARENTHESIS $@1 . marked_string_headed
8
    marked_string -> '(' STRING_EXCEPT_PARENTHESIS . ')'
9
    $accept -> text $end .
10
    marked_string_headed -> marked_string string_headed .
11
    marked_string_headed -> marked_string marked_string_headed .
12
    string_headed -> STRING_EXCEPT_PARENTHESIS $@1 marked_string_headed .
13
    marked_string -> '(' STRING_EXCEPT_PARENTHESIS ')' .

少し小さくなった。
実線のエッジが終端記号、破線のエッジが非終端記号による状態遷移を表す。
非終端記号のひとつ$@1が仕切り用にbisonが導入した文法記号である。
リストアップされたLR項で見ると、

...snip
1
...snip
    string_headed -> STRING_EXCEPT_PARENTHESIS . $@1 marked_string_headed
7
    string_headed -> STRING_EXCEPT_PARENTHESIS $@1 . marked_string_headed
...snip

であり、. $@1から$@1 .に移っていることから分かるように、
これがGOTOグラフにおける状態1から状態7への$@1による遷移に相当する。