形式语言概述(OverviewOfFromalLanguage)

  • Updated on 8th Feb 2025

背景

形式语言作为精确描述语言的工具,广泛的应用在机器翻译等自然语言处理的领域

描述语言的常用三个方法:

  1. 穷举法,对于句子数目有限的语言可以使用这种方法将所有的句子进行枚举,从而定义。
  2. 文法,可以理解为我们在英文、中文中学习的语法,通过严格定义规则,来生成合法的句子,重点在于生成句子。
  3. 自动机,不同于文法,自动机更偏向与对于输入句子的合法性检测,从而区分哪些是语言中的句子,哪些不是。

文法与自动机二者皆有所长,一定条件下可以相互转换。

符号与符号串

字母表,符号集

字母或者符号的又穷非空集合。 例:汉语字母表为汉字、数字、标点符号。

符号串

字母表中的符号组成的任何有穷序列。 例:有符号集 image 符号串为:0,1,01,10,11,00

空字符串

image表示,长度为0

符号串的头、尾、固有头、固有尾

例:如果z=abc,则 z的头为:image,a,ab,abc z的尾为:image,c,bc,cba z的固有头:image,a,ab z的固有尾:image,c,bc

符号串连接

有符号串x,y,连接xy指y符号串写在x符号串之后 例:x=ab,y=cd,xy=abcd

符号串的方幂

有符号串x,z=xxxx....,称z为x的方幂,记为imageimage

符号串的相乘

有符号串image 例:有A={a,b} B={c,d},则AB={ac,ad,bc,bd}

闭包

字母表image上所有又穷长的字符串的集合用image 来表示,其中正闭包image不包括空集

文法和语言的形式定义

规则

也称为产生式: image 其中,image

文法

定义:G定义为四元组image image

句型

image 句子一定是句型,句型不一定是句子

语言

image记为L(G)

文法类型

image

上下文无关文法

image 重点是在规则的左部只有一个非终结字符

正规文法

image

语法树

语法树表明了推倒过程中使用了什么样的产生式和用到了哪些非终结字符,并不表明顺序。 例:有下图 image 构造aabbaa的语法树,步骤如下 image

文法的二义性

image

句型分析

识别一个符号串是否为某文法的句型是整个推导的构建过程

自上而下分析法

由非终结字符串推导至终结字符串,并查看该终结字符串是否匹配

自下而上分析法

有终结字符串进行规约,最终生成的非终结字符串,是否符合规则

回溯法

image 这时候使用回溯法进行计算

简化文法

主要是去除规则中的两种类型的规则,有害规则和多与规则

有害规则

例如: U->U这种产生式,会引起文法的二义性。 多余规则:指文法中任何句子的推倒都不会用到的规则,主要有两种:

  1. 非终结字符不在任何规则的右部出现。
  2. 非终结字符无法推出终结符号串

参考

宗成庆. 统计自然语言处理[M]. 清华大学出版社, 2008. 北京大学编译原理课程