编译原理词法分析的问题

已注销
  • 388

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

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

回复
阅读 3.5k
4 个回答

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

jokester
  • 6.7k

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

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

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

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

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

宣传栏