我正在阅读计算理论。而且我没有编程编译器的实际经验。
所以我突然想到,C 或 Java 编译器是否使用巨大的 DFA 来验证程序(TOC 中的字符串)?
编译器是 DFA 的实际实现吗?
最佳答案
有些编译器会,有些则不会。那些使用 DFA 的人通常使用像 lex/flex 这样的扫描仪生成器来构建 DFA。
当然,DFA 只能带您到此为止(事实上,最多只能使用常规语言)。没有实用的编程语言可以用正则表达式来描述,因为正则表达式不能处理像括号表达式或嵌套控制流块这样的递归结构。因此,如果有的话,DFA 将仅用于将输入分解为一系列标记。然后, token 将被某种下推自动机、递归下降解析器或编码器的纯黑魔法解析。同样,PDA(如果有的话)很可能会使用 bison、ANTLR 和 many others 等工具自动生成。 .
很难找到一种足够纯的语言,以至于简单的两阶段 DFA 扫描/PDA 解析实际上可以正确地创建解析树。似乎总是有一种诱惑要添加一个只能使用图灵完备形式主义来解析的句法结构。所以在实际的编译器中,会有一些地方在潜在的优雅理论模型上钻了小孔,意大利面穿过它们。
尽管如此,解析技术的理论研究多年来大大简化了编译器的构造,并且是数学中一个非常美丽和有趣的角落。
关于compiler-construction - 语言编译器是否使用复杂的 DFA 来接受程序?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/32857081/