编译原理词法分析的问题

Question

这两天看了编译原理的语法分析,回过头去再看词法分析.里面涉及到了正则表达式,NFA 和 DFA 还有词法分析器的生成器,虎书中说这个生成器可以用来将增则表达式转化为DFA,那NFA的概念还有什么意义呢?

是不是说如果我要手工写这个词法生成器的时候, 从正则表达式到NFA 再人为改成DFA ,这是人的思考的过程, 然后如果用生成器的话这个过程是可以省略的. 还是说怎么样

Answer 1

目前大部分词法分析器仍然靠人工来写，实现方式也各有不同，你甚至可以直接通过正则来做词法分析，只要能得到你想要的结果即可。当然，虽然这种方式在处理歧义和运行效率上没有根据DFA实现的分析器效果好。

Answer 2

可以把NFA想成一种中间形式, 并不对应实际的代码

DFA和命令式语言的对应关系更直接, 因为跑程序的机器本身就是D (一个输入对应一个结果)的

Answer 3

讲词法分析时，有限自动机（FSA）有有限个状态。识别 Token 的过程，就是 FSA 状态迁移的过程。其中，FSA 分为确定的有限自动机（DFA）和非确定的有限自动机（NFA）。

DFA 的特点是，在任何一个状态，基于输入的字符串，都能做一个确定的转换。
NFA 的特点是，它存在某些状态，针对某些输入，不能做一个确定的转换。

具体细节楼主可以参考：《编译原理之美》的第 16 节