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

#1と#3で示した二種類の構文規則からyacc/bisonが生成した構文解析器に関して、
yacc/bisonは-vオプションを付けると、
構文規則から導かれるLR項の集合を個々の状態とする、
構文解析に伴う解析器の状態遷移の詳細を得ることができる。
この詳細によれば、#1の構文規則を実装した#2のparser.yから得られる解析器には18個の状態が存在し、
#3の構文規則を実装した解析器には14個の状態が存在することが分かる。
#1から#3への構文規則の変更で構文解析器は4状態分複雑度が減じているといえる。

正確に言えば、この状態数は#1や#3の構文規則そのものから得られるものより多くなる。
なぜなら、これらを実装したparser.yにおいて生成規則の途中にアクションが置かれているものが一つあるからである。
このような規則があるとyacc/bisonは仕切り用の非終端記号を一個導入して規則を書き換え、
この非終端記号を空列から生成する規則を構文規則に加える。
この加えられた単一生成規則による還元が行われるときにアクションが実行される。
これがyacc/bisonにおいて生成規則の途中でアクションを置くことができる便利書法の正体である。
このような非終端記号で元の構文規則を分割し意味動作を与えやすくする手法は太古からあった。
yacc/bisonは人間がそのためだけにわざわざ構文規則を変更しなくても機械的にそれを行ってくれる。

実際にアクション抜きで純粋に#1や#3のBNFで表した構文規則だけを記述したもの

%token CHAR_EXCEPT_PARENTHESIS

%%

text : string_headed | marked_string_headed ;
string_headed : string | string marked_string_headed ;
marked_string_headed : marked_string | marked_string marked_string_headed | marked_string string_headed ;
marked_string : '(' marked_string_body ')' ;
string : CHAR_EXCEPT_PARENTHESIS | string CHAR_EXCEPT_PARENTHESIS ;
marked_string_body : CHAR_EXCEPT_PARENTHESIS | marked_string_body CHAR_EXCEPT_PARENTHESIS ;

や

%token STRING_EXCEPT_PARENTHESIS

%%

text : string_headed | marked_string_headed ;
string_headed : STRING_EXCEPT_PARENTHESIS | STRING_EXCEPT_PARENTHESIS marked_string_headed ;
marked_string_headed : marked_string | marked_string marked_string_headed | marked_string string_headed ;
marked_string : '(' STRING_EXCEPT_PARENTHESIS ')' ;

から構文解析器を生成すると、#1は17状態、#3は13状態となり、1個ずつ状態数が減っている。
以上の話での状態数はyacc/bisonによる一実現でのものなので、最小状態数なのかどうかは別の話だが、
もし最小の状態数でないとしてもそれほど遠くはないだろう。