高级语言及其语法描述课件

高级语言及其语法描述幻灯片PPT本课件PPT仅供大家学习使用学习完请自行删除，谢谢！本课件PPT仅供大家学习使用学习完请自行删除，谢谢！本课件PPT仅供大家学习使用学习完请自行删除，谢谢！本课件PPT仅供大家学习使用学习完请自行删除，谢谢！22023/7/18软件学院2.1程序语言的定义一个程序设计语言是一个记号系统，其完整的定义应包括语法和语义两个方面语言的语法是指一组规则，用它可以形成和产生一个合适的程序上下文无关文法语法只定义什么样的符号序列是合法的，与这些符号的含义毫无关系PASCAL语言中：A:=B+C合乎语法规则，A:=B+不合乎语法规则阐明语法的一个工具是文法，这是形式语言理论的基本概念之一32023/7/18软件学院2.2程序语言的语法描述基本概念字母表、符号、符号串、闭包等文法的定义文法的分类Chromsky对文法的分类文法和语言推导、归约、句型、句子、语言语法分析树和二义性42023/7/18软件学院基本概念字母表元素的非空有限集，记为。例：={a，b，c}字母表中的元素称为符号。例：a，b，c，字母表包含了语言中所允许出现的所有符号符号串符号的有穷序列。例：a,aa,ac,abc，..，无任何符号的符号串称为空符号串，记为ε52023/7/18软件学院不包含任何字符的序列称为空字，记为ε用∑*表示∑上的所有字的全体,包含空字ε例如:设∑={a，b}，则∑*={ε,a,b,aa,ab,ba,bb,aaa,...}注：约定用a,b,c,…表示符号；用,,,…表示符号串；用A,B,C,…表示其集合。62023/7/18软件学院基本概念符号串运算符号串长度x为符号串,其长度|x|等于组成该符号串的符号个数。例：x=string，则|x|=6,|ε|=0符号串连接若x、y是定义在Σ上的符号串，则xy称为x和y的连接，xy也是Σ上的符号串εx＝xε=x72023/7/18软件学院基本概念符号串集合的乘积令A、B为符号串集合，定义符号串集合乘积AB＝{xy|x∈A,y∈B}符号串集合的方幂符号串集合A，定义A0={ε},A1=A,A2=AA,A3=A2A,…,An＝An-1A=AAn-1，n>0符号串集合的正闭包A+=A1∪A2∪…∪An…符号串集合的自反闭包A*={ε}∪A+设：U＝{a,aa}那么：

U*

={,a,aa,aaa,aaaa,…}U＋

={a,aa,aaa,aaaa,…}软件学院2.3.1上下文无关文法文法：描述语言的语法结构的形式规则Hegavemeabook.<句子><主语><谓语><间接宾语><直接宾语><主语><代词><谓语><动词><间接宾语><代词><直接宾语><冠词><名词><代词>He<代词>me<名词>book<冠词>a<动词>gave软件学院<句子><主语><谓语><间接宾语><直接宾语><主语><代词><谓语><动词><间接宾语><代词><直接宾语><冠词><名词><代词>He<代词>me<名词>book<冠词>a<动词>gave<句子><主语><谓语><间接宾语><直接宾语><代词><谓语><间接宾语><直接宾语>He<谓语><间接宾语><直接宾语>He<动词><间接宾语><直接宾语>Hegave<间接宾语><直接宾语>Hegave<代词><直接宾语>Hegaveme<直接宾语>Hegaveme<冠词><名词>Hegavemea<名词>Hegavemeabook软件学院上下文无关文法的定义：一个上下文无关文法G是一个四元式

G=(VT，VN，S，P)，其中VT：终结符集合(非空)VN：非终结符集合(非空)，且VT

VN=S：文法的开始符号，SVNP：产生式集合(有限)，每个产生式形式为P，PVN，(VT

VN)*开始符S至少必须在某个产生式的左部出现一次。软件学院例，定义只含+，*的算术表达式的文法

G=<{i，+，*，(，)}，{E}，E，P>，其中，P由下列产生式组成：EiEE+EEE*EE(E)软件学院几点规定：“”也可以用“::="表示，这种表示称为巴科斯范式(BNF)P1

P2

可缩写为P1|2||n

Pn

其中，“|”读成“或”，称为P的一个候选式。表示一个文法时，通常只给出开始符号和产生式，如上例，可表示为：G(E)：Ei|E+E|E*E|(E)例，定义只含+，*的算术表达式的文法

G=<{i，+，*，(，)}，{E}，E，P>，其中，P由下列产生式组成：EiEE+EEE*EE(E)软件学院定义：称A直接推出，即A

仅当A是一个产生式，且，(VT

VN)*

。如果1

2

n，则我们称这个序列是从1到n的一个推导。若存在一个从1到n的推导，则称1可以推导出n

。对文法G(E)：Ei|E+E|E*E|(E)E(E)(E+E)(i+E)(i+i)软件学院通常，用

表示：从1出发，经过一步或若干步，可以推出n。

用表示：从1出发，经过0步或若干步，可以推出n。

所以：即或定义：假定G是一个文法，S是它的开始符号。如果，则称是一个句型。仅含终结符号的句型是一个句子。文法G所产生的句子的全体是一个语言，将它记为L(G)。软件学院例：(i*i+i)是文法G(E)：Ei|E+E|E*E|(E)的一个句子。证明：

E(E)(E+E)(E*E+E)(i*E+E)(i*i+E)(i*i+i)E，(E)，(E*E+E)，…，(i*i+i)是句型。软件学院例：文法G1(A)：Ac|AbG1(A)的语言?L(G1)={c，cb，cbb，}以c开头，后继若干个b软件学院例：文法G2(S)：SABAaA|aBbB|bG2(S)的语言?L(G2)={ambn|m，n>0}软件学院例：给出产生语言为{anbn|n1}的文法。

G3(S)：

SaSbSab软件学院例：给出产生语言为{ambn|1nm2n}的文法。

G4(S)：

SaSb|aaSbSab|aab软件学院从一个句型到另一个句型的推导往往不唯一。

E+Ei+Ei+iE+EE+ii+i最左推导：任何一步都是对中的最左非终结符进行替换。

最右推导：任何一步都是对中的最右非终结符进行替换。软件学院2.3.2语法树与二义性用一张图表示一个句型的推导,称为语法树。(i*i+i)的语法树E(E)(E+E)(E*E+E)(i*E+E)(i*i+E)(i*i+i)E(E)(E+E)(E+i)(E*E+i)(E*i+i)(i*i+i)一棵语法树是不同推导过程的共性抽象。G(E)：Ei|E+E|E*E|(E)(i*i+i)软件学院如果使用最左(右)推导，则一个最左(右)推导与语法树一一对应。一个句型是否只对应唯一一棵语法树？软件学院定义：如果一个文法存在某个句子对应两颗不同的语法树，则说这个文法是二义的。G(E)：Ei|E+E|E*E|(E)是二义文法。语言的二义性：一个语言是二义性的，如果对它不存在无二义性的文法。可能存在G和G’，一个为二义的，一个为无二义的。但L(G)=L(G’)二义性问题是不可判定问题，即不存在一个算法，它能在有限步骤内，确切地判定一个文法是否是二义的。可以找到一组无二义文法的充分条件。软件学院二义文法：G(E)：Ei|E+E|E*E|(E)表达式项|表达式+项项因子|项*因子因子

(表达式)|i无二义文法：G(E)：ET|E+TTF|T*FF(E)|i软件学院)EEEFFTTTTi+*(EFiiET

F

(E)

(E+T)(T+T)(T*F+T)(F*F+T)(i*F+T)(i*i+T)

(i*i+F)

(i*i+i)考虑句子(i*i+i)软件学院描述程序设计语言时，对于上下文无关文法的限制：1不含PP形式的产生式2每个非终结符P必须有用处即：软件学院2.3.3形式语言鸟瞰Chomsky于1956年建立形式语言体系，他把文法分成四种类型：0，1，2，3型。与上下文无关文法一样，它们都由四部分组成，但对产生式的限制有所不同。软件学院0型(短语文法，图灵机)：产生式形如：其中：(VT

VN)*且至少含有一个非终结符；(VT

VN)*1型(上下文有关文法，线性界限自动机)：产生式形如：其中：||||，仅S例外。软件学院2型(上下文无关文法，非确定下推自动机)：产生式形如：

A

其中：AVN；(VT

VN)*。3型(正规文法，有限自动机)：产生式形如：

AB或A

其中：VT*；A，BVN

产生式形如：

AB或A

其中：VT*；A，BVN右线性文法左线性文法312023/7/18软件学院文法举例文法G=({S,A,B},{a,b,c,d,e},S,P),其中，P={SabcA|edB,AbeB,Bd}文法G是右线性文法改写为正规文法正规文法产生式只能有两种形式AB或A其中A,BVN,VT相应的正规文法为：G’=({S,A,B,A’,B’,C’,D’},{a,b,c,d,e},S,P’),P’={SaA’|eB’,A’bC’,C’cA,B’dB,AbD’,D’eB,Bd}322023/7/18软件学院332023/7/18软件学院S=>0A=>010A=>…=>0(10)*A=>0(10)*软件学院四种类型描述能力比较0型1型2型3型软件学院L5={anbn|n1}不能由正规文法产生，但可由上下文无关文法产生：

G5(S)：

SaSb|abL6={anbncn|n1}不能由上下文无关文法产生，但可由上下文有关文法产生：

G6(S)：SaSBC|aBCCB

BCaB

abbBbbbCbccC

cc软件学院程序设计语言不是上下文无关语言，甚至不是上下文有关语言。L7={c|(a|b)*}不能由上下文无关文法产生，甚至连上下文有关文法也不能产生，只能由0型文法产生。标识符引用过程调用过程中，"形-实参数地对应性"(如个数，顺序和类型一致性)现今程序设计语言的语言结构，用上下文无关文法描述就足够了。L(G1)={ai(a|b)|i>=0}

例：设文法G2＝({S},{a,b},P,S)

其中P为:(0)SaSb(1)SabL(G2)={anbn|n>=1}例：设文法G1＝({S},{a,b},P,S)

其中P为:(0)SaS(1)Sa(2)Sb注意：在词法分析和语法分析中对产生式有限制不存在PP产生式,因为它的存在除了增加二义性外没有任何用处产生式中出现的任何非终结符P必须是可达的，并且能推出终结符串。从开始符号S出发，存在推导SPP必须能推导出终结符串。即:P;VT*.*+例：设L1={a2nbn|n>=1且a,bVT}试构造生成L1的文法G1设n=1，L1=aabn=2，L1=aaaabbn=3，L1=aaaaaabbb……所以得：SaaSbSaab一、由语言构造文法

一、由语言构造文法例：设L2={aibjck|i,j,k>=1且a,b,cVT}试构造生成L2的文法G2SaSSaBBbBBbCCcC|c

一、由语言构造文法例：设L3={|(a,b)*

且中含有相同个数的a和b}试构造生成L3的文法G3SSbB，SaAAbS|b,AaAABaS|a|bBB(0)SSaSbSSbSaS一、由语言构造文法例：设L4={|(0,1)*

且中1的个数为偶数}试构造生成L4的文法G4SS0S，S1AA0A,A1S二、文法简化1、由于同一语言可以用不同的文法来描述，显然应当选择产生式的个数最少，最符合语言特征的来描述。

2、在文法中，有些产生式对推导不起作用，要删除掉。如某个产生式在推导过程中永远不会被用到，即由开始符号推导，永远推不到它左部的非终结符。再如永远导不出终结符串的产生式。如形如PP的产生式。二、文法简化3、简化步骤：查找有无形如PP的产生式，若有则删除；若某个产生式在推导过程中永远不会被用到，删除它；若某个产生式在推导过程中不能从中导出终结符，删除它。最后，整理所有剩余产生式，就得到简化的文法。二、文法简化例：化简下面的文法。(0)SBe(1)SEc(2)AAe(3)Ae(4)AA(5)BCe(6)BAf(7)CCf(8)Df(0)SBe(1)AAe(2)Ae(3)BAf三、构造无产生式的上下文无关文法1、无产生式的上下文无关文法要满足条件若P中含S，则S不出现在任何产生式右部，其中S为文法的开始符号；P中不再含有其它任何产生式。2、构造无产生式的上下文无关文法变换算法：G=(VN,VT,P,S)G’=(V’N,V’T,P’,S’)（1）由文法G找出所有经过若干步推导能推出的非终结符，放在V0集合中。三、构造无产生式的上下文无关文法2、构造无产生式的上下文无关文法变换算法

2）按下列步骤构造G’的产生式集合P’A)若V0集合中的某元素出现在某产生式的右端，则将它变成两个产生式：分别以和其原型代入；将新产生式加入P’B)不满足上一条的P中其他产生式除去产生式后也加入P’C)如果P中有产生式S，将它在P’中改为S’|S(S’是新的开始符号)，把它加入VN，形成V’N例：设G1=({S},{a,b},P,S),其中P:(0)S(1)SaSbS(2)SbSaS(1)V0={S}(2)P’(1)SabS|aSbS|aSb|ab(2)SbaS|bSaS|bSa|ba(0)S’|S故：文法G1’=({S’,S},{a,b},P’,S’),其中P’:(0)S’|S

(1)SabS|aSbS|aSb|ab(2)SbaS|bSaS|bSa|ba软件学院作业P36-6，7，8，9，10，11502023/7/18软件学院文法的分类对产生式施加不同的限制得到不同类型的文法0型（无限制文法）:G=(VN,VT,

S,

P)

规则形式：

;(VN

VT)+,(VN

VT)*且中至少含有一个非终结符1型（上下文有关）:

规则有1,其中=γ1Aγ2,=γ1δγ2;AVN,

δ

(VN

VT)+,γ1,γ2(VN

VT)*.规则形式γ1Aγ2γ1δγ2;

2型（上下文无关）:规则形式:Aδ

,

AVN

，δ

(VN

VT)+

3型（右线性和正规文法）:规则形式:

AB或A（右线性）A,BVN,(VT)*.512023/7/18软件学院左线性文法规则形式:

AB或A（左线性）A,BVN,(VT)*.正规文法规则形式:

AB或A其中A,BVN,VT，如果SP，则S不能出现在任何产生式右边正规文法中只能出现单个终结符，右线性文法中可能出现若干个终结符组成的串2型文法扩充Aδ,

AVN

，δ

(VN

VT)*允许有空产生式：A不改变描述能力522023/7/18软件学院四个文法类的定义是逐渐增加限制的，因此每一种正规文法都是上下文无关的，每一种上下文无关文法都是上下文有关的，而每一种上下文有关文法都是0型文法。称0型文法产生的语言为0型语言。上下文有关文法、上下文无关文法和正规文法产生的语言分别称为上下文有关语言、上下文无关语言和正规语言现今大多数高级程序设计语言采用上下文无关文法来描述其语法已经足够了532023/7/18软件学院文法和语言上下文无关文法定义的语言从文法的开始符号出发，反复使用产生式，对非终结符进行替换和展开，直至推导出语言的各种句子来推导与归约的概念推导、最左推导、最右推导、规范推导归约、最左归约、最右归约、规范归约句型、句子、语言的形式定义语法分析树与二义性542023/7/18软件学院推导和归约552023/7/18软件学院最左推导和最右推导规范推导最右直接推导又称为规范直接推导，最右推导又称为规范推导562023/7/18软件学院最右归约和最左归约的定义572023/7/18软件学院句型、句子、语言的定义定义2.6设S是文法G的识别符号，如果Su,则称符号串u为文法G的句型定义2.7设S是文法G的识别符号，如果Su,uVT*,则称符号串u为文法G的句子定义2.7设S是文法G的识别符号，文法G的语言L(G)={u|Su且uVT*},即文法的语言是文法所有句子的集合***582023/7/18软件学院例2.9文法G=(VN,VT,S,P)，其中VN={S}，VT={0，1}，P={S→0S1，S→01}。这里，非终结符集中只含一个元素S；终结符集由两个元素0和1组成；有两条产生式；开始符号是S592023/7/18软件学院直接推导示例对于例2.9的文法G，有如下直接推导示例

u=0S1,w=0011,直接推导：0S1=>0011，使用的规则：S→01，这里γ=0，δ=1。

u=S,w=0S1，直接推导：S=>0S1使用的规则：S→0S1，这里γ=ε，δ=ε

u=0S1,w=00S11,直接推导：0S1=>00S11，使用的规则：S→0S1，这里γ=0，δ=1。

602023/7/18软件学院对例2.9的文法，存在直接推导序列v=0S1=>00S11=>000S111=>00001111=w，即0S1=>+00001111，也可记作0S1=>*00001111

S，0S1，000111都是例2.9文法G的句型，其中000111是G的句子612023/7/18软件学院考虑例2.9的文法G，有两条产生式(规则)：(1)S→0S1和(2)S→01，通过对第一个产生式使用n-1次，然后使用第2个产生式一次，得到：

S=>0S1=>00S11=>…=>0n-1S1n-1=>

0n1n

可以推知L(G)中的元素仅是这样的串(0n1n)。从而可证明L(G)={0n1n|n≥1}.622023/7/18软件学院文法等价若L(G1)=L(G2)，则称文法G1和G2是等价的。

也就是说，如果两个文法定义的语言一样，则称这两个文法是等价的。

例如文法G[A]：

A→0R

A→01

R→A1

和例2.9的文法等价。632023/7/18软件学院证明(i*i+i)是算术表达式文法G=(VN,VT,S,P)VN={E}VT={i,+,*,(,)}S=EEi|E+E|E*E|(E)描述了算术表达式证明(i*i+i)是算术表达式如果能从文法G中推导出(i*i+i),则可证明它是算术表达式642023/7/18软件学院推导过程E=>(E)产生式：E(E)=>(E+E)产生式：EE+E=>(E*E+E)产生式：EE*E=>(i*E+E)产生式：Ei=>(i*i+E)产生式：Ei=>(i*i+i)产生式：Ei存在一个从E到(i*i+i)的推导，证明了(i*i+i)是文法G所定义的一个算术表达式652023/7/18软件学院语法分析树我们用一张树型结构的图来描述一个句子的推导，这种表示称为语法树。语法树的根结由文法开始符号标记。随着推导的进行，当某个非终结符被它的候选式所替换时，此非终结符生出其下一代新结，候选式中自左至右没有符号对应着一个新结。性质：在语法树生长的任何时候，所有那些没有后代的端末结自左至右的排列起来，就是一个句型。语法分析树的生成过程：书中第31页662023/7/18软件学院(i*i+i)的语法树E=>(E)产生式：E(E)=>(E+E)产生式：EE+E=>(E*E+E)产生式：EE*E=>(i*E+E)产生式：Ei=>(i*i+E)产生式：Ei=>(i*i+i)产生式：EiE=>(E)产生式：E(E)=>(E*E)产生式：EE*E=>(i*E)产生式：Ei=>(i*E