“编译原理”学习笔记


引论

在一个程序可以运行之前,它首先需要被翻译成一种能够被计算机执行的形式。完成这项翻译工作的软件系统称为编译器。

解释器并不通过翻译生成目标程序,解释器直接利用用户提供的输入执行源程序中指定的操作。

一个编译系统包括:

  • 源程序经过预处理器生成经过预处理的源程序;
  • 再经过编译器生成目标汇编程序;
  • 再经过汇编器生成可重定位机器代码;
  • 经过链接器/加载器(同时加入库文件、可重定位对象文件)生成机器代码。

编译器的两个主要部分:分析与综合/前端与后端。

编译器内部需要经过:词法分析、语法分析、语义分析、中间代码生成、机器无关代码优化、代码生成、机器相关代码优化后输出目标机器语言。

  • 词法分析:将输入代码中的字符流,组织称有意义的词素序列,每个词素用词法单元输出。
  • 语法分析:用递归的方式构建语法树,树中每个节点表示一个运算。
  • 语义分析:检查源程序是否和语言定义的语义一致,同时也收集类型信息,存在放在语法树或者符号表里。
  • 中间代码生成:编译器在经过上面三个步骤以后,可以生成一个明确的低级的或类机器语言的中间过程。该中间表示应该易于生成、且能够被轻松地翻译为目标机器上的语言。
  • 代码优化:代码优化器会在中间代码的基础上在时间和空间上优化代码。
  • 代码生成:最终翻译成机器能够运行的代码。
  • 符号表的管理
    • 记录在原代码中使用的标识符和属性信息;
    • 提供每一个标识符的类型、参数等。

词法分析

词法分析器是编译器的第一部分,是将输入代码中的字符流,组织称有意义的词素序列,每个词素用词法单元(tokens)输出。

词法单元:

  • 分为关键字、标识符、算术符号、多字符符号(>=,<>)
  • 识别划分词法单元用规则(pattern)
  • 词素有意义的单词
  • 因为一个 token 可能有不同的表达意思,所以需要他的属性来表示他所表示的内容,所以需要用词素
  • 可以通过定义一个无意义的 token 来过滤空白的信息。

词法分析工作步骤:

  1. 扫描输入(源代码)
  2. 去掉无意义的字符(换行、空格等)
  3. 找到 tokens
  4. 创建符号表
  5. 将 tokens 加入符号表
  6. 返回错误
  7. 将词法单元(tokens)输出给语法分析器

如何判断合法的 tokens

  • 用正则表达式来判断 tokens 是否合法
    • 正则表达式是一个构造符号序列的规则集合
      • 空串用 \(\varepsilon \) 表示
      • 正则表达式的定义:\(\varepsilon  | a | r+r|rr|r^{*}|(r)\)
  • 检验一个表达式是否合法的使用 DFA(确定型自动机)

You may also like

LEAVE A COMMENT

Statistics

  • 1
  • 44,606

Categories

Archive

Comments