【正文】 密級(jí)： 保密期限： 碩士研究生學(xué)位論文 題目: 一種自適應(yīng)的Prolog編譯器 學(xué) 號(hào)： 106894 姓 名： 高慧 專 業(yè)： 計(jì)算機(jī)科學(xué)與技術(shù) 導(dǎo) 師： 劉知青 學(xué) 院： 軟件學(xué)院 2012年 12月 31日獨(dú)創(chuàng)性（或創(chuàng)新性）聲明本人聲明所呈交的論文是本人在導(dǎo)師指導(dǎo)下進(jìn)行的研究工作及取得的研究成果。盡我所知，除了文中特別加以標(biāo)注和致謝中所羅列的內(nèi)容以外，論文中不包含其他人已經(jīng)發(fā)表或撰寫過的研究成果，也不包含為獲得北京郵電大學(xué)或其他教育機(jī)構(gòu)的學(xué)位或證書而使用過的材料。與我一同工作的同志對(duì)本研究所做的任何貢獻(xiàn)均已在論文中作了明確的說明并表示了謝意。申請(qǐng)學(xué)位論文與資料若有不實(shí)之處，本人承擔(dān)一切相關(guān)責(zé)任。本人簽名： 日期： 關(guān)于論文使用授權(quán)的說明學(xué)位論文作者完全了解北京郵電大學(xué)有關(guān)保留和使用學(xué)位論文的規(guī)定，即：研究生在校攻讀學(xué)位期間論文工作的知識(shí)產(chǎn)權(quán)單位屬北京郵電大學(xué)。學(xué)校有權(quán)保留并向國(guó)家有關(guān)部門或機(jī)構(gòu)送交論文的復(fù)印件和磁盤，允許學(xué)位論文被查閱和借閱；學(xué)?？梢怨紝W(xué)位論文的全部或部分內(nèi)容，可以允許采用影印、縮印或其它復(fù)制手段保存、匯編學(xué)位論文。（保密的學(xué)位論文在解密后遵守此規(guī)定）保密論文注釋：本學(xué)位論文屬于保密在 年解密后適用本授權(quán)書。非保密論文注釋：本學(xué)位論文不屬于保密范圍，適用本授權(quán)書。本人簽名： 日期： 導(dǎo)師簽名： 日期： 北京郵電大學(xué)碩士學(xué)位論文 2013一種自適應(yīng)的Prolog編譯器摘 要Prolog程序語言是一種建立在邏輯學(xué)理論基礎(chǔ)之上的語言，最初Prolog程序語言被應(yīng)用在自然語言等研究領(lǐng)域?，F(xiàn)在它可以用來建造專家系統(tǒng)、智能知識(shí)庫、自然語言理解等廣泛的人工智能的研究中，同時(shí)它也可以幫助到一些常用應(yīng)用程序的編寫。這是因?yàn)镻rolog的編程方法更像是使用邏輯語言來描述程序，它能夠比其他語言更快速地開發(fā)程序。隨著人工智能的興起，越來越多的人開始探索各種人工智能技術(shù)。其中Prolog程序語言作為較早的代表，更是受人追捧。傳統(tǒng)的Prolog編譯器只能按照程序的書寫順序從上到下匹配，如果寫在上面的謂詞十分難解，而非常好解的謂詞卻寫在了下面，那么Prolog解這個(gè)程序就需要一些時(shí)間。這也就是傳統(tǒng)Prolog編譯器的短板。如果在Prolog編譯器中加入Prolog匹配的“指導(dǎo)思想”告訴Prolog編譯器應(yīng)該選哪個(gè)謂詞，進(jìn)而Prolog在尋找答案的時(shí)候就不會(huì)僅憑程序員的個(gè)人習(xí)慣和概率來左右其得到答案的效率了。本文主要研究工作如下：首先本文大致討論人工智能和專家系統(tǒng)的定義和Prolog語言的組成特點(diǎn)。其次講述Prolog編譯器的開發(fā)方法。本文采用Flex詞法分析器用于Prolog的詞法開發(fā)，用正則表達(dá)式識(shí)別需要傳遞給語法分析器的記號(hào)。采用Bison用于其語法開發(fā)并在Bison中使用自頂向下的LL(1)文法。使用哈希這種數(shù)據(jù)結(jié)構(gòu)來組織符號(hào)表，并用拉鏈法來處理符號(hào)表中遇到的沖突。由于本文要用到Flex和Bison的結(jié)合使用，而且是要識(shí)別一整個(gè)程序，所以詞法分析器Flex和語法分析器Bison結(jié)合的特殊性也在研究范圍之內(nèi)。最后針對(duì)Prolog匹配出現(xiàn)的一些缺點(diǎn)，提出了利用UCB策略改進(jìn)其匹配方式，試圖使其高效率得出最優(yōu)解。關(guān)鍵詞：Prolog 編譯器 程序語言 UCB 自適應(yīng)A SELFADAPTED PROLOG COMPILERABSTRACTProlog programming language is to establish the theoretical basis of the logic of language, the initial Prolog 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 monly used application preparation. 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 intelligence techniques. Prolog programming language as one of early AI languages is chased by people. The traditional Prolog pilers 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 this is disadvantage of traditional Prolog pilers. If a guide in a Prolog piler can tell which predicate should be chosen, then this piler 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 definition of artificial intelligence and Expert System. We also argue the characteristic of Prolog. Then how to develop a Prolog piler 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 explore syntax analysis, and LL(1) which is belong to topdown 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 last as disadvantage of traditional Prolog pilers, UCB strategy is in to improve the way of match in order to trying to make it on high efficiency optimal solution.KEYWORDS: prolog piler programming language UCB selfadapted IV目 錄第一章 緒論 1 研究背景 1 課題的研究?jī)?nèi)容 2 課題的意義 2 人工智能的概念及研究意義 2 專家系統(tǒng)的概念及研究意義 2 Prolog程序語言的重要性 3 論文主要工作 3第二章 Prolog理論基礎(chǔ) 4第三章 詞法分析的實(shí)現(xiàn) 6 正則表達(dá)式 8 有限自動(dòng)機(jī) 9 Flex 9 用Flex實(shí)現(xiàn)Prolog的詞法分析 11 小結(jié) 13第四章 語法分析的實(shí)現(xiàn) 14 上下文無關(guān)文法 14 句型分析 18 Bison 23 用Bison實(shí)現(xiàn)Prolog的語法分析 24 詞法分析器Flex和語法分析器Bison的結(jié)合 27 二義性沖突 27 小結(jié) 30第五章 語義分析的實(shí)現(xiàn) 31 語義分析 31 靜態(tài)語義檢查 31 屬性文法 32 符號(hào)表 33 符號(hào)的主要屬性及作用 34 符號(hào)表的總體組織 39 符號(hào)表項(xiàng)的排列 39 符號(hào)表的實(shí)現(xiàn) 42 小結(jié) 43第六章 Prolog知識(shí)庫的搜索引擎的實(shí)現(xiàn) 44 Prolog基本運(yùn)算方法 44 深度優(yōu)先算法 44 合一 44 回溯 44 存儲(chǔ)組織和匹配算法 45 棧式動(dòng)態(tài)存儲(chǔ)分配 45 簡(jiǎn)單的棧式存儲(chǔ)分配的實(shí)現(xiàn) 46 小結(jié) 51第七章 Prolog編譯器的改進(jìn) 52 UCB 52 馬爾科夫決策過程 52 蒙特卡羅 53 蒙特卡羅規(guī)劃 54 多臂匪徒模型 55 小結(jié) 57第八章 總結(jié)和展望 58參考文獻(xiàn) 60致 謝 62攻讀學(xué)位期間發(fā)表的學(xué)術(shù)論文 63 59 第1章 緒論 研究背景比爾蓋茨曾經(jīng)預(yù)言未來家家都有機(jī)器人，未來人工智能將會(huì)飛速的發(fā)展。人工智能是一個(gè)含義很廣的詞語，具有不同學(xué)科背景的人工智能學(xué)者在其發(fā)展過程中對(duì)它有著不同的理解并提出了一些不同的觀點(diǎn)。從能力的角度看，相對(duì)于人類自有的自然智能，人工智能是指在機(jī)器上用人工的方法實(shí)現(xiàn)的智能；從學(xué)科的角度看，作為一個(gè)學(xué)科的名稱來定義人工智能。所謂人工智能是一門研究如何構(gòu)造智能機(jī)器或智能系統(tǒng)，使它能夠模擬、延伸和擴(kuò)展人類智能的學(xué)科[1]。關(guān)于人工智能研究的目標(biāo)，到目前為止還沒有一個(gè)統(tǒng)一的看法。1978年索羅門(A. Sloman)對(duì)人工智能給出了三個(gè)主要目標(biāo)：1)對(duì)智能行為進(jìn)行有效解釋的理論分析；2)解釋人類自有智能；3)構(gòu)造智能的人工產(chǎn)品。經(jīng)過幾十年的發(fā)展，人工智能有了不小的進(jìn)步，現(xiàn)在人工智能已經(jīng)從單一的方向擴(kuò)展到定理證明、專家系統(tǒng)、機(jī)器學(xué)習(xí)、自然語言理解、智能檢索、自動(dòng)程序設(shè)計(jì)、機(jī)器人學(xué)、模式識(shí)別、組合調(diào)度問題、機(jī)器視覺各個(gè)方向。目前能夠研究人工智能的技術(shù)平臺(tái)就是計(jì)算機(jī)，用計(jì)算機(jī)來模擬人的某些行為和思維過程。在60年代出現(xiàn)了Prolog程序語言，它是建立在邏輯學(xué)理論基礎(chǔ)之上，最初Prolog程序語言被應(yīng)用在自然語言等研究領(lǐng)域。現(xiàn)在它可以用來建造專家系統(tǒng)、智能知識(shí)庫、自然語言理解等廣泛的人工智能的研究中，同時(shí)它也可以幫助到一些常用應(yīng)用程序的編寫。這是因?yàn)镻rolog的編程方法更像是使用邏輯語言來描述程序，它能夠比其他語言更快速地開發(fā)程序?，F(xiàn)階段的Prolog使用深度優(yōu)先搜索的策略。它從給它提出的問題即“當(dāng)前目標(biāo)”開始，在搜索過程中系統(tǒng)保存著這個(gè)當(dāng)前目標(biāo)，并且“從左至右”的完成目標(biāo)。系統(tǒng)總是首先完成第一個(gè)子目標(biāo)，如果第一個(gè)子目標(biāo)完成不了，整個(gè)問題就沒有答案，而第二個(gè)子目標(biāo)根本不會(huì)去嘗試。當(dāng)解決一個(gè)特定的子目標(biāo)時(shí)，對(duì)事實(shí)和規(guī)則的試探總是自頂向下的。簡(jiǎn)單的說：Prolog總是從上到下從左到右以深度優(yōu)先為主工作的。在Prolog的規(guī)則中也有析取和合取的問題（合取關(guān)系用“，”表示，析取關(guān)系用“；”表示），現(xiàn)階段的Prolog運(yùn)算時(shí)間和人工輸入有很大關(guān)系，假設(shè)一個(gè)合取關(guān)系中有為假的合取項(xiàng)，而且它是規(guī)則體的第一子目標(biāo)，那么計(jì)算它耗費(fèi)時(shí)間就相對(duì)要少。若要是這一個(gè)為假的合取項(xiàng)不是規(guī)則體的第一個(gè)子目標(biāo)，而且規(guī)則體第一個(gè)子目標(biāo)很難解，這就使整個(gè)程序要花費(fèi)一段時(shí)間才能得到答案。也就是說現(xiàn)在Prolog的一個(gè)大問題是深度優(yōu)先搜索的效率問題。 課題的研究?jī)?nèi)容本課題立足于Prolog編譯器的開發(fā)，在人工智能的大背景下，著重詳細(xì)論述了一個(gè)可擴(kuò)展的Prolog編譯器的實(shí)現(xiàn)，其中包括了詞法分析、語法分析、語義分析，以及Prolog知識(shí)庫的搜索引擎的實(shí)現(xiàn)，包括深度優(yōu)先搜索算法、合一算法、匹配算法等關(guān)鍵模塊。論文也討論了改進(jìn)Prolog知識(shí)庫的搜索方法。其中詞法分析和語法分析使用Flex和Bison工具開發(fā)，在匹配問題中使用的是樹的匹配，搜索方法由原來的深度優(yōu)先改進(jìn)為最優(yōu)優(yōu)先搜索。 課題的意義 人工智能的概念及研究意義所謂的“人工智能”是指人們通過計(jì)算機(jī)模擬或?qū)崿F(xiàn)的智能[2]。很遺憾因?yàn)槿斯ぶ悄苓€在被人們探索和研究所以到現(xiàn)在為止人工智能還沒有像其他成熟學(xué)科一樣形成一套比較完整的理論體系，經(jīng)過發(fā)展現(xiàn)在有一些技術(shù)已經(jīng)開始應(yīng)用人工智能，比如推理技術(shù)、搜索技術(shù)、聯(lián)想技術(shù)等。人工智能語言是一類適應(yīng)于人工智能和知識(shí)工程領(lǐng)域的、具有符號(hào)處理和邏輯推理能力的計(jì)算