【正文】 密級(jí)： 保密期限： 碩士研究生學(xué)位論文 題目 : 一種自適應(yīng)的 Prolog 編譯器 學(xué) 號(hào)： 106894 姓 名： 高慧 專 業(yè)： 計(jì)算機(jī)科學(xué)與技術(shù) 導(dǎo) 師： 劉知青 學(xué) 院： 軟件 學(xué)院 2021 年 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)均已在論文中作了明確的說(shuō)明并表示了謝意。 申請(qǐng)學(xué)位論文與資料若有不實(shí)之處，本人承擔(dān)一切相關(guān)責(zé)任。 本人簽名： 日期： 關(guān)于論文使用授權(quán)的說(shuō)明 學(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é)位論文 2021 I 一種自適應(yīng)的 Prolog編譯器 摘 要 Prolog 程序語(yǔ)言是一種建立在邏輯學(xué)理論基礎(chǔ)之上的語(yǔ)言，最初 Prolog程序語(yǔ)言被應(yīng)用在自然語(yǔ)言等研究領(lǐng)域?，F(xiàn)在它可以用來(lái)建造專家系統(tǒng)、智能知識(shí)庫(kù)、自然語(yǔ)言理解等廣泛的人工智能的研究中，同時(shí)它也可以幫助到一些常用應(yīng)用程序的編寫。這是因?yàn)?Prolog 的編程方法更像是使用邏輯語(yǔ)言來(lái)描述程序，它能夠比其他語(yǔ)言更快速地開發(fā)程序。 隨著人工智能的興起，越來(lái)越多的人開始探索各種人工智能技術(shù)。其中 Prolog 程序語(yǔ)言作為較早的代表，更是受人追捧。傳統(tǒng)的 Prolog 編譯器只能按照程序的書寫順序從上到下匹配，如果寫在上面的謂詞十分難解，而非常好解的謂詞卻寫在了下面，那么 Prolog 解這個(gè)程序就需要一些時(shí)間。這也就是傳統(tǒng) Prolog 編譯器的短板。如果在 Prolog 編譯器中加入 Prolog 匹配的“指導(dǎo)思想”告訴 Prolog 編譯器應(yīng)該選哪個(gè)謂詞，進(jìn)而 Prolog 在尋找答案的時(shí)候就不會(huì)僅憑程序員的個(gè)人習(xí)慣和概率來(lái)左右其得到答案的效率了。 本文主要 研究工作如下： 首先 本文大致討論人工智能和專家系統(tǒng)的定義和 Prolog 語(yǔ)言的組成特點(diǎn)。 其次講述 Prolog 編譯器的開發(fā)方法。 本文采用 Flex 詞法分析器用于Prolog 的詞法開發(fā)， 用正則表達(dá)式識(shí)別需要傳遞給語(yǔ)法分析器的記號(hào)。 采用 Bison 用于其語(yǔ)法開發(fā)并在 Bison 中使用自頂向下的 LL(1)文法。使用哈希這種數(shù)據(jù)結(jié)構(gòu)來(lái)組織符號(hào)表，并用拉鏈法來(lái)處理符號(hào)表中遇到的沖突。由于本文要用到 Flex 和 Bison 的結(jié)合使用，而且是要識(shí)別一整個(gè)程序，所以 詞法分析器 Flex 和語(yǔ)法分析器 Bison 結(jié)合的特殊性也在研究范圍之內(nèi)。 最后 針對(duì) Prolog 匹配出現(xiàn)的一些缺點(diǎn)，提出了利用 UCB 策略改進(jìn)其匹配方式，試圖使其高效率得出最優(yōu)解。 關(guān)鍵詞 ： Prolog 編譯器 程序語(yǔ)言 UCB 自適應(yīng) 北京郵電大學(xué)碩士學(xué)位論文 2021 II A SELFADAPTED PROLOG COMPILER ABSTRACT Prolog 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 北京郵電大學(xué)碩士學(xué)位論文 2021 III 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 北京郵電大學(xué)碩士學(xué)位論文 2021 I 目 錄 第一章 緒論 ........................................................................................................................... 1 研究背景 ....................................................................................................................... 1 課題的研究?jī)?nèi)容 ............................................................................................................. 2 課題的意義 .................................................................................................................... 2 人工智能的概念及研究意義 .......................................................................................... 2 專家系統(tǒng)的概念及研究意義 .......................................................................................... 2 Prolog 程序語(yǔ)言的重要性 .............................................................................................. 3 論文主要工作 ................................................................................................................ 3 第二章 Prolog理論基礎(chǔ) ......................................................................................................... 4 第三章 詞法分析的實(shí)現(xiàn) .......................................................................................................... 6 正則表達(dá)式 ................................................................................................................... 8 有限自動(dòng)機(jī) ................................................................................................................... 9 Flex ............................................................................................................................. 9 用 Flex 實(shí)現(xiàn) Prolog 的詞法分析 .................................................................................... 11 小結(jié) .......................................................