语法分析教学内容

语法分析上下文无关文法4.1~4.34.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|idE

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二义性idid+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 两个不同的最左推导4.1上下文无关文法4.1.4二义性idid+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*+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_stmt4.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

ifexprthenstmt

elsestmt

|ifexprthenstmt |other 提左因子

stmt

ifexprthenstmt

optional_else_part |other

optional_else_partelsestmt |形式语言

产生式形式为：xAy->xy

产生式形式为：A->aB,A->a,A->

产生式形式为：A->⑶2型语言由2型文法定义⑵1型语言由1型文法定义⑴0型语言由0型文法定义

产生式形式为：->⑷3型语言由3型文法定义又称无限制文法！又称上下文有关文法！又称上下文无关文法！又称正规文法！【注】四类语言为包含关系，且有L0⊃L1⊃

L2⊃

L3；