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”这样的规则。任何人都可以给我任何帮助吗？谢谢你。

http://tonguim.free.fr/divers/automata.jpg

Answer 1

一般来说，每个产生式都是一个有限状态机，它显示解析器通过该产生式的进度。

自动机使用的堆栈就是这样的生产状态的堆栈。每次你进入一个生产，你推动它的初始状态。每次你结束一个，你就会弹出它现在的最终状态。终端可以被视为状态机具有单一状态的退化产品。