编译原理: 词法分析

Posted on Edited on In , Word count in article: 746 Reading time ≈ 3 mins.

词法分析

编译过程

  • 编译器分为前端和后端，前端包括词法分析、语法分析、语义分析、生成中间代码，后端包括代码优化、最终代码生成，在过程中借助符号表管理器和错误管理器
  • 通过中间代码划分前端和后端，不需要针对每一门语言都完整设计一个编译器
  • 遍：
  • 翻译器：将一门语言翻译成另一门语言的软件
  • 编译器：将一门高级语言翻译成一门低级语言的软件
  • 解释器：
  • 即时编译：

词法分析过程

  • 词法分析的目标是把源文件这一串符号流转换成记号流
  • 词法单元：源文件这一串字符串
  • 词法记号：满足一定规则的词法单元
  • 字母表：符号的集合
  • 串：符号组成的序列
  • 语言：字母表上某些串的集合，包括空串、空集
  • 句子：语言的一个元素
  • 语言的运算及正则表达式：详见Regex

自动机

不确定的有限自动机(NFA)

  • 允许出边的条件为空串
  • 允许有具有相同条件的出边
  • 由正则表达式生成NFA：
    • 或运算x s|t y：在x后添加两条空串的出边，在y前添加两条空串的入边，分别指向s和t
    • 与运算x st y：使s的出节点和t的入节点重合
    • 闭包xs*y：使x通过空串既指向s又指向y，使s的出节点通过空串指向入节点
  • 由语言生成NFA：脑补所有可能结束的状态，由初始状态遍历字母表迭代计算

确定的有限自动机(DFA)

  • 由NFA生成`：子集构造法
    • 从初始状态开始，求出闭包（经过空串能得到的所有状态）
    • 遍历每一个字母表的元素，计算上述闭包经过该元素能得到的集合，并求出新集合的闭包
    • 重复第二个步骤，直到没有任何新增的闭包
  • 化简DFA：
    • 死状态：如果存在一个字母表中的元素，有一个状态没有对应的出边，那么需要使他指向死状态，死状态的所有出边都指向它自己，相当于出错时直接跳过当前词法单元
    • 执行类似由NFA转化的步骤，但是将不可区分的状态合成为一个状态

词法分析器的生成器

  • lex和flex：使用嵌入了c/cpp的脚本语言，将脚本语言翻译成一般c程序
  • 语法：

    • 声明语句：

      1
      2
      3
      {%
      int cnt = 0; 
      %}

    • 分隔符：%%

    • 入口：yylex()，每次调用都会解析直到在匹配规则里return或分析到字符串结尾，若中途返回则下次调用从返回处继续分析

    • yytext：匹配成功，得到的完整的词法单元