私は文脈自由言語を操作するためのツールに取り組んでおり、文法の内部表現は有限オートマトンとして保存されています。EBNF と RegEx をさらに調べてみると、EBNF には「例外」があり、RegEx には否定的な先読みがあることがわかりました。これらが対称差分 NFA によってどのようにモデル化されるかはわかりますが、通常の DFA または NFA の機能を超えているのではないかと疑っていました。
しかし、私はこれに出くわしました。これは、私が間違っていたことをはっきりと示唆しています。EBNF を例外付きで、または RegEx を否定先読みで DFA に変換する方法を示す無料のリソースを誰でも指摘できますか?
否定的な先読みを、可能な一致の完全なセットから否定的な先読みの一致を差し引いた肯定的な先読みに置き換えることができます。たとえば、単一の文字 az を一致スペースとして使用している場合、は(文字列の末尾が可能な一致の 1 つであるため、 が必要です) と/what(?!n)/同じです。これは理論的には問題ありませんが、 のようなより大きな一致を扱う場合、実際にはそれほど優れていません。/what(?=[a-mo-z]|$)/$/afraid of (?!chinese)/
https://cs.stackexchange.com/questions/2557/how-to-simulate-backreferences-lookaheads-and-lookbehinds-in-finite-state-autoは、先読みをDFAのようなものに変換する適切な処理を提供します。最後に重要な注意事項。