素人プログラマーRYOの勉強日誌。


by R-STUDY

構文解析における、elseの扱い

文法にあいまいさがあると、LR 構文解析ができなくなるので、yacc は警告メッセージをだす。メッセージには2種類あり、 shift/reduce conflict, reduce/reduce conflictがある。shift/reduce conflictとは、文法規則が shift(つまり、さらに長い非終端記号にreduceできる)なのか、reduce(そこで打ち切って、非終端記号にしてしまう)か、解釈ができることを示す。この conflictは一概に文法定義が間違っているということではない場合がある。有名な例として、IF文の定義がある。

statement : IF '(' expression ')' statement
| IF '(' expression ')' statement ELSE statement
....;

これは次の場合にあいまいになる。
if (a > 0)
if (b > 0) c = 100;
else
c = 2000;

else を読んだとき、この token は内側の if 文の一部であると考え、遷移すればよいのだろうか、それとも、内側のif 文は完了したと考え、還元して、読みこんだ else は外側の if 文の一部であるとして遷移すればよいのだろうか?一般に yacc は、shift/reduce conflict がおきたときには、例外条件として、遷移(shift)を優先させる。したがって上のelse は内側の if 文の一部と解釈される。この解釈は、C 言語を始めほとんどの言語の仕様と一致するので、一般にif 文にまつわる shift/reduce conflict はそのままにしておいて問題ない。
[PR]
by R-STUDY | 2005-10-16 05:05 | 勉強メモ