编译原理第三章文法和语言

第三章文法和语言课前索引【课前思考】◇高级语言有哪些一般特性？◇你所见到的程序设计语言的手册或语言标准是怎样陈述语言的语法和语义的？◇学习编译程序为什么要研究语言的描述问题？【学习目标】本章目的是为语言的语法描述寻求工具◇掌握对源程序给出精确无二义（严谨、简洁、易读）的语法描述手段之一---文法。◇熟练使用文法定义程序设计语言的单词和语法成分◇对形式语言的理论有一个初步基础【学习指南】◇什麽是文法,什麽是它定义的语言？◇在乔姆斯基（Chomsky）的文法类型中，我们为什麽关注上下文无关文法？◇什么是语法分析？语法分析方法的分类？【难重点】关于文法和语言的概念是形式语言的理论基础，形式语言抽象地定义为一个数学系统。形式是指这样的事实：语言的所有规则只以什麽符号串能出现的方式来陈述。这里介绍的语言的语法描述工具正是这样的系统。【知识结构】第3章文法和语言3.1引言和预备知识一个程序设计语言是一个记号系统，如同自然语言一样，它的完整的定义应包括语法和语义两个方面。所谓一个语言的语法是指一组规则，用它可以形成和产生一个合适的程序。目前广泛使用的手段是上下文无关文法，即用上下文无关文法作为程序设计语言语法的描述工具。语法只是定义什么样的符号序列是合法的，与这些符号的含义毫无关系，比如对于一个PASCAL程序来说，一个上下文无关文法可以定义A∶=B+C是合乎语法的，而A∶=B+是不合乎语法的。但是，如果B是实型的，而C是布尔型的，或者B，C中任何一个变量没有事先说明，则A∶=B+C仍不是正确的程序，也就是说程序结构上的这种特点，类型匹配，变量作用域等是无法用上下文无关手段检查的，这些工作属于语义分析工作。我们常常把程序设计语言的语义分为两类：静态语义和动态语义。静态语义是一系列限定规则，并确定哪些合乎语法的程序是合适的；动态语义也称作运行语义或执行语义，表明程序要做些什么，要计算什么。阐明语法的一个工具是文法，这是形式语言理论的基本概念之一。本章将介绍文法和语言的概念，重点讨论上下文无关文法及其句型分析中的有关问题。文法的直观概念在给出文法和语言的形式定义之前，我们先直观地认识一下文法的概念。当我们表述一种语言时，无非是说明这种语言的句子，如果语言只含有有穷多个句子，则只需列出句子的有穷集就行了，但对于含有无穷句子的语言来讲，存在着如何给出它的有穷表示的问题。以自然语言为例，人们无法列出全部句子，但是人们可以给出一些规则，用这些规则来说明(或者定义)句子的组成结构，比如：我是大学生是汉语的一个句子。汉语句子可以是由主语后随谓语而成，构成谓语的是动词和直接宾语，我们采用第2章所介绍的EBNF来表示这种句子的构成规则：〈句子〉∷=〈主语〉〈谓语〉〈主语〉∷=〈代词〉|〈名词〉〈代词〉∷=我|你|他〈名词〉∷=王明|大学生|工人|英语〈谓语〉∷=〈动词〉〈直接宾语〉〈动词〉∷=是|学习〈直接宾语〉∷=〈代词〉|〈名词〉“我是大学生”的构成符合上述规则，而“我大学生是”不符合上述规则，我们说它不是句子。这些规则成为我们判别句子结构合法与否的依据，换句话说，这些规则看成是一种元语言，用它描述汉语。这里仅仅涉及汉语句子的结构描述。这样的语言描述称为文法。一旦有了一组规则以后，我们可以按照如下方式用它们去推导或产生句子。我们开始去找∷=左端的带有〈句子〉的规则并把它表示成∷=右端的符号串，这个动作如右页所示：〈句子〉〈主语〉〈谓语〉，然后在得到的串〈主语〉〈谓语〉中，选取〈主语〉或〈谓语〉，再用相应的规则∷=右端代替之。比如，选取了〈主语〉，并采用规则〈主语〉∷=〈代词〉，那么得到：〈主语〉〈谓语〉〈代词〉〈谓语〉，重复做下去。得到句子我是大学生的全部动作过程是：〈句子〉〈主语〉〈谓语〉〈代词〉〈谓语〉我〈谓语〉我〈动词〉〈直接宾语〉第3章文法和语言我是〈直接宾语〉我是〈名词〉我是大学生符号的含义是，使用一条规则，代替左边的某个符号，产生右端的符号串。显然，按照上述办法，不仅生成我是大学生这样的句子，还可以生成王明是大学生，王明学习英语，我学习英语，'他学习英语，你是工人，你学习王明等几十个句子。事实上，使用文法作为工具，不仅为了严格地定义句子的结构，也是为了用适当条数的规则把语言的全部句子描述出来，是以有穷的集合刻划无穷的集合的工具。语言概述语言是由句子组成的集合，是由一组符号所构成的集合。汉语--所有符合汉语语法的句子的全体英语--所有符合英语语法的句子的全体程序设计语言--所有该语言的程序的全体研究语言每个句子构成的规律每个句子的含义每个句子和使用者的关系研究程序设计语言每个程序构成的规律每个程序的含义每个程序和使用者的关系语言研究的三个方面语法Syntax语义Semantics语用Pragmatics语法--表示构成语言句子的各个记号之间的组合规律语义--表示按照各种表示方法所表示的各个记号的特定含义。（各个记号和记号所表示的对象之间的关系）语用--表示在各个记号所出现的行为中，它们的来源、使用和影响。每种语言具有两个可识别的特性，即语言的形式和该形式相关联的意义。语言的实例若在语法上是正确的，其相关联的意义可以从两个观点来看，其一是该句子的创立者所想要表示的意义，另一是接收者所检验到的意义。这两个意义并非总是一样的，前者称为语言的语义，后者是其语用意义。幽默、双关语和谜语就是利用这两方面意义间的差异。如果不考虑语义和语用，即只从语法这一侧面来看语言，这种意义下的语言称作形式语言。形式语言抽象地定义为一个数学系统。“形式”是指这样的事实：语言的所有规则只以什麽符号串能出现的方式来陈述。形式语言理论是对符号串集合的表示法、结构及其特性的研究。是程序设计语言语法分析研究的基础。正如英语是由句子组成的集合，而句子又是由单词和标点符号组成的序列那样，程序设计语言PASCAL或C，是由一切PASCAL或C程序所组成的集合，而程序是由类似IF，BEGIN，END的符号，字母和数字这样一些基本符号所组成，从字面上看，每个程序都是一个基本符号串，设有一基本符号集，那么PASCAL或C语言可看成是在这个基本符号集上定义的，按一定规则构成的一切基本符号串组成的集合，因此有必要请你将有关符号串的一些概念做一回顾，作为文法和语言的形式定义的预备知识。字母表S：符号（元素）的非空有穷集合。符号：可以相互区别的记号（元素）。符号串：由字母表S中的符号组成的任何有穷序列称为该字母表上的符号串。即：第3章文法和语言①符号串ε(没有符号的符号串)是S上的符号串称为空串；②若x是∑上的符号串，a是∑的元素，则xa是∑上的符号串；③y是∑上的符号串，当且仅当它可以由1和2导出。符号串的运算符号串的长度：符号串中符号的个数.符号串s的长度记为|s|。ε的长度为0连接：符号串x、y的连接,是把y的符号写在x的符号之后得到的符号串xy如x=ab,y=cd则xy=abcd有εa=aε方幂：符号串自身连接n次得到的符号串an定义为aa…aan个aa1=a,a2=aa则a0=ε使用∑*表示S上的一切符号串（包括ε）组成的集合。∑*称为Σ的闭包。∑上的除ε外的所有符号串组成的集合记为∑+。∑+称为Σ的正闭包。语言语言是由句子组成的集合，是由一组符号所构成的集合。换言之，字母表∑上的一个语言是∑上的一些符号串的集合(字母表∑上的每个语言是∑*的一个子集)。例如：若有字母表Σ={a,b},则∑*={ε,a,b,aa,ab,ba,bb,aaa,aab,…}根据上述关于语言的概念，我们说集合A={ab,aabb,aaabbb,…,anbn,…}为字母表∑上的一个语言，也可以把集合A描述为{w|w∈∑*且w=anbn,n≥1}。我们说集合B={a,aa,aaa,…}为字母表∑上的一个语言，同样也可以把集合B描述为{w|w∈∑*且w=an,n≥1}。注意：{ε}是一个语言。Φ即{}是一个语言。给出有关语言的运算既然将语言定义为一个集合，那么有关集合的运算也适合语言。即：设L是（∑上的）一个语言,M是（∑上的）一个语言，则语言L和M的并，交，差，补是一个语言。语言L和M的并表示为L∪M，是一个语言，满足:{w|wisinLorisinM}如：L1={a,b,…y,z}M1={1,2…8,9}L1∪M1={a,b,…y,z，1,2…8,9}语言L和M的连接是一个语言，记为LMLM={st|s∈L且t∈M}如：L1M1={a1,b1,…y1,z1,a2,b2…a9…z9}有L{ε}={ε}L=LL的n次连接Ln=LL...L语言L的闭包记为L*L*=L0∪L1∪L2∪...L0={ε}，Ln=LLn-1=Ln-1L,n≥1语言L的正闭包记为L+，L+=L1∪L2∪L3...L+=LL*=L*LL*=L+∪{ε}如：（L1∪M1）*={a,b,…y,z，1,2…8,9，aa,1a,…xyz,6789st..}L1（L1∪M1）*={所有字母打头的字母和数字符号串}第3章文法和语言3.2文法和语言的形式定义我们现在讨论如何形式地描述一种语言？显然，如果语言是有穷的（只含有有穷多个句子），可以将句子逐一列出来表示；但是如果语言是无穷的，我们不可能将语言的句子逐一列出来，而是希望寻求语言的有穷表示。语言的有穷表示有两个途经：一种是生成方式，就是利用文法，利用文法的规则和推导手段，可以将语言中的每个句子用严格定义的规则来构造。另一种方法是识别方式，是使用自动机的行为描述语言：它的行为相当於一个过程，当输入的一个符号串属于某语言时，该过程经有限次计算后就会停止并回答是，若这个符号串不属于此语言，该过程要麽能停止并回答不是，要麽永远继续下去。我们要介绍的文法即是生成方式描术语言的：语言中的每个句子可以用严格定义的规则来构造。下面给出文法的定义。进而在文法的定义的基础上，给出推导的概念，句型、句子和语言的定义。定义3.1文法G定义为四元组(Vn，VT，P，S)。其中Vn为非终结符号(或语法实体，或变量)集；VT为终结符号集；P为产生式(也称规则)的集合；Vn，VT和P是非空有穷集。称作识别符号或开始符号，它是一个非终结符，至少要在一条产生式中作为左部出现。Vn和VT不含公共的元素，即Vn∩VT=φ通常用V表示Vn∪VT，V称为文法G的字母表或字汇表。其中规则，也称重写规则、产生式或生成式，是形如α→β或α∷=β的(α，β)有序对，其中α是字母表V的正闭包V+中的一个符号，β是V*中的一个符号。α称为规则的左部，β称为规则的右部。文法---是一个数学系统一个形式数学系统可由下列基本成分来刻画：一组基本符号，一组形成规则，一组公理，一组推理规则。例3.1文法G=(Vn，VT，P，S)，其中Vn={S}，VT={0，1}，P={S→0S1，S→01}。这里，非终结符集中只含一个元素S；终结符集由两个元素0和1组成；有两条产生式；开始符号是S。例3.2文法G=(Vn，VT，P，S)其中Vn={标识符，字母，数字}VT={a,b,c,…，x,y,z,0,1,…，9}P={〈标识符〉→〈字母〉〈标识符〉→〈标识符〉〈字母〉〈标识符〉→〈标识符〉〈数字〉〈字母〉→a〈字母〉→b…〈字母〉→z〈数字〉→0〈数字〉→1…〈数字〉→9}第3章文法和语言S=〈标识符〉这里，使用尖括号〈和〉括起非终结符。很多时候，不用将文法G的四元组显式地表示出来，而只将产生式写出。一般约定，第一条产生式的左部是识别符号；用尖括号括起来的是非终结符号，不用尖括号括起来的是终结符号，或者用大写字母表示非终结符号，小写字母表示终结符号。另外也有一种习惯写法，将G写成G[S]，其中S是识别符号，例3.1还可以写成：G：S→0S1S→01或G[S]：S→0S1S→01有时，为书写简洁，常把相同左部的产生式，形如A→α1A→α2…A→αn缩写为：A→α1|α2|…|αn这里的元符号|读做或。一个文法的几种写法①G=({S,A}，{a,b}，P，S)其中P：S→aAbA→abA→aAbA→ε②G：S→aAbA→abA→aAbA→ε③G[S]：A→abA→aAbA