编译原理笔记4-词法分析和状态转换图

词法分析器

从左到右逐个字符地扫描源程序，产生一个个单词符号。把作为字符的源程序改造为单词符号串组成的中间程序

功能：

  • 读入源程序字符串，识别具有独立含义的最小语法单位
  • 把单词变成长度统一且为定长的属性字
  • 滤掉空格、跳过注释换行符、加工处理等

安排：

  • 作为独立的遍
  • 作为被语法分析器调用的子程序

词法分析器实现方式

相对独立的方式：

​ 语法分析程序使用getToken接口，获取从词法分析程序的Token，实现一趟编译程序

完全独立的方式：

​ 词法分析程序将源程序转换为属性字序列。

  • 简化设计、降低了语法分析的复杂性
  • 提高编译效率，增加编译系统的可移植性

词法分析器的输出形式

  • 单词：程序语言的基本语法符号
    • 基本字：每个基本字当成一个类
    • 标识符：当成一类，以内部码值加以区别
    • 常数、运算符、界符等
  • 词法分析器中单词的输出形式：二元式（单词类别、单词内部码值）

状态转换图

一张有限方向图，结点代表状态，状态之间用箭弧连接，箭弧的标记代表射出结状态下可能出现的输入字符或字符类

状态转换图的实现

每个结点对应一段程序，前面状态结的程序调用其后继结点的程序

引入一下标准过程、变量：

  • Char：全程字符变量，存放最新读入的源程序字符
  • 字符串Token：存放构成单词符号的字符串
  • 过程GETChar：读入一个源程序字符，放入Char中，搜索指针前移
  • 过程GETNBC：反复调用GETChar，直到进入下一个非空字符
  • 过程CONCAT：把Char中的字符连接到Token的末尾
  • 函数Letter/digit：判断Char中是否为字母/数字
  • 过程Return(c，val)：已经识别一个单词，以二元式返回
  • 过程Retract：搜索器指针回拨一个字符