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

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

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

{
    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的一个特例

• 这两棵语法分析树对应于两种带括号的表达式：（9 - 5） + 2 和 9 - （5 + 2）
• 第二种方法给出的表达式时意想不到的2，而不是通常的值6

运算符的结合性

• 9 + 5 + 2 等价于 （9 + 5）+ 2，9 - 5 - 2 等价于（9 - 5）-  2
• 当一个运算分量，的左右两侧都有运算符时，我们需要一些规则来决定哪个运算都应用于该运算分量
• 我们说运算符"+"是左结合的，因为当一个运算分量左右两侧都有"+"号时，它属于其左边的运算符
• 加、减、乘、除四种算术运算符都是左结合的
• 某些常用运算符是右结合的，比如指数运算，C语言中的赋值运算符"="及其后裔（+=、-=）也是右结合的
• 对表达式a=b=c的处理和对表达式 a =（b=c）的处理相同
• 左结合运算符的语法分析树和一个右结合运算符的语法分析树
• 9 - 5 -2（左结合）的语法分析树向左下端延伸，而a=b=c（右结合）的语法分析树则向右下端延伸

运算符的优先级

• 如果*先于+获得运算分量，我们就说*比+具有更高的优先级
• 通常的算术中，乘法和除法比加法和减法具有更高的优先级

例2.6

• 算术表达式的文法可以根据表示运算符结核性和优先级的表格来构建
• 运算符按照优先级递增的顺序排列，同一行上的运算符具有相同的结合性和优先级
• 左结合： + -  左结合： * /
• 创建两个非终结符号expr和term，分别对应于这两个优先级层次，并使用另一个非终结符号factor来生成表达式中的基本单元
• factor → digit | (expr)
• 生产式和左结合列表的产生式类似：
• term → term * factor
• | term / fatoer
• | fator
• 类似地，expr生成由加减运算符分隔的term列表
• expr → expr + term
• | expr - term
• | term

最终得到的文法：

• expr → expr + term + expr - term | term
• term → term * factor | term / factor | factor
• factor → digit | (expr)

factor

• 因子（factor）是不能被任何运算符分开的表达式，原子性
• 一个项（term）是一个可能被高优先级的运算符*和/分开的，但不能被低优先级运算符分开的表达式
• 一个表达式可能被任何一个运算符分开

例2.7

• 在stmt的第一个产生式中，终结符号id表示任意标识符
• 非终结符号expression的产生式还没有给出
• 第一个产生式描述的赋值语句复合Java的语法，虽然Java将 = 号看作是咳出现在表达式内部的赋值运算符
• 非终结符号stmts产生一个可能为空的语句列表
• stmts的第二个产生式生成一个空列表 ε
• 第一个产生式生成的是一个可能为空的列表再跟上一个语句
• 分号的放置方式很微妙，它们出现在所有不以stmt结尾的产生式的末尾
• 可以避免在if或while的语句后面出现多余的分号，因为if和while语句的最后一个嵌套的子语句
• 当嵌套子语句是一个赋值语句或do-while语句时，分号将作为这个子语句的一部分被生成