编译原理和技术课件

编译原理和技术

第一章引论

名词解释翻译器(translator)、编译器(compiler)解释器(interpreter)编译器从逻辑上可以分成若干个阶段每个阶段把源程序从一种表示变换成另一种表示本章通过描述编译器的各个阶段来介绍编译这个课题1.1编译器概述词法分析器语法分析器语义分析器源程序中间代码生成器独立于机器的代码优化器代码生成器依赖于机器的代码优化器目标机器代码符号表符号表

positioninitialrate.........123词法分析器id,1

=

id,2

+

id,3

60

position=initial+rate

601.1编译器概述

记号流

字符流1.1编译器概述表达式的语法特征任何一个标识符都是表达式任何一个数都是表达式如果e1和e2都是表达式，那么

e1+e2

e1

*

e2

(e1)也都是表达式表达式表达式表达式标识符表达式表达式(initial)标识符(rate)数(60)*+initial+rate*60的分析树符号表

positioninitialrate.........123语法分析器id,1

=

id,2

+

id,3

60

=

+

60

id,1

id,2

id,3

语法树1.1编译器概述

记号流符号表

positioninitialrate.........1231.1编译器概述语义分析器

=

+

60

id,1

id,2

id,3

=

+

inttofloatid,1

id,2

id,3

60

语法树

语法树符号表

positioninitialrate.........123中间代码生成器t1=inttofloat(60)t2=id3

t1t3=id2+t2id1=t3

=

+

inttofloatid,1

id,2

id,3

60

1.1编译器概述

三地址中间代码

语法树符号表

positioninitialrate.........123代码优化器t1=inttofloat(60)t2=id3

t1t3=id2+t2id1=t3t1=id3*60.0id1=id2+t11.1编译器概述

三地址中间代码

三地址中间代码符号表

positioninitialrate.........123代码生成器MOVFid3,R2MULF#60.0,R2MOVFid2,R1ADDFR2,R1MOVFR1,id1t1=id3*60.0id1=id2+t11.1编译器概述

三地址中间代码

汇编代码1.1编译器概述解释器和编译器的区别词法分析器语法分析器语义分析器源程序中间代码生成器独立于机器的代码优化器代码生成器依赖于机器的代码优化器目标机器代码解释器不生成目标代码，而是直接执行源程序所指定的运算

解释器也需要对源程序进行词法、语法和语义分析,中间代码生成1.1编译器概述BASIC年代的解释器功能：它将高级语言的源程序翻译成一种中间语言程序，然后对中间语言程序进行解释执行在那个年代，编译和解释两个功能是合在一个程序中，该程序被称为解释器Java年代的解释器上述两个功能分在两个程序中前一个叫做编译器，它把源程序翻译成一种叫做字节码的中间语言程序后一个叫做解释器，它对字节码程序进行解释执行1.1编译器概述阶段分组前端后端词法分析器语法分析器语义分析器源程序中间代码生成器独立于机器的代码优化器代码生成器依赖于机器的代码优化器目标机器代码1.1编译器概述词法分析器语法分析器语义分析器源程序中间代码生成器独立于机器的代码优化器代码生成器依赖于机器的代码优化器目标机器代码阶段分组遍1.2编译器技术的应用

高级语言的实现高级编程语言易于编程，但程序运行较慢低级语言编程时可实施更有效的控制方式，得到更有效的代码，但难编写、易出错、难维护流行编程语言的大多数演变都是朝着提高抽象级别的方向每一轮编程语言新特征的出现都刺激编译器优化的新研究1.2编译器技术的应用

高级语言的实现 每一轮编程语言新特征的出现都刺激编译器优化的新研究支持用户定义的聚合数据类型和高级控制流，如数组和记录、循环和过程调用：C、Fortran面向对象的主要概念是数据抽象和性质继承，使得程序更加模块化并易于维护：Smalltalk、C++、C#、Java类型安全的语言：Java没有指针，也不允许指针算术。它用无用单元收集机制来自动地释放那些不再使用的变量占据的内存Java设计来支持代码移植和代码移动1.2编译器技术的应用

针对计算机体系结构的优化计算机体系结构的迅速演化引起对新的编译器技术一种不知足的需要并行化

编译器重新整理指令，使得指令级并行更有效

编译器从传统的串行程序自动生成并行代码，使之运行于多处理器上内存分层

编译器优化历来集中在优化处理器的执行上，但是现在更强调要使内存分层更有效1.2编译器技术的应用

新计算机体系结构的设计现在计算机系统的性能不仅仅取决于它的原始速度，还取决于编译器是否能生成充分利用其特征的代码在现代计算机体系结构的研究中，在处理器的设计阶段就开发编译器，并将编译生成的代码在模拟器上运行，以评价拟采用体系结构的特征编译器技术影响计算机体系结构设计的一个著名例子是精简指令集计算机（RISC）的发明1.2编译器技术的应用

程序翻译二进制翻译

编译器技术可用于把一种机器的二进制代码翻译成另一种机器的代码，以运行原先为别的指令集编译的代码数据库查询解释器

数据库查询由一些谓词组成，这些谓词由包含关系运算的布尔表达式组成，可以被解释执行,也可以被编译成搜索数据库的命令2.1词法记号及属性

2.1.1词法记号、模式、词法单元

记号名

词法单元例举

模式的非形式描述

if if 字符i,f

for for 字符f,o,rrelation <,<=,=,… <或<=或=或…id sum,count,D5 由字母开头的字母数字串number 3.1,10,2.8E12 任何数值常数literal “seg.error” 引号“和”之间任意不含 引号本身的字符串2.1词法记号及属性历史上词法定义中的一些问题忽略空格带来的困难

DO8I

3.75 等同于 DO8I

3.75DO8I

3,75关键字不保留

IFTHENTHENTHEN=ELSE；ELSE…关键字、保留字和标准标识符的区别保留字是语言预先确定了含义的词法单元标准标识符也是预先确定了含义的标识符，但程序可以重新声明它的含义2.1词法记号及属性2.1.2词法记号的属性

position=initial+rate

60的记号和属性值：

id，指向符号表中position条目的指针

assign_op

id，指向符号表中initial条目的指针

add_op

id，指向符号表中rate条目的指针

mul_op

number，整数值60

2.1词法记号及属性2.1.3词法错误词法分析器对源程序采取非常局部的观点例：难以发现下面的错误

fi(a==f(x))

…在实数是“数字串.数字串”格式下，可以发现下面的错误 123.x紧急方式的错误恢复 删掉当前若干个字符，直至能读出正确的记号错误修补 进行增、删、替换和交换字符的尝试2.2词法记号的描述与识别

2.2.1串和语言字母表：符号的有限集合，例：={0,1}串：符号的有穷序列，例：0110,

语言：字母表上的一个串集 {,0,00,000,…},{},句子：属于语言的串串的运算连接（积） xy，s

=s=s

幂

s0为，si为si-1s（i>0）

2.2词法记号的描述与识别

语言的运算并： L

M={s|s

L或s

M}连接： LM={st|s

L且t

M}幂： L0是{

}，Li是Li-1L

闭包： L

=L0

L1

L2

…正闭包： L+=L1

L2

…例L:{A,B,…,Z,a,b,…,z},D:{0,1,…,9}L

D,LD,L6,L*,L(L

D)*,D+

2.2词法记号的描述与识别

2.2.2正规式正规式用来表示简单的语言，叫做正规集

正规式 定义的语言 备注

{

}

a {a} a

(r)|(s) L(r)∪L(s) r和s是正规式 (r)(s)

L(r)L(s) r和s是正规式

(r)*

(L(r))* r是正规式

(r) L(r) r是正规式 ((a)(b)*)|(c)可以写成ab*|c

2.2词法记号的描述与识别

正规式的例子

={a,b}a|b

{a,b}(a|b)(a|b)

{aa,ab,ba,bb}aa|ab|ba|bb

{aa,ab,ba,bb}a* 由字母a构成的所有串集(a|b)* 由a和b构成的所有串集复杂的例子(00|11|((01|10)(00|11)

(01|10)))

句子：010011010000100000101110012.2词法记号的描述与识别

2.2.3正规定义

对正规式命名，使表示简洁 d1

r1 d2

r2 ... dn

rn各个di的名字都不同每个ri都是

{d1,d2,…,di-1}上的正规式2.2词法记号的描述与识别

正规定义的例子C语言的标识符是字母、数字和下划线组成的串

letter_

A|B|…|Z|a|b|…

|z|_

digit

0

|1|…|9 id

letter_(letter_

|digit)*

2.2词法记号的描述与识别

正规定义的例子

无符号数集合，例1946,11.28,63E8,1.99E

6

digit

0

|1|…|9

digits

digit

digit*

optional_fraction

.digits|

optional_exponent

(E(+|

|

)digits)|

number

digitsoptional_fractionoptional_exponent

简化表示 number

digit+(.digit+)?(E(+|

)?digit+)?2.2词法记号的描述与识别

正规定义的例子（进行下一步讨论的例子）

while

while do

do relop

<|<=|=|<>|>|>=

letter

A|B|…|Z|a|b|…

|z id

letter(letter|digit)* number

digit+(.digit+)?(E

(+|

)?

digit+)?delim

blank|tab|newline

ws

delim+2.2词法记号的描述与识别

2.2.4转换图关系算符的转换图

051624837return(relop,LE)return(relop,NE)return(relop,LT)return(relop,GE)return(relop,GT)return(relop,EQ)开始<=>=>=**otherother2.2词法记号的描述与识别

标识符和关键字的转换图91011开始letterother*letter或digitreturn(installId())2.2词法记号的描述与识别

无符号数的转换图 number

digit+(.digit+)?(E

(+|

)?

digit+)?开始1912131415161718digitdigitdigitdigitdigitdigitother.E+/

Edigitotherotherreturn(installNum())*2.2词法记号的描述与识别

空白的转换图delim

blank|tab|newlinews

delim+2122开始delimother*delim202.3有限自动机

2.3.1不确定的有限自动机（简称NFA） 一个数学模型，它包括：

1、有限的状态集合S

2、输入符号集合

3、转换函数move:S

(

{

})

P(S)

4、状态s0是唯一的开始状态

5、F

S是接受状态集合识别语言(a|b)*ab

的NFA12开始a0abb输入符号ab0{0,1}{0}1

{2}2

状态

NFA的转换表2.3有限自动机

识别语言(a|b)*ab

的NFA12开始a0abb2.3有限自动机

例

识别aa*|bb*的NFA12开始a0abb34

2.3.2确定的有限自动机（简称DFA)

一个数学模型，包括：1、有限的状态集合S2、输入字母集合

3、转换函数move:S

S，且可以是部分函数4、唯一的开始状态s05、接受状态集合F

S12开始a0abbab识别语言(a|b)*ab

的DFA2.3有限自动机

2.3有限自动机

例 DFA，识别{0,1}上能被5整除的二进制数 已读过 尚未读 已读部分的值 某时刻 101 0111000 5 读进0 1010 111000 52=10 读进1 10101 11000 102+1=21

5个状态即可，分别代表已读部分的值除以5的余数例 DFA，识别{0,1}上能被5整除的二进制数0123开始410010101012.3有限自动机

10102=10101112=710例 DFA,接受0和1的个数都是偶数的字符串00003211奇0奇1奇0偶11011开始偶0偶1偶0奇12.3有限自动机

2.3.3NFA到DFA的变换

子集构造法 1、DFA的一个状态是NFA的一个状态集合

2、读了输入a1a2…an后，

NFA能到达的所有状态：s1,s2,…,sk，则

DFA到达状态{s1,s2,…,sk}12a开始0abb{0}{0,1}aba{0,2}b2.3有限自动机

未画完19开始

0ab

ab6782345

例 (a|b)*ab，NFA如下，把它变换为DFA2.3有限自动机

19开始

0ab

ab6782345

输入符号ab状态

2.3有限自动机

19开始

0ab

ab6782345

输入符号abA状态

A={0,1,2,4,7}

2.3有限自动机

19开始

0ab

ab6782345

输入符号abAB状态

A={0,1,2,4,7}B={1,2,3,4,6,7,8}

2.3有限自动机

19开始

0ab

ab6782345

输入符号abABB状态

A={0,1,2,4,7}B={1,2,3,4,6,7,8}2.3有限自动机

19开始

0ab

ab6782345

输入符号abABCB状态

A={0,1,2,4,7}B={1,2,3,4,6,7,8}C={1,2,4,5,6,7}

2.3有限自动机

19开始

0ab

ab6782345

输入符号abABCBC状态

A={0,1,2,4,7}B={1,2,3,4,6,7,8}C={1,2,4,5,6,7}2.3有限自动机

19开始

0ab

ab6782345

输入符号abABCBBC状态

A={0,1,2,4,7}B={1,2,3,4,6,7,8}C={1,2,4,5,6,7}2.3有限自动机

19开始

0ab

ab6782345

输入符号abABCBBDC状态

A={0,1,2,4,7}B={1,2,3,4,6,7,8}C={1,2,4,5,6,7}D={1,2,4,5,6,7,9}

2.3有限自动机

19开始

0ab

ab6782345

输入符号abABCBBDCD状态

A={0,1,2,4,7}B={1,2,3,4,6,7,8}C={1,2,4,5,6,7}D={1,2,4,5,6,7,9}

2.3有限自动机

19开始

0ab

ab6782345

输入符号abABCBBDCBCD状态

A={0,1,2,4,7}B={1,2,3,4,6,7,8}C={1,2,4,5,6,7}D={1,2,4,5,6,7,9}

2.3有限自动机

19开始

0ab

ab6782345

输入符号abABCBBDCBCDBC状态

A={0,1,2,4,7}B={1,2,3,4,6,7,8}C={1,2,4,5,6,7}D={1,2,4,5,6,7,9}

2.3有限自动机

19开始

0ab

ab6782345

输入符号abABCBBDCBCDBC状态

BD开始aAabbabCba2.3有限自动机

19开始

0ab

ab6782345

BD开始aAabbabCba12开始a0abbab识别语言(a|b)*ab

的自动机2.3有限自动机

19开始

0ab

ab6782345

BD开始aAabbabCba12开始a0abbab识别语言(a|b)*ab

的自动机子集构造法不一定得到最简DFA2.3有限自动机

BD开始aAabbaa,bCbaEb2.3.4DFA的化简死状态在转换函数由部分函数改成全函数表示时引入左图需要引入死状态E；右图无须引入死状态BD开始aAabbabCba2.3有限自动机

可区别的状态A和B是可区别的状态

从A出发，读过单字符b构成的串，到达非接受状态C，而从B出发，读过串b，到达接受状态DA和C是不可区别的状态 无任何串可用来像上面这样 区别它们BD开始aAabbabCba2.3有限自动机

方法1.{A,B,C},{D}move({A,B,C},a)={B}move({A,B,C},b)={C,D}2.{A,C},{B},{D}move({A,C},a)={B}move({A,C},b)={C}BD开始aAabbabCba12开始a0abbab2.3有限自动机

从正规式建立识别器的步骤从正规式构造NFA（本节介绍） 用语法制导的算法，它用正规式语法结构来指导构造过程把NFA变成DFA（子集构造法，已介绍）将DFA化简（合并不可区别状态，也已介绍）2.4从正规式到有限自动机首先构造识别

和字母表中一个符号的NFA重要特点：仅一个接受状态，它没有向外的转换i开始

识别正规式

的NFAafif开始识别正规式a的NFA2.4从正规式到有限自动机构造识别主算符为选择的正规式的NFA重要特点：仅一个接受状态，它没有向外的转换

fi开始识别正规式s|t的NFAN(s)N(t)

2.4从正规式到有限自动机构造识别主算符为连接的正规式的NFA重要特点：仅一个接受状态，它没有向外的转换识别正规式st的NFAiN(s)f开始N(t)2.4从正规式到有限自动机构造识别主算符为闭包的正规式的NFA重要特点：仅一个接受状态，它没有向外的转换N(s)f开始识别正规式s*的NFAi

2.4从正规式到有限自动机对于加括号的正规式(s)，使用N(s)本身作为它的NFA2.4从正规式到有限自动机本方法产生的NFA有下列性质N(r)的状态数最多是r中符号和算符总数的两倍N(r)只有一个接受状态，接受状态没有向外的转换2.4从正规式到有限自动机19开始

0ab

ab6782345

本方法产生的NFA有下列性质N(r)的每个状态有一个用

的符号标记的指向其它结点的转换，或者最多两个指向其它结点的

转换2.4从正规式到有限自动机19开始

0ab

ab6782345

2.4从正规式到有限自动机

19开始

0ab

ab6782345

r9r7r8r4r3r5r6*)(r2r1a|bab(a|b)*ab的分解2.4从正规式到有限自动机

19开始

0

ab678ab2345

r9r7r8r4r3r5r6*)(r2r1a|bab(a|b)*ab的分解2.4从正规式到有限自动机

19开始

0ab

ab6782345

r9r7r8r4r3r5r6*)(r2r1a|bab(a|b)*ab的分解2.4从正规式到有限自动机

19开始

0ab

ab6782345

r9r7r8r4r3r5r6*)(r2r1a|bab(a|b)*ab的分解2.4从正规式到有限自动机

19开始

0ab

ab6782345

r9r7r8r4r3r5r6*)(r2r1a|bab(a|b)*ab的分解2.4从正规式到有限自动机19开始

0ab

ab6782345

r9r7r8r4r3r5r6*)(r2r1a|bab(a|b)*ab的分解2.4从正规式到有限自动机

19开始

0ab

ab6782345

r9r7r8r4r3r5r6*)(r2r1a|bab(a|b)*ab的分解

(a|b)*ab的两个NFA的比较12开始a0abb手工构造:算法构造:2.4从正规式到有限自动机19开始

0ab

ab6782345

小结：从正规式建立识别器的步骤从正规式构造NFA把NFA变成DFA将DFA化简存在其它办法2.4从正规式到有限自动机

用Lex建立词法分析器的步骤Lex编译器Lex源程序lex.llex.yy.cC编译器lex.yy.ca.outa.out输入流记号序列2.5词法分析器的生成器Lex程序包括三个部分声明％％翻译规则％％辅助过程Lex程序的翻译规则p1 {动作1}p2 {动作2}… …pn {动作n}2.5词法分析器的生成器例——声明部分%{/*常量LT,LE,EQ,NE,GT,GE, WHILE,DO,ID,NUMBER,RELOP的定义*/%}/*

正规定义

*/delim [\t\n]ws {delim}+letter [A

Za

z]digit [0

9]id {letter}({letter}|{digit})*number {digit}+(\.{digit}+)?(E[+\

]?{digit}+)?2.5词法分析器的生成器例——翻译规则部分{ws} {/*

没有动作，也不返回*/}while {return(WHILE);}do {return(DO);}{id} {yylval=install_id();return(ID);}{number} {yylval=install_num(); return(NUMBER);}“<” {yylval=LT;return(RELOP);}“<=” {yylval=LE;return(RELOP);}“=” {yylval=EQ;return(RELOP);}“<>” {yylval=NE;return(RELOP);}“>” {yylval=GT;return(RELOP);}“>=” {yylval=GE;return(RELOP);}2.5词法分析器的生成器例——辅助过程部分installId(){ /*

把词法单元装入符号表并返回指针。 yytext指向该词法单元的第一个字符， yyleng给出的它的长度 */}installNum(){ /*

类似上面的过程，但词法单元不是标识符而是数*/}2.5词法分析器的生成器词法分析器的作用和接口，用高级语言编写词法分析器等内容掌握下面涉及的一些概念，它们之间转换的技巧、方法或算法非形式描述的语言

正规式正规式

NFA非形式描述的语言

NFANFA

DFADFA

最简DFA非形式描述的语言

DFA（或最简DFA）本章要点叙述下面的正规式描述的语言，并画出接受该语言的最简DFA的状态转换图

(1|01)*0*描述的语言是，所有不含子串001的0和1的串

3start001.1012刚读过的不是0连续读过一个0连续读过不少于两个0例题1bbbaabbaabbstartabbaaaaabababbabaababababababbbabaabb例题2用状态转换图表示接受 (a|b)

a(a|b)(a|b)的DFA写出语言“所有相邻数字都不相同的非空数字串”的正规定义

123031357106798035790123answer

(0|no_00)(no_00)

(no_0|

)|no_0

no_0

(1|no_0-11)(no_0-11)

(no_0-1|

)|no_0-1

...no_0-8

9将这些正规定义逆序排列就是答案例题3 下面C语言编译器编译下面的函数时，报告 parseerrorbefore‘else’longgcd(p,q)longp,q;{if(p%q==0)

/*thenpart*/ returnq 此处遗漏分号 else

/*elsepart*/ returngcd(q,p%q);}例题43.1上下文无关文法3.1.1上下文无关文法的定义正规式能定义一些简单的语言，能表示给定结构的固定次数的重复或者没有指定次数的重复 例：a(ba)5,a(ba)*正规式不能用于描述配对或嵌套的结构 例1：配对括号串的集合 例2：{wcw|w是a和b的串}

3.1上下文无关文法上下文无关文法是四元组（VT,VN,S,P）VT

: 终结符集合VN

: 非终结符集合S: 开始符号，非终结符中的一个P

: 产生式集合，产生式形式:A

例({id,+,

,

,(,)},{expr,op},expr,P)expr

expr

op

expr expr

(expr)expr

expr expr

idop

+ op

3.1上下文无关文法简化表示expr

expr

op

expr |

(expr)|

expr|idop

+|

简化表示E

EAE|(E)|

E|idA

+|

3.1上下文无关文法3.1.2

推导把产生式看成重写规则，把符号串中的非终结符用其产生式右部的串来代替例 E

E+E|E

E|(E)|

E|id

E

E

(E)

(E+E)

(id+E)

(id+id)概念 上下文无关语言、等价的文法、句型记号S

*

、S

+w

3.1上下文无关文法例E

E+E|E

E|(E)|

E|id

最左推导 E

lm

E

lm

(E)

lm

(E

+E)

lm

(id+E)

lm

(id+id)最右推导（规范推导） E

rm

E

rm

(E)

rm

(E+E)

rm

(E+id)

rm

(id+id)3.1上下文无关文法3.1.3分析树例E

E+E|E

E|(E)|

E|idEE

()EEE+idid3.1上下文无关文法3.1.4二义性 E

E

E

E

E+E

id

E

E

E+E

id

E+E

id

E+E

id

id+E

id

id+E

id

id+id

id

id+id 两个不同的最左推导3.1上下文无关文法3.1.4二义性 E

E

E

E

E+E

id

E

E

E+E

id

E+E

id

E+E

id

id+E

id

id+E

id

id+id

id

id+id 两棵不同的语法树EEE*+EEidididEEidE*+EEidid3.2

语言和文法文法的优点

文法给出了精确的，易于理解的语法说明自动产生高效的分析器可以给语言定义出层次结构以文法为基础的语言的实现便于语言的修改文法的问题文法只能描述编程语言的大部分语法，不能描述语言中上下文有关的语法特征3.2

语言和文法3.2.1

正规式和上下文无关文法的比较正规式(a|b)*ab文法A0

a

A0|bA0|a

A1A1

b

A2A2

12开始a0abb3.2

语言和文法3.2.2分离词法分析器理由为什么要用正规式定义词法

词法规则非常简单，不必用上下文无关文法对于词法记号，正规式描述简洁且易于理解从正规式构造出的词法分析器效率高3.2

语言和文法从软件工程角度看，词法分析和语法分析的分离有如下好处简化设计编译器的效率会改进编译器的可移植性加强便于编译器前端的模块划分3.2

语言和文法能否把词法分析并入到语法分析中，直接从字符流进行语法分析若把词法分析和语法分析合在一起，则必须将语言的注解和空白的规则反映在文法中，文法将大大复杂注解和空白由自己来处理的分析器，比注解和空格已由词法分析器删除的分析器要复杂得多3.2

语言和文法3.2.3

验证文法产生的语言G:S

(S)S|

L(G)=配对的括号串的集合3.2

语言和文法3.2.3

验证文法产生的语言G:S

(S)S|

L(G)=配对的括号串的集合按推导步数进行归纳：推出的是配对括号串归纳基础：S

归纳假设：少于n步的推导都产生配对的括号串归纳步骤：n步的最左推导如下：

S(S)S*(x)S*(x)y3.2

语言和文法3.2.3

验证文法产生的语言G:S

(S)S|

L(G)=配对的括号串的集合按串长进行归纳：配对括号串可由S推出归纳基础：S

归纳假设：长度小于2n的都可以从S推导出来归纳步骤：考虑长度为2n(n

1)的w=(x)y

S(S)S*(x)S*(x)y3.2

语言和文法3.2.4适当的表达式文法用一种层次观点看待表达式 id

id

(id+id)+id

id+id3.2

语言和文法3.2.4适当的表达式文法用一种层次观点看待表达式

id

id

(id+id)+id

id+id

id

id

(id+id)

文法 expr

expr+term|term term

term

factor|factor

factor

id|(expr)3.2

语言和文法expr

expr+term|termterm

term

factor|factor

factor

id|(expr)expridtermfactorididterm*termfactorfactor*exprexpr+idfactortermididterm*termfactorfactorid+id

id分析树

id

id

id分析树

3.2

语言和文法3.2.5消除二义性stmt

ifexprthenstmt |ifexprthenstmtelsestmt |other句型：ifexprthenifexprthenstmt

elsestmt两个最左推导：

stmt

ifexprthenstmt

ifexprthenifexprthenstmtelsestmt

stmt

ifexprthenstmtelsestmt

ifexprthenifexprthenstmtelsestmt

3.2

语言和文法

无二义的文法stmt

matched_stmt

|unmatched_stmtmatched_stmt

ifexprthenmatched_stmt

elsematched_stmt

|otherunmatched_stmt

ifexprthenstmt |ifexprthenmatched_stmt

elseunmatched_stmt3.2

语言和文法3.2.6消除左递归文法左递归 A

+Aa

直接左递归 A

Aa|b

串的特点 ba...a消除直接左递归 A

bA

A

aA

|

3.2

语言和文法例

算术表达文法

E

E+T|T （T+T...+T） T

T

F|F （F

F...

F） F

(E)|id消除左递归后文法 E

TE

E

+TE

|

T

FT

T

FT

|

F

(E)|id3.2

语言和文法非直接左递归 S

Aa|b

A

Sd|

先变换成直接左递归 S

Aa|b A

Aad|bd|

再消除左递归

S

Aa|b A

bdA

|A

A

adA

|

3.2

语言和文法3.2.7

提左因子有左因子的文法 A

1|

2提左因子 A

A

A

1|

2

3.2

语言和文法例

悬空else的文法 stmt

ifexprthenstmtelsestmt

|ifexprthenstmt |other 提左因子 stmt

ifexprthenstmt

optional_else_part |other optional_else_part

elsestmt |

3.2

语言和文法3.2.8

非上下文无关的语言构造L1={wcw|w属于(a|b)*}标识符的声明应先于其引用的抽象

L2={anbmcndm|n

0,m

0}形参个数和实参个数应该相同的抽象

L3={anbncn|n

0}早先排版描述的一个现象的抽象

b

e

g

i

n：5个字母键，5个回退键，5个下划线键3.2

语言和文法L1

={wcwR|w

(a|b)*}

S

aSa|bSb|c

L2={anbmcmdn|n

1,m

1}

S

aSd|aAd A

bAc|bcL

2={anbncmdm|n1，m1} S

AB A

aAb|ab

B

cBd|cd3.2

语言和文法L3

={anbn|n

1}

S

aSb|abL3

是不能用正规式描述的语言的一个范例

若存在接受L3

的DFAD，状态数为k个设D读完,

a,aa,

…,ak

分别到达状态s0,s1,

…,sk至少有两个状态相同，例如是si和sj，则ajbi属于L3

si…fs0标记为ai的路径标记为bi的路径标记为aj

i的路径…

…3.2

语言和文法3.2.9

形式语言鸟瞰文法G=(VT

,VN,S,P)0型文法：

，,(VN

VT)*,|

|13.2

语言和文法3.2.9

形式语言鸟瞰文法G=(VT

,VN,S,P)0型文法：

，,(VN

VT)*,|

|1短语文法3.2

语言和文法3.2.9

形式语言鸟瞰文法G=(VT

,VN,S,P)0型文法：

，,(VN

VT)*,|

|11型文法：|

||

|，但S

可以例外短语文法3.2

语言和文法3.2.9

形式语言鸟瞰文法G=(VT

,VN,S,P)0型文法：

，,(VN

VT)*,|

|11型文法：|

||

|，但S

可以例外短语文法、上下文有关文法3.2

语言和文法3.2.9

形式语言鸟瞰文法G=(VT

,VN,S,P)0型文法：

，,(VN

VT)*,|

|11型文法：|

||

|，但S

可以例外2型文法：A

，A

VN,

(VN∪VT)*短语文法、上下文有关文法3.2

语言和文法3.2.9

形式语言鸟瞰文法G=(VT

,VN,S,P)0型文法：

，,(VN

VT)*,|

|11型文法：|

||

|，但S

可以例外2型文法：A

，A

VN,

(VN∪VT)*短语文法、上下文有关文法、上下文无关文法3.2

语言和文法3.2.9

形式语言鸟瞰文法G=(VT

,VN,S,P)0型文法：

，,(VN

VT)*,|

|11型文法：|

||

|，但S

可以例外2型文法：A

，A

VN,

(VN∪VT)*3型文法：A

aB或A

a，A,B

VN,a

VT

短语文法、上下文有关文法、上下文无关文法3.2

语言和文法3.2.9

形式语言鸟瞰文法G=(VT

,VN,S,P)0型文法：

，,(VN

VT)*,|

|11型文法：|

||

|，但S

可以例外2型文法：A

，A

VN,

(VN∪VT)*3型文法：A

aB或A

a，A,B

VN,a

VT

短语文法、上下文有关文法、上下文无关文法、正规文法3.2

语言和文法例 L3＝{anbncn|n

1}的上下文有关文法S

aSBC

S

aBC

CB

BCaB

ab

bB

bb bC

bccC

ccanbncn的推导过程如下：S

*an-1S(BC)n

1 用S

aSBCn-1次S

+an(BC)n

用S

aBC1次S

+anBnCn 用CB

BC交换相邻的CBS

+anbBn

1Cn 用aB

ab1次S

+anbnCn

用bB

bbn-1次S

+anbncCn-1 用bC

bc1次S

+anbncn 用cC

cc

n-1次3.3

自上而下分析3.3.1自上而下分析的一般方法例 文法 S

aCb C

cd|c

为输入串w=acb建立分析树SaCbSaCbcdSaCbc 不能处理左递归3.3

自上而下分析不能处理左递归的例子 算术表达文法

E

E+T|T T

T

F|F F

(E)|idEE+TE+TE+T………3.3

自上而下分析3.3.1自上而下分析的一般方法例 文法 S

aCb C

cd|c

为输入串w=acb建立分析树SSSaCbaaCCbbcdc 不能处理左递归、复杂的回溯技术3.3

自上而下分析3.3.1自上而下分析的一般方法例 文法 S

aCb C

cd|c

为输入串w=acb建立分析树SSSaCbaaCCbbcdc 不能处理左递归、复杂的回溯技术、回溯导致语义工作推倒重来3.3

自上而下分析3.3.1自上而下分析的一般方法例 文法 S

aCb C

cd|c

为输入串w=acb建立分析树SSSaCbaaCCbbcdc 不能处理左递归、复杂的回溯技术、回溯导致语义工作推倒重来、难以报告出错的确切位置3.3

自上而下分析3.3.1自上而下分析的一般方法例 文法 S

aCb C

cd|c

为输入串w=acb建立分析树SSSaCbaaCCbbcdc 不能处理左递归、复杂的回溯技术、回溯导致语义工作推倒重来、难以报告出错的确切位置、效率低3.3

自上而下分析3.3.2LL(1)文法对文法加什么样的限制可以保证没有回溯？先定义两个和文法有关的函数FIRST(

)={a|

*a…,a

VT} 特别是，

*

时，规定

FIRST(

) 对A的任何两个不同选择

i

和

j，希望有 FIRST(

i)

FIRST(

j)=

若FIRST(

i)或FIRST(

j)含，还需增加条件3.3

自上而下分析3.3.2LL(1)文法对文法加什么样的限制可以保证没有回溯？先定义两个和文法有关的函数FIRST(

)={a|

*a…,a

VT} 特别是，

*

时，规定

FIRST(

)FOLLOW(A)={a|S

*…Aa…，a

VT} 如果A是某个句型的最右符号，那么$属于FOLLOW(A)3.3

自上而下分析LL(1)文法 任何两个产生式A

|

都满足下列条件：FIRST(

)

FIRST(

)=

若

*

，那么FIRST(

)

FOLLOW(A)=

例如,对于下面文法，面临a…时，第2步推导不知用哪个产生式S

A

BA

ab| a

FIRST(ab)

FOLLOW(A)

B

aCC…3.3

自上而下分析LL(1)文法 任何两个产生式A

|

都满足下列条件：FIRST(

)

FIRST(

)=

若

*

，那么FIRST(

)

FOLLOW(A)=

LL(1)文法有一些明显的性质没有公共左因子不是二义的不含左递归3.3

自上而下分析例 E

TE

E

+TE

|

T

FT

T

FT

|

F

(E)|idFIRST(E)=FIRST(T)=FIRST(F)={(,id}FIRST(E

)={+,

}FRIST(T

)={

,

}FOLLOW(E)=FOLLOW(E

)={),$}FOLLOW(T)=FOLLOW(T

)={+,),$}FOLLOW(F)={+,

,),$}3.3

自上而下分析3.3.3递归下降的预测分析为每一个非终结符写一个分析过程这些过程可能是递归的例 type

simple |

id |array[simple]oftype simple

integer |char |numdotdotnum3.3

自上而下分析一个辅助过程voidmatch(terminalt){ if(lookahead==t)lookahead=nextToken(); elseerror();}3.3

自上而下分析voidtype(){ if((lookahead==integer)||(lookahead==char)|| (lookahead==num)) simple(); elseif(lookahead==

){match(

);match(id);} elseif(lookahead==array){ match(array);match(

[

);simple(); match(

]

);match(of);type(); } elseerror();}

type

simple |

id |array[simple]oftype3.3

自上而下分析voidsimple(){ if(lookahead==integer)match(integer); elseif(lookahead==char)match(char); elseif(lookahead==num){ match(num);match(dotdot);match(num); } elseerror();}

simple

integer |char |numdotdotnum3.3

自上而下分析3.3.4非递归的预测分析a+b$输入预测分析程序分析表M输出

XYZ$栈3.3

自上而下分析非终结符输

入

符

号

id

+

...EE

TE

E

E

+TE

T

T

FT

T

T

T

FT

F

F

id分析表的一部分3.3

自上而下分析栈

输

入

输

出

$E

id

id+id$

预测分析器接受输入id

*

id+id的前一部分动作

3.3

自上而下分析栈

输

入

输

出

$E

id

id+id$

$E

T

id

id+id$

E

TE

预测分析器接受输入id

*

id+id的前一部分动作

3.3

自上而下分析栈

输

入

输

出

$E

id

id+id$

$E

T

id

id+id$

E

TE

$E

T

F

id

id+id$

T

FT

预测分析器接受输入id

*

id+id的前一部分动作

3.3

自上而下分析栈

输

入

输

出

$E

id

id+id$

$E

T

id

id+id$

E

TE

$E

T

F

id

id+id$

T

FT

$E

T

id

id

id+id$

F

id

预测分析器接受输入id

*

id+id的前一部分动作

3.3

自上而下分析栈

输

入

输

出

$E

id

id+id$

$E

T

id

id+id$

E

TE

$E

T

F

id

id+id$

T

FT

$E

T

id

id

id+id$

F

id

$E

T

id+id$

预测分析器接受输入id

*

id+id的前一部分动作

3.3

自上而下分析栈

输

入

输

出

$E

id

id+id$

$E

T

id

id+id$

E

TE

$E

T

F

id

id+id$

T

FT

$E

T

id

id

id+id$

F

id

$E

T

id+id$

$E

T

F

id+id$

T

FT

预测分析器接受输入id

*

id+id的前一部分动作

3.3

自上而下分析栈

输

入

输

出

$E

id

id+id$

$E

T

id

id+id$

E

TE

$E

T

F

id

id+id$

T

FT

$E

T

id

id

id+id$

F

id

$E

T

id+id$

$E

T

F