编译原理与技术课件

词法分析本章内容词法分析器：把构成源程序的字符流翻译成记号流，还完成和用户接口的一些任务围绕词法分析器的自动生成展开介绍正规式、状态转换图和有限自动机概念

词法分析器语法分析器符号表记号(token)取下一个记号源程序2.1词法记号及属性

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

词法记号 词法单元例举

模式的非形式描述

var var varfor for forrelation <,<=,=,… <或<=或=或…id sum,count,D5 由字母开头的字母数字串num 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,*

num，整数值60

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

fi(a==f(x))…在实数是a.b格式下，可以发现下面的错误 123.紧急方式的错误恢复错误修补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

r1d2

r2...dn

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

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

正规定义的例子

Pascal语言的标识符集合 letter

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

|z

digit

0

|1|…|9 id

letter(letter|digit)*

2.2词法记号的描述与识别

正规定义的例子

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

6

digit

0

|1|…|9

digits

digit

digit*

optional_fraction

.digits|

optional_exponent

(E(+|

|

)digits)|

num

digitsoptional_fractionoptional_exponent简化表示 num

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

)?digit+)?

2.2词法记号的描述与识别

正规定义的例子

while

while do

do relop

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

letter(letter|digit)* num

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(install_id())2.2词法记号的描述与识别

无符号数的转换图开始1912131415161718digitdigitdigitdigitdigitdigitother.E+/

Edigitotherotherreturn(install_num())*num

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

)?

digit+)?

2.2词法记号的描述与识别

空白的转换图delim

blank|tab|newline

ws

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

2.3.1不确定的有限自动机（简称NFA） 一个数学模型，它包括：状态集合S输入符号集合

转换函数move:S

(

{

})

P(S)状态s0是开始状态

F

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

的NFA12开始a0abb识别语言(a|b)*ab

的NFA输入符号ab0{0,1}{0}1

{2}2

状态

NFA的转换表2.3有限自动机

2.3有限自动机

例

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

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

一个数学模型，包括：

状态集合S输入字母表转换函数move:S

S唯一的初态s

S终态集合F

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

的DFA2.3有限自动机

例：识别={0,1}上能被能5整除的二进制数0123开始4101 01110001010 11100010101 11000

2.3有限自动机

例：识别={0,1}上能被能5整除的二进制数0123开始402.3有限自动机

例：识别={0,1}上能被能5整除的二进制数0123开始4102.3有限自动机

例：识别={0,1}上能被能5整除的二进制数0123开始41002.3有限自动机

例：识别={0,1}上能被能5整除的二进制数0123开始410012.3有限自动机

例：识别={0,1}上能被能5整除的二进制数0123开始4100102.3有限自动机

例：识别={0,1}上能被能5整除的二进制数0123开始41001012.3有限自动机

例：识别={0,1}上能被能5整除的二进制数0123开始410010102.3有限自动机

例：识别={0,1}上能被能5整除的二进制数0123开始4100101012.3有限自动机

例：识别={0,1}上能被能5整除的二进制数0123开始41001010102.3有限自动机

例：识别={0,1}上能被能5整除的二进制数0123开始410010101012.3有限自动机

例：识别={0,1}上能被能5整除的二进制数0123开始4100101010110102=10101112=7102.3有限自动机

例：DFA，接受0和1的个数都是偶数的字符串312011110000开始偶0偶1奇0奇1奇0偶1偶0奇12.3有限自动机

2.3.3NFA到DFA的变换

子集构造法DFA的一个状态是NFA的一个状态集合读了输入a1a2…an后，

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

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

2.3.3NFA到DFA的变换

子集构造法DFA的一个状态是NFA的一个状态集合读了输入a1a2…an后，

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

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

2.3.3NFA到DFA的变换

子集构造法DFA的一个状态是NFA的一个状态集合读了输入a1a2…an后，

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

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

2.3.3NFA到DFA的变换

子集构造法DFA的一个状态是NFA的一个状态集合读了输入a1a2…an后，

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

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

2.3.3NFA到DFA的变换

子集构造法DFA的一个状态是NFA的一个状态集合读了输入a1a2…an后，

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

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

2.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有限自动机BD开始aAabbabCba19开始

0ab

ab6782345

输入符号abABCBBDCBCDBC状态

2.3有限自动机BD开始aAabbabCba12开始a0abbab19开始

0ab

ab6782345

识别语言(a|b)*ab

的自动机2.3有限自动机BD开始aAabbabCba12开始a0abbab19开始

0ab

ab6782345

识别语言(a|b)*ab

的自动机子集构造法不一定得到最简DFA2.3有限自动机BD开始aAabbaa,bCbaEb2.3.4DFA的化简死状态左图无须加死状态，右图加入死状态E。BD开始aAabbabCba2.3有限自动机可区别的状态A和B是可区别的状态A和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开始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.4从正规式到有限自动机

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

首先构造识别

和字母表中一个符号的NFAi开始

识别正规式

的NFAafif开始识别正规式a的NFA2.4从正规式到有限自动机

构造识别主算符为选择的正规式的NFA

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

2.4从正规式到有限自动机

构造识别主算符为连接的正规式的NFA

iN(s)f开始识别正规式st的NFAN(t)2.4从正规式到有限自动机

构造识别主算符为闭包的正规式的NFA

N(s)f开始识别正规式s*的NFAi

2.4从正规式到有限自动机

对于加括号的正规式(s)，使用N(s)本身作为它的NFA。2.4从正规式到有限自动机

本方法产生的NFA有下列性质:N(r)的状态数最多是r中符号和算符总数的两倍N(r)只有一个开始状态和一个接受状态，接受状态没有向外的转换N(r)的每个状态有一个用

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

转换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的分解2.4从正规式到有限自动机

(a|b)*ab的两个NFA的比较12开始a0abb19开始

0ab

ab6782345

手工构造:算法构造:2.4从正规式到有限自动机

小结：从正规式建立识别器的步骤从正规式构造NFA把NFA变成DFA将DFA化简存在其它办法2.5词法分析器的生成器

用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词法分析器的生成器例---辅助过程部分install_id(){ /*

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

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

正规式正规式

NFA非形式描述的语言

NFANFA

DFADFA

最简DFA非形式描述的语言

DFA（或最简DFA）例题1

叙述下面的正规式描述的语言，并画出接受该语言的最简DFA的状态转换图

(1|01)*0*

例题1

叙述下面的正规式描述的语言，并画出接受该语言的最简DFA的状态转换图

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

例题1

叙述下面的正规式描述的语言，并画出接受该语言的最简DFA的状态转换图

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

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

a(a|b)(a|b)的DFA例题2用状态转换图表示接收(a|b)

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

123031357106798035790123例题3写出语言“所有相邻数字都不相同的非空数字串”的正规定义

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将这些正规定义逆序排列就是答案例题4

下面C语言编译器编译下面的函数时，报告 parseerrorbefore‘else’longgcd(p,q)longp,q;{if(p%q==0)

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

/*elsepart*/ returngcd(q,p%q);}例题4

现在少了第一个注释的结束符号后，反而不报错了longgcd(p,q)longp,q;{if(p%q==0)

/*thenpart returnq 此处遗漏分号 else

/*elsepart*/ returngcd(q,p%q);}3.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上下文无关文法例({id,+,

,

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

expr

op

expr expr

(expr)expr

expr expr

idop

+ op

简化表示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

EE

EE

()EEE

()EEE+

EE

()EEE+idEE

()EEE+idid3.1上下文无关文法3.1.3二义性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+id3.1上下文无关文法3.1.3二义性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+idEEE*+EEidididEEidE*+EEidid3.2

语言和文法文法的优点

文法给出了精确的，易于理解的语法说明3.2

语言和文法文法的优点

文法给出了精确的，易于理解的语法说明自动产生高效的分析器3.2

语言和文法文法的优点

文法给出了精确的，易于理解的语法说明自动产生高效的分析器可以给语言定义出层次结构3.2

语言和文法文法的优点

文法给出了精确的，易于理解的语法说明自动产生高效的分析器可以给语言定义出层次结构以文法为基础的语言的实现便于语言的修改3.2

语言和文法文法的优点

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

语言和文法3.2.1

正规式和上下文无关文法的比较正规式(a|b)*ab3.2

语言和文法3.2.1

正规式和上下文无关文法的比较正规式(a|b)*ab12开始a0abb3.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.2分离词法分析器理由为什么要用正规式定义词法

词法规则非常简单，不必用上下文无关文法对于词法记号，正规式描述简洁且易于理解3.2

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

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

语言和文法把词法分析从语法分析中分离出来的理由

简化设计3.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)=配对的括号串的集合按推导步数进行归纳：推出的是配对括号串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推出3.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+id

3.2

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

id

id

(id+id)+id

id+id

id

id

(id+id)

3.2

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

id

id

(id+id)+id

id+id

id

id

(id+id)

文法 expr

expr+term|term

3.2

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

id

id

(id+id)+id

id+id

id

id

(id+id)

文法 expr

expr+term|term term

term

factor|factor

3.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|term term

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

3.2

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

ifexprthenstmt |ifexprthenstmtelsestmt |other句型：ifexprthenifexprthenstmt

elsestmt两个最左推导：

stmt

ifexprthenstmt

ifexprthenifexprthenstmtelsestmt

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

3.2

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

+Aa

直接左递归 A

Aa|b

串的特点 ba...a3.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)|id3.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|

3.2

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

Aa|b

A

Sd|

先变换成直接左递归 S

Aa|b A

Aad|bd|

3.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|

23.2

语言和文法3.2.7

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

1|

2提左因子 A

A

A

1|

2

3.2

语言和文法例

悬空else的文法 stmt

ifexprthenstmtelsestmt

|ifexprthenstmt |other

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)*}

标识符的声明应先于其引用的抽象

3.2

语言和文法3.2.8

非上下文无关的语言结构L1={wcw|w属于(a|b)*}

标识符的声明应先于其引用的抽象

L2={anbmcndm|n0,m0}形参个数和实参个数应该相同的抽象

3.2

语言和文法3.2.8

非上下文无关的语言结构L1={wcw|w属于(a|b)*}

标识符的声明应先于其引用的抽象

L2={anbmcndm|n0,m0}形参个数和实参个数应该相同的抽象

L3={anbncn|n0}早先排版描述的一个现象的抽象3.2

语言和文法L1

={wcwR|w

(a|b)*}

S

aSa|bSb|c

3.2

语言和文法L1

={wcwR|w

(a|b)*}

S

aSa|bSb|c

L2={anbmcmdn|n1,m1}

S

aSd|aAd A

bAc|bc3.2

语言和文法L1

={wcwR|w

(a|b)*}

S

aSa|bSb|c

L2={anbmcmdn|n1,m1}

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|ab3.2

语言和文法L3

={anbn|n

1}

S

aSb|abL3

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

3.2

语言和文法L3

={anbn|n

1}

S

aSb|abL3

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

若存在接受L3

的DFAD，状态数为k个3.2

语言和文法L3

={anbn|n

1}

S

aSb|abL3

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

若存在接受L3

的DFAD，状态数为k个

设D读完,

a,aa,

…,ak

分别到达状态s0,s1,

…,sk3.2

语言和文法L3

={anbn|n

1}

S

aSb|abL3

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

若存在接受L3

的DFAD，状态数为k个

设D读完,

a,aa,

…,ak

分别到达状态s0,s1,

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

3.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

cc3.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次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次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交换相邻的CB

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次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次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次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交换相邻的CB

S

+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建立分析树3.3

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

文法 S

aCb C

cd|c

为输入串w=acb建立分析树SaCb3.3

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

文法 S

aCb C

cd|c

为输入串w=acb建立分析树SSaCbaCbcd3.3

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

文法 S

aCb C

cd|c

为输入串w=acb建立分析树SSSaCbaaCCbbcdc3.3

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

文法 S

aCb C

cd|c

为输入串w=acb建立分析树SSSaC