第2次课 上下文无关文法 2.1-2.2

本章主要内容 主要描述编译器的前端 词法分析、语法分析和语义分析 通过本章对编译的过程有所了解

一个简单的语法制导翻译器 一个简单的语法制导编译器 词法分析 语法分析 中间代码生成

2.1 引言（2.1） 语法制导翻译器 一个编译器前端的模型：图2.3 词法：词素的正确形式（正则文法：略） 语法：程序的正确形式（上下文无关文法） 语义：程序的含义，即程序在运行时做什么事情（非形式化描述和启发式实例）

2.1 引言 中间代码 抽象语法树（简称语法树）：图2.4a 三地址码：x = y op z 图2.4b 最多只执行一个运算，通常是计算、比较或者分支跳转

2.1 概述 程序设计语言由语法(syntax)和语义(semantics)两个方面定义。 程序设计语言的语法通常用上下文无关文法来表示。 语义的描述则比语法的描述难得多，采用非形式化的自然语言描述

如何描述语法 上下文无关文法Context Free Grammar (CFG) IP  NP-SBJ VP NP-SBJ  DNP NP NN  贷款|本息 | 回收|中国 语法分析树 Parse Tree

上下文无关文法 Context-Free Grammar, CFG 上下文无关文法CFG是一个四元组(Vt, Vn, S, P)，其中： Vt 是一个非空有穷集合，称作终结符号集合 Vn 是一个非空有穷集合，称作非终结符号集合，且VtVn = 。 S  Vn ，称作开始符号。 P是一个非空有穷集合，称为产生式集合，每条产生式形为A，其中AVn，(VtVn)*。

例2.1 简单的算术表达式 list  list + digit list  list - digit list  digit 例2.1　简单的算术表达式 9-5+2 list list  list + digit list  list - digit list  digit digit  0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 list + digit 2 list － digit digit 5 终结符号：+ - 0 1 2 3 4 5 6 7 8 9  Vt 非终结符号 ：list digit  Vn 开始符号：list “”：推导，左部是非终结符，右部是(VtVn)* “|” 表示“或者” 9

例2.1 简单的算术表达式 list  list + digit | list – digit | digit 例2.1　简单的算术表达式 list  list + digit | list – digit | digit digit  0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 上述文法定义的是由加号和减号分隔的数字序列构成的列表。

例2.2 数字序列9 - 5 + 2的推导（derive） list  list + digit  list - digit + digit  digit - digit + digit  9 - digit + digit  9 - 5 + digit  9 - 5 + 2 P1 : list  list + digit P2 : list  list - digit P3 : list  digit P4 : digit  9 P4 : digit  5 P4 : digit  2 从开始符号推导得到的所有的终结符号串的集合称为该文法定义的语言(language)。

例2.3 函数调用中的参数列表 call  id ( opt_params ) opt_params  params |  params  params, param | param main() square(n) max(m,n)

2.2.1 分析树(Parse Tree) A X Y Z 分析树描述如何从文法的开始符号推导出它的语言中的一个语句。 如果非终结符A有产生式 A XYZ，则A的一棵分析树为： A X Y Z

句法分析树Parse Tree 分析树具有如下性质： 根结点是开始符号Start Symbol 叶子结点是终结符或 内部结点是一个非终结符 Non-Terminal If A  x1x2…xn, Then A 是一个非终结符; x1x2…xn 是A 的孩子，是终结符或非终结符 一个文法生成的语言是它的某个分析树生成的串的集合。为给定的符号串找到一棵分析树的过程称为串的语法分析(parsing)。

推导过程可以用分析树（ Parse Tree ）表示 list  list + digit  list - digit + digit  digit - digit + digit  9 - digit + digit  9 - 5 + digit  9 - 5 + 2 list digit 9 5 2 - + token

2.2.2 二义性 Ambiguity 9-5+2 文法Grammar: list  list + digit | list – digit | digit 2.2.2 二义性 Ambiguity 9-5+2 文法Grammar: string  string + string | string – string | 0 | 1 | …| 9 string + 2 - 5 9 对某个文法，如一个句子有两棵以上的分析树，称为二义（歧义）文法。

2.2.3运算符的结合性 可以用括号来表明计算顺序，如 9-5+2 = (9-5)+2 如果对某个运算符op，x1,x2,x3为运算对象，且x1 op x2 op x3 表示 (x1 op x2) op x3，则称op是左结合的；如果x1 op x2 op x3 表示 x1 op (x2 op x3)，则称op是右结合的。 左结合例子：a=3-4-5; a=3-4+5； 右结合例子：a=b=c+1; a=**p；q=&*p；

Left vs. Right a=b=c 9-5+2 right letter list digit list  list + digit | list - digit | digit digit  0 | 1 | … | 9 right  letter = right | letter letter  a | b | c | …| z 终结符在右侧 终结符在左侧

2.2.4 算符优先级 Operator Precedence 9 + 5 * 2 是什么含义? (9 + 2) * 5 或9 + (5 * 2) ？ 不同的运算符号有不同的优先级，如9+5*2 表示 9+(5*2)，所以*的优先级比+高。 ( ) * / + - 优先级

通过适当改写文法规则，可以描述不同的结合律和优先级： factor  digit | ( expr ) term  term * factor | term / factor | factor expr  expr + term | expr – term | term factor(因子)：不能被任何运算符分开的表达式 term(项)：可以被高优先级的运算符*和/分开，但不能被低优先级运算符分开的表达式 expr(表达式)：expression 对于处理n层优先级的情况，我们需要n+1个非终结符号。

Java语句的语法 stmt  id = expr ; | if (expr )then stmt | if (expr ) stmt else stmt | while (expr) stmt | do stmt while (expr); | { stmts } stmts  stmts stmt |  假设改为：if (expr )then stmt； 又假设stmt为赋值语句， 那么 语句就会多出现一个分号， 例如：if( a>0 ) b++; ; 注意:“;”的设置

作业 中序表示转换为后序表示 1+2*3->123*+

重点 语法制导翻译器的组成部分？ 什么是上下文无关文法？ 上下文无关文法的形式化定义（四元组）？ 什么是分析树？ 什么是二义性？ 什么是运算符的结合性？

练习 自己写表达式，基于文法构建语法树 自顶向下的方法 ppt-11页的文法规则 ppt-13页的文法规则