应用研究
编译技术中文法的实用限制研究
卿桐
(湖南城市学院湖南益阳413000)
数事费与应用
摘要：程序设计语言的文法中含有多余规则和有害规则时是错误的，国此检查文法是否含有达两类规则是十分必要的。本文对此微了较为深入的分析，并提出了利用有向图求多余规则的新方法。
关键词：文法有害规则多余规则有向图
中图分类号：TP393 1、问题的提出
文献标识码：A
文章编号：1007-9416(2012)11-0078-01
p
编译技术是计算机领域的核心技术之一。在编译技术中引进了文法，是为了更好地描述和提高程序设计语言的质量在实际应用中，常常需要对文法做出一些限制，以便更准确地描述程序设计语言。我们限制在文法中不得含有有害规则和多余规则，因此很有必
要检查文法中是否含有有害规则和多余规则。 2、关于文法
文法是描述语言的工具，它由一组形如α一→β的规则构成，其中 α和β称为规则的左部和右部，且α不能为空且至少包含一个非终结符。按照对规则的限制不同，姆斯基把文法分成四种类型，即短语文法，上下文有关文法、上下文无关文法和正规文法。对于程序设计语言中单词的描述，正规文法已经足够。本文的论述也只限于正规文法。
3、有害规则
先阐述一下文法的二义性概念。如果一个文法中存在某个句子，它有着两个或两个以上不同的最左推导或者最右推导，我们说这样的文法是二义性的。二义性文法所描述的程序设计语言其语句的含义不具有确定性，因此，我们应尽可能消除文法的二义性。
所谓有害规则，是指形如D一D的规则。为什么说这种规则是有害的呢?我们先看一个实例。
[例1]已知正规文法G[N]:N→N
N→0N1 N→01
对于句子0011做如下的最左推导：推导—:N==>0N1==>0011
推导二,N==>N==>0N1==>(011
显然，规则N一N的存在使得句子具有了两个不同的最左推导，面且,对任意长度大于等于1的推导N==>==>α，都有N==> N==>α成立。可见，规则N-N的存在只会引起文法的二义性，
因而是有害的。 4、多余规则
所谓多余规则，是指文法中那些在任何一个句子的推导中都不会用到规则。多余规则文可以分为两种情况，一种是指文法中的某些非终结符不出现在任何规则的右部，以至于含有该非终结符的规则在任何推导中都不可能用到，我们称这种非终结符是不可到达的。另一种是从文法的某个非终结符出发不能够推导出终结符串来，我们把这种非终结符称为不可终止的，含有这两种非终结符的规则都是多余的。
对于多余规则，我们通常采用推导的方式加以识别。[例2]已知正规文法G[S]：
A→aA I bB I cC B→bD I eB
S→aA Ibc
C→aC I bD I eF F→aBbEb
D→dD bB P→xD bQ
采用推导法求多余规则，步骤如下：
第一步，求出文法中不可终止的非终结符
E→aEeDe Q→cP I dF I d
S==>aA==>abB==>abbD==>abbbB,不可继续,S==>
aA==>acC==>acbD,不可继续 bbD==>bbbB，不可继续；
由上述推导可知，非终结符B和D是不可终止的，则文法中所有含有非终结符B或D的规则都是多余的。
第二步，求出文法中不可到达的非终结符
由S==>aA==>abB==>abbD,可知非终结符A、B,D是可到达的；
由S==>bC==>beF==>bebE，可知非终结符C、E,F是可到达的。
由上述推导可知，非终结符P、Q是不可到达的，则文法中所有含有非终结符P或Q的规则都是多余的
显然，上述推导法采用的是回溯式求解，繁项面且容易出现错漏。下面介绍一种新的方法一一有向图法。
构造有向图；用方形结点表示非终结符，如果某个规则的右部只含有终结符或者。，则用圆形结点表示该终结符或者。以开始符结点为起点，如果存在规则A→αB,则产生有向边；若有
规则A→β,其中β为终结符或者ε，则产生有向边。
如图1所示，搜索多余规则，从结点S出A 发，沿着有向边搜索，所有不能到达的方形结点，其所对应的非终结符都是不可到达的(结点P.Q)；以每一个方形
结点为起点，若不能找到至少一条通向任意圆形结点的路径，则该方形结点对应的非终结符是不可终止的(结点B,D)。含有这两类非终结符的规则都是多余的。去掉多余规则后文法G[S]变为：
S→aA LbC
A→aA I cC
C→aCeF
E→aE|e
F→bE1b
显然，结合有向图搜索文法的多余规则比起推导法要简便有效
得多，尤其是对于规则较多的复杂文法，效率更高。 5、结语
自从乔姆斯基建立起形式语言的描述以来，形式语言理论得到了迅速的发展，对程序设计语言的设计、编译方法以及计算复杂性方法等方面产生了极为深刻的影响。语言文法，作为程序设计语言的描述工具，其规则的严密性决定了程序设计语言的质量，迅速而准确地搜索并清除文法中的多余规则和有害规则，对程序设计语言
有着十分重要的意义。参考文献
[1 JChrles N.Fischer, Richard J. LeBlanC, Jr. Crafting A Compiler. The Ben,jamin/Cummings Pub lishing.1 98B
[2］陈火旺，刘春林，潭庆平.赵克佳，刘越.程序设计语盲缩译累理（第3版)国防工业出版社，2006
[3]Kenneth C.Louden,冯博琴译.编译累理及实践.机械工业出版社， 2004-