编译原理课件：第四章 语法分析2

词法单元：记号名、属性、词素、模式正则表达式、正则定义状态转换图有限自动机不确定有限自动机（NFA）确定有限自动机（DFA）正则式NFADFA最简DFA正则式DFALex工具第三章复习期中考试

11月19日：15:00~17:00

文思209、2082编译原理第四章语法分析第四章语法分析本章内容上下文无关文法自上而下分析和自下而上分析围绕分析器的自动生成展开词法分析器记号取下一个记号源程序分析树前端的其余部分分析器中间表示符号表4.1上下文无关文法4.1.1上下文无关文法的定义正则式能定义一些简单的语言，能表示给定结构的固定次数的重复或者没有指定次数的重复 例：a(ba)5,a(ba)*正则式不能用于描述配对或嵌套的结构 例1：配对括号串的集合 例2：{wcw|w是a和b的串}

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

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

expr

op

expr |

(expr)|

expr|idop+|简化表示E

EAE|(E)|E|idA+|4.1上下文无关文法文法书写上的约定终结符字母表中的小写字母，如a，b，c黑体串，如id,while数字0,1,…,9标点符号，如括号，逗号等运算符号，如+,-等非终结符字母表中的大写字母，如A,B,C字母S，并且通常代表开始符号小写字母的名字（斜体），如expr,stmt4.1上下文无关文法文法书写上的约定字母表中后面的大写字母，如X，Y，Z，可以是终结符或非终结符字母表中后面的小写字母，如u，v

…z可代表终结符号串小写希腊字母，如a，b，可代表文法的符号串对于Aa1，Aa2，...

Aan可以写成

Aa1|a2|…

|an4.1上下文无关文法4.1.2

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

E+E|E

E|(E)|

E|id

E

E

(E)

(E+E)

(id+E)(id+id)概念 S*、S+w

，于是**

b，且b

γ,则*

γ

4.1上下文无关文法4.1.2

推导概念 上下文无关语言A→γ,且a、b是任意符号串，则aAb

aγb由上下文无关文法生成的语言是上下文无关语言等价的文法如果两个文法产生同样的语言，则两个文法等价句型文法G的开始符为S，S*，可能含有非终结符，则叫做文法G的句型。4.1上下文无关文法例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)4.1上下文无关文法4.1.3分析树例E

E+E|E

E|(E)|

E|idEE()EEE+idid4.1上下文无关文法4.1.4二义性 E

E

E

E

E+E idE

E

E+E

id

E+E id

E+E

idid+E idid+E idid+id idid+id 两个不同的最左推导4.1上下文无关文法4.1.4二义性 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*+EEidid4.2语言和文法文法的优点

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

语言和文法4.2.1

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

a

A0|bA0|a

A1A1

b

A2A2

12开始a0abb4.2

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

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

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

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

语言和文法4.2.3

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

(S)S|L(G)=配对的括号串的集合4.2

语言和文法4.2.3

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

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

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

S(S)S*(x)S*(x)y4.2

语言和文法4.2.3

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

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

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

1)的w=(x)y

S(S)S*(x)S*(x)y4.2

语言和文法4.2.4适当的表达式文法用一种层次观点看待表达式 idid(id+id)+idid+id4.2

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

idid(id+id)+idid+id

id

id

(id+id)

文法 expr

expr+term|term term

term

factor|factor

factor

id|(expr)4.2

语言和文法expr

expr+term|termterm

term

factor|factor

factor

id|(expr)expridtermfactorididterm*termfactorfactor*exprexpr+idfactortermididterm*termfactorfactorid+idid分析树

ididid分析树

4.2

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

ifexprthenstmt |ifexprthenstmtelsestmt |other句型：ifexprthenifexprthenstmt

elsestmt两个最左推导：

stmtifexprthenstmt

ifexprthenifexprthenstmtelsestmt

stmtifexprthenstmtelsestmt

ifexprthenifexprthenstmtelsestmt

4.2

语言和文法

无二义的文法stmt

matched_stmt

|unmatched_stmtmatched_stmt

ifexprthenmatched_stmt

elsematched_stmt

|otherunmatched_stmt

ifexprthenstmt |ifexprthenmatched_stmt

elseunmatched_stmt上节复习上下文无关文法是四元组（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|b)*ab文法A0

a

A0|bA0|a

A1A1

b

A2A2

12开始a0abb4.2

语言和文法4.2.6消除左递归消除左递归AA

α|βAβRRαR|ε4.2

语言和文法4.2.6消除左递归文法左递归 A+Aa

直接左递归 AAa|b

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

bA A

aA|

4.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)|id4.2

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

Aa|b

A

Sd|先变换成直接左递归 S

Aa|b A

Aad|bd|

再消除左递归

SAa|b A

bdA

|A A

adA

|4.2

语言和文法4.2.7

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

1|2提左因子 A

A A

1|2

4.2

语言和文法例

悬空else的文法 stmt

ifexprthenstmtelsestmt

|ifexprthenstmt |other 提左因子

stmt

ifexprthenstmt

optional_else_part |other

optional_else_partelsestmt |4.2

语言和文法4.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个下划线键4.2

语言和文法L1={wcwR|w(a|b)*}

SaSa|bSb|c

L2={anbmcmdn|n

1,m

1}

SaSd|aAd AbAc|bcL

2={anbncmdm|n1，m1} SAB AaAb|ab

BcBd|cd4.2

语言和文法L3

={anbn|n

1}

SaSb|abL3是不能用正则式描述的语言的一个范例

若存在接受L3的DFAD，状态数为k个设D读完,

a,aa,

…,ak

分别到达状态s0,s1,

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

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

…4.2

语言和文法4.2.9

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

,VN,S,P)0型文法：，,(VNVT)*,||14.2

语言和文法4.2.9

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

,VN,S,P)0型文法：，,(VNVT)*,||1短语文法4.2

语言和文法4.2.9

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

,VN,S,P)0型文法：，,(VNVT)*,||11型文法：||||，但S可以例外短语文法4.2

语言和文法4.2.9

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

,VN,S,P)0型文法：，,(VNVT)*,||11型文法：||||，但S可以例外短语文法、上下文有关文法4.2

语言和文法4.2.9

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

,VN,S,P)0型文法：，,(VNVT)*,||11型文法：||||，但S可以例外2型文法：A，AVN,(VN∪VT)*短语文法、上下文有关文法4.2

语言和文法4.2.9

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

,VN,S,P)0型文法：，,(VNVT)*,||11型文法：||||，但S可以例外2型文法：A，AVN,(VN∪VT)*短语文法、上下文有关文法、上下文无关文法4.2

语言和文法4.2.9

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

,VN,S,P)0型文法：，,(VNVT)*,||11型文法：||||，但