第二章高级语言与其语法描述

第二章高级语言与其语法描述第一页，共61页。第二章高级语言及其语法描述

2.1、程序设计语言的定义语法（Syntax）：程序语言的语法通常是指形成和产生一系列合式的程序的一组规则。词法规则:规定什么样的字符序列可以构成语言的有效符号(单词符号)语法规则:确定一个符号序列是否为一个句子,并提供句子的结构（什么样的符号序列是合法的）语言＝语法(规则)＋语义(规则)第二页，共61页。语义（Semantics）：程序语言的语义通常是指这样的一组规则,用它可以定义一个程序的意义。这组规则称为语义规则。语用（Pragmatics）：有关程序设计技术和语言成分的使用方法，表示语言符号及其使用者之间的关系，涉及符号的来源、使用和影响。语法Syntax-----每个程序构成的规律语义Semantics-----每个程序的含义语用Pragmatics-----每个程序和使用者的关系第三页，共61页。对于赋值语句a:=b+c

语法：赋值语句由一个变量，后随一个符号“:=”或“=”，再在后面跟一个表达式所构成。

语义：先对该语句的右部表达式求值，然后把结果与语句左部变量相结合，并取代该变量原来的值。

语用：赋值语句可用来计算和保存表达式的值。第四页，共61页。2.3程序语言的语法描述一、字母表和符号串1、字母表：是一个非空有穷集合。

例：∑={a，b，c}

2、符号（字符）：字母表中的元素。例：a，b，c

3、符号串：符号的有穷序列。例：a,aa,ac,abc，…

4、符号串集合：字母表上所有符号串的全体。

例：

∑*={ε，a，b，c，aa,ab,ac,bc,cb,bb,cc,aaa,abc,acb,…}

空符号串：无任何符号的符号串或长度为零的符号串，记为ε

第五页，共61页。2、符号串长度：设x是字母表上的符号串，符号串中包含符号的个数称为符号串x的长度，用x表示。例:(1).||=0;(2).|ax|=|xa|=|x|+1(a∈∑)1、符号串相等：设x、y是字母表上的两个符号串，若x与y的诸符号依次相等，则该两符号串相等，记为x=y3、符号串的连结：设x与y是字母表上的两个符号串，把y的所有符号相继写在x的符号之后所得到的符号串称为x与y的连结，用xy表示。注意:(1).|xy|=|x|+|y|;(2).x=x=x;(3).xy≠yx(一般说来)4、符号串的逆：设x是字母表上的符号串，其逆为符号串x的倒置，记为。(1).若x=abcd,则=dcba.(2).=

二、符号串的运算第六页，共61页。5、符号串的前缀、后缀和子串：设x、y、z是字母表上的符号串，则称x为符号串xy的前缀，y是符号串xy的后缀，x、y、z、xy、yz是符号串xyz的子串6、符号串集合的乘积：设A、B为两个符号串集合，其乘积为AB={xy|xA,yB}例:abcdef例:(1).若A={ab,cd},B={ef,gh}则:AB={abef,abgh,cdef,cdgh}(2).∵x=x=x∴{}A=A{}=A7、空集：不含任何元素的集合{}，记为Ø注意:(1).ØA=AØ=Ø;(2).Ø{}，和Ø区分:第七页，共61页。8、符号串的幂：设x是字母表上的符号串，则x的幂运算为x0=x1=xx2=xx••••••xn=xn-1x(xxn-1)9、符号串集合的幂：设A是符号串集合，则符号串A的幂运算为：A0={}，A1=A，A2=AA••••••，An=An-1A(AAn-1)例:若x=ab则:x0=,x1=ab,x2=abab,••••••,xn=abab•••ab例:若A={ab,cd}则:A0={},A1={ab,cd},A2={abab,abcd,cdab,cdcd},••••••第八页，共61页。注意:(1).A*=A0∪A+;(2).A+=AA*=A*A;(3).若A={a,b}则:A*={,a,b,aa,ab,ba,bb,aaa,•••}A+={a,b,aa,ab,ba,bb,aaa,•••}10、集合A的闭包与正闭包：正闭包表示为A+集合A的闭包表示为A*A0={},第九页，共61页。2.3.1文法和语言文法是描述语言语法结构的形式规则。一、文法和推导G=(VT，VN，S，P)

VT是终结符的非空有限集；

VN是非终结符的非空有限集；

S是文法的开始符号，S∈VN；

P是产生式的非空有限集，文法的形式定义S至少在某个产生式的左部出现一次第十页，共61页。非终结符与终结符非终结符：用大写字母A,B,C,…表示非终结符VN集合中的元素，A

∈VN终结符：用小写大写字母a,b,c,…表示VT集合中的元素，a∈VT注意:(1).V=VN∪VT;(2).VN∩VT=

Ø.,β,γ,…表示由终结符和／或非终结符组成的符号串,∈V*第十一页，共61页。产生式的简化------若干左部相同的产生式，可以缩写，

→1

→2…

→n→1

|2

|…|n产生式（规则）：

一个产生式是一个二元组，通常写作A：：=或A→“→”左边是A是非终结符，称为产生式的左部符号，

“→”右边是是非终结符，称为产生式的右部，1，2，…，n称为侯选式第十二页，共61页。例如,用S、L、N分别表示标识符、字母和数字,则有标识符的文法G[I]:S→

LS→

SLS→

SNL→

aL→

b••••••L→

zN→

0N→

1••••••N→

9则Vt和Vn分别为:

Vn={S,L,N}Vt={a,b,c,•••,z,0,1,2,•••,9}第十三页，共61页。4、直接推导与直接归约：对于文法G，有规则U：：=

u，x和y是Vt上的符号串（可以是空串），若Vt上存在另外两个符号串v和w使v=xUy,w=xuy则称v直接推导出w，或称w直接归约到v，分别记为：v=>w第十四页，共61页。例如,设有文法G[E]:E→

E+T|TT→

T*F|FF→(E)|i对i+i*i直接推导为:E=>E+T

=>

T+T=>F+T=>i+T=>i+T*F=>i+F*F=>i+i*F=>i+i*i第十五页，共61页。5、推导与归约：对于文法G,如果存在一直接推导序列v=u0

=>u1=>

u2=>

••••••=>

un=w,(n>0)

则称v推导出w，或称w归约到v，分别记为:v=>

w+特别:如果v=>

w或者v=w,则分别记为:v=>

w+*称n为推导长度。第十六页，共61页。直接推导和推导：定义V*中的符号之间的关系：直接推导：长度为n(n≥1)的推导：长度为n(n≥0)的推导：*+第十七页，共61页。例1：对文法G1：S→A|SAA→0|1|2|3|4|5现讨论推导数25是否唯一,推导如下:S=>SA=>S5=>A5=>25S=>SA=>AA=>2A=>25第十八页，共61页。6、规范推导（最右推导）：设有文法G，对于xUy=>

xuy,若yV*t，则称这种推导为规范推导,记为xUy=>xuy

r规范推导（最右推导）：任何一步推导：=>β都是对中的最右非终结符进行替换。7、最左推导最左推导：任何一步推导：=>β都是对中的最左非终结符进行替换。S=>SA=>S5=>A5=>25S=>SA=>AA=>2A=>25第十九页，共61页。二、文法和语言1、句型、句子和语言：句型：对于一个文法G，开始符号为S，如果S=>*,

V*，那么称为句型，句子：仅含终结符的句型是句子文法G=(VT,VN,S,P),S*α若αV*,则α为文法G的一个句型若αVT*,则α是一个句子句型与句子的关系是？只含终结符的句型就是一个句子。一个句子是句型。一个句型不一定是句子。第二十页，共61页。注意:(1).句子是语言的最小单位;(2).语言是所有终结符号所组成的集合的一个子集,即L(G[S])VT*.语言：文法G的句子的全体是语言，表示为L(G),L(G)={|S=>*,∈VT*}

第二十一页，共61页。很多时候，不用将文法G的四元组显式地表示出来，而

只将产生式写出G：S→0S1，S→01L(G)={0n1n|n≥1}第二十二页，共61页。例2,设有文法G2:S→

aSb|ab于是有:S=>aSb=>aaSbb=>••••••=>an-1Zbn-1=>anbn可见此文法定义的语言为:L(G2)={anbn|n≥1}例1：对文法G1：S→bAA→aA|aS=>bA

=>baA

=>baaA

=>baaaA

=>……

=>ban此文法定义的语言为:

L(G1)={ban|n≥1}第二十三页，共61页。

S→aS|aPP→bP|bQQ→cQ|cL(G3)={aibjck│i,j,k1}G3(S):第二十四页，共61页。给定一种语言，能确定其文法，但这种文法不是唯一的，即LG1或G2或G3••••••例如,已知语言为:L(G[S])={abna|n≥1}可以构造文法G1:S::=aBaB::=b|Bb可以构造文法G2:S::=aBB::=ba|bB可以构造文法G2:S::=BaB::=ab|Bb第二十五页，共61页。定义：若L(G1)＝L(G2)，则称文法G1和G2是等价的例如文法G[A]：A0RA01RA1和文法G[S]：S0S1S01等价L(G)={0n1n|n≥1}第二十六页，共61页。等价文法例1设有语言为:L={a2nb|n≥1}文法G1:S::=AbA::=aa|aAa文法G2:S::=aab|aaS例2由奇数个a的符号串构成的语言L可由文法G1=({S},{a},{SaSa|a},S)或G2=({S,A},{a},{SaA|a,AaS},S)产生，即L(G1)=L(G2)=L第二十七页，共61页。四、短语、简单短语与句柄1、短语与简单短语：设有文法G[Z]，w=xuy是一个句型,如果有Z

xUy

且Uu，则称u是句型w的相对于U的短语。*+若有Z

xUyUu，则称u是句型w的相对于U的简单短语。其中UVn,uV+*考察v=xUy与w=xuy的关系:由于Uu所以xUyxuy于是有：ZxUyxuy,u为句型xuy相对于U的短语++*+如果Uu，则u为简单短语如果Uu且u在规则最左出现，则u为句柄第二十八页，共61页。2、句柄：句型的最左简单短语称为该句型的句柄。(1).因为EET+i,所以T+i为句型T+i相对于E的短语;(2).因为ET+TT+i,所以i为句型T+i相对于T的短语;(3).因为ET+FT+i,所以i为句型T+i相对于F的短语,且为简单短语;(4).因为EE+iT+i,所以T为句型T+i相对于E的短语,且为简单短语.*+*+*+*+例如,设有文法G[E]:E::=E+T|TT::=T*F|FF::=(E)|i根据定义求句型T+i的所有短语和简单短语:U作为短语必须满足两个条件：第一，u可以归约到U；第二，原句型归约后仍为一个句型。第二十九页，共61页。语法树和二义性一、语法树和推导1、语法树:表示句型的推导设有文法G[S]，满足下列条件的树称为G的语法树：（1）每个结点都是G的某一终结符或非终结符；（2）树根是文法的开始符S；（3）若某一结点至少有一个从它出来的分枝，则该结点一定是非终结符（4）若某一结点A有n个分枝，其分枝结点为B1、B2、••••••、Bn,则A：：=B1B2••••••Bn一定是G的一个规则。

第三十页，共61页。例3.7：文法G=({S，A},{a,b},P,E)其中P为：(1)SaAS (2)ASbA (3)ASS(4)Sa (5)Aba图3.1的推导树是文法G的句型aabbaa的推导过程把aabbaa叫做推导树的结果，

把推导树叫做句型aabbaa的语法树图3.1推导树第三十一页，共61页。例：G[E]:

Ei EE+E EE*E E(E)句型i*i+i的两个：推导1：EE+EE*E+Ei*E+Ei*i+Ei*i+i推导2：EE*Ei*Ei*E+Ei*i+Ei*i+i一个句型是否只对应唯一的一棵语法树？一个句型是否只有唯一的一个最左（最右）推导？不是第三十二页，共61页。图3.2推导1的语法树图3.3推导2的语法树第三十三页，共61页。例如,设有文法G[S]:S::=aABA::=Ba|aB::=bd则下面两棵树都是G的语法树:SABabdBaSABabdBa第三十四页，共61页。2、推导过程与语法树的生成末端结点(树叶):没有分枝向下射出的结点.如果末端结点都是由终结符号组成,则这些结点所组成的符号串为句子,否则为句型.例如,设有文法G[N]:N::=ND|DD::=0|1|2|•••|9N=>ND=>DD=>2D=>

25最右推导出句子25:N=>

ND=>

N5=>D5=>25最左推导出句子25:推导生成的语法树如右:NDND25第三十五页，共61页。3、子树与短语:子树与简单子树:语法树的某个结点连同它向下射出的部分组成了语法树的子树.只含有单层分枝的子树称为简单子树.例如,上例的子树为:NDND25(a)DN2(b)D2(c)D2(d)例如,上例中的(c)(d).第三十六页，共61页。子树与短语的关系:结论:(1)子树的末端结点组成的符号串是相对于子树根的短语;(2)简单子树的末端结点组成的符号串是相对于简单子树根的简单短语;(3)最左简单子树的末端结点组成的符号串为句柄.ZUxyu••••••由语法树(右图)知:ZxUy*Uu++有:ZxUyxuy*第三十七页，共61页。例如,设有文法G[E]:E::=E+T|TT::=T*F|FF::=(E)|i现用语法树求句型T+i的所有短语、简单短语和句柄.E=>E+T=>E+F=>

E+i=>

T+i句型T+i的推导过程为:推导生成的语法树如右:结论:(1).T+i为句型T+i相对于E的短语;(2).T为句型T+i相对于E的短语,且为简单短语;(3).i为句型T+i相对于T的短语;(4).i为句型T+i相对于F的短语,且为简单短语.E+ETTFi因此,句型的短语、简单短语和句柄分别为:T+i,T,i;T,i;T第三十八页，共61页。4、由语法树构造推导:这种每一步都归约当前句柄的归约称之为最左归约(规范归约).例如,设有文法G[N],其句子25的语法树如右:NDND2525D5N5NDN其最左归约序列为:于是上述语法树的推导序列为:NNDN5D525rrrr即:N25+r第三十九页，共61页。二、文法的二义性1、文法的二义性:例如,对于文法G[E]:E::=E+E|E*E|(E)|i现考虑如何推导出句子i+i*i,又是怎样生成相应的语法树的.E=>E+E=>E+E*E=>

i+i*i由文法有推导:生成的语法树如右(a):又有推导:生成的语法树如右(b):E+EEi*iEEi(a)E+EEi*iEEi(b)E=>E*E=>E+E*E=>

i+i*i第四十页，共61页。文法的二义性的形式定义如果一个文法所定义的句子中,存在某个句子有两棵不同的语法树,则称该文法是二义性的,否则该文法是无二义性的.如果文法所定义的句子中，存在某个句子有两种不同的最右(或最左)推导,则该文法是二义性的.若文法所定义的句子中存在某个句子,它有两种不同的最右(或最左)归约,即在归约中某些规范句型的句柄不唯一,则该文法是二义性的.第四十一页，共61页。文法的二义性例如,设定义语句S的文法为G[E]:S::=ifBthenS|ifBthenSelseS|A推导下面句型ifBthenifBthenSelseS,并建立语法树.S=>

ifBthenS=>ifBthenifBthenSelseS由文法有推导:生成的语法树如右(a):又有推导:生成的语法树如右(b):S=>

ifBthenSelseS=>ifBthenifBthenSelseSS(a)ifBthenSelseifBthenSS(b)ifBthenSelseifBthenSSS第四十二页，共61页。修改编译算法规定:第一,*、/的优先级高于+、—（优先级高的先归约）；第二，相同优先级是先左后右（左边先归约）。2、二义性的解决办法:E+EE*EE句子i+i*i有唯一的语法树见右图:例如,对于文法G[E]:E::=E+E|E*E|(E)|i是二义性文法.第四十三页，共61页。修改文法对于一个文法，若不存在等价的非二义性文法，则称该文法为先天二义性的。例如,设有文法G[E]:E::=E+T|E-T|TT::=T*F|T/F|FF::=(E)|i现考虑表达式i+i*i,根据文法只有唯一的语法树,如右图:E+ET*TFFiiTFi第四十四页，共61页。因为对于句型SSS有两种不同的语法树,如右图:SSSSS(b)SSSSS(a)例如,对于文法G[S]:S::=SS|是二义性文法.若对文法进行如下修改:S::=SA|AA::=则二义性可以消除.第四十五页，共61页。文法和语言分类0型文法（短语文法）1型文法（上下文有关文法）2型文法（上下文无关文法）3型文法（线性文法/正规文法）乔姆斯基(Chomsky)在1956年建立了形式语言的描述，把文法分成四个类型：这个分类在于对产生式施加不同的限制:。第四十六页，共61页。3.4文法的类型乔姆斯基(Chomsky)于1956年建立形式语言的描述他把文法分成：0型、1型、2型、3型四个文法类的定义是逐渐增加限制的0型1型2型3型第四十七页，共61页。1、0型文法与0型语言：若文法G中的每个规则为α

β，α,βV*,且α至少含一个非终结符，

αV*，βV*，则称G是0型文法。0型文法确定的语言为0型语言，表示为L0.例如,设有文法:G={VN,VT,S,P}其中:P={S::=ACaB,Ca::=aaCCB::=DB,CB::=EaD::=Da,AD::=ACaE::=Ea,AE::=}VN={S,A,B,C,D,E}VT={a}文法和语言分类第四十八页，共61页。其确定的0型语言为:L0={|i≥0}a2i对于句子aaaa有推导:S=>ACaB=>AaaCB=>AaaDB=>AaDaB=>ADaaB=>

ACaaB=>AaaCaB=>AaaaaCB=>

AaaaaE=>

aaaa2、1型文法与1型语言：若文法G中的每个规则为α

β并且|α|≤|β|，仅仅Sε例外，但S不得出现在任何产生式的右部

，α,βV*,α至少含一个非终结符，则称G是1型文法。1型文法确定的语言为1型语言，表示为L1。第四十九页，共61页。例：文法G[S]：SCD AbbA CaCA BaaB CbCB BbbB ADaD Cε BDbD Dε AabDL(G)={w|w∈{a,b}*}第五十页，共61页。例如,有1型文法:G={Vn,Vt,S,P}其中:Vn={S,B,C,D}Vt={a,b,c}P={S::=aSBC|aBC,CB::=DBDB::=DC,DC::=BCaB::=ab,bB::=bbbC::=bc,cC::=cc}其确定的1型语言为:L1={aibici|i≥1}对于句子aabbcc有推导:S=>aSBC=>aaBCBC=>aabCBC=>aabDBC=>aabDCC=>

abbacy=>aabbCC=>aabbcC=>aabbcc第五十一页，共61页。3、2型文法与2型语言：若文法G中的每一个规则为α

β,αVn,βV*则称G是2型文法。2型文法确定的语言为2型语言，表示为L2.例如,有2型文法:G={Vn,Vt,S,P}其中:Vn={S,A}Vt={a,b,c}P={S::=Ac|Sc,A::=ab|aAb}其确定的1型语言为:L1={aibici|i≥1}对于句子aabbccc有推导:S=>Sc=>

Scc=>

Accc=>

aAbccc=>

aabbccc第五十二页，共61页。有时将2型文法的产生式表示为Aβ的形式，其中A∈VN，也就是用β取代非终结符A时，与A所在的上下文无关，因此取名为上下文无关例3.1、3.2第五十三页，共61页。例3.1文法G=（VN，VT，P，S），其中VN={S}，VT={0,1}，P={S0S1,S01}

思考：S＝？

第五十四页，共61页。例3.2文法G=（VN，VT，P，S），其中VN={标识符，字母，数字}，S=<标识符>VT={a,b,c,…x,y,z,0,1,…,9}P＝{<标识符><字母> <标识符><标识符><字母> <标识符><