资源描述：
《编译原理第2章+形式语言基础ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第二章语言的基本知识§2.1语言概述§2.2符号和符号串§2.3文法与语言§2.4语法分析初步§2.5文法和语言分类§2.6文法其他表示法1§2.1语言概述一、语言的定义二、形式语言提出三、语言描述方法四、与语言有关的几个概念2一、语言的定义任何一种语言都是在某个特定字母表上定义的、按照一定的规则构成的字符串的集合。3二、形式语言提出形式语言是研究符号的语言，它仅考虑符号间的关系，不考虑含义，即用数学方法（主要是代数方法）对语言进行形式化描述。1956年N.Chomsky(乔姆斯基）在研究自然语言过程中
2、提出一种文法数学模型，为形式语言理论打下了基础，成为计算机科学理论一个重要分支，即形式语言与自动机。4三、语言描述方法枚举法文法生成法：就是用有限个规则来产生出语言中无限个句子，这种规则集合称文法。自动机识别法：用自动机对语言中的句子进行识别5四、与语言有关的几个概念元语言：可用来描述其它语言的一种语言语法：是在字母表上构造句子的一组规则语义：是按照语法规则所构成结构的含义语用：是表示语言符号与使用者关系6§2.2符号和符号串一、字母表二、符号串三、符号串集合7一、字母表有限个元素的非空集合称字母表，也
3、称符号集。它是组成一个语言最基本的成分。字母表中元素称符号。习惯上用V、Σ或其它大写字母表示。例如V={a,b,c}，V={α,β…ω}
4、V
5、表示字母表中符号的个数。对于不同程序设计语言有不同字母表。例如，机器语言字母表={0,1}，PASCAL语言的字母表由字母、数字以及一些特殊符号，如+，-，*，/，·，(，)，=，…等组成。注意：在一个语言中不能出现字母表以外的符号。8二、符号串1、定义符号串是字母表中的符号所组成的任何有穷序列(有时也称为符号行或字)例如：设V={a,b,c},则符号串有a,b,
6、c,aa,ab,ac,ba,abc…又如：设V={0,1},则符号串有0，1，00，01，10，11，000…由上例可以看出，符号串与符号组成顺序有关，如符号串ab不同于ba，符号串01不同于10，今后我们常用t,u,v,…x,y,z等小写字母表示符号串。92、空符号串不包含任何符号的符号串称为空符号串，记为ε。3、符号串长度符号串中所含符号个数称为该符号串的长度，设符号串为x，则用
7、x
8、来表示x的长度。例如：x=abc，则
9、x
10、=3,显然,
11、ε
12、=0。104、关于符号串的几种运算（1）符号串的联结设有
13、符号串x和y，则它们的联结xy是将符号串y直接拼接在符号串x之后，即x=x1x2x3…xm,y=y1y2y3…yn则xy=x1x2x3…xmy1y2y3…yn显然εx=x，xε=x11（2）符号串的方幂若x是符号串则x0=ε，x1=x，x2=xx，x3=xxx，…xn=xx…x(n个）如x=abc则x0=ε,x1=abc,x2=abcabcX3=abcabcabc∩12三、符号串集合举例：字母表V={a,b}，问用V中的符号，可以组成哪些符号串？解：ε,a,b,aa,ab,ba,bb,aaa,…bbb,
14、…1、定义：若集合A中的一切元素都是字母表V上的符号串，则称A为字母表V上的符号串集合13V*定义：字母表V上各种长度符号串构成串集合，记为V*，不包括空行的集合记为V+即V*={x
15、x是V上符号串且包括空符号串}V+={x
16、x是V上符号串且不包括空符号串}V+=V*-{ε}如：V={a,b}，则V*={ε,a,b,aa,ab,ba,bb,aaa,…bbb,…}V+={a,b,aa,ab,ba,bb,aaa,…bbb,…}142、关于串集合的运算（1）串集合乘积设A和B为两个符号串集合，并包含于V*，则
17、A和B的乘积定义为：AB={xy
18、x∈A且y∈B}由此定义，乘积AB是满足x∈A且y∈B的所有符号串xy所组成的集合。如：V={0，1}V*={ε,0,1,00,01,10,11,000,001，010，011，100,101…}如果A={0，101}B={10，11，110}则AB={010，011，0110，10110，10111，101110}符号ø表示空集15（2）符号串集合的方幂设符号串集合A则A的方幂运算定义为：A0={ε},A1=A,A2=AA,A3=AAA,…An=AAA…A(n个）如：
19、设A={a,b}，则A0={ε},A1={a,b}A2={a,b}{a,b}={aa,ab,ba,bb}A3={aaa,aab,aba,abb,baa,bab,bba,bbb}16(3)符号串集合的闭包和正闭包设A为符号串集合，则A的正闭包定义为A+=A1∪A2∪…∪An∪…符号串集合A的闭包定义为A*=A0∪A+={ε}∪A+如A={a,b}则A+={a,b}∪{aa,ab,ba,bb}∪…={a,b,aa,ab,ba,bb,aaa,…,
