高级语言及其语法描述.ppt

形式语言的最初起因：语言学家乔姆斯基（Chomsky）想用一套形式化方法来描述语言。形式语言在自然语言研究中起步，在计算机科学中得到广泛应用。最初的应用：编译现在已广泛应用在人工智能、图象处理、通信协议、通信软件等多个领域在计算机理论科学方面：是可计算理论（算法―在有限步骤内求得解、算法复杂性、停机问题、）、定理自动证明、程序转换（程序自动生成）、模式识别等的基础。*为什么用形式语言#2022*形式语言与自动机理论的发展1956年，乔姆斯基（Chomsky）从产生的角度研究语言文法1951-1956年间，克林（Kleene）从识别的角度研究语言自动机1959年，乔姆斯基不仅确定了文法和自动机分别从生成和识别的角度去表达语言，而且证明了文法与自动机的等价性。形式语言真正诞生*基本概念字母表：元素的非空有穷集合。例：{a,b,c,…,z}（拉丁字母表）{α,β,γ,…,ω}(希腊字母表）{0,1} （二进制数字字母表）符号：字母表中的元素。如a,b,…*基本概念符号串：字母表中的符号组成的任何有穷序列。例.设字母表∑={a,b,c}其符号串有：a,b,c,ab,ac,aa,abc,…符号串与符号组成的顺序有关。符号串的长度：符号串中符号的数目,用|x|表示空符号串（空字）：不包含任何符号的符号串，记为ε。*子符号串设有非空符号串u=xvy，则称v为符号串u的子符号串。例.符号串x=a+b-(c+d)则a,a+b-,(c+d)等都是x的子符号串，且其长度分别为：|a|=1,|a+b-|=4,|(c+d)|=5*符号串的前缀与后缀符号串的前缀与后缀符号串左部的任意子串，称为符号串的前缀；符号串右部的任意子串，称为符号串的后缀。例.字母表A={a,b,c}上的符号串x=ab,则x的前缀有：ε、a、ab；后缀有：ε、b、ab。*基本概念符号串集合：若集合中所有元素都是某字母表?上的符号串，则称之为该字母表上的符号串集合。用?*表示?上的所有符号串的全体，空字也包括在其中。例.若?={a,b}则?*={??,a,b,aa,ab,bb,aaa,…}。?表示不含任何元素的空集{}注意区分：?、ε、{ε}*（连接）积?*的子集U和V中的（连接）积定义为:UV={??∣??U??V}即集合UV中的符号串是由U和V的符号串连接而成的。例.设U={a,b},V={α，β，γ}则UV={aα,aβ,aγ,bα,bβ,bγ}注意：一般UV?VU，但（UV)W=U(VW).n次（连接）积V自身的n次（连接）积记为：规定V0={?}.令：V*=V0?V1?V2?…，称V*是V的闭包。闭包V*中的每个符号都是由V中的符号串经有限次连接而成的。记V+=VV*,称V+是V的正则闭包。Vn=VVV…Vn*闭包定理.若A是符号串集合，则A*=(A*)*。则x∈AM，因此推得x∈A*，所以(A*)*?A*，故A*=(A*)*。证明：显然A*?(A*)*,现证(A*)*?A*任给符号串x∈(A*)*，则存在n，使得x∈(A*)n，x必存在n个子串x1,…,xn，使得x=x1…xn，且xi∈A*(i=1,…,n)。由xi∈A*，必存在整数pi,使得xi∈Api，令 **文法（Grammar）所谓文法是用来定义语言的一个数学模型。表示语言的方法：若语言L是有限集合，可用列举法若L是无限集合（集合中的每个元素有限长度），用其他方法。方法一：文法产生系统，由定义的文法规则产生出语言的每个句子方法二：机器识别系统：当一个字符串能被一个语言的识别系统接受，则这个字符串是该语言的一个句子，否则不属于该语言。Chomsky文法体系Chomsky文法体系中，任何一种文法必须包含两个不同的有限符号的集合非终结符集合VN终结符集合VT一个起始符S一个形式规则的有限集合￡（产生式集合）。注意￡中的产生式是用来产生语言句子的规则，而句子则是仅由终结符组成的字符串。这些字符串必须从一个起始符S开始，不断使用￡中的产生式而导出来。文法的核心是产生式的集合，它决定了语言中句子的产生。**文法的形式定义文法G