什么是编译器设计中的子集构造?

问题描述 投票:-2回答:2

here is the algorithm : 我正在浏览关于Compiler Construction的aho,Ulman参考书,它解释了NFA到DFA转换的子集构造实现算法。那里的解释非常简短。我想更深入地了解这一过程如何在更深层次上发挥作用。任何人都可以建议我一个很好的参考或网站,可以清除这些难以消化的概念?

compiler-construction lexical-analysis finite-automata
2个回答
0
投票

Compiler Construction是一本很好的书,但它的内容非常深刻,可能很难理解(它是为编译器的整个领域而设计的,并且它的总体内容需要很长时间才能完成)。

任何人都可以建议我一个很好的参考或网站,可以清除这些难以消化的概念?

你应该试试Compilers: Principles, Techniques, and Tools

我第一次将NFA实施到DFA正在研究这本书。


0
投票

这只是在编译器设计期间使用的算法的名称。

在设计语言时,您需要设计语言的词法结构,部署一个称为正则表达式的工具。正则表达式虽然是声明性的,但充当生成器,而您需要一些可以充当识别器的东西。

为此,您希望到达一台“机器”,即所谓的有限自动机。您可以使用称为Thompson's Construction的算法从正则表达式生成非确定性有限自动机。

你最终得到的NFA的问题在于,由于非确定性,以编程方式模拟是相当困难的。出于这个原因,我们想要执行另一个转换,从NFA转到DFA,该算法称为Subset Construction

© www.soinside.com 2019 - 2024. All rights reserved.