parsing - LR パーサー reduce/reduce (YACC など)

Question

次の文脈自由文法があると仮定すると、その特定の順序で (YACC の場合):

• z→x
• z → zx

次の入力がある場合：

(z (zx

パーサーは削減しますか:

1. 「x」から「z」
2. 「z x」から「z」

私はその2番だと思っていますが、その理由はよくわかりません。どうもありがとう

編集：明確にするために入力を変更しました

Answer 1

あなたの文法は左再帰的であるため、左結合です。左連想とは、入力が左から右にスキャンされるときに生成が貪欲に行われることを意味します。別のものをスキャンして縮小することによりz、より長く拡張された a が常にあります。zx

あなたの質問に関しては、入力z z xは終端記号で構成されているため、入力を行うことはできません。おそらくx終端記号です (それ以外の場合、文法は不完全です)。zは明らかに非終端です。

部分文形を考えることができますz z x。しかし、そのような形式はこの文法では生成できません。

から始めてz、次のステップは を生成するx(したがって終了する) または を生成することz xです。その後の次の可能なステップはz、2 つの方法のいずれかで を置き換えることです: 生成x x(および終了) または を生成しz x xます。

ご覧のとおりz z x、これらのルールでは文字列に到達できません。