编译原理基础知识---文法和语言(一)

一、文法直观概念

  我们常常把程序设计语言定义为两类:静态语义和动态语义。静态语义是一系列限定规则,并确定哪些合乎语法的程序是合适的;动态语义也称作运行语义或执行语义,表明程序要做什么,要计算什么。

  在给出文法和语言的形式定义之前,我们先直观地认识一下文法的概念。

  当我们表述一种语言时,无非是说明这种语言的句子,如果语言只含有有穷多个句子,则只需列出句子的有穷集就行,但对于含有无穷句子的语言来讲,存在着如何给出它的有穷表示的问题。事实上,使用文法作为工具,不仅是为了严格地定义句子的结构,也是为了用适当条数的规则把语言的全部句子描述出来,可以说文法是以有穷的集合刻画出无穷的集合的一个工具。

二、符号与符号串

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的自身连接记为x其中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υΣ+

  Σ+=ΣΣ*=Σ*Σ

上一篇:Note -「模板」FHQ-Treap


下一篇:宋浩概率论与数理统计笔记——第八章