曖昧な文法のLRパース

多くのプログラミング言語は，以下のような文法規則を持っている．
```
    
```
```
                
```
```
                
```
この文法により以下のようなプログラムを許す．
if a then if b then s1 else s2
このプログラムは，以下のように 2 種類に解釈することができる．
1. if a then { if b then s1 else s2 }
2. if a then { if b then s1 } else s2
ほとんどのプログラミング言語では else は，最も近い位置にある then にマッチしなければならない．そのため (1) の解釈が正しいことになる．

LR パース表では，シフト-還元 conflict を生じる．

$S\rightarrow\:if\:\:E\:\:then\:\:S.$

$\:\:\:\:\:\:else$

シフトは (1) を意味し，還元は (2) を意味する．

曖昧さは，以下のように非終端記号

(matched statement)，

(unmatched statement) を導入することにより削除することができる．

$S\rightarrow\:M$

$S\rightarrow\:U$

しかし，文法を書き換えることなしに，シフト-還元 conflict を我慢し，文法を変更しないようにすることができる．
この conflict のときは，(1) になるように，シフトしようとしなければならない．
この場合は (ここでの dangling-else のようにな場合，73ページに述べるように演算子の優先順位など)，よく知られたことである．
多くのシフト-還元 conflicts ，還元-還元 conflicts は，パース表の上でごまかすべきではない．それらはすべて，間違って指定した文法の兆しであり，曖昧を削除することにより解決すべきである．

平成12年8月22日