编译原理形式语言基础.ppt

该【编译原理形式语言基础 】是由【qinqinzhang】上传分享，文档一共【152】页，该文档可以免费在线阅读，需要了解更多关于【编译原理形式语言基础 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。(优选)编译原理第章形式语言基础
现在是1页\一共有152页\编辑于星期一
1
一、语言的定义
任何一种语言都是在某个特定字母表上定义的、按照一定的规则构成的字符串的集合。
现在是2页\一共有152页\编辑于星期一
2
二、形式语言提出
形式语言是研究符号的语言,它仅考虑符号间的关系,不考虑含义,即用数学方法(主要是代数方法)对语言进行形式化描述。
(乔姆斯基)在研究自然语言过程中提出一种文法数学模型,为形式语言理论打下了基础,成为计算机科学理论一个重要分支,即形式语言与自动机。
现在是3页\一共有152页\编辑于星期一
3
三、语言描述方法
枚举法
文法生成法:就是用有限个规则来产生出语言中无限个句子,这种规则集合称文法。
自动机识别法:用自动机对语言中的句子进行识别
现在是4页\一共有152页\编辑于星期一
4
四、与语言有关的几个概念
元语言:可用来描述其它语言的一种语言
语法:是在字母表上构造句子的一组规则
语义:是按照语法规则所构成结构的含义
语用:是表示语言符号与使用者关系
现在是5页\一共有152页\编辑于星期一
5
§
一、字母表
二、符号串
三、符号串集合
现在是6页\一共有152页\编辑于星期一
6
一、字母表
有限个元素的非空集合称字母表,也称符号集。它是组成一个语言最基本的成分。字母表中元素称符号。|V|表示字母表中符号的个数。
对于不同程序设计语言有不同字母表。例如,机器语言字母表={0,1},PASCAL语言的字母表由字母、数字以及一些特殊符号,如+,-,*,/,·,(,),=,…等组成。
注意:在一个语言中不能出现字母表以外的符号。
现在是7页\一共有152页\编辑于星期一
7
二、符号串
1、定义符号串是字母表中的符号所组成的任何有穷序列(有时也称为符号行或字)
例如:设V={a,b,c},则符号串有
a,b,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等小写字母表示符号串。
现在是8页\一共有152页\编辑于星期一
8
2、空符号串不包含任何符号的符号串称为空符号串,记为ε。
3、符号串长度符号串中所含符号个数称为该符号串的长度,设符号串为x,则用|x|来表示x的长度。例如:x=abc,则|x|=3,显然,|ε|=0。
现在是9页\一共有152页\编辑于星期一
9
4、关于符号串的几种运算
(1)符号串的联结
设有符号串x和y,则它们的联结xy是将符号串y直接拼接在符号串x之后,即
x=x1x2x3…xm,y=y1y2y3…yn
则
xy=x1x2x3…xmy1y2y3…yn
显然εx=x,xε=x
现在是10页\一共有152页\编辑于星期一
10