编译原理课件：复习

编译原理Compilers–Principles,TechniquesandTools复习第一章：编译简介编译器的工作可以分成若干阶段，每个阶段把源程序从一种表示变换成另一种表示。例：第三章词法分析：词法记号的描述与识别

正则表达式正则表达式用来表示简单的语言，叫做正则集

正则式 定义的语言 备注

{}

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

词法记号的描述与识别

正则表达式的例子={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)))

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

正则定义

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

r1 d2

r2 ... dn

rn各个di的名字都不同每个ri都是{d1,d2,…,di-1}上的正则式词法记号的描述与识别

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

letter_

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

|z|_

digit

0

|1|…|9 id

letter_(letter_

|digit)*

第三章词法分析：有限自动机

不确定的有限自动机（简称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的转换表有限自动机

识别语言(a|b)*ab

的NFA12开始a0abb确定的有限自动机（简称DFA)

一个数学模型，包括：1、有限的状态集合S2、输入字母集合3、转换函数move:SS4、唯一的开始状态s05、接受状态集合FS12开始a0abbab识别语言(a|b)*ab

的DFA有限自动机

有限自动机

正则表达式NFADFA最简DFA从正则式到NFA

19开始0abab6782345r9r7r8r4r3r5r6*)(r2r1a|bab(a|b)*ab的分解从正则式到NFA

19开始0ab678ab2345r9r7r8r4r3r5r6*)(r2r1a|bab(a|b)*ab的分解从正则式到NFA

19开始0abab6782345r9r7r8r4r3r5r6*)(r2r1a|bab(a|b)*ab的分解从正则式到NFA

19开始0abab6782345r9r7r8r4r3r5r6*)(r2r1a|bab(a|b)*ab的分解从正则式到NFA

19开始0abab6782345r9r7r8r4r3r5r6*)(r2r1a|bab(a|b)*ab的分解从正则式到NFA19开始0abab6782345r9r7r8r4r3r5r6*)(r2r1a|bab(a|b)*ab的分解从正则式到NFA

19开始0abab6782345r9r7r8r4r3r5r6*)(r2r1a|bab(a|b)*ab的分解有限自动机

正则表达式NFADFA最简DFANFA到DFA的变换

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

2、读了输入a1a2…an后，

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

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

未画完19开始0abab6782345

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

19开始0abab6782345输入符号ab状态

有限自动机

19开始0abab6782345输入符号abA状态

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

有限自动机

19开始0abab6782345输入符号abAB状态

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

有限自动机

19开始0abab6782345输入符号abABB状态

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

19开始0abab6782345输入符号abABCB状态

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

有限自动机

19开始0abab6782345输入符号abABCBC状态

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

19开始0abab6782345输入符号abABCBBC状态

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

19开始0abab6782345输入符号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}

有限自动机

19开始0abab6782345输入符号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}

有限自动机

19开始0abab6782345输入符号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}

有限自动机

19开始0abab6782345输入符号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}

有限自动机

19开始0abab6782345输入符号abABCBBDCBCDBC状态

BD开始aAabbabCba有限自动机

有限自动机正则表达式NFADFA最简DFABD开始aAabbaa,bCbaEbDFA

最简DFA死状态在转换函数由部分函数改成全函数表示时引入死状态对所有输入符号都转换到本身左图需要引入死状态E；右图无须引入死状态BD开始aAabbabCba有限自动机

DFA

最简DFA方法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开始a0abbab有限自动机有限自动机实现词法分析器的方法：正则表达式NFADFA最简DFA正则表达式DFA

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

正则定义

*/delim [\t\n]ws {delim}+letter [AZaz]digit [09]id {letter}({letter}|{digit})*number {digit}+(\.{digit}+)?(E[+\]?{digit}+)?词法分析器的生成器例——翻译规则部分{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);}词法分析器的生成器例——辅助过程部分installId(){ /*

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

类似上面的过程，但词法单元不是标识符而是数*/}词法分析器的生成器第四章语法分析本章内容上下文无关文法自上而下分析和自下而上分析围绕分析器的自动生成展开词法分析器记号取下一个记号源程序分析树前端的其余部分分析器中间表示符号表第四章语法分析：上下文无关文法上下文无关文法是四元组（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

上下文无关文法例E

E+E|E

E|(E)|

E|id

最左推导 E lm

Elm

(E)lm

(E

+E)

lm

(id+E)lm(id+id)最右推导 E rm

Erm

(E)rm

(E+E)

rm

(E+id)rm(id+id)上下文无关文法二义性 E

E

E

E

E+E idE

E

E+E

id

E+E id

E+E

idid+E idid+E idid+id idid+id 两棵不同的语法树EEE*+EEidididEEidE*+EEidid第四章语法分析：语言和文法消除左递归文法左递归 A+Aa

直接左递归 AAa|b

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

bA A

aA|

语言和文法例

算术表达文法

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)|id语言和文法形式语言鸟瞰文法G=(VT

,VN,S,P)0型文法：，,(VNVT)*,||11型文法：||||，但S可以例外2型文法：A，AVN,(VN∪VT)*3型文法：AaB或Aa，A,BVN,aVT

短语文法、上下文有关文法、上下文无关文法、正则文法第四章语法分析：分析方法自上而下分析方法（预测分析方法）递归的方法非递归的方法——LL方法（Left-to-rightLeftmost）自下而上分析方法LR方法（Left-to-rightRightmost）第四章语法分析：自上而下分析LL(1)文法 任何两个产生式A|都满足下列条件：FIRST(

)FIRST()=若

*

，那么FIRST()FOLLOW(A)=LL(1)文法有一些明显的性质没有公共左因子不是二义的不含左递归自上而下分析递归下降的预测分析为每一个非终结符写一个分析过程这些过程可能是递归的例 type

simple |id |array[simple]oftype simpleinteger |char |numdotdotnum自上而下分析一个辅助过程voidmatch(terminalt){ if(lookahead==t)lookahead=nextToken(); elseerror();}自上而下分析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]oftype自上而下分析voidsimple(){ if(lookahead==integer)match(integer); elseif(lookahead==char)match(char); elseif(lookahead==num){ match(num);match(dotdot);match(num); } elseerror();}

simple

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

XYZ$栈自上而下分析非终结符输

入

符

号

id

+

...EE

TE

E

E

+TE

T

T

FT

T

T

T

FTF

F

id分析表的一部分自上而下分析栈

输

入

输

出

$E

idid+id$

$ET

idid+id$

E

TE

$ETF

idid+id$

T

FT

$ETid

idid+id$

F

id

$ET

id+id$

$ETF

id+id$

T

FT

$ETF

id+id$

$ETid

id+id$

F

id

预测分析器接受输入id

*

id+id的前一部分动作

自上而下分析构造预测分析表（1）对文法的每个产生式A

，执行(2)和(3)（2）对FIRST()的每个终结符a， 把A

加入M[A,a]（3）如果在FIRST()中，对FOLLOW(A)的每个终结符b（包括$）,把A

加入M[A,b]（4）M中其它没有定义的条目都是error自下而上分析

例：EE+E|EE|(E)|id栈

输

入

动

作

$id1

id2+id3$移进

$id1

id2+id3$按E

id归约

$E

id2+id3$移进

$E

id2+id3$移进

$Eid2

+id3$按E

id归约

$EE

+id3$移进

$EE+id3$移进

$EE+id3

$按E

id归约

$EE+E

$按E

E+E归约

$EE

$按E

EE归约

$E

$接受

第四章语法分析：LR分析器LR分析算法输入LR分析程序输出栈LR分析器的模型actiongotosmXmsm-1Xm-1…s0…a1ai…an$LR分析器例 E

E+T|E

T T

TF|

T

F F(E)|Fid状态动

作

转

移

id

+()$

E

TF

0s5s41231s6acc

2

r2s7r2r23r4r4r4r44s5s4

823LR分析器栈

输

入

动

作

0idid+id

$移进

0id5

id+id

$按F

id归约

0F3

id+id

$按T

F归约

0T2

id+id

$移进

0T27id+id$移进

0T27id5+id$按F

id归约

0T27F10+id$按T

TF归约

.........0E1$接受

LR分析器构造SLR分析表术语：LR(0)项目（简称项目）在右部的某个地方加点的产生式加点的目的是用来表示分析过程中的状态例 AXYZ对应有四个项目

A·XYZ AX·YZ AXY·Z AXYZ·例 A只有一个项目和它对应 A·

LR分析器构造SLR分析表的两大步骤1、从文法构造识别可行前缀的DFA2、从上述DFA构造分析表LR分析器1、从文法构造识别可行前缀的DFA

1）拓广文法

EE+T|T TTF|F F(E)|id

LR分析器1、从文法构造识别可行前缀的DFA

1）拓广文法

EE

EE+T|T TTF|F F(E)|id

LR分析器1、从文法构造识别可行前缀的DFA 2）构造LR(0)项目集规范族I0:

E·ELR分析器1、从文法构造识别可行前缀的DFA 2）构造LR(0)项目集规范族I0:

E·E E·E+T E·TLR分析器1、从文法构造识别可行前缀的DFA 2）构造LR(0)项目集规范族I0:

E·E E·E+T E·T T·T

F T·FLR分析器1、从文法构造识别可行前缀的DFA 2）构造LR(0)项目集规范族I0:

E·E E·E+T E·T T·T

F T·F F·(E) F·idLR分析器1、从文法构造识别可行前缀的DFA 2）构造LR(0)项目集规范族I0:

E·E (核心项目) E·E+T E·T (非核心项目， T·T

F 通过对核心项目求闭包

T·F 而获得) F·(E) F·idLR分析器1、从文法构造识别可行前缀的DFA 2）构造LR(0)项目集规范族I0: I1:

E·E EE·

E·E+T EE·+T

E·T T·T

F T·F F·(E) F·id ELR分析器1、从文法构造识别可行前缀的DFA 2）构造LR(0)项目集规范族I0: I1:

E·E EE·

E·E+T EE·+T

E·T T·T

F I1:=goto(I0,E) T·F F·(E) F·id ELR分析器1、从文法构造识别可行前缀的DFA 2）构造LR(0)项目集规范族I0: I1:

E·E EE· E·E+T EE·+T

E·T T·T

F I2: T·F E

T·

F·(E) TT·

F

F·id ETLR分析器1、从文法构造识别可行前缀的DFA

2）构造LR(0)项目集规范族I0: I1:

E·E EE·

E·E+T EE·+T

E·T T·T

F I2: T·F E

T·

F·(E) TT·

F

F·id I3:

TF·

ETFLR分析器I0: I4:

E·E F(·E) E·E+T E·T T·T

F T·F F·(E) F·id

(LR分析器I0: I4:

E·E F(·E) E·E+T E·E+T E·T E·T T·T

F T·T

F T·F T·F F·(E) F·(E) F·id F·id

(LR分析器I0: I4:

E·E F(·E) E·E+T E·E+T E·T E·T T·T

F T·T

F T·F T·F F·(E) F·(E) F·id F·id

I5:

F

id·

(idLR分析器I1I0EI3I2I4I5TF(id

LR分析器I1I0+指向I7EI6I9I3I2I4I11I8I7I10*TI5指向I4指向I3指向I5指向I4指向I5指向I6指向I2指向I3F(FTid*id(F(Eid+)id(FTLR分析器构造SLR分析表的两大步骤1、从文法构造识别可行前缀的DFA2、从上述DFA构造分析表LR分析器2、从DFA构造SLR分析表状态i从Ii构造，它的action函数如下确定：如果[A·a]在Ii中，并且goto(Ii,a)=Ij，那么置action[i,a]为sj如果[A·]在Ii中，那么对FOLLOW(A)中的所有a，置action[i,a]为rj,j是产生式A的编号如果[SS·]在Ii中，那么置action[i,$]为接受accLR分析器2、从DFA构造SLR分析表状态i从Ii构造，它的action函数如下确定：...使用下面规则构造状态i的goto函数：对所有的非终结符A，如果goto(Ii,A)=Ij,那么goto[i,A]=jLR分析器2、从DFA构造SLR分析表状态i从Ii构造，它的action函数如下确定：...使用下面规则构造状态i的goto函数：...不能由上面两步定义的条目都置为error分析器的初始状态是包含[S·S]的项目集对应的状态第四章语法分析：分析器的生成器分析器的生成器Yacc

Yacc编译器Yacc源程序translate.yy.tab.cC编译器y.tab.ca.outa.out输入输出分析器的生成器%{#include<ctype.h>#include<stdio.h>#defineYYSTYPEdouble/将栈定义为double类型/%}

%tokenNUMBER%left‘+’‘’%left‘’‘/’%rightUMINUS%%分析器的生成器lines :linesexpr‘\n’{printf(“%g\n”,$2)} |lines‘\n’ |/

/ ;expr :expr‘+’expr {$$=$1+$3;} |expr‘’expr {$$=$1$3;} |expr‘’expr {$$=$1$3;} |expr‘/’expr {$$=$1/$3;} |‘(’expr‘)’ {$$=$2;} |‘’expr%precUMINUS {$$=$2;} |NUMBER ;%%分析器的生成器yylex(){ intc; while((c=getchar())==‘’); if((c==‘.’)||(isdigit(c))){ ungetc(c,stdin); scanf(“%lf”,&yylval); returnNUMBER; } returnc;}第五章语法制导的翻译本章内容1、介绍语义描述的一种形式方法：语法制导的翻译，它包括两种具体形式语法制导的定义翻译方案2、介绍语法制导翻译的实现方法第五章语法制导的翻译：语法制导的定义语法制导定义的形式基础文法每个文法符号有一组属性每个文法产生式A

有一组形式为b=f(c1,c2,…,ck)的语义规则，其中b和c1,c2,…,ck

是该产生式文法符号的属性，f

是函数综合属性：如果b是A的属性，c1,c2,…,ck

是产生式右部文法符号的属性或A的其它属性继承属性：如果b是右部某文法符号X的属性语法制导的定义综合属性S属性定义：仅使用综合属性的语法制导定义产

生

式

语

义

规

则

L

E

n

print(E.val)

E

E1+T

E.val=E1.val+T.val

E

T

E.val=T.val

T

T1

F

T.val=T1.val

F.val

T

F

T.val=F.val

F(E)

F.val=E.val

F

digit

F.val=digit.lexval语法制导的定义注释分析树:结点的属性值都标注出来的分析树8+5*2n的注释分析树digit.lexval=2LE.val=18nT.val=10E.val=8T.val=8F.val=8digit.lexval=8T.val=5+F.val=5F.val=2digit.lexval=5第五章语法制导的翻译:

S属性定义的自下而上计算简单计算器的语法制导定义改成栈操作代码

......ZZ.zYY.yXX.x......栈statevaltop产

生

式

语义规则

L

E

n

print(E.val)

E

E1+T

E.val=E1.val+T.val

E

T

E.val=T.val

T

T1

F

T.val=T1.val

F.val

T

F

T.val=F.val

F(E)

F.val=E.val

F

digit

F.val=digit.lexvalS属性定义的自下而上计算简单计算器的语法制导定义改成栈操作代码

......ZZ.zYY.yXX.x......栈statevaltop产

生

式

代码段

L

E

n

print(val[top1])

E

E1+T

val[top2]=val[top2]+val[top]

E

T

T

T1

F

val[top2]=val[top2]val[top]

T

F

F(E)

val[top2]

=val[top1]

F

digit

第五章语法制导的翻译:L属性定义继承属性

intid,id,id产生式

语

义

规

则

D

TL

L.in=T.type

T

int

T.type=integer

T

real

T.type=real

L

L1,

id

L1.in=L.in;

addType(id.entry,L.in)

L

id

addType(id.entry,L.in)

L属性定义的自上而下计算L属性定义如果每个产生式AX1…Xj-1Xj…Xn的每条语义规则计算的属性是A的综合属性；或者是Xj

的继承属性，但它仅依赖：该产生式中Xj左边符号X1,X2,…,Xj-1的属性；A的继承属性S属性定义属于L属性定义L属性定义的自上而下计算预测翻译器的设计为每个非终结符A构造一个函数，A的每个继承属性作为形参，A的综合属性作为返回值产生式R+TR|

的分析过程syntaxTreeNode

R(syntaxTreeNodei){ syntaxTreeNodenptr,i1,s1,s;

charaddoplexeme;

if(lookahead=='+'){/

产生式R+TR

/

addoplexeme=lexval;

match('+');nptr=T();

i1