文法和形式语言.pptVIP

第二章 文法和形式语言 形式化定义，基本概念 文法的写法，BNF表示法 规则的推导，语法树及其二义性 文法变换，文法和语言的分类 概 述 程序设计语言包含三方面 如：x=a+b*c 语法：语言的构成规律,C语言中赋值语句的写法 语义：语言所代表的含义，对=号右边的表达式进行计算，再赋值给左边的变量 语用：语言的实际应用，用于计算和保存值 形式化方法：定义基本符号串和规则，根据规则“造句” 形式语言：只看语法，不考虑含义 用规定的符号串和规则来书写的语言 2.1 符号和符号串 组成形式语言的基本要素 字母表 是符号的非空有穷集合 习惯用大写字母表示 如有字母表Σ、V：Σ={a,b,c} V={0,1} 符号(字符) 字母表中的元素 如：a，b，c即为符号 不同文种的语言有适用于该语言的字母表 符号串与符号串集合 符号串： 字母表中符号组成的有穷序列。 如： Σ={a,b,c}，则可以有符号串a, b, c, aa, ab, ac, aaa…… 有序性：若符号串中符号出现的顺序不同，符号串也不同，如ab和ba是不同的符号串 空串：不含有任何符号的串称作空串，记作?。 符号串集合： 字母表Σ上若干个符号串组成的集合 如：有符号串集合 A={ab,bc} B={a,ab,abc} 句子和语言 句子 字母表上符合某种规则构成的符号串。 语言 字母表上句子的集合。 注： 用a, b, c, …, r表示符号； 用s, t, u, …, z表示符号串； 用A, B, C, …, Z表示符号串集合。 如在字母表?={a, b, c}上，有符号串集合A={a, ab, aa, abc}，s=ab是A中的符号串，a, b, c都是字母表中的符号 二、符号串的运算 符号串相等 字母表∑上的两个符号串x，y，若x，y的各个符号依次相等，则该两符号串相等，记x=y 符号串的幂 符号串x自身连接n次得到的 如：x=ab， 则有x0= ? x1=ab x2=abab … xn=abab…ab(n个ab相连，而不是相乘) 注：用an表示n个a相连接的符号串，而不是n个a相乘 符号串集合的乘积 定义：若串集A={?1, ?2, …}，串集B={?1, ?2, …}，则乘积AB={? ?| ? ? A and ? ? B} 在A中任取一个符号串与B中任一符号串连接 例如：A={ab,bc}; B={ac,cb} 则AB={abac，abcb，bcac，bccb} 注： 由于 ? x= x ? =x 所以 {?} A=A {?} =A 串集的自身乘积称作串集的方幂 空集?：不包含任何元素 有?A=A?=?，但??? 符号串集合的幂 例如：串集A的各次方幂定义为： A0={?} A1=A A2=AA …… An=AAn-1 （=An-1A） (n0) 为符号串集合A的自身乘积 2.2 文法和语言 类似自然语言由句子构成，句子要符合一定的规则，称为“文法” 语言是无穷的，规则确是有限的 如何用有限的文法规则推导出无限的句子，即“语言的有穷表示” 一、文法的概念 文法 构造句子的规则，用于产生或推导句子 规则，二元组 形如：U::=u或U?u，即“符号::=符号串”的形式 含义：U定义为u，或者U由u组成 规则又叫产生式：U产生出u 引 例 例如：自然语言中有下面的句子 Young men like pop music. 其语法规则如下： 句子?主语谓语：句子由主语和谓语构成 主语 ?形容词名词 谓语 ?动词宾语 宾语 ? 形容词名词 形容词 ?Young | pop：形容词可以是young或者pop 名词 ?men | music 动词 ?like 形式化定义 文法写成G[Z]的形式 Z为开始符号或识别符号，至少要出现一次在某一条规则的左部 规则中出现的所有符号构成字汇表，记为V 规则的组成元素 推论： V=Vn∪Vt Vn∩Vt=? 句子是由终结符组成的 BNF表示法 用“|”表示“或”，用以合并左部相同的规则 规则的左部只有单个非终结符 Chomsky对文法的定义 文法是四元组G= {Vn ,Vt , P, S } Vn：非空有穷的非终结符号集合,即规则左部符号的集合 ?Vt：非空有穷终结符号集合； 且Vn∩Vt＝ ? ；字汇表V= Vn∪Vt S属于Vn?，称为开始符号或识别符号。 P是一个产生式(规则)的非空有穷集合，每个产生式的形式是α?β(或α::=β)，其中α∈V+，β∈V*。 开始符号S至少必须在某个产生式的左部出