形式语法概述
背景
形式语言作为精确描述语言的工具，广泛的应用在机器翻译等自然语言处理的领域
描述语言的常用三个方法：
- 穷举法，对于句子数目有限的语言可以使用这种方法将所有的句子进行枚举，从而定义。
- 文法，可以理解为我们在英文、中文中学习的语法，通过严格定义规则，来生成合法的句子，重点在于生成句子。
- 自动机，不同于文法，自动机更偏向与对于输入句子的合法性检测，从而区分哪些是语言中的句子，哪些不是。
文法与自动机二者皆有所长，一定条件下可以相互转换。
符号与符号串
字母表，符号集
字母或者符号的又穷非空集合。
例：汉语字母表为汉字、数字、标点符号。
符号串
字母表中的符号组成的任何有穷序列。
例：有符号集
符号串为：0，1，01，10，11，00
空字符串
表示，长度为0
符号串的头、尾、固有头、固有尾
例：如果z=abc，则
z的头为：，a，ab，abc
z的尾为：，c，bc，cba
z的固有头：，a，ab
z的固有尾：，c，bc
符号串连接
有符号串x，y，连接xy指y符号串写在x符号串之后
例：x=ab，y=cd，xy=abcd
符号串的方幂
有符号串x，z=xxxx….，称z为x的方幂，记为
且
符号串的相乘
有符号串
例：有A={a,b} B={c,d},则AB={ac,ad,bc,bd}
闭包
字母表
上所有又穷长的字符串的集合用
来表示，其中正闭包
不包括空集
文法和语言的形式定义
规则
也称为产生式：
其中，
文法
定义：G定义为四元组
句型
句子一定是句型，句型不一定是句子
语言
记为L(G)
文法类型
上下文无关文法
重点是在规则的左部只有一个非终结字符
正规文法
语法树
语法树表明了推倒过程中使用了什么样的产生式和用到了哪些非终结字符，并不表明顺序。
例：有下图
构造aabbaa的语法树，步骤如下
文法的二义性
句型分析
识别一个符号串是否为某文法的句型是整个推导的构建过程
自上而下分析法
由非终结字符串推导至终结字符串，并查看该终结字符串是否匹配
自下而上分析法
有终结字符串进行规约，最终生成的非终结字符串，是否符合规则
回溯法
这时候使用回溯法进行计算
简化文法
主要是去除规则中的两种类型的规则，有害规则和多与规则
有害规则
例如：
U->U这种产生式，会引起文法的二义性。
多余规则：指文法中任何句子的推倒都不会用到的规则，主要有两种：
- 非终结字符不在任何规则的右部出现。
- 非终结字符无法推出终结符号串
参考
宗成庆. 统计自然语言处理[M]. 清华大学出版社, 2008.
北京大学编译原理课程
版权声明:本文由littleji.com创作并发表,转载请注明作者及出处,欢迎关注公众号:littleji_com
本文遵守CC BY0SA 4.0
if you have any questions, please leave a message behind or give an issue
本文链接为：https://blog.littleji.com/2018/10/16/20181016FormalLanguageGenerality/