《文法与语言》PPT课件.ppt

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

1、第二章文法和形式语言本章主要介绍形式语言理论中的一些最基本的概念和基础知识，它是学习以后各章节的基础。2.1符号和符号串2.1.1字母表与符号串①字母表:元素的非空有穷集合，习惯上用大写字母表示。②符号：字母表中元素。③符号串：符号的有穷序列。④空符号串：不含任何符号的符号串，记为ε。⑤符号串集合：字母表Σ上的符号串组成的集合。2.1.2符号串的运算①符号串的长度：符号串中所包含的符号个数。设符号串为x，则其长度记为

2、x

3、。例：空符号串长度为0，即

4、ε

5、=0。②符号串的连接：设有符号串x和y，把y的所有符号相继写在x的符号串之后所得到的符号串即称为x和y的连接，记为xy.例：εx=xε=x

6、③符号串的方幂：设x是符号串，则x的n次连接称为n次方幂，记为xn.例：x0=ε④符号串的前缀、后缀、子串假设x是一个符号串，则有：符号串x的前缀是指：从符号串x的尾部删除若干（含0个）符号后得到的符号串；符号串x的后缀是指：从符号串x的头部删除若干（含0个）符号后得到的符号串；符号串x的子串是指：删除了x前缀（或删除x的后缀或删除x的前缀和后缀）后得到的符号串；对任意的符号串x，x的前缀、后缀都是x的子串，但x的子串不一定是x的前缀或后缀。对任意的符号串x，x和ε都是符号串x的前缀、后缀，也是x的子串。2.1.3符号串集合的运算①符号串集合的乘积：设A、B为符号串集合，则符号串集合的乘积

7、表示为AB={xy

8、x∈A,y∈B}，即A中的任意符号串和B中的任意符号串的连接所构成的集合。因为有xε=εx=x,所以有{ε}A={ε}A=A②符号串集合的方幂：即同一个符号串集合的乘积。例：设A为符号串集合，则A0={ε}，A1=A，A2=AA，……③符号串集合的闭包设A为符号串集合，则A的闭包表示为A＊，其定义为：A的若干次幂（包括0次幂）的并集。它表示符号串集合A上的所有可能的符号串（含ε）的集合。A＊=A0∪A1∪A2……∪An④符号串集合的正闭包：A的正闭包表示为A＋，其定义为：A的若干次幂（不包括0次幂）的并集。它表示符号串集合A上的所有可能的符号串（不含ε）的集合。A＋=A

9、1∪A2……∪An显然有A＊=A0∪A＋={ε}∪A＋A＋=AA＊=A＊A2.2文法和语言语言是特定字母表上具有一定语法结构的符号串的集合。若用L表示语言，用Σ表示字母表，则L∈Σ＊文法(Grammar)是定义或描述语言的语法结构的一组形式规则(即语法规则)。一个程序语言的文法的目的就是用适当条数的规则把该程序语言全部成分描述出来。2.2.1文法及文法的BNF表示1、规则即产生式，是一有序对（U，x）,通常记为U→x(或U∷=x)其中U为规则的左部，是一个符号，x为规则的右部，为有穷符号串。规则U→x表示符号U由符号串x组成（或符号U定义为符号串x）2、文法和字汇表文法可以定义成一个四元组

10、G[S]=(VN，VT，S，P)。其中，VT:非空有限的终结符号集；VN:非空有限的非终结符号集；S:开始符号，是文法G规定的最终目标；P:产生式的集合。V=VN∪VT称为文法G[S]的字汇表。VN∩VT=，SVN。为了方便，表示文法时只列出产生式，而不以4元组显示地表示出来。3、文法的BNF（巴科斯范式）表示即在规则中引入或者符号“∣”，将左部相同的规则缩写到一起。4、递归规则和递归文法左部和右部含有相同非终结符号的规则称为递归规则，至少含有一条递归规则的文法称为递归文法。2.2.2推导和归约设文法G=(VN，VT，P，S)，U→u是其中的产生式，αβ是文法任意的符号串，则有αUβ

11、αuβ其中符号“”仅表示“一步推导”，即利用产生式对左边符号串中的一个非终结符进行替换，得到右边的符号串。我们称αUβ直接推导出αuβ，也可以说αuβ直接归约到αUβ。如果有直接推导序列：a0a1a2…an则说a0推导出an推导，记作：，我们称这个序列是一个从到的长度为n的推导，其中表示0步或多步推导。a0an﹡a0an﹡最左、最右推导和规范推导1、在xUyxuy直接推导中，即U是符号串xUy中最左非终结符，则称此直接推导为最左直接推导。若一个推导的每一步直接推导都是最左直接推导，那么此推导称为最左推导。2、在xUy::=xuy直接推导中，即U是符号串xUy中最右非终结符，

12、则称此直接推导为最右直接推导。若一个推导的每一步直接推导都是最右直接推导，则称此推导为最右推导。最右直接推导又称为规范直接推导，最右推导又称为规范推导。最左推导的逆过程是最右归约，最右推导的逆过程是最左归约。2.2.3句型、句子和语言定义：设G[S]是字汇表V上的一个文法，如果符号串u是由文法的开始符号推导出来的，则称u是文法G[S]的句型。如果u仅由终结符号组成，则称u是文法G[S]的句子。即：若,uV*，则称u是文