意识的作用-教学课件29-人教课标版

二章语言的基本知识二章语言的基本知识学习本章的目的构造编译程序的算法是从研究源程序及目标程序产生的，首先找到源语言的形式描述，根据这种描述，构造出相应的分析加工程序。语言分语法，语义和语用。程序语言语法的形式描述是很好用的，语义的形式描述不那磨好用，但它推动语言理论的发展。2学习本章的目的构造编译程序的算法是从研究源程序及目标程序产生

2.1符号串

2.1.1字母表2.1.2符号串

一.符号串的定义二.术语三.符号串的运算四.符号串集合的运算3

2.1符号串

2.1.1字母表3字母表是符号的非空有穷集合。任何程序语言都有自己的字母表，例如:1.计算机语言：由符号“0”和“1”组成的字母表,∑={0，1}2.ASCII字符集；3.Pascal字母表为：∑={A

Z,a

z,0

9,+,-,*,/,<,=,>,:,',',;，.，,(,),{,},[,]}

2.1.1字母表

4字母表是符号的非空有穷集合。任何程序语言都有自己的字母一.符号串的定义(1)ε是∑上的一个符号串。(2)若x是∑上的符号串，而a是∑的元素,则xa是∑上的符号串。(3)y是∑上的符号串,当且仅当它由(1)和(2)导出。由字母表中的符号所组成的的任何有穷序列被称之为该字母表上的符号串,也称作"字"。2.1.2符号串5一.符号串的定义2.1.2符号串5设s是符号串前缀：移走s的尾部的零个或多于零个符号后缀：删去s的头部的零个或多于零个符号子串:从s中删去一个前缀和一个后缀子序列:从s中删去零个或多于零个符号(这些符号不要求是连续的）逆转（用SR表示）：将S中的符号按相反次序写出而得到的符号串。长度：是该符号串中的符号的数目。例如|aab|=3,|ε|=0。二

术语6设s是符号串二术语6：符号串s=banana前缀：,b,ba,ban,bana,banan,banana后缀：banana,anana,nana,ana,na,a,

子串:banana,anana,banan,anan,…,

真前缀，真后缀，真子串:x≠sx≠

子序列:baa(这些符号不要求是连续的）逆转（用SR表示）：ananab长度：

banana=6例7：符号串s=banana例71.连接：设x和y是符号串，它们的连接xy是把y的符号写在x的符号之后得到的符号串。例如，x=ba,y=nana,xy=banana.2.方幂：x0=

;x1=x;x2=xx;……;xn=xn-1x;例如,x=ba,

x1=ba,x2=baba,x3=bababa,…...三.符号串的运算8三.符号串的运算8

设L和M是两个符号串集合，则1.合并：L∪M＝｛s|s

Lors

M}

2.连接：LM＝｛st|s

Landt

M}3.方幂：L0={ε}，L1＝L，L2＝LL,...,Ln＝Ln-1L4.语言L的Kleene闭包，记作L*，L*＝∪Li(i>=0)=L0∪L1∪L2∪L3∪…

5．语言L的正闭包，记作L+（L+＝L

L*）L+＝∪Li(i>=1)=L1∪L2∪L3∪L4∪…四.符号串集合(语言）的运算9四.符号串集合(语言）的运算9如：L={A~Z,a~z}D={0~9}

1．L∪D={A~Z,a~z,0~9}2．LD是由所有用一个字母后跟一个数字组成的符号串所构成的集合。3．L4是由所有的四个字母的符号串构的集合。4．L（L∪D)*是由所有的字母打头的字母和数字组成的符号串所构成的集合.5．D+是由所有的长度大于等于1的数字串所构成的集合.例10如：L={A~Z,a~z}D={0~9}例102.2文法和语言的定义2.2.1引子2.2.2文法和语言的定义一.

文法和语言的定义二.

推导三.

语言四.最左推导和最右推导五。短语，直接短语，句柄112.2文法和语言的定义2.2.1引子11

引子分析：Thegreywolfwilleatthegoat〈谓语〉〈主语〉〈冠词〉〈形容词〉〈名词〉〈动词〉〈直接宾语〉助动词〈句子〉动原冠词名词Thegreywolfwilleatthegoat12引子分析：Thegreywolfwill

为了进行机械分析，：“句子由主语后跟随谓语组成”表示为：

句子主语谓语（1）主语冠词形容词名词（2）冠词the形容词

grey

谓语

动词直接宾语（5）

动词助动词动词原形（6）助动词will动词原形

eat直接宾语

冠词名词（9）名词wolf名词

goat语法规则13为了进行机械分析，：“句子由主语后跟随谓语组成：终结符号集，非终结符号集，语法规则，开始符号。终结符号集VT={the，grey,wolf,will,eat,goat}非终结符号集VN={

句子，主语，谓语，冠词，形容词，名词，

动词，

直接宾语，助动词，动词原形}语法规则集P={句子

主语谓语，……}

开始符号S=

句子句子的语法有四部分14：终结符号集，非终结符号集句子主语谓语

冠词形容词名词谓语

the

形容词名词谓语

thegrey名词谓语

thegreywolf

谓语

thegreywolf

动词直接宾语…...

thegreywolfwilleatthegoat句子根据规则推导出来

15句子主语谓语句子根据规则推导出来

15句子thegreywolfwilleatthegoat

thegreywolfwilleatthewolf

thegreygoat

willeatthewolfthegreygoat

willeatthegrey合符语法且合符语义的句子仅是：

thegreywolfwilleatthegoat+

句子既要合符语法又要合符语义

16句子thegreywolfwi分析：Thegreywolfwilleatthegoat〈句子〉〈主语〉〈谓语〉〈冠词〉〈形容词〉〈名词〉〈动词〉〈直接宾语〉助动词动原冠词名词goat

theeatwillThegreywolf句型分析一17分析：Thegreywolfwilleat分析：Thegreywolfwilleatthegoat〈句子〉〈主语〉〈谓语〉〈冠词〉〈形容词〉〈名词〉〈动词〉〈直接宾语〉助动词动原冠词名词goat

theeatwillThegreywolf句型分析二18分析：Thegreywolfwilleat一个上下文无关文法

G=（VT，VNS,P），其中：

VT是一个非空有穷终结符号集合；

VN是一个非空有穷的非终结符号集合，且VT∩VN＝Φ；S

VN，称为开始符号。

P是一个产生式的非空有穷集合，每个产生式的形式是A

α(或A::＝α)，其中A∈VN，α∈（VT∪VN）*。开始符号S至必须在某个产生式的左部出现一次。缩写形式：

A

α1|α2一

文法的定义

19一个上下文无关文法一文法的定义

19G=({a,+,*,(,)},{<表达式>，<项>，<因子>}，<表达式>，P)P：<表达式>

<表达式>

＋<项>

<项><项>

<项>*<因子>

<因子><因子>

（<表达式>)

a

E

E+T

TT

T*F

FF

(E)

a(2.1)例2.2算术表达式的文法G:

20例2.2算术表达式的文法G:

20令G=(VT,VN,S,P),若A

γ∈P,且α,β∈(VT∪VN)*,则称αAβ直接推出αγβ,表示成αAβ

αγβαAβ直接推出αγβ

αγβ直接归约到αAβ如果存在一个直接推导序列：

0

α1

α2

…

αn（n＞0）表示成

α0αn

0

αn或者α0=αn或者α0

αn+

+

*

二.定义2.3直接推导和推导的定义

21++*二.定义2.3直接推导和推导的定义

21例：E

E+TT+TF+T

a+Ta+Fa+a22例：EE+TT+TF+T

设文法G＝（VT，VN，S,P）。如果Sα,则称α是一个句型。仅含终结符号的句型是一个句子。语言L(G）是由文法G产生的所有句子所组成的集合：

L(G)＝{α|Sα且α∈VT*}例2.3考虑一个文法G＝({a,b},{S},S，P）其中P：S

aSb

abS

aSb

aaSbb

a3Sb3

……

an-1Sbn-1

anbn*

+

三.定义2.4：语言的定义

23*+三.定义2.4：语言的定义

23设G=(VT={a,b},VN={S,A,B},S,P}P由下列产生式组成:S→aB|bA

A→a|aS|bAA

B→b|bS|aBBL(G)={w|w∈{a,b}+,且w中有相同个数的a和b}。用归纳法证明下面结论（对w的长度）：(1)Sw,当且仅当w中含有相同个数的a和b。(2)Aw,当且仅当w中a的个数比b的个数多一个。(3)Bw,当且仅当w中b的个数比a的个数多一个。归纳基础当|w|=1，A

a,B

b,

不能从S导出长度

为1的终极行,则上述结论显然成立。*

*

*

例2.424设G=(VT={a,b},VN={S,A,B},S设(1),(2)和(3)对于长度不超过k-1的所有w都成立。那么，证明对|w|=k也成立。对于（1），推导的第一步必是S

aB或S

bA,对于第一种情形，必有w=aw1且Bw1，|w1|=k-1，它含的b个数比a多一个，因此，w中a,b的个数相等。推导的第一步是S

bA,证明完全类似。反之，|w|=k,w中a,b的个数相等,要证Sw。考虑的S推导，推导出的开始符号，或为a或为b。若S

aB,Bw1,

|w1|=k-1,w1中b的个数比a多一个,w=aw1。若S

bA，证明和类S

aB类似。（2）和（3）的证明留给同学们。*

*

*

归纳步骤25设(1),(2)和(3)对于长度不超过k:对于w和G,wL(G)

是否存在Sw，如何构造

例如，G[E]（例2.2）和w=a+a

aEE+TT+TF+Ta+Ta+TF

a+FFa+aFa+aa（最左）特点：

A(A)，VT*EE+TE+TFE+TaE+FaE+aaT+aaF+aaa+aa特点：

A(A)，VT*（最右）+

四.最左推导和最右推导26

令G[S]是一个文法，如果有

SαAδ且Aβ则称β是一个关于非终结符号A的，句型αβδ的短语。其次如果有

SαAδ且A

β则称β是直接短语。一个句型的最左直接短语称为该句型的句柄。文法（2．1）的一个句型a1*a2+a3，尽管有Ea2＋a3，但是a2＋a3并不是该句型的一个短语,因为不存在Ea1*E。短语：a1,a2,a3，a1

*a2,a1*a2+a3

直接短语:a1，a2

,a3

句柄:a1+

*

*

+

+

定义2.527令G[S]是一个文法，如果有+**++定2.3分析树和二义性一.分析树的定义二.如何画出分析树三.子树四.二义性文法的定义五.在构造编译程序中如何处理二义性文法282.3分析树和二义性一.分析树的定义28设G=（VT，VN，S，P）,G的一棵分析树满足如下条件：1.每一个结点有一个标记，此标记是VT∪VN∪{ε}中的符号。2．根的标记是S。3．如果一个结点是内部结点，且有标记A,那么A必在VN中。4．如果编号为n的结点有标记A,结点n1,n2,…,nk是点n的从左到右的儿子，并分别有标记X1,X2,…,Xk，则A

X1X2…Xk必须是P中的产生式。5.如果结点n有标记ε，那么结点n是叶子，且是它父亲唯一的儿子。一.分析树的定义29一.分析树的定义29G=(VT,VN,S,P),其中P:SaASaASbASSba3124657891011SaASSbAaaba例2.530G=(VT,VN,S,P),其中312

根据推导序列，对每步推导画相应分枝ASaSbSAaaba

aSbAS

aabAS

aabbaS

aabbaa

aAS

S二.如何画出分析树(1.自顶向下）31ASaSbSAaabaaSbASaabASaab

根据归约序列，对每步归约画相应分枝ASaSbSAaaba

aAa

aSbAa

aSbbaa

aabbaa

aAS

S二.如何画出分析树(2.自底向上）32ASaSbSAaabaaAaaSbAaaSbba1.一个句型推导或分析用一棵树结构图示出来，它反应了一个句子语法结构的层次。2.对于一个句子的多种推导（若文法是无二义性的），采用各种推导过程，画出的分析树是一样的。分析树并未描述推导过程。3.在书中，用画分析树的过程解释语法分析过程，用分析树图解语法结构。分析树是推导的图形表示。关于分析树的几点说明

331.一个句型推导或分析用一棵树结构图示出来，一棵分析树中一个特有的结点连同它的全部后裔，连接这些后裔的边以及这些结点的标记。例如：SAbSaSbaAaa三.

子树

34SAbSaSbaAaa三.子树

34短语：一棵子树的所有叶子自左至右排列起来形成一个相对于子树根的短语。直接短语：仅有父子两代的一棵子树，它的所有叶子自左至右排列起来所形成的符号串。句柄：一个句型的分析树中最左那棵只有父子两代的子树的所有叶子的自左至右排列。例如，对表达式文法G[E]和句子a1+a2*a3，挑选出推导过程中产生的句型中的短语，直接短语，句柄。用子树解释短语，直接短语，句柄:35用子树解释短语，直接短语，句柄:35E

E+T

T+T

F+T

a1+T

a1+T*F

a1+F*F

a1+a2*FE+TT,T+TF,F+Ta1,a1+Ta1,T*F,a1+T*Fa1,F,F*F,a1+F*F

a1,a2,a1+a2*F,a2*F

a1,a2,a3,a2*

a3

a1+a2*a3EE+TTFa1T*FFa2a3

a1+a2*a3短语例(a)36EE+TT+TF+Ta1+Ta1+T*FaE

E+T

E+T*F

E+T*a3

E+F*a3

E+a2*a3

T+a2*a3

F+a2*a3

EE+TTFa1T*FFa2a3

a1+a2*a3例(b)37EE+TE+T*FE+T*a3E+F*a3E+a描述一个句子的文法不是唯一的；2.对于一个句子的分析应是唯一的。考虑表达式下面的文法G[E],其产生式如下：

E

E+E

E*E

(E)

a

对于句子a+a*a,有如下两个最左推导：

EE+Ea+Ea+E*Ea+a*Ea+a*a

EE*EE+E*Ea+E*Ea+a*Ea+a*a四.文法的二义性的定义

38四.文法的二义性的定义

38

EE+Ea+Ea+E*Ea+a*Ea+a*a

EE*EE+E*Ea+E*Ea+a*Ea+a*aEE+EE*EaaaEE*E+EEaaa最左推导例(1)39EE+Ea+EEE*EE+E*E

EE+EE+E*EE+E*aE+a*aa+a*a

EE*EE*aE+E*aE+a*aa+a*aEE+EE*EaaaEE*E+EEaaa最右推导例(2)40EE+EE+E*EEE*EE*a如果一个文法的句子存在两棵分析树,那磨,该句子是二义性的。如果一个文法包含二义性的句子,则称这个文法是二义性的;

否则，该文法是无二义性的。几点说明：1.一般来说，程序语言存在无二义性文法，对于表达式来说，文法（2.1）是无二义性的。对于条件语句，经常使用二义性文法描述它：SifexprthenSifexprthenSelseSother二义性的句子:ife1thenife2thens1elses2

四.二义性（歧义性，ambiquity)的定义:

41四.二义性（歧义性，ambiquity)的定义:

41下面是

Smathed_sunmathed_smathed_sifexprthenmathed_selsemathed_sotherunmathed_sifexprthenSifexprthenmathed_selseunmathed_s它显然比较复杂，因此：2.在能驾驭的情况下，使用二义性文法。描述if语句的无二义性文法的产生式:42下面是描述if语句的无二义性文法的产生式:423.对于任意一个上下文无关文法，不存在一个算法，判定它是无二义性的；但能给出一组充分条件，满足这组充分条件的文法是无二义性的。4.存在先天二义性语言。例如，

aibicji,j1

aibjcji,j1

存在一个二义性的句子akbkck。压缩过的文法（化简了的文法）：1．形式的产生式：

A→AP；

2.每个非终结符号A必须都有用处。即，

SαAβ且Aγ，γ∈VT*

*

+

定义之3,4433.对于任意一个上下文无关文法，不存在一个算法，2.4形式语言概观2.4.1文法分类2.4.2非上下文无关文法的语言结构2.4.3上下文无关语言和正规语言的区别442.4形式语言概观2.4.1文法分类44逐渐对产生式施加限制四种类型：0型，1型，2型，3型0型：G=(VT,VN,S,P)

规则形式：

,(VT

VN)*,

推导：1型（上下文有关）：规则形式：

A

A

VN,

,,.(VT

VN)*,

2型（上下文无关）：规则形式：

A

A

VN，

(VT

VN)*3型（右线性）：A

aBA

a

（左线性）A

BaA

aa

VT{}2.4.1文法分类45逐渐

在我们使用的程序语言中,有些语言结构并不是总能用上下文无关文法描述的。

例2.9

L1={wcw|w∈{a,b}+}。例如,aabcaab就是L1的一个句子。这个语言是检查程序中标识符的声明应先于引用的抽象

。

例2.10

L2={anbmcndm|n,m≥0}，它是检查过程声明的形参个数和过程引用的参数个数一致问题的抽象。2.4.2非上下文无关的语言结构462.4.2非上下文无关的