首页 > 代码库 > 文法、语言、正则表达式

文法、语言、正则表达式

文法的形式定义于分类

一个上下文无关文法有四个元素组成:

  • 一个终结符号集合,也称为词法单元。
  • 一个非终结符号集合,也称为语法变量。
  • 一个产生式集合。
  • 一个开始符号。

文法G可以抽象成四元组的形式:G=(VN,VT,P,S)

其中VN表示非终结符集,VT表示终结符集,P表示产生式集,S表示开始符号。

文法G描述的语言用L(G)表示L(G)={w|w∈VT*且S=+>w}

  • 符号串w从开始符号推导出来
  • w仅由终结符号组成
  • w称为该语言的句子
  • L(G)由所有这样的句子构成

约定:

  • 大写字母A~Z表示非终结符,或用尖括号把非终结符括起来。
  • 前面的小写符号a、b、c表示单个终结符号。
  • 后面的小写字母u、v、w、x、y、z以及α、β、γ等符号表示(VT∪VN)上的符号串。

文法的分类:

  1. 0型文法:无限制文法、短语文法,α->β,α中至少含一个非终结符。
  2. 1型文法:上下文有关文法,α->β满足|α|<=|β|,对于产生式α12->α1βα2,用β替换A时,只能在上下文为α1和α2时才能进行。
  3. 2型文法:上下文无关文法,A->β,其中A为单个非终结符,当用β替换A时,与A的上下文环境无关。
  4. 3型文法:正则文法,每个产生式形为A->aB或A->a。

分别被四种自动机识别:

  1. 图灵机
  2. 线性界线自动机
  3. 下推自动机
  4. 有穷自动机

串和语言和语言上的运算

字母表是一个有限的符号集合。

某个字母表上的串是该字母表中符号的一个有穷序列。

语言是某个给定字母表上任意的可数的串集合。

串的基本术语有:前缀prefix、后缀suffix、子串substring、真前缀真后缀真子串、子序列subsequence。

定义两个串的乘积为两个串的连接。

定义指数运算:s0=ε,并且对于i>0,si为si-1s。因为εs=s,由此可知s1=s,s2=ss,以此类推。

语言上最重要的运算有:并、连接和闭包、正闭包。

例:令L表示字母的集合{A,B,...,Z,a,b,...,z},令D表示数位的集合{0,1,...,9}。将L和D看做语言,它们所有串的长度都为1。

根据运算符从L和D中构造新语言:L∪D、LD、L4、L*、L(L∪D)*、D+

正则表达式

正则表达式可以由较小的正则表达式按照如下规则递归的构建。每个正则表达式r表示一个语言L(r),这个语言也是根据r的字表达式所表示的语言递归的定义的。

归纳基础

  1. ε是一个正则表达式,L(ε)={ε}。
  2. 如果a是Σ上的一个符号,那么a是一个正则表达式,L(a)={a}。

归纳步骤

假定r和s都是正则表达式,分别表示语言L(r)和L(s),那么:

  1. (r)|(s)是一个正则表达式语言,表示语言L(r)∪L(s)。
  2. (r)(s)是一个正则表达式语言,表示语言L(r)L(s)。
  3. (r)*是一个正则表达式语言,表示语言(L(r))*。
  4. (r)是一个正则表达式语言,表示语言L(r)。

进行如下约定丢掉括号:

  1. 一元运算符*具有最高的优先级,并且是左结合的。
  2. 连接具有次高的优先级,它是左结合的。
  3. |的优先级最低,也是左结合的。

可以用一个正则表达式定义的语言叫做正则集合。如果两个正则表达式r和s表示同样的语言,则称r和s等价,记做r=s。

一些对任意正则表达式r、s、t都成立的代数定律:

  • r|s=s|r,|交换律
  • r|(s|t)=(r|s)|t,|结合律
  • r(st)=(rs)t,连接结合律
  • r(s|t)=rs|rt;(s|t)r=sr|tr,连接分配率
  • εr=rε=r,ε是连接的单位元
  • r*=(r|ε)*,闭包中一定包含ε
  • r**=r*,*具有幂等性

 如果∑是基本符号的集合,那么一个正则定义是具有如下形式的定义序列:di=ri(1<=i<=n)

  • 每个di都是一个新符号,它们都不在∑中,并且各不相同。
  • 每个ri是字母表∑∪{d1,...,di-1}上的正则表达式。避免递归定义问题。

 

文法、语言、正则表达式