编译原理--词法分析--正则表达式到NFA

正则表达式语法

  菜鸟教程

正则文法和上下文无关文法区别

  每次学习编译原理，总会不禁疑惑，到底什么才是正则文法，什么是上下文无关文法？区别到底在哪？我们先看个例子:
  文法表示连续n个a后跟着连续n个b

  咋一看好像也可以用正则表达式表示:

  但是n是变化的，也就是一个正则表达式，最多匹配一个结果
  究其原因，正则文法无法记录已经匹配的a的个数，用于b的匹配。正则表达式中的n是预先定义的，不是在匹配过程动态生成的。
  怎么在匹配过程记录a的个数？

• 增加一个计数器，每次遇到一个a就加1，直到遇到b为止。每次遇到一个b，计数器就减1，直到读完所有输入，若计数器最终为0，则输入串符合文法，否则不符合。
• 输入ababab，计数器正常工作，但是不符合L文法。可见仅仅考虑个数是不够的。
• 文法L以a开始，紧随一个L文法后，必须以b结束。
• 文法L以a开始后，遇到L文法，又去匹配L文法，直到遇到b。此时，匹配到的a字符借助编程语言的栈得以保存。以a开始的L文法结束后，必须匹配b字符。否则错误。

  正则文法是以下三种

  正则文法产生式右边的终结符右边没有任何非终结符或者终结符限定

正则表达式基础运算

为了方便学习，仅定义以下三种运算和括号

• 连接(Concatenation), 例如 abc, 由a, b, c组成
• 联合(Union), 例如 a|b|c, 表示a或者b或者c
• Kleene闭包(Kleene ), 例如 (ab), 表示ab串不出现，或者出现1次或一次以上

逆波兰表达式

  表达式为以下树的中序遍历。

Thompson算法--生成NFA

• 一个终结符
    一个终结符，生成两个状态，s1和s2，一条为a的边从s1指向s2，初始状态为s1，结束状态为s2

• 连接运算
    两个状态机，一条为:e:的边，从一个状态机的结束状态，指向另一个状态机的起始状态。

• 联合运算
    生成两个新的状态，一个起始状态s1，另一个结束状态s6，s1以:e:边分别指向两个状态机起始状态，两个状态机的结束状态以:e:指向s6结束状态

• Kleene闭包
    在原有状态机上增加4条:e:边