学海网

毕业论文-一种自适应的Prolog编译器，共74页，33759字
摘 要
Prolog程序语言是一种建立在逻辑学理论基础之上的语言，最初Prolog程序语言被应用在自然语言等研究领域。现在它可以用来建造专家系统、智能知识库、自然语言理解等广泛的人工智能的研究中，同时它也可以帮助到一些常用应用程序的编写。这是因为Prolog的编程方法更像是使用逻辑语言来描述程序，它能够比其他语言更快速地开发程序。
随着人工智能的兴起，越来越多的人开始探索各种人工智能技术。其中Prolog程序语言作为较早的代表，更是受人追捧。传统的Prolog编译器只能按照程序的书写顺序从上到下匹配，如果写在上面的谓词十分难解，而非常好解的谓词却写在了下面，那么Prolog解这个程序就需要一些时间。这也就是传统Prolog编译器的短板。如果在Prolog编译器中加入Prolog匹配的“指导思想”告诉Prolog编译器应该选哪个谓词，进而Prolog在寻找答案的时候就不会仅凭程序员的个人习惯和概率来左右其得到答案的效率了。
本文主要研究工作如下：
首先本文大致讨论人工智能和专家系统的定义和Prolog语言的组成特点。
其次讲述Prolog编译器的开发方法。本文采用Flex词法分析器用于Prolog的词法开发，用正则表达式识别需要传递给语法分析器的记号。采用Bison用于其语法开发并在Bison中使用自顶向下的LL(1)文法。使用哈希这种数据结构来组织符号表，并用拉链法来处理符号表中遇到的冲突。由于本文要用到Flex和Bison的结合使用，而且是要识别一整个程序，所以词法分析器Flex和语法分析器Bison结合的特殊性也在研究范围之内。
最后针对Prolog匹配出现的一些缺点，提出了利用UCB策略改进其匹配方式，试图使其高效率得出最优解。
关键词：Prolog 编译器 程序语言 UCB 自适应

目 录
第一章 绪论 1
1.1 研究背景 1
1.2 课题的研究内容 2
1.3 课题的意义 2
1.3.1 人工智能的概念及研究意义 2
1.3.2 专家系统的概念及研究意义 2
1.3.3 Prolog程序语言的重要性 3
1.4 论文主要工作 3
第二章 Prolog理论基础 4
第三章 词法分析的实现 6
3.1 正则表达式 8
3.2 有限自动机 9
3.3 Flex 9
3.4 用Flex实现Prolog的词法分析 11
3.5 小结 13
第四章 语法分析的实现 14
4.1 上下文无关文法 14
4.2 句型分析 18
4.3 Bison 23
4.4 用Bison实现Prolog的语法分析 24
4.5 词法分析器Flex和语法分析器Bison的结合 27
4.6 二义性冲突 27
4.7 小结 30
第五章 语义分析的实现 31
5.1 语义分析 31
5.1.1 静态语义检查 31
5.1.2 属性文法 32
5.2 符号表 33
5.2.1 符号的主要属性及作用 34
5.2.2 符号表的总体组织 39
5.2.3 符号表项的排列 39
5.3 符号表的实现 42
5.4 小结 43
第六章 Prolog知识库的搜索引擎的实现 44
6.1 Prolog基本运算方法 44
6.1.1 深度优先算法 44
6.1.2 合一 44
6.1.3 回溯 44
6.2 存储组织和匹配算法 45
6.2.1 栈式动态存储分配 45
6.2.2 简单的栈式存储分配的实现 46
6.3 小结 51
第七章 Prolog编译器的改进 52
7.1 UCB 52
7.1.1 马尔科夫决策过程 52
7.1.2 蒙特卡罗 53
7.1.3 蒙特卡罗规划 54
7.1.4 多臂匪徒模型 55
7.2 小结 57
第八章 总结和展望 58
参考文献 60
致 谢 62
攻读学位期间发表的学术论文 63

课题的研究内容
本课题立足于Prolog编译器的开发，在人工智能的大背景下，着重详细论述了一个可扩展的Prolog编译器的实现，其中包括了词法分析、语法分析、语义分析，以及Prolog知识库的搜索引擎的实现，包括深度优先搜索算法、合一算法、匹配算法等关键模块。论文也讨论了改进Prolog知识库的搜索方法。其中词法分析和语法分析使用Flex和Bison工具开发，在匹配问题中使用的是树的匹配，搜索方法由原来的深度优先改进为最优优先搜索。

论文主要工作
本文从开发传统Prolog编译器开始，包括从词法分析器的组织到最后匹配算法。本文的组织结构如下：
第一章 绪论。对论文研究背景对论文的主要研究工作做以概述，并阐明整篇文章的组织结构。
第二章 理论基础。阐述Prolog语言的组成部分，为下文做铺垫。
第三章 词法分析的实现。首先介绍什么是词法分析，词法分析的原理及程序中哪些记号需要被分析出来，然后用Flex词法编辑器来实现Prolog编译器的词法分析部分。
第四章 语法分析的实现。首先介绍了语法分析在整个编译过程中的位置，然后介绍本文要用到的文法规则，最后用Bison语法分析器来实现Prolog编译器的语法分析部分。
第五章 语义分析的实现。首先说明了语义分析需要检查的定义，然后介绍了符号表的作用及组织方法，最后论述了符号表的实现。
第六章 Prolog知识库的搜索引擎的实现。首先论述Prolog基本运算方法包括深度优先搜索算法、合一算法、匹配算法等关键模块，然后存储组织和匹配算法在最后论述。
第七章 Prolog编译器的改进。通过马尔科夫决策、蒙特卡罗法、蒙特卡罗规划和多臂匪徒模型引出了UCB决策策略，UCB算法是自适应Prolog编译器的核心部分，有了它才可以使Prolog编译器知道应该选择匹配哪个谓词。
第八章 总结与展望。对论文工作进行总结，并对下一步工作方向做出展望。