实现 lex 时将多个正则表达式转换为 DFA
我正在学习编写一个词法分析器生成器（lex的克隆），基于正则表达式到“龙书”中描述的DFA直接翻译算法。
现在我可以成功地将正则表达式转换为 DFA，但是当存在多个规则时我会陷入困境，例如：
abc { printf("abc"); }
a* { printf("a*); }
我可以将 abc 和 a* 转换为两个 DFA 图，但如何将这两个 DFA 图合并为一张呢？
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
事实上，我几年前就做过这个练习——我以这本书为指导，用 C++ 构建了一个集成的词法分析器和 LALR 解析器。这本书实际上告诉你如何将正则表达式直接转换为 NFA，然后使用我现在不太记得名称的算法将 NFA 转换为 DFA。要支持多个规则，您只需为每个规则创建一个 NFA。然后，您创建一个新的开始状态，并从您的开始状态到为每个规则创建的每个 NFA 的开始状态创建 epsilon 转换。至少，这是我在不检查代码的情况下能记住的。
I actually did this exercise several years ago - I built an integrated lexer and LALR parser in c++ using the book as a guide. The book actually tells you how to convert regexes directly into NFAs and then you convert the NFAs into DFAs using using an algo I can't quite remember the name of right now. To support multiple rules you just need to create an NFA for each one. Then you create a new start state and create a epsilon transition from your start state the the start state of each of the NFAs you created for each rule. At least, thats what I can remember without reviewing my code.