1
私はDFAに文脈自由文法を変換する方法については、この記事を見てきました： Automata theory : Conversion of a Context free grammar to a DFAすべての文脈自由文法をNFA/DFAに変換できますか？
しかし、思っ全ての文脈自由文法は、DFA/NFAに変換することができますか？正規表現として表現できない文脈自由文法はどうですか？ Ex。 S - >（S）| （）
ありがとう！
http://hackingoff.com/images/basic-bottom-up-parser/2016-12-13_18-37-59_-0800-dfa.svgちょうどこれを見て、今少しLRのDFAについて混乱させる0）パーサ。 DFA for LR（0）パーサーは文脈自由文法の変換ですか？それとも、LR（0）パーサー（複数の仕上げ状態）を構築するのに役立つのでしょうか？ – ssssay
@ssssay：このページではDFAとしてのグラフについて説明していますが、LRパーサを駆動するのは実際にはF（有限）ではないPDA（プッシュダウンオートマトン）です。プッシュトランジションは表示されず、「受け入れ」状態は実際にはポップトランジション（ポップトランジションはスタックの内容に依存するためグラフ化できません）です。そうであることは容易にわかります。そのマシンを使用して実際に入力を処理するだけです。 （また、すべてのCFGがLR（0）またはLR（k）であるとは限りません）。 – rici