《形式语言概论》ppt课件

《《形式语言概论》ppt课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第二章形式语言概论编译程序使得高级语言源程序所描述的功能得以在计算机上实现。编译程序的设计者就是高级语言的实现者，源程序的编写者就是高级语言的使用者，他们必须遵循同样的准则——高级语言程序的构成规则，才能使写出的源程序能够被成功地翻译.构造一个编译程序，首先要了解被编译的源程序的结构及其含义。要搞清楚源语言的词法规则、语法规则和语义规则是如何描述的。文法描述的就是高级语言程序的构成规则。第二章形式语言概论本章主要介绍形式语言理论中的一些最基本的概念和基础知识，它是学习以后各章节的基础。大多数程序设计语言的单词和语句是由正规文法和上下文无关

2、文法来描述的。有穷自动机是词法分析的理论基础。2.1语言成分一个语言的成分包括字母表（Alphabet）,文法(Grammar)以及它的语义。本节将主要讨论字母表和符号串的一些基本概念。字母表与符号：字母表是元素的非空有穷集合。字母表中的元素称为符号。举例说明。符号串及其运算：①符号串的概念②符号串的长度。③符号串的连接。④符号串集合的乘积。⑤符号串的方幂。⑥符号串集合的方幂。⑦符号串集合的正闭包。⑧符号串集合的自反闭包。形式语言形式语言是字母表上按某种规则构成的所有串的集合，这些串称为句子或字。对于一个具体的语言，都有语法和语义两个方面

3、，形式语言是指不考虑语言的具体意义。形式语言的表示方法有穷语言：枚举法无穷语言：文法2.2产生式文法和语言文法(Grammar)是对语言结构的定义和描述，换句话说，在形式上用来描述语言语法结构的就是文法。通常是由一组规则构成的。一个程序语言的文法的就是用适当条数的规则把该程序语言全部成分描述出来。2.2.1产生式文法定义2.1产生式文法定义成一个四元组G=(VN，VT，S，P)，VT:非空有限的终结符号集(符号表)；VN:非空有限的非终结符号集(变量表)；S:开始符号(识别符号)，是文法G规定的最终目标；P:产生式（规则）的集合。其中VN

4、∩VT=，SVN。我们令V=VN∪VT，则P中产生式的一般形式为A

5、AVN且,V＋或A::=

6、(本书中统一采用“A

7、”的表示方法)。2.2.2上下文无关文法定义2.2文法G是一个四元组，G=(VN，VT，P，S)，其中，VN、VT分别是非空有限的非终结符号集和终结符号集，VN∩VT=，P是产生式集，SVN称为文法的识别符号或开始符号。开始符号S必须至少在某个产生式的左部出现一次。程序设计语言表达式的文法G1=(VN,VT，S，P)VN={E}VT=(i,+,*,(,)}S=EP={E→i,E→E+E,E→E

8、*E,E→(E)}2.2.3上下文无关文法定义的语言定义2.3设文法G=(VN，VT，P，S)，A→是其中的产生式，若有符号串,(VN∪VT)*，使得U=A，w=则称w为U应用产生式A→所得到的直接推导(DirectDeriavtion)，也称w可直接归约到U,记为Uw,即A特别的，当==时，有A即每个产生式的右部都是它左部的直接推导，符号“”仅指“推导一步”的意思。举例说明.2.2.3上下文无关文法定义的语言定义2.4如果存在一个直接推导的序列v=012…n=w（n>0）则称

9、符号串w为符号串u的一个推导，或称“w可归约到v”记为推导举例.2.3文法的分类2.3.1文法分类乔姆斯基根据产生式的形式把文法分为4类:0型文法（短语文法、无限制文法）1型文法（上下文有关文法）2型文法（上下文无关文法）3型文法（左、右线性文法和正规文法）0型文法产生式具有以下形式：→其中，(VN∪VT)+，(VN∪VT)*1型文法（上下文有关文法）1型文法G的产生式具有以下形式：→要求：1≤∣∣≤∣∣其中=1A2；=12；1，2(VN∪VT)*；AVN；(VN∪VT)+。例1型文法G6=(

10、VN，VT，P，S)其中，VN={S，X，Y，Z}VT=（x，y，z）P={S→xSYZxYZ,xY→xy，yY→yy,yZ→yzZY→YZ,zZ→zz}2型文法（上下文无关文法）在1型文法的产生式中上下文1和2用空符号串代替，则有以下形式的产生式称为2型文法：A→其中，AVN，(VN∪VT)+。例2型文法G3=(VN，VT，P，E)其中，VN={E，T，F}VT={+，*，(，)，i}P={E→E+TT，T→TFF，F→(E)i}3型文法（右线性文法和正规文法)如果P中的产生式只含有下面的两种形式：A→A→B

11、则称该文法为右线性文法，其中，A，BVN，VT*。例右线性文法G4=(VN，VT，P，S)其中，VN={S，A，B}VT={0,1}P={S→011A0B，A→1A0B，B→0