编译原理第2章：高级语言及其语法描述

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

2.1程序语言的定义2.2程序语言的语法描述22023/11/262.1程序语言的定义一个程序设计语言是一个记号系统，其完整的定义应包括语法和语义两个方面语言的语法是指一组规则，用它可以形成和产生一个合适的程序上下文无关文法语法只定义什么样的符号序列是合法的，与这些符号的含义毫无关系PASCAL语言中：A:=B+C合乎语法规则，A:=B+不合乎语法规则阐明语法的一个工具是文法，这是形式语言理论的基本概念之一32023/11/262.2程序语言的语法描述基本概念字母表、符号、符号串、闭包等文法的定义文法的分类Chromsky对文法的分类文法和语言推导、归约、句型、句子、语言语法分析树和二义性42023/11/26基本概念字母表元素的非空有限集，记为

。例：

={a，b，c}字母表中的元素称为符号。例：a，b，c，字母表包含了语言中所允许出现的所有符号符号串符号的有穷序列。例：a,aa,ac,abc，..，无任何符号的符号串称为空符号串，记为ε52023/11/26基本概念符号串运算符号串长度x为符号串,其长度|x|等于组成该符号串的符号个数。例：x=string，则|x|=6,|ε|=0符号串连接若x、y是定义在Σ上的符号串，则xy称为x和y的连接，xy也是Σ上的符号串εx＝xε=x62023/11/26基本概念符号串集合的乘积令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+72023/11/26文法的直观描述什么是文法文法是定义或描述语法结构一组形式规则例句：Hegavemeabook.英语中的基本语法规则：<句子>

<主语><谓语><间接宾语><直接宾语><主语>

<代词>|<名词><谓语>

<动词><间接宾语>

<代词><直接宾语>

<冠词><名词><代词>He|me<名词>

book<动词>

gave<冠词>

a|an|the82023/11/26例句：Hegavemeabook.根据上述语法规则对例句进行分析，可推出该例句。<句子>=><主语><谓语><间接宾语><直接宾语>

=><代词><谓语><间接宾语><直接宾语>=>He<谓语><间接宾语><直接宾语>=>He<动词><间接宾语><直接宾语>=>Hegave<间接宾语><直接宾语>=>Hegave<代词><直接宾语>=>Hegaveme<直接宾语>=>Hegaveme<冠词><名词>=>Hegavemea<名词>=>Hegavemeabook92023/11/26用图形化方式表示这种推导，形成一颗语法分析树。

<句子><主语><代词><冠词>Hea<谓语><间接宾语><直接宾语><动词>gave<代词>me<名词>book语法成分（在形式语言中又称“非终结符”）单词符号（在形式语言中又称“终结符号”)102023/11/26上述定义英文句子的规则可以说就是一个上下文无关文法归纳起来，一个上下文无关文法G包括四个组成部分：一组终结符号一组非终结符号一个开始符号一组产生式112023/11/26文法形式化定义文法定义成一个四元组G=(VN,VT,S,P)VN:非空有限的非终结符集；VT:非空有限的终结符集；S:开始符号；P:产生式集合。其中，VN

∩VT

=Φ，S∈VNP中产生式一般形式为:A

α|β，其中A∈VN

，α,β∈（VN∪VT

）*122023/11/26例1：文法G=(VN,VT,S,P)，其中VN={S}，VT={0，1}，P={S→0S1，S→01}。这里，非终结符集中只含一个元素S；终结符集由两个元素0和1组成；有两条产生式；开始符号是S132023/11/26一个文法的几种写法

①G=({S,A}，{a,b}，P，S)

其中P：S→aAb

A→ab

A→aAb

A→ε

②G：S→aAb

A→ab

A→aAb

A→ε

③G[S]：A→abA→aAbA→εS→aAb

④G[S]：A→ab|aAb|εS→aAb

142023/11/26文法的分类对产生式施加不同的限制得到不同类型的文法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)*.152023/11/26左线性文法规则形式:

AB或A（左线性）

A,BVN,(VT)*.正规文法规则形式:

AB或A其中A,BVN,VT，如果S

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

AVN

，δ

(VN

VT)*允许有空产生式：A

不改变描述能力162023/11/26四个文法类的定义是逐渐增加限制的，因此每一种正规文法都是上下文无关的，每一种上下文无关文法都是上下文有关的，而每一种上下文有关文法都是0型文法。称0型文法产生的语言为0型语言。上下文有关文法、上下文无关文法和正规文法产生的语言分别称为上下文有关语言、上下文无关语言和正规语言现今大多数高级程序设计语言采用上下文无关文法来描述其语法已经足够了172023/11/26文法举例文法G=({S,A,B},{a,b,c,d,e},S,P),其中，P={S

abcA|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’={S

aA’|eB’,A’bC’,C’cA,B’dB,AbD’,D’eB,Bd}182023/11/26192023/11/26S=>0A=>010A=>…=>0(10)*A=>0(10)*202023/11/26文法和语言上下文无关文法定义的语言从文法的开始符号出发，反复使用产生式，对非终结符进行替换和展开，直至推导出语言的各种句子来推导与归约的概念推导、最左推导、最右推导、规范推导归约、最左归约、最右归约、规范归约句型、句子、语言的形式定义语法分析树与二义性212023/11/26推导和归约222023/11/26最左推导和最右推导规范推导最右直接推导又称为规范直接推导，最右推导又称为规范推导232023/11/26最右归约和最左归约的定义242023/11/26句型、句子、语言的定义定义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*},即文法的语言是文法所有句子的集合*

*

*

252023/11/26例2.9文法G=(VN,VT,S,P)，其中VN={S}，VT={0，1}，P={S→0S1，S→01}。这里，非终结符集中只含一个元素S；终结符集由两个元素0和1组成；有两条产生式；开始符号是S262023/11/26直接推导示例对于例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。

272023/11/26对例2.9的文法，存在直接推导序列v=0S1=>00S11=>000S111=>00001111=w，即0S1=>+00001111，也可记作0S1=>*00001111

S，0S1，000111都是例2.9文法G的句型，其中000111是G的句子282023/11/26考虑例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}.292023/11/26文法等价若L(G1)=L(G2)，则称文法G1和G2是等价的。

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

例如文法G[A]：

A→0R

A→01

R→A1

和例2.9的文法等价。302023/11/26证明(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),则可证明它是算术表达式312023/11/26推导过程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所定义的一个算术表达式322023/11/26语法分析树我们用一张树型结构的图来描述一个句子的推导，这种表示称为语法树。语法树的根结由文法开始符号标记。随着推导的进行，当某个非终结符被它的候选式所替换时，此非终结符生出其下一代新结，候选式中自左至右没有符号对应着一个新结。性质：在语法树生长的任何时候，所有那些没有后代的端末结自左至右的排列起来，就是一个句型。语法分析树的生成过程：书中第31页332023/11/26(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+E)产生式：EE+E=>(i*i+E)产生式：Ei=>(i*i+i)产生式：Ei342023/11/26文法的二义性一个文法，如果它的一个句子有两棵或两棵以上的语法树，则称此句子具有二义性。如果一个文法含有二义性的句子，则该文法具有二义性。换一个说法：如果一个文法存在某个句子对应两棵或两棵以上不同的语法树，则称该文法是二义的352023/11/26例1．注：文法的二义性是不可判定的，但可以通过约定加以改造。例2．文法G1：A→AN|NN→0|1|…|9

则L(G1)为无符号整数例3．文法G2：B→aBb|ab,求L(G2)

解：B=>aBb=>aaBbb=>aaaBbbb=>……

即，

∴L(G2)={anbn|n≥1}362023/11/26例题构造文法生成下列语言(1){an|n≥1}S

aA|

A

aA|

或

S

aS|

(2){an