巧用语法树求句型短语.pdf

ISSN 1009-3044 E-mail: eduf@ 第7 卷第35 期 (2011 年12月) Computer Knowledge and Technology 电脑知识与技术 Computer Knowledge and Technology 电脑知识与技术 Vol.7, No.35, December 2011. Tel:+86-551-5690963 5690964 巧用语法树求句型短语 卿 桐 （湖南城市学院，湖南益阳413000 ） 摘要：编译技术历来是令广大初学者感到头疼的一门学科，为了帮助初学者更好地理解和掌握语法树和句型短语之间的关系，该文 对此做了较深入的分析，并提出了利用语法树求句型短语的新方法。 关键词：语法树；句型；句子；短语；简单短语；句柄 中图分类号：TP393 文献标识码：A 文章编号：1009-3044(2011)35-9219-03 How To Use Syntax Tree To Seek Sentence Pattern QINGTong (HunanCityUniversity,Yiyang413000,China) Abstract ：Compilertechnologyhasalwaysbeenadifficultsubjectforbeginners.Inordertohelpbeginnerstounderstandandmasterthere⁃ lationshipbetweensyntaxtreeandsentencephraseseasily.Thispaperdiscussesthisindetail,andoffersanewmethod. Keywords ：syntaxtree;sentencepattern;sentence;phrase;simplephrase;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]的句子。 短语，若串abg 是文法G[S]的句型，且存在如下的推到关系：S ⇒*aAg ，A ∈VN ，A ⇒+b ，则b 是句型abg 相对于非终结符A 的短语。 简单短语，若b 是句型abg 相对于非终结符A 的短语，且存在推到关系A ⇒b ，则称b 是句型abg 相对于产生式A→b 的简单短语 或者直接短语。 句柄，是指句型的最左简单短语。 可见，短语是句型的一个子串，但并不是所有的子串都是短语。 3 一个问题实例 对于给定文法G[S]及其句型α，求α的短语、简单短语和句柄，这是一个很基本也很简单的问题，通常采用的方法是逐个推导，但 这种方法有点繁琐，对于初学者来说不容易理清，而利用语法树进行分析，就要显得清晰明了得多。下面就分别采用这两种方法求 句型短语。 【例】已知表达式文法G[E] ： E→T | EAT