词法分析任务

词法分析任务

• 字符流到记号流的转换
• 可以将整个流程展示如下图：

源程序>词法分析器>记号流>语法分析器>抽象语法树>语义分析器>中间表示

记号流

• 其实就是编译器内部定义的数据结构，编译所所识别出的词法单元

正则表达式

归纳定义

• 如果M和N是正则表达式，则以下也是正则表达式：
  • 选择：M | N = {M,N}
  • 连接：MN = {mn|m∈M,n∈N}
  • 闭包：M* = {ε,M,MM,MMM...}

自动机

自动机例子

• 图1.png

• 什么样的串可被接受

• 图2.png

转移函数

• {(q0,a)->q1,(q0,b)->q0
• (q1,a)->q2,(q1,b)->q1
• (q2,a)->q2,(q2,b)->q2}
• 读完所有的串后，最终的状态是否可被接受，也即是最终的状态需要是图1中的F