[巧用语法树求句型短语] 语法树句型短语

时间：2020-03-11 07:35:55　来源：雅意学习网本文已影响人

　　摘要：编译技术历来是令广大初学者感到头疼的一门学科，为了帮助初学者更好地理解和掌握语法树和句型短语之间的关系，本文对此做了较深入的分析，并提出了利用语法树求句型短语的新方法。
　　关键词：语法树；句型；句子；短语；简单短语；句柄
　　中图分类号：TP393 文献标识码：A
　　
　　How To Use Syntax Tree To Seek Sentence Pattern
　　Qing Tong
　　(Hunan City University, Yiyang 413000, China)
　　Abstract：Compiler technology has always been a difficult subject for beginners. In order to help beginners to understand and master the relationship between syntax tree and sentence phrases easily. This paper discusses this in detail, and offers a new method.
　　Keywords：syntax tree;sentence pattern; sentence; phrase; simple phrase; handle
　　
　　1 问题的提出
　　编译原理是大学计算机专业重要的专业基础科之一，由于这门课程涉及到的理论比较复杂，实践性强，如何学好教好编译原理这门课，一直是广大师生比较头痛的一件事。编译原理之难，难在对理论的理解和在实践中的运用，而对理论的理解是解决困难的前提。本文旨在利用语法树求句型短语的问题上做一些探讨，以帮助初学者对这一知识点的理解和掌握。
　　2 语法树、句型、短语及其关系
　　先明确几个概念：（以下*表示长度≥0的推导，+表示长度≥1的推导）
　　语法树，也称推导树，是对句型推导过程的一个静态的描述。给定文法G=（VN，VT，P，S），对于G的任一句型都能构造与之关联的一棵语法树，而与推导方式无关。一个句型的语法树具有下述几个特点：
　　（1）每个结点都用字母表V中的一个符号标记；
　　（2）根结点的标记是G的开始符S，分支结点的标记都是非终结符集VN中的符号，对于句子的推导树来说，叶子结点的标记都是终结符集VT中的符号；
　　（3）每一个分支结点都与它的孩子序列（从左至右）形成一个产生式；
　　句型，是指从文法G[S]的开始符S推导出来的符号串α，即S*α。
　　句子，如果句型α中不含有非终结符，则称串α是文法G[S]的句子。
　　短语，若串是文法G[S]的句型，且存在如下的推到关系：S*A，A∈VN，A+，则是句型相对于非终结符A的短语。
　　简单短语，若是句型相对于非终结符A的短语，且存在推到关系A，则称是句型相对于产生式A→的简单短语或者直接短语。
　　句柄，是指句型的最左简单短语。
　　可见，短语是句型的一个子串，但并不是所有的子串都是短语。
　　3 一个问题实例
　　对于给定文法G[S]及其句型α，求α的短语、简单短语和句柄，这是一个很基本也很简单的问题，通常采用的方法是逐个推导，但这种方法有点繁琐，对于初学者来说不容易理清，而利用语法树进行分析，就要显得清晰明了得多。下面就分别采用这两种方法求句型短语。
　　【例】已知表达式文法G[E]：
　　E→T | EAT
　　T→F | TBF
　　F→(E) | x
　　A→+ | -
　　B→* | /
　　求句型ω= (x+x)*x/(x-x)的所有短语、简单短语和句柄。
　　为了便于阐述，将句型中的x从左到右添加下标，则句型ω改写为(x1+x2)*x3/(x4-x5)。
　　方法一，采用推导法。
　　句型(x1+x2)*x3/(x4-x5)的最左推导如下：
　　ETBFTBFBFFBFBF(E)BFBF(EAT)BFBF
　　(TAT)BFBF(FAT)BFBF(x1AT)BFBF(x1+T)BFBF
　　(x1+F)BFBF (x1+ x2)BFBF (x1+ x2)*FBF
　　(x1+ x2)* x3BF (x1+ x2)* x3/F(x1+ x2)* x3/ (E)
　　(x1+ x2)* x3/(EAT) (x1+ x2)* x3/(TAT)
　　(x1+ x2)* x3/(FAT) (x1+ x2)* x3/( x4AT)
　　 (x1+ x2)* x3/( x4-T)
　　(x1+ x2)* x3/( x4-F)
　　 (x1+ x2)* x3/( x4- x5)
　　根据上述推导求句型短语，步骤如下：
　　⑴首先，句型ω是它自身相对于开始符E的短语；
　　⑵由E* TBF，且T* (x1+ x2)* x3，可得 (x1+ x2)* x3是句型ω相对于非终结符T的短语；
　　⑶由E* (x1+ x2)* x3BF，且B /，可得
　　子串/是句型ω相对于非终结符F的短语，也是句型相对于产生式F→x的简单短语；
　　⑷由E* (x1+ x2)* x3/F，且F* (x4- x5)，可得(x4- x5)是句型ω相对于非终结符F的短语；
　　⑸由E* FBFBF，且F* (x1+ x2)，可得(x1+ x2)是句型ω相对于非终结符F的短语；
　　⑹由E* (x1+ x2)BFBF，且B *，可得
　　子串*是句型ω相对于非终结符F的短语，也是句型相对于产生式B→*的简单短语；
　　⑺由E* (x1+ x2)*FBF，且F x3，可得
　　子串x3是句型ω相对于非终结符F的短语，也是句型相对于产生式F→x的简单短语；
　　⑻由E* (x1+ x2)* x3/ (E)，且E* x4- x5，可得x4- x5是句型ω相对于非终结符E的短语；
　　⑼由E* (x1+ x2)* x3/(FAT)，且F x4，
　　可得子串x4是句型ω相对于非终结符F的短语，也是句型相对于产生式F→x的简单短语；
　　⑽由E* (x1+ x2)* x3/( x4AT)，且A -，可得
　　子串-是句型ω相对于非终结符F的短语，也是句型相对于产生式F→x的简单短语；
　　⑾由E* (x1AT)BFBF，且A +，可得
　　子串+是句型ω相对于非终结符A的短语，也是句型相对于产生式A→+的简单短语；
　　⑿由E* (x1+ x2)* x3/( x4-F)，且F x5，可得
　　子串x5是句型ω相对于非终结符F的短语，也是句型相对于产生式F→x的简单短语；
　　⒀由E* (E)BFBF，且E* x1+ x2，可得x1+ x2是句型ω相对于非终结符E的短语；
　　⒁由E* (FAT)BFBF，且F x1，可得
　　子串x1是句型ω相对于非终结符F的短语，也是句型相对于产生式F→x的简单短语；
　　⒂由E* (x1+F)BFBF，且Fx2，可得
　　子串x2是句型ω相对于非终结符F的短语，也是句型相对于产生式F→x的简单短语；
　　所以，句型(x1+ x2)* x3/( x4- x5)的短语有x1，+ ，x2，* ，x3，/ ，x4 ，-，x5，x1+ x2，(x1+ x2)，(x1+ x2)* x3，x4- x5，( x4- x5)，(x1+ x2)* x3/( x4- x5)
　　简单短语有x1，+ ，x2，* ，x3，/ ，x4 ，-，x5
　　句柄是x1
　　方法二，利用语法树求解。
　　先画出句型(x1+ x2)* x3/( x4- x5)的语法树。
　　
　　根据语法树及短语的定义，不难发现，语法树中每个分支结点P与以该分支结点为根的子树的叶子序列α（从左至右排列）存在着这样的关系，即序列α是句型相对于非终结符P的短语。这样，只要找出语法树的所有子树，就可以找出句型的所有短语了。方法也很简单，只要逐层消除语法树的结点和边，就可以找出对应的短语了。
　　
　　
　　方法一中的步骤1――15是一一对应的，很显然，利用语法树求句型短语比推导法思路更清晰，过程更简单，更有利于初学者对该知识点的理解和掌握。
　　值得注意的是，利用语法树求句型短语时，要避免短语重复计数，如上述图9中x4既是句型(x1+ x2)* x3/( x4- x5)相对于非终结符E的短语，也是句型相对于非终结符T和F的短语，但短语数目只能记一次，而不是三个，相同情况的还有图12、图14和图15。
　　4 结束语
　　编译技术之难学，首先在于对知识的理解，只有理解透彻了，才谈得上实践应用。语法树是句型分析过程的描述，而短语是句型中的特殊子串，二者存在紧密的关系，理解了二者之间的关系，就可以使问题简化，从而加深对知识的理解和掌握。
　　
　　参考文献
　　[1] Chrles N. Fischer, Richard J. LeBlanc, Jr. Crafting A Compiler. The Benjamin/Cummings Publishing, 1988.
　　[2] Slfred V. Aho, Ravi Sethi, Jeffrey D. Vllman. Compilers Principles,Techniques,and Tools. AddisonWesley, 1985.
　　[3] 陈火旺，钱家骅，孙永强. 程序设计语言编译原理. 国防工业出版社，1983.
　　[4] 陈火旺，刘春林，谭庆平，赵克佳，刘越. 程序设计语言编译原理（第3版）. 国防工业出版社，2006.
　　[5] 张素琴，吕映芝，蒋维杜，戴桂兰. 编译原理（第2版）. 清华大学出版社，2005.
　　[6] 格林著，冯博琴译. 现代编译程序设计. 人民邮电出版社，2003.
　　[7] 陈意云. 编译原理. 高等教育出版社，2003.
　　[8] Kenneth C.Louden，冯博琴译. 编译原理及实践. 机械工业出版社，2004 .
　　
　　本人联系方式：
　　姓名：卿桐
　　通信地址：湖南.益阳.湖南城市学院.惠泽园.1-602.省略
　　Tel：13786781567

[巧用语法树求句型短语] 语法树句型短语

最新文章

热门文章