context-free-grammar - オートマトンを文脈自由にプッシュダウンする：それを行う方法は？

Question

生成するCFGを次のオートマトンに書き込む必要があります。

私はこのような移行を知っています：

-es, es; S lead to a rule like S-> es
-es, B; es lead to a rule like B -> es
-es, B; aB lead to a rule like B-> aB

esは空の文字列を表します。

しかし、私は「c、a;a」のようなルールをどのように扱うかを知りません。誰でも私に助けを与えることができますか？ありがとうございました。

score 0 · Accepted Answer

一般的に言えば、各プロダクションは、そのプロダクションを通じてパーサーの進行状況を示す有限状態マシンです。

オートマトンが使用するスタックは、このような生産状態のスタックです。プロダクションに降りるたびに、その初期状態にプッシュします。1 つを終了するたびに、現在の最終状態をオフにします。端末は、ステートマシンが単一の状態を持つ縮退プロダクションと見なすことができます。

1 に答える 1