【文章內(nèi)容簡介】 析、語義分析， 以及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ì)算機(jī)程序設(shè)計(jì)語言 [3]。能夠用它來編寫程序求解非數(shù)值計(jì)算、知識(shí)處理、推理、規(guī)劃、決策等具有智能的各種復(fù)雜問題。 在未來人工智能領(lǐng)域會(huì)改變?nèi)藗兊纳罘绞?，許多大的企業(yè)，如谷歌、微軟和蘋果都在努力探索人工智能領(lǐng)域。 專家系統(tǒng) 的 概念及研究 意義 專家系統(tǒng)（ Expert System）是一種用計(jì)算機(jī)程序來模擬人類專家解決某些特定領(lǐng)域問題的系統(tǒng) [4]。 因?yàn)槟硞€(gè)領(lǐng)域大量的專家水平的知識(shí)與經(jīng)驗(yàn)被記錄到專家系統(tǒng)內(nèi)部，所以系統(tǒng)能夠通過運(yùn)用人類專家的專業(yè)知識(shí)和解決專業(yè)問題的方法，模擬人類專家判斷推理和決策過程，來解決該領(lǐng)域的復(fù)雜問題。 自從 1965 年 在美國斯坦福大學(xué) 第一個(gè)專家系統(tǒng)問世以來，專家系統(tǒng)在人工智能應(yīng)用研究中表現(xiàn)的最廣泛和最活躍?，F(xiàn)如今存在著許多種不同的專家系統(tǒng)，這些專家系統(tǒng)已影響著各個(gè)專業(yè)領(lǐng)域并且獲得很大的成功。 北京郵電大學(xué)碩士學(xué)位論文 2021 3 專家系統(tǒng)按任務(wù)分類可分為：診斷型、解釋型、調(diào)試型、教育型、預(yù)測型、規(guī)劃型、控制型、設(shè)計(jì)型、監(jiān)測型。 Prolog 程序語言的重要性 Prolog 語言屬于一種人工智能語言， 21 世紀(jì)注定是屬于人工智能的時(shí)代 。 在經(jīng)過了幾十年的發(fā)展， 雖然 Prolog 語言已經(jīng)在例如機(jī)器定理證明和專家系統(tǒng)等方面體現(xiàn)了重要的 作用，但是幾乎主流的 Prolog 編譯器除了界面和編寫語言不同之外，沒有什么實(shí)質(zhì)性的創(chuàng)新，它們都是隨機(jī)的選取合一的謂詞進(jìn)行深度優(yōu)先的計(jì)算，有時(shí)由于隨機(jī)出的謂詞很難得到結(jié)果而影響到編譯器的效率。本文提出的方法是更改 Prolog 編譯器的搜索引擎，使其由原來的深度優(yōu)先變成最有優(yōu)先算法，進(jìn)而提高其計(jì)算效率。 論文主要工作 本文 從開發(fā)傳統(tǒng) Prolog 編譯器開始， 包括從詞法分析器的組織到最后匹配算法。本文的組織結(jié)構(gòu)如下： 第一章 緒論。 對(duì) 論文研究背景對(duì)論文的主要研究工作做以概述，并闡明整篇文章的組織結(jié)構(gòu)。 第二章 理論基礎(chǔ) 。 闡述 Prolog 語言的組成部分 ， 為下文做鋪墊 。 第 三 章 詞法分析的實(shí)現(xiàn) 。 首先介紹什么是詞法分析，詞法分析的原理及程序中哪些記號(hào)需要被分析出來，然后 用 Flex詞法編輯器來實(shí)現(xiàn) Prolog編譯器的詞法分析部分。 第 四 章 語法分析的 實(shí)現(xiàn) 。 首先介紹了 語法分析在整個(gè)編譯過程中的位置，然后介紹 本文要用到的 文法規(guī)則，最后用 Bison 語法分析器 來 實(shí)現(xiàn) Prolog 編譯器的語法分析部分。 第五章 語義分析的實(shí)現(xiàn) 。首先說明了語義分析需要檢查的定義，然后介紹了符號(hào)表的作用及組織方法，最后論述了符號(hào)表的實(shí)現(xiàn)。 第六章 Prolog 知識(shí)庫的搜索引擎的實(shí)現(xiàn)。首先論述 Prolog 基本運(yùn)算方法 包括深度優(yōu)先搜索算法、合一算法、匹配算法等關(guān)鍵模塊 ，然后存儲(chǔ)組織和匹配算法在最后論述。 第七章 Prolog 編譯器的改進(jìn)。 通過馬爾科夫決策、蒙特卡羅法、蒙特卡羅規(guī)劃和多臂匪徒模型引出了 UCB 決策策略， UCB 算法是自適應(yīng) Prolog 編譯器的核心部分，有了它才可以使 Prolog 編譯器知道應(yīng)該選擇匹 配哪個(gè)謂詞 。 第 八 章 總結(jié)與展望。對(duì)論文工作進(jìn)行總結(jié)，并對(duì)下一步工作方向 做出 展望 。 北京郵電大學(xué)碩士學(xué)位論文 2021 4 第二章 Prolog 理論基礎(chǔ) Prolog 的基本語句有：事實(shí)、規(guī)則、目標(biāo)這三種類型語句 [5]。 它們都用一種叫做“謂詞”的形式表示，所謂謂詞就是由一個(gè)謂詞名和一些參數(shù)組成。因?yàn)橹^詞清楚簡單，語句類型少，因而文法簡捷，程序邏輯性強(qiáng)，清晰易懂。 Prolog 是陳述性語言，只要必要的事實(shí)和規(guī)則提交，它不需要在程序中列出詳細(xì)的求解步驟就能使用內(nèi)部的演繹推理機(jī)制自動(dòng)求解程序給定的目標(biāo)。 Prolog 程序語言的基本語句說明如表 21 所示 語句 組成方式 例子 說明 事實(shí) 事實(shí)是一種用來說明問題中已知的對(duì)象和它們之間關(guān)系的謂詞，在 Prolog 程序中，事實(shí)由謂詞名及用小括號(hào)括起來的一個(gè)或幾個(gè)對(duì)象組成 例如 eat(alex， apple). 表示 是一個(gè)名為 eat 的關(guān)系，表示 alex 吃蘋果這個(gè)事實(shí) 。 規(guī)則 規(guī)則是由幾個(gè) 謂詞或者說簡單句 組成 并且他們之間有依賴性存在 ，事實(shí) 與事實(shí) 間的 類似于 依賴 的 關(guān)系被規(guī)則所描述 。 規(guī)則的組成很簡單，它一般由兩部分組成： 左邊 是規(guī)則頭，表示結(jié)論，而 右邊 是規(guī)則體，表示條件的前提 。 例如bird(X):animal(X),has(X,feather). 表示凡是有羽毛的動(dòng)物就是鳥。 目標(biāo) 目標(biāo)即是詢問， 一旦事實(shí)和規(guī)則被寫進(jìn) Prolog程序中之后， Prolog 就準(zhǔn)備好被 詢問有關(guān)問題 了 ， 這個(gè)時(shí)候 程序的運(yùn)行目標(biāo) 就是用戶詢問的問題 。目標(biāo)分內(nèi)、外兩種，外部目標(biāo)需要在程序運(yùn)行時(shí)手工鍵例如 ?student(alex). 表示“ alex 是學(xué)生嗎？” 北京郵電大學(xué)碩士學(xué)位論文 2021 5 入，內(nèi)部目標(biāo)需要寫在程序中。目標(biāo)的結(jié)構(gòu)與事實(shí)或規(guī)則一樣，它可以是多個(gè)謂詞的組合，或者是一個(gè)簡單的謂詞。 Prolog 可以在知道一些已知的事實(shí)的前提下通過邏輯推理得出一些未直接給出的事實(shí)。一個(gè) Prolog 程序在典型情況下并不是一個(gè)動(dòng)作序列，它是通過聚合在一起的事實(shí)和規(guī)則，由規(guī)則從那些事實(shí)中得出結(jié)論。 表 21 Prolog程序語言基本組成 Prolog 的基本組成理論是研究開發(fā) Prolog 編譯器的基礎(chǔ)，只有了解其組成才能根據(jù)其特點(diǎn)來開發(fā)適合的編譯器。 北京郵電大學(xué)碩士學(xué)位論文 2021 6 第三章 詞法分析 的實(shí)現(xiàn) 詞法分析是編譯工作的第一個(gè)階段。 詞法分析器的主要任務(wù)是從左到右將讀入源程序的輸入字符組成詞素。所謂詞素是源程序中的一個(gè)字符序列，它和某個(gè)詞法單元的模式匹配，并被詞法分析器識(shí)別為該詞法單元的一個(gè)實(shí)例 [6]。 在組成詞素后，詞法分析器生成并輸出一個(gè)詞法單元序列即 TOKEN，每個(gè)詞法單元對(duì)應(yīng)于一個(gè)詞素。然后語法分析器對(duì)這個(gè)詞法單元序列進(jìn)行語法分析。 詞法分析階段將讀入源程序的輸入字符組成詞素。詞素類似于自然語言的單詞，單詞可以分為名詞、動(dòng)詞和形容詞等不同類型，詞素也可以用一些規(guī)則進(jìn)行劃分，我們把劃分詞素的規(guī)則稱為模式。模式和詞素組成了詞法單元。詞 法單元有一個(gè)詞法單元名。詞素、模式和詞法單元之間的關(guān)系可以如表 31 所示 詞法單元 模式的非正式描述 詞素舉例 number 任何數(shù)值常數(shù) ， 10 relation ， =， =， ， = 或 =或 =或 或 = string 在兩個(gè) ”之間，除 ”之外的任何字符 “Hello World” separator (， )， , (或 )或 , date 方括號(hào)內(nèi)的字符序列 [20210101 15:30:00] 表 31詞素、模式和詞法單元的關(guān)系 詞法分析器除了識(shí)別詞法單元之外，還要完成其他的一些任務(wù)，比如：進(jìn)行詞法檢查發(fā)現(xiàn)錯(cuò)誤要報(bào)告所發(fā)現(xiàn)的錯(cuò)誤；為了后續(xù)語法分析發(fā)現(xiàn)錯(cuò)誤之后能給出正確的位置，詞法分析器需要提交詞法單元的位置；識(shí)別字符復(fù)合而成的算符和邊界符，并把它們合并成完整的單詞符號(hào)；略去沒用過的空白字符等。 根據(jù)詞法分析器與語法分析器協(xié)同的方式不同，詞法分析器在整個(gè)詞法分析階段有不同的工作方式： 1) 詞語法分析器并行工作， 詞法分析器將記號(hào)提交到一個(gè)隊(duì)列中供語法分析器調(diào)用。其工作方式如圖 31 所示： 北京郵電大學(xué)碩士學(xué)位論文 2021 7 圖 31并行工作方式 2) 詞法分析器單獨(dú)工作，這種方式就是詞法分析器單獨(dú)進(jìn)行一遍掃描，這期間語法分析器不會(huì)工作，詞法分析器識(shí)別出各個(gè)單詞并轉(zhuǎn)換成語法分析器需要的記號(hào)， 然后將記號(hào)作為語法分析器的輸入供語法分析器調(diào)用，它的工作方式如圖 32 所示： 圖 32詞法分析器獨(dú)立工作 3) 這種方式中詞法分析器是語法分析器的子程序，詞法分析器先分析出一個(gè)記號(hào)，然后記錄斷點(diǎn)，并把記號(hào)提供給語法分析器調(diào)用，當(dāng)語法分析器分析完當(dāng)前的記號(hào)之后，它就會(huì)給詞法分析器一個(gè)信號(hào)，使詞法分析器從斷點(diǎn)處繼續(xù)分析記號(hào)然后供語法分析器調(diào)用。這中工作方式如圖 33： 圖 33 作為子程序的詞法分析器的工作方式 正規(guī)式和有限自動(dòng)機(jī)是描述詞法規(guī)則的有效工具。 北京郵電大學(xué)碩士學(xué)位論文 2021 8 正則表達(dá)式 我們用叫做“模式”的規(guī)則來描述字符串集合。這里用正則表達(dá)式來表示規(guī)則。正則式是一種十分有效的工具，尤其是描述詞素的組成結(jié)構(gòu)。正則表達(dá)式通過使用元語言(metalanguage)來表達(dá)編程人員想要匹配的模式。它一般使用標(biāo)準(zhǔn)的文本字符，其中一部分代表模式而另外一部分則代表他們自身。 在正則表達(dá)式中有特殊意義的字符為： ^ 如果它是正則表達(dá)式的第一個(gè)字符就匹配行首。它也被用于方括號(hào)中表示補(bǔ)集。 [] 字符類 (character class)，可以匹配方括號(hào)中的任意一個(gè)字符。如果字符類中的第一個(gè)字符是抑揚(yáng)符號(hào) (^)，則改變?yōu)槠ヅ涑嚼ㄌ?hào)內(nèi)字符以外的任何字符。字符類里的破折號(hào)表示字符的范圍，例如， [09]意味著 [123456789]而 [az]則表示任意小寫字母。 $ 如果它是正則表達(dá)式的最后一個(gè)字符就匹配行尾。 {} 當(dāng)花括號(hào)中帶有一個(gè)或者兩個(gè)數(shù)字時(shí)，它表示前一個(gè)模式可以匹配的最小和最大次數(shù)。例如， A{1,3}匹配一到三個(gè)字母 A，而 0{5}匹配 ，它指向以這個(gè)名字命名的模式。 \ 用來表示元字符自身和一部分常用的 C 語言轉(zhuǎn)義序列。例如， \n 表示換行符，而\*則是字面意義上的星號(hào)。 * 匹配零個(gè)或者多個(gè)緊接在前面的表達(dá)式。例如， [ \t]*可以匹配任意多個(gè)空格和 tab，也就是空白字符，它能夠匹配 ” ”、 ”tabtab”或者一個(gè)空字符串。 + 匹配一個(gè)或者多個(gè)緊接在前面的表達(dá)式。例如， [09]+可以匹配數(shù)字字符串，像1,1111 或者 1234，但不能是一個(gè)空字符。 ? 匹配零個(gè)或者一個(gè)緊著在前面的表達(dá)式。例如， ?[09]+匹配一個(gè)有符號(hào)數(shù)字，它帶有一個(gè)可選的前置負(fù)號(hào)。 | 選 擇操作符，匹配緊著在前面的表達(dá)式或者緊跟在后面的表達(dá)式。 “…” 所有引號(hào)中的字符將基于字面意義被解釋。不屬于 C 轉(zhuǎn)義序列的元字符將失去它的特殊意義。 () 把一系列的正則表達(dá)式組成一個(gè)新的正則表達(dá)式。例如， (01)匹配字符序列 01，而 a(bc|de)匹配 abc 或者 ade。 / 尾部上下文，匹配斜線前的正則表達(dá)式，但是要求其后緊跟著斜線后的表達(dá)式。例如， 0/1 匹配字符串 01 中的 0，但是不會(huì)匹配字符串 0 或者 會(huì)被“消耗掉”，它們會(huì)返還給輸入以便于繼續(xù)匹配。每個(gè)模式只允許一個(gè)尾部上下文操作符 。 北京郵電大學(xué)碩士學(xué)位論文 2021 9 正確識(shí)別正則式的方法有幾種，我們可以使用有限自動(dòng)機(jī) (Finite Automata)來識(shí)別，也可以使用 Lex（ Flex）詞法分析器來識(shí)別。 有限自動(dòng)機(jī) 用有限自動(dòng)機(jī)識(shí)別正則式只能對(duì)每個(gè)字符串回答 ” Yes ” or “ No ”。我們使用狀態(tài)圖來直觀圖示有限自動(dòng)機(jī)。狀態(tài)圖是有向圖，它由一組矢量線連接的有限個(gè)結(jié)點(diǎn)組成。結(jié)點(diǎn)用圓圈表示，代表識(shí)別單詞后詞法分析器所處的狀態(tài)，狀態(tài)的名字或者編號(hào)寫在圓圈中。有限自動(dòng)機(jī)有一個(gè)初始態(tài)和多個(gè)終態(tài)，終態(tài)通常用雙圓圈表示，以示和其他狀態(tài)的區(qū)別。狀態(tài)之間由稱為“邊”的帶箭頭的 弧連接，我們在邊上寫上指示輸入字符的標(biāo)記，通常標(biāo)記用一個(gè)字符 表示，它表示當(dāng)詞法分析器所處的狀態(tài)可能會(huì)引入該邊的結(jié)點(diǎn)時(shí)可能會(huì)掃描到的字符，當(dāng)詞法分析器進(jìn)入了這個(gè)結(jié)點(diǎn)，則會(huì)有邊指示下一個(gè)狀態(tài)。如果有些情況出現(xiàn)需要回退一個(gè)結(jié)點(diǎn)時(shí)，我們就在終態(tài)的右上角加一個(gè) ” * ” 。從一個(gè)狀態(tài)轉(zhuǎn)換圖的初態(tài)出發(fā)到某一個(gè)終態(tài)，遍歷這個(gè)路徑可以識(shí)別一定的字符串。如圖 34 表示了由字母開頭后跟數(shù)字或者字母組成的標(biāo)示符的轉(zhuǎn)換圖 圖 34 標(biāo)示符的狀態(tài)轉(zhuǎn)換圖 有限自動(dòng)機(jī)可以分為確定的有限自動(dòng)機(jī) (Deterministic Finite Automata, DFA)和不確定的有限自動(dòng)機(jī) (Nondeterministic Finite Automata, NFA) [7]。它們的區(qū)別就在于自動(dòng)機(jī)在識(shí)別過程中下一個(gè)狀態(tài)是否是確定的。如果對(duì)于同一個(gè)字符有若干個(gè)下一個(gè)狀態(tài)，那么這就是不確定的有限自動(dòng)機(jī)；如果只有一個(gè)下一個(gè)狀態(tài)，那么就是確定的有限自動(dòng)機(jī)。不確定的有限