计算机科学与技术专业学位论文-一种自适应的Prolog编译器

1、密级： 保密期限： 硕士研究生学位论文 题目: 一种自适应的Prolog编译器 学 号： 106894 姓 名： 高慧 专 业： 计算机科学与技术 导 师： 刘知青 学 院： 软件学院 2012年 12月 31日独创性（或创新性）声明本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得北京邮电大学或其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。申请学位论文与资料若有不实之处，本人承担一切相

2、关责任。本人签名： 日期： 关于论文使用授权的说明学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定，即：研究生在校攻读学位期间论文工作的知识产权单位属北京邮电大学。学校有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许学位论文被查阅和借阅；学校可以公布学位论文的全部或部分内容，可以允许采用影印、缩印或其它复制手段保存、汇编学位论文。（保密的学位论文在解密后遵守此规定）保密论文注释：本学位论文属于保密在 年解密后适用本授权书。非保密论文注释：本学位论文不属于保密范围，适用本授权书。本人签名： 日期： 导师签名： 日期： 北京邮电大学硕士学位论文 2013一种自适应的Prolo

3、g编译器摘 要Prolog程序语言是一种建立在逻辑学理论基础之上的语言，最初Prolog程序语言被应用在自然语言等研究领域。现在它可以用来建造专家系统、智能知识库、自然语言理解等广泛的人工智能的研究中，同时它也可以帮助到一些常用应用程序的编写。这是因为Prolog的编程方法更像是使用逻辑语言来描述程序，它能够比其他语言更快速地开发程序。随着人工智能的兴起，越来越多的人开始探索各种人工智能技术。其中Prolog程序语言作为较早的代表，更是受人追捧。传统的Prolog编译器只能按照程序的书写顺序从上到下匹配，如果写在上面的谓词十分难解，而非常好解的谓词却写在了下面，那么Prolog解这个程序就需要

4、一些时间。这也就是传统Prolog编译器的短板。如果在Prolog编译器中加入Prolog匹配的“指导思想”告诉Prolog编译器应该选哪个谓词，进而Prolog在寻找答案的时候就不会仅凭程序员的个人习惯和概率来左右其得到答案的效率了。本文主要研究工作如下：首先本文大致讨论人工智能和专家系统的定义和Prolog语言的组成特点。其次讲述Prolog编译器的开发方法。本文采用Flex词法分析器用于Prolog的词法开发，用正则表达式识别需要传递给语法分析器的记号。采用Bison用于其语法开发并在Bison中使用自顶向下的LL(1)文法。使用哈希这种数据结构来组织符号表，并用拉链法来处理符号表中遇到

5、的冲突。由于本文要用到Flex和Bison的结合使用，而且是要识别一整个程序，所以词法分析器Flex和语法分析器Bison结合的特殊性也在研究范围之内。最后针对Prolog匹配出现的一些缺点，提出了利用UCB策略改进其匹配方式，试图使其高效率得出最优解。关键词：Prolog 编译器 程序语言 UCB 自适应A SELF-ADAPTED PROLOG COMPILERABSTRACTProlog programming language is to establish the theoretical basis of the logic of language, the initial Prol

6、og programming language is used in the field of natural language research. Now it can be used to build a wide range of expert systems, intelligent knowledge base, natural language understanding, artificial intelligence research, at the same time, it can also help to some commonly used application pr

7、eparation. This is because the Prolog programming method is more like using a logical language to describe the program and its ability to develop programs more quickly than in other languages.With the development of artificial intelligence, more and more people begin to explore different artificial

8、intelligence techniques. Prolog programming language as one of early AI languages is chased by people. The traditional Prolog compilers just can match predicate from top to bottom. If the top one is so difficult to solve, but the easy one is beneath, it will cost more time to find an answer. And thi

9、s is disadvantage of traditional Prolog compilers. If a guide in a Prolog compiler can tell which predicate should be chosen, then this compiler will get an answer efficiently but not depend on programmer personal habits and probability. The main task of this paper is:First we argue basically the de

10、finition of artificial intelligence and Expert System. We also argue the characteristic of Prolog. Then how to develop a Prolog compiler is talked. We are going to use Flex to explore lexical analysis, regex is used to pass TOKEN which is needed to recognize to Bison. We are going to use Bison to ex

11、plore syntax analysis, and LL(1) which is belong to top-down analysis is used in Bison. We use Hash to explore symbol table, and zipper law is used to deal with conflict when it happened. As Flex and Bison have to be used together, particularity of Flex and Bison is also discussed in this paper.At l

12、ast as disadvantage of traditional Prolog compilers, UCB strategy is in to improve the way of match in order to trying to make it on high efficiency optimal solution.KEYWORDS: prolog compiler programming language UCB self-adapted IV目 录第一章绪论11.1研究背景11.2课题的研究内容21.3课题的意义21.3.1人工智能的概念及研究意义21.3.2专家系统的概念及

13、研究意义21.3.3Prolog程序语言的重要性31.4论文主要工作3第二章Prolog理论基础4第三章词法分析的实现63.1正则表达式83.2有限自动机93.3Flex93.4用Flex实现Prolog的词法分析113.5小结13第四章语法分析的实现144.1上下文无关文法144.2句型分析184.3Bison234.4用Bison实现Prolog的语法分析244.5词法分析器Flex和语法分析器Bison的结合274.6二义性冲突274.7小结30第五章语义分析的实现315.1语义分析315.1.1静态语义检查315.1.2属性文法325.2符号表335.2.1符号的主要属性及作用345.

14、2.2符号表的总体组织395.2.3符号表项的排列395.3符号表的实现425.4小结43第六章Prolog知识库的搜索引擎的实现446.1Prolog基本运算方法446.1.1深度优先算法446.1.2合一446.1.3回溯446.2存储组织和匹配算法456.2.1栈式动态存储分配456.2.2简单的栈式存储分配的实现466.3小结51第七章Prolog编译器的改进527.1UCB527.1.1马尔科夫决策过程527.1.2蒙特卡罗537.1.3蒙特卡罗规划547.1.4多臂匪徒模型557.2小结57第八章总结和展望58参考文献60致 谢62攻读学位期间发表的学术论文63 59 第1章 绪论

15、1.1 研究背景比尔盖茨曾经预言未来家家都有机器人，未来人工智能将会飞速的发展。人工智能是一个含义很广的词语，具有不同学科背景的人工智能学者在其发展过程中对它有着不同的理解并提出了一些不同的观点。从能力的角度看，相对于人类自有的自然智能，人工智能是指在机器上用人工的方法实现的智能；从学科的角度看，作为一个学科的名称来定义人工智能。所谓人工智能是一门研究如何构造智能机器或智能系统，使它能够模拟、延伸和扩展人类智能的学科1。关于人工智能研究的目标，到目前为止还没有一个统一的看法。1978年索罗门(A. Sloman)对人工智能给出了三个主要目标：1)对智能行为进行有效解释的理论分析；2)解释人类自

16、有智能；3)构造智能的人工产品。经过几十年的发展，人工智能有了不小的进步，现在人工智能已经从单一的方向扩展到定理证明、专家系统、机器学习、自然语言理解、智能检索、自动程序设计、机器人学、模式识别、组合调度问题、机器视觉各个方向。目前能够研究人工智能的技术平台就是计算机，用计算机来模拟人的某些行为和思维过程。在60年代出现了Prolog程序语言，它是建立在逻辑学理论基础之上，最初Prolog程序语言被应用在自然语言等研究领域。现在它可以用来建造专家系统、智能知识库、自然语言理解等广泛的人工智能的研究中，同时它也可以帮助到一些常用应用程序的编写。这是因为Prolog的编程方法更像是使用逻辑语言来描

17、述程序，它能够比其他语言更快速地开发程序。现阶段的Prolog使用深度优先搜索的策略。它从给它提出的问题即“当前目标”开始，在搜索过程中系统保存着这个当前目标，并且“从左至右”的完成目标。系统总是首先完成第一个子目标，如果第一个子目标完成不了，整个问题就没有答案，而第二个子目标根本不会去尝试。当解决一个特定的子目标时，对事实和规则的试探总是自顶向下的。简单的说：Prolog总是从上到下从左到右以深度优先为主工作的。在Prolog的规则中也有析取和合取的问题（合取关系用“，”表示，析取关系用“；”表示），现阶段的Prolog运算时间和人工输入有很大关系，假设一个合取关系中有为假的合取项，而且它是

18、规则体的第一子目标，那么计算它耗费时间就相对要少。若要是这一个为假的合取项不是规则体的第一个子目标，而且规则体第一个子目标很难解，这就使整个程序要花费一段时间才能得到答案。也就是说现在Prolog的一个大问题是深度优先搜索的效率问题。1.2 课题的研究内容本课题立足于Prolog编译器的开发，在人工智能的大背景下，着重详细论述了一个可扩展的Prolog编译器的实现，其中包括了词法分析、语法分析、语义分析，以及Prolog知识库的搜索引擎的实现，包括深度优先搜索算法、合一算法、匹配算法等关键模块。论文也讨论了改进Prolog知识库的搜索方法。其中词法分析和语法分析使用Flex和Bison工具开发

19、，在匹配问题中使用的是树的匹配，搜索方法由原来的深度优先改进为最优优先搜索。1.3 课题的意义1.3.1 人工智能的概念及研究意义所谓的“人工智能”是指人们通过计算机模拟或实现的智能2。很遗憾因为人工智能还在被人们探索和研究所以到现在为止人工智能还没有像其他成熟学科一样形成一套比较完整的理论体系，经过发展现在有一些技术已经开始应用人工智能，比如推理技术、搜索技术、联想技术等。人工智能语言是一类适应于人工智能和知识工程领域的、具有符号处理和逻辑推理能力的计算机程序设计语言3。能够用它来编写程序求解非数值计算、知识处理、推理、规划、决策等具有智能的各种复杂问题。在未来人工智能领域会改变人们的生活方

20、式，许多大的企业，如谷歌、微软和苹果都在努力探索人工智能领域。1.3.2 专家系统的概念及研究意义专家系统（Expert System）是一种用计算机程序来模拟人类专家解决某些特定领域问题的系统4。因为某个领域大量的专家水平的知识与经验被记录到专家系统内部，所以系统能够通过运用人类专家的专业知识和解决专业问题的方法，模拟人类专家判断推理和决策过程，来解决该领域的复杂问题。自从1965年在美国斯坦福大学第一个专家系统问世以来，专家系统在人工智能应用研究中表现的最广泛和最活跃。现如今存在着许多种不同的专家系统，这些专家系统已影响着各个专业领域并且获得很大的成功。专家系统按任务分类可分为：诊断型、解

21、释型、调试型、教育型、预测型、规划型、控制型、设计型、监测型。1.3.3 Prolog程序语言的重要性Prolog语言属于一种人工智能语言，21世纪注定是属于人工智能的时代。在经过了几十年的发展，虽然Prolog语言已经在例如机器定理证明和专家系统等方面体现了重要的作用，但是几乎主流的Prolog编译器除了界面和编写语言不同之外，没有什么实质性的创新，它们都是随机的选取合一的谓词进行深度优先的计算，有时由于随机出的谓词很难得到结果而影响到编译器的效率。本文提出的方法是更改Prolog编译器的搜索引擎，使其由原来的深度优先变成最有优先算法，进而提高其计算效率。1.4 论文主要工作本文从开发传统P

22、rolog编译器开始，包括从词法分析器的组织到最后匹配算法。本文的组织结构如下：第一章 绪论。对论文研究背景对论文的主要研究工作做以概述，并阐明整篇文章的组织结构。第二章 理论基础。阐述Prolog语言的组成部分，为下文做铺垫。第三章 词法分析的实现。首先介绍什么是词法分析，词法分析的原理及程序中哪些记号需要被分析出来，然后用Flex词法编辑器来实现Prolog编译器的词法分析部分。第四章 语法分析的实现。首先介绍了语法分析在整个编译过程中的位置，然后介绍本文要用到的文法规则，最后用Bison语法分析器来实现Prolog编译器的语法分析部分。第五章 语义分析的实现。首先说明了语义分析需要检查的

23、定义，然后介绍了符号表的作用及组织方法，最后论述了符号表的实现。第六章 Prolog知识库的搜索引擎的实现。首先论述Prolog基本运算方法包括深度优先搜索算法、合一算法、匹配算法等关键模块，然后存储组织和匹配算法在最后论述。第七章 Prolog编译器的改进。通过马尔科夫决策、蒙特卡罗法、蒙特卡罗规划和多臂匪徒模型引出了UCB决策策略，UCB算法是自适应Prolog编译器的核心部分，有了它才可以使Prolog编译器知道应该选择匹配哪个谓词。第八章 总结与展望。对论文工作进行总结，并对下一步工作方向做出展望。第2章 Prolog理论基础Prolog的基本语句有：事实、规则、目标这三种类型语句5。

24、它们都用一种叫做“谓词”的形式表示，所谓谓词就是由一个谓词名和一些参数组成。因为谓词清楚简单，语句类型少，因而文法简捷，程序逻辑性强，清晰易懂。Prolog是陈述性语言，只要必要的事实和规则提交，它不需要在程序中列出详细的求解步骤就能使用内部的演绎推理机制自动求解程序给定的目标。Prolog程序语言的基本语句说明如表2-1所示语句组成方式例子说明事实事实是一种用来说明问题中已知的对象和它们之间关系的谓词，在Prolog程序中，事实由谓词名及用小括号括起来的一个或几个对象组成例如eat(alex，apple).表示是一个名为eat的关系，表示alex吃苹果这个事实。规则规则是由几个谓词或者说简单

25、句组成并且他们之间有依赖性存在，事实与事实间的类似于依赖的关系被规则所描述。规则的组成很简单，它一般由两部分组成：左边是规则头，表示结论，而右边是规则体，表示条件的前提。例如bird(X):-animal(X),has(X,feather).表示凡是有羽毛的动物就是鸟。目标目标即是询问，一旦事实和规则被写进Prolog程序中之后，Prolog就准备好被询问有关问题了，这个时候程序的运行目标就是用户询问的问题。目标分内、外两种，外部目标需要在程序运行时手工键入，内部目标需要写在程序中。目标的结构与事实或规则一样，它可以是多个谓词的组合，或者是一个简单的谓词。例如?-student(alex).表

26、示“alex是学生吗？”Prolog可以在知道一些已知的事实的前提下通过逻辑推理得出一些未直接给出的事实。一个Prolog程序在典型情况下并不是一个动作序列，它是通过聚合在一起的事实和规则，由规则从那些事实中得出结论。表2-1 Prolog程序语言基本组成Prolog的基本组成理论是研究开发Prolog编译器的基础，只有了解其组成才能根据其特点来开发适合的编译器。第3章 词法分析的实现词法分析是编译工作的第一个阶段。词法分析器的主要任务是从左到右将读入源程序的输入字符组成词素。所谓词素是源程序中的一个字符序列，它和某个词法单元的模式匹配，并被词法分析器识别为该词法单元的一个实例6。在组成词素后

27、，词法分析器生成并输出一个词法单元序列即TOKEN，每个词法单元对应于一个词素。然后语法分析器对这个词法单元序列进行语法分析。词法分析阶段将读入源程序的输入字符组成词素。词素类似于自然语言的单词，单词可以分为名词、动词和形容词等不同类型，词素也可以用一些规则进行划分，我们把划分词素的规则称为模式。模式和词素组成了词法单元。词法单元有一个词法单元名。词素、模式和词法单元之间的关系可以如表3-1所示词法单元模式的非正式描述词素举例number任何数值常数3.14159，10relation，=或或=string在两个”之间，除”之外的任何字符“Hello World”separator(，)，,(

28、或)或,date方括号内的字符序列2008-01-01 15:30:00表3-1词素、模式和词法单元的关系词法分析器除了识别词法单元之外，还要完成其他的一些任务，比如：进行词法检查发现错误要报告所发现的错误；为了后续语法分析发现错误之后能给出正确的位置，词法分析器需要提交词法单元的位置；识别字符复合而成的算符和边界符，并把它们合并成完整的单词符号；略去没用过的空白字符等。根据词法分析器与语法分析器协同的方式不同，词法分析器在整个词法分析阶段有不同的工作方式：1) 词语法分析器并行工作，词法分析器将记号提交到一个队列中供语法分析器调用。其工作方式如图3-1所示：图3-1并行工作方式2) 词法分析

29、器单独工作，这种方式就是词法分析器单独进行一遍扫描，这期间语法分析器不会工作，词法分析器识别出各个单词并转换成语法分析器需要的记号，然后将记号作为语法分析器的输入供语法分析器调用，它的工作方式如图3-2所示： 图3-2词法分析器独立工作3) 这种方式中词法分析器是语法分析器的子程序，词法分析器先分析出一个记号，然后记录断点，并把记号提供给语法分析器调用，当语法分析器分析完当前的记号之后，它就会给词法分析器一个信号，使词法分析器从断点处继续分析记号然后供语法分析器调用。这中工作方式如图3-3：图3-3 作为子程序的词法分析器的工作方式正规式和有限自动机是描述词法规则的有效工具。3.1 正则表达式

30、我们用叫做“模式”的规则来描述字符串集合。这里用正则表达式来表示规则。正则式是一种十分有效的工具，尤其是描述词素的组成结构。正则表达式通过使用元语言(metalanguage)来表达编程人员想要匹配的模式。它一般使用标准的文本字符，其中一部分代表模式而另外一部分则代表他们自身。在正则表达式中有特殊意义的字符为： 如果它是正则表达式的第一个字符就匹配行首。它也被用于方括号中表示补集。 字符类(character class)，可以匹配方括号中的任意一个字符。如果字符类中的第一个字符是抑扬符号()，则改变为匹配除方括号内字符以外的任何字符。字符类里的破折号表示字符的范围，例如，0-9意味着1234

31、56789而a-z则表示任意小写字母。$ 如果它是正则表达式的最后一个字符就匹配行尾。 当花括号中带有一个或者两个数字时，它表示前一个模式可以匹配的最小和最大次数。例如，A1,3匹配一到三个字母A，而05匹配00000.当花括号中带有名字时，它指向以这个名字命名的模式。 用来表示元字符自身和一部分常用的C语言转义序列。例如，n表示换行符，而*则是字面意义上的星号。* 匹配零个或者多个紧接在前面的表达式。例如， t*可以匹配任意多个空格和tab，也就是空白字符，它能够匹配” ”、”或者一个空字符串。+ 匹配一个或者多个紧接在前面的表达式。例如，0-9+可以匹配数字字符串，像1,1111或者123

32、4，但不能是一个空字符。? 匹配零个或者一个紧着在前面的表达式。例如，-?0-9+匹配一个有符号数字，它带有一个可选的前置负号。| 选择操作符，匹配紧着在前面的表达式或者紧跟在后面的表达式。“” 所有引号中的字符将基于字面意义被解释。不属于C转义序列的元字符将失去它的特殊意义。() 把一系列的正则表达式组成一个新的正则表达式。例如，(01)匹配字符序列01，而a(bc|de)匹配abc或者ade。/ 尾部上下文，匹配斜线前的正则表达式，但是要求其后紧跟着斜线后的表达式。例如，0/1匹配字符串01中的0，但是不会匹配字符串0或者02.斜线后匹配的内容不会被“消耗掉”，它们会返还给输入以便于继续匹

33、配。每个模式只允许一个尾部上下文操作符。正确识别正则式的方法有几种，我们可以使用有限自动机(Finite Automata)来识别，也可以使用Lex（Flex）词法分析器来识别。3.2 有限自动机用有限自动机识别正则式只能对每个字符串回答” Yes ” or “ No ”。我们使用状态图来直观图示有限自动机。状态图是有向图，它由一组矢量线连接的有限个结点组成。结点用圆圈表示，代表识别单词后词法分析器所处的状态，状态的名字或者编号写在圆圈中。有限自动机有一个初始态和多个终态，终态通常用双圆圈表示，以示和其他状态的区别。状态之间由称为“边”的带箭头的弧连接，我们在边上写上指示输入字符的标记，通常标

34、记用一个字符表示，它表示当词法分析器所处的状态可能会引入该边的结点时可能会扫描到的字符，当词法分析器进入了这个结点，则会有边指示下一个状态。如果有些情况出现需要回退一个结点时，我们就在终态的右上角加一个” * ” 。从一个状态转换图的初态出发到某一个终态，遍历这个路径可以识别一定的字符串。如图3-4表示了由字母开头后跟数字或者字母组成的标示符的转换图图3-4 标示符的状态转换图有限自动机可以分为确定的有限自动机(Deterministic Finite Automata, DFA)和不确定的有限自动机(Nondeterministic Finite Automata, NFA) 7。它们的区别

35、就在于自动机在识别过程中下一个状态是否是确定的。如果对于同一个字符有若干个下一个状态，那么这就是不确定的有限自动机；如果只有一个下一个状态，那么就是确定的有限自动机。不确定的有限自动机可以转换成等价的确定有限自动机。3.3 Flex词法分析器Flex通过识别正则表达式然后将输入流分解为若干个记号(token)提供给程序使用。Flex程序由定义部分、规则部分和用户子例程三部分构成。这三部分被由两个百分号组成的行分隔。其中前两个部分是必须的、一定要有的，但它们的内容可以为空。它们的基本格式如下所示：.定义部分.%.规则部分.%.用户子例程.其中，定义部分包含文字块、选项、开始条件、定义和转换等。规

36、则部分包括C代码和模式行。处于%和%之间的内容或者直接以空白字符开始则被认为是C代码，它们会被原样不动地拷贝到yylex()例程中，yylex()例程与调用记号(token)有关，大多数包含Flex词法分析器的程序为了方便语法分析器的处理都使用词法分析器来获得一个记号流。每次当程序需要一个记号时，yylex()就会被调用来读取一小部分输入，然后返回相应的记号。当程序需要下一个新记号时，yylex()会被再次调用并返回记号。那些出现在规则部分开头的C代码也会相应出现在yylex()的开头，它可以包含词法分析器中需要使用的变量的声明，以及每次调用yylex()所需要运行的代码。当Flex词法分析器

37、运行时，每次它发现一个符合规则部分模式的匹配，和这个模式所关联的C代码就会被执行。如果模式后面紧跟的不是C代码而是一个竖线的话，这个模式就会使用它下面模式的C代码。当任何模式与输入字符无法匹配时，词法分析器就认为它匹配了一个动作代码为ECHO的模式（宏ECHO是用来把记号输出到当前的输出文件yyout中），相应的，词法分析器输出该记号8。Flex词法分析器器原样拷贝用户子例程的内容到C文件。这个部分通常包含规则中所需要调用的例程。Flex的工作流程如图3-5所示：图3-5 Flex的工作流程本课题词法分析拟用Flex（GNU下的Lex）来实现。3.4 用Flex实现Prolog的词法分析根据P

38、rolog的定义以及本课题自身的情况特点，在词法分析阶段Flex词法分析器需要识别出由大写字母开头的变量、小写字母及单引号开头的常量、整数、浮点数、特殊字符等。本课题在Flex定义部分除了必要的C代码和与语法分析器Bison连接的代码之外，为了方便管理还把一些过长的正则式用简短的名字代替，如变量variable：(A-Z(_|A-Z|0-9|a-z)*)|_常量name：(a-z(_|A-Z|0-9|a-z)*)|(.*)整数natural_number: -+?0-9+空格whitespace： t+浮点数float_number：-+?0-9+.0-9+回车换行EOL：n在规则部分写出了词

39、法分析器需要识别出的符号，它们如表3-2所示：词法符号C代码表示的意义+return PLUS;识别标准符号-return MINUS;*return MULTIPLY;/return DIVIDE;,return AND;return OR;!return CUT;(return LPAREN;)return RPAREN;return LBRACKET;return RBRACKET;|return SPLIT;:return COLON;.return DOT;:-return H_CON_B;识别规则符号?-return ASK;识别询问符号/.*/* skip comment */单

40、行注释/*BEGIN(COMMENT);*/BEGIN(INITIAL);(*|n)+|.printf(ERROR);eolreturn EOL;回车换行nameyylval-cname=malloc(sizeof(char)*30);strcpy(yylval-cname,yytext); return NAM;常量natural_numberyylval-intnum=atoi(yytext);return NATURAL_NUMBER;float_numberyylval-doublenum=atof(yytext);return FLOAT_NUMBER;variableyylval-

41、cname=malloc(sizeof(char)*30);strcpy(yylval-cname,yytext); return VARIABLE;whitespace/*whitespace*/空白行yyterminate();结束.printf(bad input character %s at line %dn,yytext,yylineno);表3-2词法分析器需要识别出的符号Flex和Bison配合使用有两个问题要解决：一个是它们的衔接问题，Flex怎么把找到的元素传给Bison用于语法分析，Bison如何通知Flex继续寻找元素；第二个问题就是如何使它们可以重入。就Flex这部分

42、来说，在定义部分要包含Bison的头文件，Flex词法分析器需要识别的元素也不需要在Flex定义阶段给出，它们而是由Bison语法分析器定义。为了使Flex词法分析器支持可重入，需要在定义部分加入可以使可重入词法语法分析器相兼容的文件，使可重入的词法分析器的调用方法可以和Bison兼容。由于词法分析器只是整个编译器的一部分，所以它的用户子例程部分为空。3.5 小结本章节先讲述了词法分析的理论以及Flex词法分析器的特点，然后论述了根据Prolog语言的词法特点用Flex词法分析器开发Prolog编译器的词法分析部分。第4章 语法分析的实现阐明语法的一个工具是文法。文法G定义为四元组（VN,VT

43、,P,S）。其中，VN是一个非空有限非终结符集；VT是一个非空有限终结符集；P是规则（）的有限集合，VNVT*被称为规则的左部，VNVT*被称为规则的右部，S是开始符号必须至少要在某个规则中作为左部出现。VNVT=，即VN和VT不含公共的元素。词法分析的问题实际上是识别正则表达式的问题。语法分析的主要任务是在词法分析的基础上判断表达式的语法结构是不是符合文法规则。语法分析器从词法分析器获得一个由词法单元组成的串，并验证这个串是否可以由源语言的文法生成9，如图4-1所示。有些表达式虽然能满足词法分析的要求，但是不符合文法规则，这样的表达式就不能构成有效的表达式。我们期望语法分析器报告的语法错误能

44、够易于理解，我们还期望语法分析器能够从一些常见的错误中回复过来并且能够继续处理程序剩下的部分。图4-1编译器模型中语法分析器的位置4.1 上下文无关文法上下文无关文法（Content-free Grammar）是程序设计语言的语法分析常用的文法规则，上下文无关文法在命名惯例和运算上与正则表达式极为类似10。上下文无关文法区别于正则表达式是它使用递归的规则，例如，while语句结构中可以嵌套其他的while语句，这在正则表达式中是不允许的。由于这个区别，上下文无关文法识别的结构类别要多于正则表达式识别的结构类。因为上下文无关文法必须使用递归调用或者显式管理的分析栈，所以上下文无关文法用作识别这些

45、结构的算法也与扫描算法差别很大。上下文无关文法经常使用的基本结构是语法树（syntax tree）。有这样一个上下文无关文法G=（E，+，*，i，(，)，P，E）其中P为:EiEE+EEE*EE(E)这里的非终结符E表示一类算术表达式。i表示程序设计语言中的“变量”，该文法定义了由变量、+、*、(和)组成的算术表达式的语法结构，即：变量也是算术表达式；如果E1和E2是算术表达式，那么E1*E2、E1+E2和E1也都是算术表达式。当然，上面的文法也可以写成Ei|E+E| E+E|(E)。文法G=（VN,VT,P,S）给定，对于G的任何句型我们都能构造相关联的语法树，语法树应该满足下面4个条件：1

46、) S是树根2) 每个结点都有一个V的符号作为标记3) 如果一个结点n除它自己外还有至少一个有标记A的子孙，那么A肯定在VN中4) 若结点n的直接子孙从左到右的次序是n1，n2，nk，并且对应的标记分别为A1,A2,Ak，那么P中一定有产生式AA1A2Ak。再看一个上下文谷关文法的例子G=(S,A,a,b,P,S)，其中P是：1) SaAS2) ASbA3) ASS4) Sa5) Aba它的语法树如图4-2图4-2 G=(S,A,a,b,P,S)的推导树从这课语法树知顶端结点S是树根，a，A和S这三个结点是它的直接子孙，树的第1、2层表示的是产生式SaAS。类似于S，结点A除它自己外还有别的子

47、孙，所以A肯定是非终结符。图非常直观自然的描述文法G的句型aabbaa的推导过程，即语法树的叶子结点。由于语法树只表示出了在推导过程中哪有非终结符使用哪个产生式，它并没有产生式的使用顺序。对文法G的句型aabbaa的推导可以有3个不同推导过程：1) S aAS aSbAS aabAS aabbaS aabbaa2) S aAS aAa aSbAa aSbbaa aabbaa3) S aAS aSbAS aSbAa aabAa aabbaa第一个推导过程在推导中使用产生式替换当前串中的最左非终结符，使用产生式的顺序是1、2、4、5、4。而第二个推导过程使用产生式替换当前串中的最右非终结符，使用产

48、生式的顺序是1、4、2、5、4。如果对于句型、，在推导中都是替换的最左非终结符，那么这种推导就是最左推导。上述第1个推导即为最左推导。同理，替换的都是最右非终结符那就是最右推导。例如上述第1个推导。最右推导又叫做规范推导，所到的句型叫做规范句型。有时候同一个文法会有不同的语法树，比如文法G=（E，+，*，i，(，)，P，E）中句型i*i+i就可以有两个不同的最左推导：1) E E+E E*E+E i*E+E i*I+E i*i+i2) E E*E i*E i*E+E i*i+E i*i+i这两个推导对应的语法树如图4-3、4-4图4-3 推导1的语法树图4-4 推导2的语法树如果在一个文法中有

49、某个或者某些句子对应不止一棵语法树，那么这个文法是二义的。二义文法是分析程序表示的一个严重问题，因为它不能准确的指出程序的语法结构。二义性被认为是一种语言语法不完善的说明，应该避免它。解决二义性有两个基本方法，第一个是在每个二义性情况下设置一个规则，用规则指出哪一个语法树是正确的。我们把这样的规则称作消除二义性规则11。消除二义性规则的好处在于，有时候文法很复杂，它不需要修改文法就可以消除二义性。它的缺点是文法不能单独提供语言的语法结构。另一种方法是强制改变文法，把它改变成一个正确的语法树。4.2 句型分析句型分析，就是识别一个符号串是否是某个文法的句型。句型分析的问题就是如何知道所给定的符号

50、串是文法的句型，是否是某个推导的构造过程。句型分析是一个过程，该过程识别输入符号串是否是语法上正确的程序。句型分析分为自顶向下分析和自底向上分析两种方法。自顶向下分析：自顶向下的分析算法的分析顺序是由根节点到叶子结点。常用的自顶向下的语法分析方法有两种，这两种方法是LL（1）分析法和递归子程序法。一、 LL（1）分析之所以叫LL（1），是因为第一个L指的是由左向右的处理输入，第2个L是它使用的是最左推导，而括号中的数字1表示它使用输入中的一个符号来预测分析的方向，总之用一句话总结LL（1）分析法的基本思想，就是在从左到右扫描源程序的同时从识别符号生成句子的最左推导，并且只要向前查看一个输入符号

51、。LL（1）分析要求计算First集合Follow集。LL（1）分析法的分析程序由一个总控程序、一个符号栈S和一个分析表M构成。不同的LL（1）分析法分析的文法程序，它们总控程序都是相同的，但是分析表M是不同的。文法的符号由符号栈S存放。当文法和待分析符号串确定后，随着语法分析过程符号栈的内容也在不断变化。由预先根据文法G设计的分析表M和符号栈S控制整个语法分析的过程。事实上并不是所有的上下文无关文法都可以用LL（1）进行语法分析，如果想要用LL（1）分析，必须满足几个条件：第一，文法必须是不含有多余规则的文法；第二，文法不能有回溯；第三，文法不能有左递归。所以，有些文法想要满足LL（1）文法

52、的要求就要经过一些等价变换。变换操作包括去掉多余规则，消除能够产生回溯的间接左递归，消除文法的直接左递归等。我们用符号串的推导的终结头符号集First（x）和文法符号的后跟符号集Follow（U）来判断一个文法是否是LL（1）文法。除了First和Follow集，还有一个表示First集或者First集和Follow集并集运算结果的Select集。判定文法是否是LL（1）文法可以分为两种情况：一种是当空符号串不属于First集，只要每一条规则的不同右部的First集两两无交集这个条件满足，那么可以判定这个文法是LL（1）文法。第二种就是当空符号串属于First集，空符号串ZFirst（x），如

53、果文法满足该文法符号的Follow集与First集无交集和同一非终结符的右部的First集两两无交集的话，那么该文法也是LL（1）文法。A. 计算First集计算First集大致上分为两种方法：第一种是根据First集的定义，第二种是由关系图求First。1) 根据First集的定义计算的步骤有如下几步对每一个文法符号XV由First集的定义计算First（X）。(1) 若XVT，那么First（X）=X。(2) 若XVN，且有产生式Xa，aVT，则aFirst（X）。(3) 若XVN，X，则First（X）。(4) 若X，Y1，Y2，Yn都属于VN，而有产生式XY1Y2Yn。当Y1，Y2，Y

54、i-1都*时，其中1in，则First（Y1）-，First（Y2）-，FirstYi-1-，FirstYi都包含在First（X）中。(5) 当(4)中i=1,2，n时，所有Yi*，则First（X）=First(Y1)FirstY2FirstYn。反复使用上述2至5步直到每个符号的First集不再增大为止。若符号串V*，=X1X2Xn，当X1*，则First（）=First（X1）。若对任何j（1ji-1，2in）First（Xj）；First（Xi），则First（）=j=1i-1（FirstXj-）First（Xi）。当所有First（Xj）（1jn）都含有时，则First（）=j=1n(FirstXj)。2) 由关系图法求文法符号的First集的步骤有如下几步：(1) 文法图中的每个结点代表一个文法符号，对应非终结符的结点用First（S）来标记，其