编译原理--语法制导翻译器（一）

getianao

2020-01-08

本章重点在前端，特别是词法分析，语法分析和中间代码生成

首先建立一个将中缀算术表达式转换成后缀表达式的语法制导翻译器，然后我们扩展这个翻译器，将某些程序片段转换为如图所示三地址代码

{
    int i; int j; float[100] a; float v; float x;
    while(true){
        do i = i + 1; while(a[i] < v);
        do j = j + 1; while(a[j] > v);
        if(i >= j) break;
        x = a[i]; a[i] = a[j]; a[j] = x;
    }   
}

编译器在分析阶段把一个源程序划分成各个组成部分

引言

编译器在分析阶段把一个源程序划分成各个组成部分，并生成源程序的内部表示形式，这种内部表现形式称为中间代码
编译器在合成阶段将这个中间代码翻译成目标程序
分析阶段的工作是围绕着待编译语言的"语法"展开的
语法（syntax），描述了该语言的程序的正确形式；语义（semantics），定义了程序的含义，每个程序时应该做什么事
上下文无关文法，不仅可以描述一个语言的语法，还可以知道程序的翻译过程

编译原理--语法制导翻译器（一）

编译前端的模型

词法单元

词法分析器，使得翻译器可以处理由多个字符组成的构造，标识符由多个字符组成，在语法分析阶段被当作一个单元进行处理

中间代码形成

中间代码形成，抽象语法树（abstract syntax tree），或简称语法树（syntax tree）
语法分析器生成一个语法树，它又被进一步翻译为三地址代码，有些编译器会将语法分析和中间代码形成合并为一个组件

编译原理--语法制导翻译器（一）

三地址指令，显示了更加完整的示例，这个中间代码形式的名字源于它的指令形式： x = y op z，op是一个二元运算符
y和z是运算分量的地址，x是运算结果的存放地址

编译原理--语法制导翻译器（一）

语法定义

描述程序设计语言语法的表示方法--"上下文无关文法"，文法自然地描述了大多数程序设计语言构造地层次化语法结构
if (expression) statement else statement 表示为 stmt→if (expr) stmt else stmt
箭头 →，可以读作"可以具有如下形式"，这样的规则称为产生式（production）
像关键字 if 和括号这样的词法元素称为终结符号（terminal），像 expr 和 stmt 这样的变量表示终结符号的序列，称为 非终结符号（nonterminal）

文法定义

一个上下文无关文法（context-free grammar）由四个元素组成
一个终结符号集合，有时称为"词法单元"，终结符号是该文法所定义的语言的基本符号的集合
一个非终结符号集合，有时称为"语法变量"，每个非终结符号表示一个终结符号串的集合
一个产生式集合，每个产生式包括一个称为 产生式头或左部 的非终结符号，一个箭头，和一个称为 产生式体或右部 的由终结符号及非终结符号组成的序列
产生式用来表示某个构造的某种书写形式，如果产生式头非终结符号代表一个构造，该产生体代表了该构造的一种书写方式
指定一个非终结符号为开始符号

词法单元

由两个部分组成：名字和属性值
词法单元的名字，是语法分析器进行语法分析时使用的抽象符号，我们常常把这些词法单元名字称为 终结符号
我们假设数位、符号（如 < ，<=）和黑体字符串（如while）都是终结符号
斜体字符串表示非终结符号，所有非斜体的名字或符号都可以看作是 终结符号
以同一个非终结符号为头部的多个产生式的体可以放在一起表示，不同体之间用符号 | 分隔

例2.1

使用由数位和+、-符号组成的表达式，比如 9 - 5 + 2、3 - 1 或 7。两个数位之间必须出现 + 或 - ，我们把这样的表达式称为 "由 +、- 号分隔的数位序列"
文法的产生式包括： list→list + digit，list→list - digit，list→digit，digit→ 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
以非终结符号list为头部的三个产生式可以等价地组合为 list→list + digit | list - digit | digit
根据我们的习惯，该文法的终结符号包括，+ - 0 1 2 3 4 5 6 7 8 9
该文法的非终结符号是斜体名字 list 和 digit，list是该文法的开始符号
若某个非终结符号是某个产生式的头部，就说该产生式是该非终结符号的产生式
一个终结符号串是由零个或多个终结符号组成的序列
空串（empty string），零个终结符号组成的串，记为 ε

推导

从开始符号推导得到所有终结符号串的集合，称为该文法定义的语言（language）

例2.2

非终结符号digit的10个产生式使得digit可以表示0、1、...、9中的任意数位，单个数位本身是一个list
任何列表后跟一个符号 + 或 - 以及另一个数位可以构成一个新的列表，按照如下方法推导处 9 - 5 + 2 是一个list
list→list + digit，list→list - digit，list→digit，digit→ 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
因为9是digit，根据产生式可知9是list
因为5是digit，且9是list，9 - 5也是list
因为2是digit，9 - 5 是list，9 - 5 + 2 也是list

例2.3

另有一种不同的列表是函数调用中的参数列表
在Java中，参数是包括在括号中的，例如max(x, y)表示使用参数x和y调用函数max，这种列表的微妙之处是终结符号"(" 和 ")"之间的参数列表可能是空串
我们可以为这样的序列构造具有如下产生式的文法
call → id（optparams）
optparams → params | ∈
params → params，param | param
注意，在optparams（可选参数列表）的产生式中，第二个可选择体是∈，它表示空的符号串
也就是说，optparams可以被替换为空串，params的产生式和上式的list产生式类似，只是将算术运算符 + 或 - 换成了逗号，并将digit换成param
函数参数实际上可以是任意表达式，但是在这里我们没有给出param的产生式

语法分析（parsing）的任务

接受一个终结符号串作为输入，找出从文法的开始符号推导出这个串的方法
如果不能从文法的开始符号推导得到该终结符号串，报告该终结符号串中的语法错误
语法分析是所有编译过程中最基本的问题之一
一般情况下，一个源程序中会包含由多字符组成的词素，这些词素由词法分析器组成词法单元，而词法单元的第一个分量就是被语法分析器处理的终结符号

语法分析树

语法分析树用图形方式展现了从文法的开始符号推导出相应语言中的符号串的过程，如果非终结符号A有一个产生式A→XYZ，那么在语法分析树中就可能有一个标号为A的内部结点，该结点有三个结点，从左向右的标号分别为X、Y、Z

编译原理--语法制导翻译器（一）

给定一个上下位无关文法，该文法的一棵语法分析树（parse tree）具有以下性质

根结点的标号为文法的开始符号
每个叶子结点的标号为一个终结符号或∈
每个内部结点的标号为一个非终结符号
如果非终结符号A是某个内部结点的标号，并且它的子结点的标号从左至右分别为X₁，X_2，...，X_n，那么必然存在产生式A→X₁X₂...X_n，其中X₁，X₂，...，X_n既可以是终结符号，也可以是非终结符号。作为一个特殊情况，如果A→∈是一个产生式，那么一个标号为A的结点可以只有一个标号为∈的子结点

例题2.4

例题2.2中 9 - 5 + 2 的推导可以用下图的树来演示

根结点的子结点的标号从左向右分别为list、+和digit， list→list + digit

编译原理--语法制导翻译器（一）

一棵语法树的叶子结点从左向右构成了树的结果（yield），也就是从这棵语法树的根结点上的非终结符号推导得到的符号串
所有的叶子结点都放在底层，我们不一定会把叶子结点按照这种方法排列，任何树的叶子结点都有一个自然的从左到右的顺序
如果X和Y是同一个父结点的子结点，并且X在Y的左边，那么X的所有后代结点都在Y的后代结点的左边
一个文法的语言的另一个定义是指任何能够由某棵语法分析树生成的符号串的几何
为一个给定的终结符号串构建一棵语法分析树的过程称为对该符号进行语法分析

二义性

一个文法可能具有多棵语法分析树能够生成同一个给定的终结符号串，这样的文法称为具有二义性（ambiguous）
要证明一个文法具有二义性，只需要找到一个终结符号串，说明它是两棵以上语法分析树的结果

例2.5

假如我们使用一个非终结符号string
string → string + string | string - string | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
将符号digit和list合并为非终结符号string是有一些意义的，因为单个的digit是list的一个特例

编译原理--语法制导翻译器（一）