本文共 1586 字,大约阅读时间需要 5 分钟。
文法是以有穷的集合刻画无穷的集合的一个工具。
语言:是句子组成的集合,是由一组符号所构成的集合 语法:是每个句子构成的规则 语义:是每个句子的含义
闭包的概念:
*代表任意次推导,也叫克林闭包
+代表至少一次推导,成为正闭包。
文法定义为四元组(Vn,Vt,P,S)
Vn:非终结符的集合(一般用大写字母表示)
Vt:终结符的集合(一般用小写字母表示) P:产生式的集合 S:为开始符号
推导:用产生式的右侧来替换产生式的左侧。
规约:用产生式的左侧来替换产生式的右侧。句型:从文法的开始符号经过任意次推导可以得到的符号串,称为一个句型,一个文法可以有很多个句型。
文法是用来描述语言的,这个语言是该文法一切句子的集合。
乔姆斯基把文法分成4中类型,0型、1型、2型、3型,他们的差别在于对产生式施加不同的限制。
0型文法(PSG): α∈(VN∪VT)* ,且至少含一个VN
β∈(VN∪VT)* 对产生式没有任何限制例如:A0→A0 , A1→B
0型文法说明: 0型文法也称为短语文法。 一个非常重要的理论结果是,0型文法的能力相当于图灵机(Turing)。或者说,任何0型语言都是递归可枚举的;反之,递归可枚举集必定是一个0型语言。 对0型文法产生式的形式作某些限制,以给出1,2和3型文法的定义。 (注意) 文法G 定义为四元组(VN ,VT ,P,S) ¨VN :非终结符集 ¨VT :终结符集 ¨P :产生式集合(规则集合) ¨S :开始符号(识别符号)1型文法(上下文有关文法context-sensitive):
对任一产生式α→β,都有|β|>=|α|, 仅仅 S→ε除外 产生式的形式描述:α1Aα2→α1βα2 (其中,α1、α2、β∈(VN∪VT)*,β≠ε,A∈VN) 即:A只有出现在α1α2的上下文中,才允许用β替换。 产生的语言称“上下文有关语言”但S不能出现在产生式的右部。例如:0A0→011000 1A1→101011
2型文法(CFG):对任一产生式α→β,都有α∈VN,β∈(VN∪VT)*
产生式的形式描述:A→β(A∈VN) 即β取代A时,与A所处的上下文无关。 产生的语言称“上下文无关语言” 例如:G[S]:S→01 S→0S13型文法(RG):也称正规文法
每个产生式均为 “A→aB”或“A→a” —— 右线性 “A→Ba”或“A→a” —— 左线性 其中,A、B∈VN,a∈VT* 产生的语言称“正规语言” 例如:G[S]: S→0A | 0 A→1B | B B→1 | 04个文法类的定义是逐渐增加限制的,因此每一种正规文法都是上下文无关的,每一种上下文无关文法都是上下文有关的,而每一种上下文有关文法都是0型文法。
子树:由任意节点和它的分支所构成的部分树。
简单子树:只有父子两代的子树。 句型:每棵子树的叶子组成一个句型 短语:每棵子树的叶子组成一短语 简单短语:每棵简单子树的叶子组成一个简单短语 句柄:最左边简单子树的叶子构成一个句柄。 素短语:不含其它短语的短语 最左素短语:最左边的素短语
规范:
如果每次推导都是对最左(最右)边的非终结符进行替换,则成这种推导为最左(最右)推导。最右推导称为规范推导,由规范推导所得的句型称为右句型或规范句型。
最左规约为规范规约。
就是识别一个符号串是否为某文法的句型。分为:自顶向下和自底向上。
自顶向下是从文法的开始符号触发,反复使用各种产生式,寻找“匹配”于输入符号串的推导。
问题:如何选择那一个推导式来进行推导自底向上则是从输入符号开始,逐步进行“规约”,直至规约到文法的开始符号。
问题:如何识别可规约的串
转载地址:http://ycqmi.baihongyu.com/