一、文法直观概念
我们常常把程序设计语言定义为两类:静态语义和动态语义。静态语义是一系列限定规则,并确定哪些合乎语法的程序是合适的;动态语义也称作运行语义或执行语义,表明程序要做什么,要计算什么。
在给出文法和语言的形式定义之前,我们先直观地认识一下文法的概念。
当我们表述一种语言时,无非是说明这种语言的句子,如果语言只含有有穷多个句子,则只需列出句子的有穷集就行,但对于含有无穷句子的语言来讲,存在着如何给出它的有穷表示的问题。事实上,使用文法作为工具,不仅是为了严格地定义句子的结构,也是为了用适当条数的规则把语言的全部句子描述出来,可以说文法是以有穷的集合刻画出无穷的集合的一个工具。
二、符号与符号串
1.简单概念
字母表:字母表是元素的非空有穷集合,我们把字母表中的元素称为符号,因此,字母表也称为符号集。
符号串:由字母表中的符号组成的任何有穷序列称为符号串,例如,00,11,10是字母表∑={0,1}上的符号串。
如果某符号串x中有m个符号,则称其长度为m,表示为|x| = m,
允许空符号串,即不包含任何符号的符号串,用ε表示,其长度为0,即|ε|=0
2.关于符号串的一些运算
(1)连接运算
x与y连接,记为xy
注意:①x与y的连接和y与x的连接不相等
②(xy)z=x(yz)
③xε=x=εx
(2)求长度
|xy| = 2
|ε| = 0
|abc| = 3
(3)方幂
x的自身连接记为xn 其中n=0时,xn=ε
n>0时,xn=xn-1*x=x*xn-1
(4)f符号串集合
若集合A中的一系列元素都是某字母表上的符号串,则称A为该字符表上的符号串集合。两个符号串集合A和B的乘积定义如下:AB={xy|x€A且y€B},即AB是满足x属于A,y属于B的所有符号串xy所组成的集合。例如,若A={a,b},B={c,d},则集合AB={ac,ad,bc,bd}。因为对任意符号串x有εx = xε =x,所以有{ε}A=A{ε}=A.
指定字母表Σ之后,可用Σ*表示Σ上的所有有穷长的串的集合。例,Σ={0,1},则Σ*= {ε,0,1,00,01,10,11,000,001,010....},也可表示为字母表的方幂形式:
Σ*= Σ0υΣ1υ...Σn...,Σ*称为Σ的闭包。而Σ+=Σ1υΣ2....υΣn称为Σ的正闭包。
Σ*= Σ0υΣ+
Σ+=ΣΣ*=Σ*Σ