3

Niklaus Wirth のCompiler Constructionを読もうとしています。x*(y+z)23 ページで、次の文法が与えられた場合に LALR がどのように式を解析するかを説明し始めます。

E  = T  | E "+" T. expression 
T  = F  | T "*" F. term 
F  = id | "(" E ")". factor

彼は続けて、削減を次のように示しています。

     Action   Stack     Remaining
1             x         * (y + z) 
2    S        x         * (y + z) 
3    R        F         * (y + z) 
4    R        T         * (y + z) 
6    S        T*          (y + z) 
7    S        T*(          y + z) 
8    S        T*(y           + z) 
9    R        T*(F           + z) 
10   R        T*(T           + z) 
11   R        T*(E           + z) 
12   S        T*(E+            z) 
13   S        T*(E + z          ) 
14   R        T*(E + F          ) 
15   R        T*(E + T          ) 
16   R        T*(E              ) 
17   S        T*(E) 
18   R        T*F 
19   R        T 
20   R        E

アクションが S (シフトの場合) または R (リダクションの場合) である場合、わかりやすくするために行番号を追加しました。というわけで、1から4までと4から20まではわかると思いますが、4自体はわかりません。たとえば、ステップ 1 は x をスタックにプッシュします。x はルール 'F' の RHS を表すため、還元が発生します -> F. F はルール 'T' の最初の "OR" を表し、別の還元が発生する可能性があります -> T. それが正しい場合 (私はそうではありません)確かにそうですか?)、では、T はルール「E」の RHS の最初の「OR」を表すため、T も E に置き換えないのはなぜですか。ルール E には、いわば暗黙の「EOF」があるためでしょうか (そして、EOF に達していないため、それを減らすことはできません)。それとも、この時点であいまいだからですか (T は、ルール T の RHS の 2 番目の「OR」の最初の部分も表します ... つまり、T "*" F)? それとも、まったく別のものですか？

ありがとう！

4

1 に答える 1

5

パーサーは2つの基準を使用して、次に実行するアクション（シフトまたは削減）を決定します。1つ目は、スタック上のトークンがプロダクションの右側と一致する場合です。ステップ4の後、スタックのTはE = Tの生成と一致するため、それが唯一の基準である場合、その時点で減少する可能性があります。ただし、パーサーは先読み（つまり、「残り」の最初のトークン）も調べて、実行するアクションを決定します。接頭辞としてE"*"を使用するルールはないため、削減は無効であり、唯一のアクションはシフトです。ステップ20の後、E = Tの生成は有効です。これは、（ご想像のとおり）先読みトークンが事実上EOFであり、これが一致するためです。

一部のあいまいな文法では、shiftアクションとreduceアクションの両方が有効になる可能性があることに注意してください。これらの場合、バイソンは「シフト」を支持して解決します。詳細については、Bisonのドキュメントを参照してください。ただし、上記の文法はあいまいではありません。先読みのトークン1つで、明確にすることができます。

于 2011-03-29T03:39:20.110 に答える