[ 登录注册 ]

系统运维

[编译原理]文法二

2016-08-25 20:48:05 admin 返回上一页

四、著名语言学家NoamChomsky(乔姆斯基)根据对产生式所施加的限制的不同,把文法分成四种类型,即0型、1型、2型和3型。


文法类型

产生式的限制

文法产生的语言

0型文法

αβ

其中αβ∈(VTVN) *,∣α∣≠0

0型语言

1型文法

αβ

其中αβ∈(VTVN) *,∣α∣≤∣β

1型语言,即上下文有关语言

2型文法

Aβ

其中AVNβ∈(VTVN) *

2型语言,即上下文无关语言

3型文法

A→α|αB(右线性)A→α|Bα(左线性)

其中,ABVNαVT{ε}

3型语言,即正规语言,

又分为左线性语言和右线性语言

 

0型文法:α∈(VTVN) * 且至少含有一个非终结符,而β∈(VTVN) *

                       例:A→a,Aa→a,aA→a(左边至少有一个大写字母)


1型文法:有一特例:αε也满足1型文法。

         例:A→a,A→ab,Aa→BAc(左边至少有一个大写字母,且左边的长度小于等于右边的长度)


2型文法:每一个Aβ都有A非终结符

        例:A→a,A→ab,AB→BAc(在1型文法的前提下,左边必须都是大写字母)


3型文法:如有:A→a,A→aB,B→a,B→cB,则符合3型文法的要求。

但如果推导为:A→ab,A→aB,B→a,B→cB或推导为:A→a,A→Ba,B→a,B→cB则不符合3型方法的要求了。

例子:A→ab,A→aB,B→a,B→cB中的A→ab不符合3型文法的定义,如果把后面的ab,改成aB(即“一个非终结符+一个终结符”)就对了。

例子:A→a,A→Ba,B→a,B→cB中如果把B→cB改为B→Bc的形式就对了,因为A→α|αB(右线性)和A→α|Bα(左线性)两套规则不能同时出现在一个语法中,只能完全满足其中的一个,才能算3型文法。

 

如果所有终端结点都是与终结符关联的,每棵推导树的终端结点自左至右所构成的字符串应该是文法G的一个句型,则该字符串是文法G的一个句子,此时该推导树是完全推导树


如:文法G={a,b}{S,A},S,P,其中:SaAS|a,ASbA|SS|ba,句型aabAa相对应的构造树。

 

解释:

文法G={VTVNSP},即VT={a,b}VN={S,A}

SaAS|a,即SaASSa

ASbA|SS|ba,即ASbAASSAba

                                              


五、正规文法到正规式:


 

文法产生式

正规式

规则1

AxBBy

A=xy

规则2

AxA|y

A=x*y

规则3

Ax,Ay

A=x|y



规则1:由AxBBy,可知:AxBxy


规则2:由AxA|y,可知:AxA,Ay,依次往下推AxAx2Ax3A……x*Ax*y


规则3:Ax,Ay简写成A=x|y


六、关于对计算机的意义和作用:

    对于形式语言的一个分层,正规语言是最小的集合,上下文无关语言、上下文相关语言、计算语言是那些语言的扩充集合,这些语言它们可以被不同类型的设备识别,有限状态自动机,下推自动机,线性有界自动机,图灵机等等。

文法提供了很多的优点:

(l)文法为语言给出了精确的、易于理解的语法说明。

(2)对于某些文法类,可以自动产生高效的分析器。额外的好处是,分析器的自动构造

过程可以揭示出语法的二义性和其他不属于该文法类的语法结构,这些问题在语言及其编

译器的最初设计阶段很可能没有发现。

(3)设计得漂亮的文法可以给程序定义一些语法子结构,这些结构对于把源程序翻译

成为正确的目标代码和错误诊断都是有用的。把以文法为基础的翻译描述变换成为相应程

序的工具也是存在的。

(4)语言也是逐渐完善的,需要补充新的结构并完成新增的任务。如果存在以文法为

基础的语言的实现,这些新结构的加入就更方便。

 

详细参加:http://zhidao.baidu.com/question/124218285.html(英文的)


七、小结:


    上面描述的这些文法是对一些式子做一些运算,α属于某个集合,β属于某个集合,αβ,需要满足的一些具体的条件,根据不同的条件又可以分为不同的类型,可以采用递推的方式,将这些式子接着往下推,即可得到正规文法到正规式。


文章来源:http://www.bozhiyue.com/system/2016/0825/431910.html
返回上一页    返回分类 上一篇:   下一篇:
相关