编译程序原理与实现：第3章 形式语言与语法分析

1、编译程序原理与实现张晶2013.02第三章 语法分析介绍第3章 outline语法分析概述1.功能需求(输入，输出，主要功能)2.分析算法+数据结构3.构造语法分析器的通用过程上下文无关文法语法分析树和抽象语法树二义性文法文法变换算法语法错误处理知识关系图开发语法分析程序语法定义基于上下文无关文法使用实现自顶向下自底向上3.1 语法分析概述部分语法分析程序的功能输入：词法分析程序输出的Token/TokenList输出：语法结构的内部表示(抽象语法树，AST) 或语法错误信息分析过程：从左到右扫描Token序列，根据上下文无关文法，建立语法结构的内部表示，检查语法错误。语法分析Token序列

2、抽象语法树语法错误语法分析过程C程序：Parser输入：Parser输出：if (x=y) z=1; else z=0; IF Lparen id EQ id Rparen LG id EQ num semi RG else LG id EQ num semi RGIF_Stmt=idid =idnum =idnum程序设计语言的语法结构(1) 程序(2) 声明- 常量声明- 类型声明- 变量声明- 过程/函数声明(3) 程序体(4) 语句（赋值语句，条件语句，循环语句，函数调用语句） (5) 表达式 (算术表达式，逻辑表达式，关系表达式)语法错误语法错误的类型语法结构的开始单词错误表达式E的

3、开始单词是id, (, n-其他Token则出错语法结构的后继单词错误语句；语句-语句，语句标识符或者常量错id := E - begin := E 或 123:=E关键字错if E then 语句 else 语句 -其他关键字则出错括号配对错（）（） -）（）语法错误的例子int GetMax( int x ; int y) if (xy) return x else return y; vod main() real 10, y; 10 + ; GetMax( x, y) ;后继单词错括号配对错关键字错,开始单词错标识符错开始单词错语法分析方法自顶向下的分析 从上往下生成树的过程自底向上的

4、分析 从下往上生成树的过程IF_Stmt=idid =idnum =id0递归下降分析LL(1)分析LR(0),SLR(1),LR(1),LALR(1)语法分析与词法分析的比较阶段（Phase）输入（Input）输出（Output）词法分析（scanner）字符序列Token序列语法分析（parser）Token序列抽象语法树第3章 outline语法分析概述1.功能需求(输入，输出，主要功能)2.分析算法+数据结构3.构造语法分析器的通用过程上下文无关文法语法分析树和抽象语法树二义性文法文法变换算法语法错误处理3.2 上下文无关文法 不是所有的Token串都是合法的程序，因此需要一个工具来描

5、述合法的Token串。 一般地，程序设计语言的结构都是递归结构(recursive structure)例如：表达式，上下文无关文法非常适合描述这种结构变量是表达式（表达式）是表达式表达式+表达式是表达式3.2 上下文无关文法上下文无关文法是一个四元组(VT,VN,S,P)VT是有限的终极符集合VN是有限的非终极符集合S是开始符，S VNP是产生式的集合，且具有下面的形式： AX1X2Xn 其中AVN，Xi (VTVN )符号约定：非终极符用大写字母表示 终极符用小写字母表示 开始符是第一条产生式左部的符号不绝对！上下文无关文法的例子例1：简单算术表达式的上下文无关文法，E id E (E)E

6、 E + EE E * EE id | (E) | E + E |E * EE id | (E) | E + E |E * EVT: id, (,),+,*VN: ES : E上下文无关文法的例子例2：语句的上下文无关文法： VT：id，（，），+，*, =, if , else, while, ;VN：E, StmtS：StmtStmt id = EStmt if E Stmt else StmtStmt while E StmtStmt Stmt;Stmt E id E (E)E E + EE E * E上下文无关文法的例子例3：变量声明的上下文无关文法： 变量声明 变量声明 一个变量定义

7、;变量声明 一个变量定义 ; 变量声明 变量定义 类型 标识符序列标识符序列 一个标识符标识符序列 一个标识符 , 标识符序列VarDec VarDec VarDef;VarDec VarDef; VarDecVarDef Type IdListIdList idIdList id ,IdList上下文无关文法是怎样定义语言的？与上下文无关文法有关的一些概念直接推导()：如果A是一个产生式，则有A ,其中表示一步推导(用A)。这时称是由A直接推导的。“” 的含义是，使用一条规则，代替左边的某个符号，产生右端的符号串推导(+)：若通过一步或多步推导可从串导出串,则称为的推导,并记为 + 星推导(

8、*):称 * 当且仅当 = 或 + 例子(E) (E+T) (应用产生式2)(E) (T) (应用产生式1)E直接推导出E+T或E直接推导出TE T F （E） （E+T） （T+T） （F+T） （i+T） （i+F） （i+n) ,记作E + (i+n)E经过多步推导出i+nE * EE * i +(i） E经过若干步推导出i+(i）P:(1) E T(2) E E + T(3) T F(4) T T * F(5) F (E)(6) F i(7) F n与上下文无关文法有关的一些概念句型：如果有S * , S是文法的开始符, (VTVN )*，则称是G的句型句子：如果有S + , S是文法

9、的开始符, VT*，则称是G的句子语言： L(G) = | S + , VT* 即文法G的所有句子的集合文法等价： G1和G2两个文法,若L(G1) = L(G2),则称G1和G2等价例子句型: E, T, E+T, F, T*F, i, n, (E), . 句子: i, n, (i), (n), i+i, i+n, 语言:i, n, (i), (n), i+i, i+n , P:(1) E T(2) E E + T(3) T F(4) T T * F(5) F (E)(6) F i(7) F n与上下文无关文法有关的一些概念最左(右)推导：在推导过程中，总是对当前符号串中最左(右)边的非终极

10、符进行替换，称为最左(右)推导,记为l(r)m规范推导：最右推导左(右)句型：通过最左(右)推导得到的句型，称为左(右)句型规范句型：右句型例子最左推导: i+T*n +F lm i + F*n + F最右推导: i+T*n +F rm i + T*n +i左句型: i + i*F右句型: E+(i)P:(1) E T(2) E E + T(3) T F(4) T T * F(5) F (E)(6) F i(7) F n特别注意例如文法G : N D | N D D 0 | 1| 2 | | 9 N rm ND rm N 8 rm ND 8 rm N 98 rm D98 rm198,句子198

11、的最右推导 N rm ND N D D ,句型NDD不存在最右推导 每个句子一定有最右(规范)推导每个句型不一定有最右(规范)推导上下文无关文法小结Context Free Grammar, CFG(VT,VN,S,P)推导，句型，句子，语言的概念及含义语言与文法 Chomsky文法分类Chomsky文法分类上下文无关文法只是文法的一种。文法有很多种。Chomsky将文法分为四类：0型文法：短语文法。产生式：，中至少有一个非终极符。0型语言。1型文法：上下文相关文法。产生式： A , ,可为。1型语言(上下文有关语言)。2型文法：上下文无关文法。产生式： A ， 可为。2型语言(上下文无关语言

12、)。3型文法：正则文法。产生式： A aB, A a。3型语言(正则语言)。Chomsky文法分类描述能力：0型文法 1型文法 2型文法 3型文法对应自动机：0型文法 对应 图灵机1型文法 对应 线性有届自动机2型文法 对应 下推自动机3型文法 对应 有限自动机第3章 outline语法分析概述1.功能需求(输入，输出，主要功能)2.分析算法+数据结构3.构造语法分析器的通用过程上下文无关文法语法分析树和抽象语法树二义性文法文法变换算法语法错误处理3.3 语法分析树和抽象语法树问题: 推导是从开始符产生句型的一种方法; 对同一个句型存在多个推导：NND NDD ND8 N98 或 N9D N9

13、8 或 DDD DD8 D98 198 或 D9D D98 198 或 1DD 19D 198 或 1D8 198 即线性推导不能唯一地表示句子的结构语法分析树: (Syntax Analysis Tree)用于表示句型结构的一种较好方法;例子P:(1) E T(2) E E + T(3) T F(4) T T * F(5) F (E)(6) F i(7) F n 句型（句子） : i + i * n该句型存在多个推导： 语法分析树：语法分析树语法分析树是针对某个特定CFG的带标号的树树的每个节点都标记一个符号：树的根节点标记文法的开始符;树的每个叶子节点标记一个终极符;若有树的中间节点标记为

14、A,它有n个儿子节点，从左到右标记为B1,Bn,则G中定存在产生式A B1 Bn; 抽象语法树(AST)语法分析树存在的问题包含很多不必要(对语义分析和代码生成而言)的节点 抽象语法树只包含必要的节点作为语法分析程序输出 句型(句子): i + i * nP:(1) E T(2) E E + T(3) T F(4) T T * F(5) F (E)(6) F i(7) F n第3章 outline语法分析概述1.功能需求(输入，输出，主要功能)2.分析算法+数据结构3.构造语法分析器的通用过程上下文无关文法语法分析树和抽象语法树二义性文法文法变换算法语法错误处理3.4 二义性文法二义性文法(a

15、mbiguous grammar) 如果文法的一个句子有两棵或两棵以上不同的语法分析树，则称该句子是二义性的。 包含二义性句子的文法，称为二义性文法。二义性文法的例子P:Exp Exp + ExpExp Exp ExpExp Exp * ExpExp Exp / ExpExp (Exp)Exp idExp numid + id * id if then else if then .假设有条件语句 if e1 then if e2 then s1 else s2则可有下图所示的两棵不同的语法分析树： if语句的二义性ififthenelsethene1e2s1s2elsethenifthenif

16、e1e2s1s1二义性文法(ambiguous grammar)二义性会给语法分析带来不确定性，应尽量避免写出二义性的文法。但有时用二义性文法定义语法结构更简单直观。文法二义性问题是不可判定的，也就是不存在一种算法，能在有限步内确切的判定一个文法不是二义性文法。若要证明文法是二义性的，只要举出一个有两棵以上语法分析树的句子即可。若能控制文法的二义性，即加入人为的附加条件，则二义文法的存在并非坏事，有时二义性文法可以简化文法的表示。消除文法二义性的常用方法 1、规定符号的优先级 2、规定符号的结合性表达式的无二义性文法有二义性的表达式文法:Exp Exp + ExpExp Exp ExpExp

17、Exp * ExpExp Exp / ExpExp (Exp)Exp idExp num无二义性的表达式的文法：E TE E + T | E - TT FT T * F | T / FF ( E )F idF numIf语句的无二义性文法定义 Stmt Matched_stmt | Unmatched_stmt Matched_stmt if E then Matched_stmt else Matched_stmt | other Unmatched_stmt if E then Stmt | if E then Matched_stmt else Unmatched_stmt第3章 out

18、line语法分析概述1.功能需求(输入，输出，主要功能)2.分析算法+数据结构3.构造语法分析器的通用过程上下文无关文法语法分析树和抽象语法树二义性文法文法变换算法语法错误处理文法变换有些语法分析方法要求被分析的文法满足一定的约束条件，当被分析的文法不满足这些条件时，常常要进行文法变换。文法变换必须保证变换前后的两个文法G1和G2是等价的，即L(G1) = L(G2)常用文法变换方法增补文法去除空产生式消除无用产生式消除特型产生式消除公共前缀消除左递归(直接，间接)文法变换算法（1）何时需要增补：在自底向上(bottom to up)的语法分析方法中，要求文法开始符不能出现在产生式的右部. 否

19、则，需要对文法进行增补。变换方法： 在原产生式基础上，增加一条产生式：Z S，S为原文法的开始符，Z为增补文法的开始符文法变换算法（2）文法中空产生式的存在常常给语法分析带来困难，因此最好将空产生式消除掉。变换依据：文法G中除了S以外的空产生式(A)可以消除; 变换方法：找出所有可以推导出的非终极符,记为S;对于所有产生式A X1 X2 Xi-1XiXi+1XnXi S增加A X1 X2 Xi-1Xi+1Xn直到没有新的产生式产生删除对应空产生式, 除了S不可以删除 消除空产生式的例子S | A a BBA B B | aB |bS=S, B, AA BA BB S a BBSA a BB S

20、 A a BS Aa S a S aB 变换后得到的文法：S | A a BB | aBB | AaB | aB | Aa | aA B B | B | aB b文法变换算法（3）无用产生式: A , A不出现在任何句型中;消除方法：关键是找到这样的非终极符，how?生成会出现在句型中的非终极符集合SSSS = S Si SS, Si 1 , Si n把1 , n中的所有非终极符加入SS中;重复直到没有新的非终极符加入;不属于SS的非终极符,它们的产生式是无用产生式,删除掉;消除无用产生式的例子S | A a BBA B B | aB |bC cSS = SSS = S, A, BSS = S

21、, A, BC c是无用产生式文法变换算法（4）特型产生式: A B消除算法对每个非终极符A,构造 SA = B| A+B, BVN如果C SA,而且C 不是特型产生式,则增加 A ;删除特型产生式;删除无用产生式;消除特型产生式的例子S | AA B | aB bSS = A,BSA = BS aS bA bS | a | bA a | bB bSB = 文法变换算法（5）消除公共前缀(left factoring)公共前缀A 1 | | n| 1| m提取公因子A A| 1| mA 1 | | n文法变换算法（6-1）消除左递归(left recursion) 递归分为直接左递归和间接左递

22、归直接左递归: A A 1 | | A n| 1| m消除方法: A 1A| mA A 1A | | nA|消除左递归的例子P:(1) E T(2) E E + T(3) T F(4) T T * F(5) F (E)(6) F i(7) F n E T E E +T E | E E + T | T = + T 1 = T文法变换算法（6-2）消除左递归(left recursion)间接左递归: 消除方法: 非终极符排序消元法 S A b A S a | b 1:S 2:A A Aba | b A bA A baA | 文法变换算法（6-2）消除左递归(left recursion)间接左递

23、归: 消除方法: 非终极符排序消元法 S Qc | c Q Rb | b R S a | a 1:R 2:Q 3:S R Sa | a Q Rb | b Sab | ab | b S Qc | c Sabc | abc | bc | c S (abc | bc | c)S S abcS | 文法变换算法（6-2）消除左递归(left recursion)间接左递归: 排序不同，变换后文法也不同 S Qc | c Q Rb | b R S a | a 1:S 2:Q 3:R S Qc | c Q Rb | b R Sa | a (Qc|c)a | a Qca | ca |a (Rb|b)ca | ca | a S Qc | cQ Rb | bR (bca | ca | a)R R bcaR | 第3章 outline语法分析概述1.功能需求(输入，输出，主要功能)2.分析算法+数据结构3.构造语法分析器的通用过程上下文无关文法语法分析树和抽象语法树二义性文法文法变换算法语法错误处理语法错误处理编译器的任务是检测invalid的程序，并将valid的程序翻译成目标代码。Erro