形式语言学_Ch2_文法

《形式语言学_Ch2_文法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、形式语言学IntroductiontoFormalLanguages第2章文法对任何语言L，有一个字母表∑，使得L∑*。L的具体组成结构是什么样的？一个给定的字符串是否为一个给定语言的句子?如果不是，它在结构的什么地方出了错？进一步地，这个错误是什么样的错？如何更正？……。这些问题对有穷语言来说，比较容易解决。这些问题对无穷语言来说，不太容易解决。语言的有穷描述。第2章文法主要内容文法的直观意义与形式定义，推导、文法产生的语言、句子、句型；乔姆斯基体系，左线性文法、右线性文法，文法的推导与归约；空语句。重点文法、推导、归约、模

2、型的等价性证明。难点形式化的概念，文法的构造。2.1启示文法的概念最早是由语言学家们在研究自然语言理解中完成形式化。归纳如下句子的描述：⑴哈尔滨是美丽的城市。⑵北京是祖国的首都。⑶集合是数学的基础。⑷形式语言是很抽象的。⑸教育走在社会发展的前面。⑹中国进入WTO。2.1启示6个句子的主体结构<名词短语><动词短语><句号><名词短语>={哈尔滨，北京，集合，形式语言，教育，中国}<动词短语>={是美丽的城市，是祖国的首都，是数学的基础，是很抽象的，走在社会发展的前面，进入WTO}<句号>={。}2.1启示<动词短语>可以是<动词

3、><形容词短语>或者<动词><名词短语>。<名词短语>={北京、哈尔滨、形式语言、中国、教育、集合、WTO、美丽的城市、祖国的首都、数学的基础、社会发展的前面}。<动词>={是、走在、进入}。<形容词短语>={很抽象的}。把<名词短语><动词短语><句号>取名为<句子>。2.1启示2.1启示表示成αβ形式<句子><名词短语><动词短语><句号><动词短语><动词><形容词短语><动词短语><动词><名词短语><动词>是2.1启示<动词>走在<动词>进入<形容词短语>很抽象的<名词短语>北京<名词短语>哈尔滨<

4、名词短语>形式语言2.1启示<名词短语>中国<名词短语>教育<名词短语>集合<名词短语>WTO<名词短语>美丽的城市<名词短语>祖国的首都<名词短语>数学的基础<名词短语>社会发展的前面<句号>。2.1启示表示一个语言，需要4种东西⑴形如<名词短语>的“符号”它们表示相应语言结构中某个位置上可以出现的一些内容。每个“符号”对应的是一个集合，在该语言的一个具体句子中，句子的这个位置上能且仅能出现相应集合中的某个元素。所以，这种“符号”代表的是一个语法范畴。⑵<句子>所有的“规则”，都是为了说明<句子>的结构而存

5、在，相当于说，定义的就是<句子>。2.1启示⑶形如北京的“符号”它们是所定义语言的合法句子中将出现的“符号”。仅仅表示自身，称为终极符号。⑷所有的“规则”都呈αβ的形式在产生语言的句子中被使用，称这些“规则”为产生式。2.2形式定义文法(grammar)G=(V，T，P，S)V——为变量(variable)的非空有穷集。A∈V，A叫做一个语法变量(syntacticVariable)，简称为变量，也可叫做非终极符号(nonterminal)。它表示一个语法范畴(syntacticCategory)。所以，有时候又称之为语法范

6、畴。2.2形式定义T——为终极符(terminal)的非空有穷集。a∈T，a叫做终极符。由于V中变量表示语法范畴，T中的字符是语言的句子中出现的字符，所以，有V∩T=Φ。S——S∈V，为文法G的开始符号(startsymbol)。2.2形式定义P——为产生式(production)的非空有穷集合。P中的元素均具有形式αβ，被称为产生式，读作：α定义为β。•其中α∈(V∪T)+，且α中至少有V中元素的一个出现。β∈(V∪T)*。•α称为产生式αβ的左部，β称为产生式αβ的右部。产生式又叫做定义式或者语法规则。2.2形式定义

7、例2-1以下四元组都是文法。⑴({A}，{0，1}，{A01，A0A1，A1A0}，A)。⑵({A}，{0，1}，{A0，A0A}，A)。⑶({A，B}，{0，1}，{A01，A0A1，A1A0，BAB，B0}，A)。⑷({A，B}，{0，1}，{A0，A1，A0A，A1A}，A)。2.2形式定义⑸({S，A，B，C，D},{a，b，c，d,#}，{SABCD，Sabc#，AaaA，ABaabbB，BCbbccC，cCcccC，CDccd#，CDd#，CD#d}，S)。⑹({S},{

8、a，b}，{S00S，S11S，S00，S11}，S)。2.2形式定义约定⑴对一组有相同左部的产生式αβ，αβ，…，αβ12n可以简单地记为：αβ

9、β

10、…

11、β12n读作：α定义为β，或者β，…，或者β。并且称它们12n为α产生式。β，β，…，β称