编译原理之将正则表达式变为有穷自动机

编译原理之将正则表达式变为有穷自动机

从正则表达式变为NFA

• 首先先看看简单的基本的正则表达式是如何对应的相关的NFA的
  • 字母表中的符号a对应的NFA

• r = r1r2对应的NFA

• r = r1|r2对应的NFA

• r = （r1）^*对应的NFA

实例将对应的r=(a|b)^*abb转成对应的NFA

• 将r当作一个正则表达式，直接带入整体
  
• 将与连接的直接分解成顺序结构

• 将克林闭包转成经过自己的循环

• 将或运算进行拆解
  

基本思路就是不断地增加新地点，有的可能会用不同地方式进行替代，如采用Thompson法进行替代

• 用下图代替a|b

• 用下图代替ab
  
• 用下图代替a^*
  

例题

构建((0|1*)|0)*11对应的NFA