compiler-construction - LR オートマトンは実際にどのように機能しますか?

Question

この LR(0) オートマトンでは

非端末にもトランジションがありますが、わかりません。入力がaab. それからあなたはただの状態になってしまうでしょうA->a·。入力またはその他の入力によって到達した状態を視覚化する場合aab、それらの間にアークがない状態間の遷移はありませんか?

これが、開始状態から開始し、受け入れ状態に到達するまでオートマトンのアークに沿ってのみ移行する DFA や NFA と異なる理由がわかりません。

Answer 1

LR オートマトンは、DFA のように単一の現在の状態ではなく、状態のスタックを使用するプッシュダウン オートマトンです。アクション (shift、reduce、goto) は、現在スタックの一番上にある状態によって管理されます。shift と goto は新しい状態をプッシュし、reduce ルールに基づいて一定数の状態をポップします。あなたの例では、列の状態に番号を付けると (0 は左上の初期状態、3 は中央の列の状態)、入力文字列 'ab' を解析する方法を示すことができます。

Action              Stack
initial state       0
shift a             0 1
reduce A->a         0
goto A              0 3
shift b             0 3 4
reduce B->b         0 3
goto B              0 3 5
reduce S->AB        0
goto S              0 2
accept

これは LR(0) パーサーであるため、各状態には shift/goto アクションまたは単一の reduce アクションのいずれかがあり、次に何をすべきかを知るために先読みは必要ありません (ただし、入力トークンを消費するシフトはそれに依存します)どの状態に移行するかを決定するためのトークン)。

入力 'aab' の場合、プロセスは少しだけ長くなります。

Action              Stack
initial state       0
shift a             0 1
reduce A->a         0
goto A              0 3
shift a             0 3 1
reduce A->a         0 3
goto A              0 3 3
shift b             0 3 3 4
reduce B->b         0 3 3
goto B              0 3 3 5
reduce S->AB        0 3
goto S              0 3 6
reduce B->S         0 3
goto B              0 3 5
reduce S->AB        0
goto S              0 2
accept

は、入力 (B -> S -> AB) 内の複数の a に一致する右再帰規則の効果を示しています。これにより、再帰シーケンスの最後まで、すべての a がシフトされます (スタックに状態がプッシュされます)。その後、一連のreduce/gotoアクションが続き、それらを元に戻します。左再帰ルールを使用する方が優れており、一定量のスタック領域を使用して、シフトと削減を交互に行います。