計算機科學(xué)與技術(shù)專業(yè)學(xué)位論文-一種自適應(yīng)的Prolog編譯器

1、密級： 保密期限： 碩士研究生學(xué)位論文 題目: 一種自適應(yīng)的Prolog編譯器 學(xué) 號： 106894 姓 名： 高慧 專 業(yè)： 計算機科學(xué)與技術(shù) 導(dǎo) 師： 劉知青 學(xué) 院： 軟件學(xué)院 2012年 12月 31日獨創(chuàng)性（或創(chuàng)新性）聲明本人聲明所呈交的論文是本人在導(dǎo)師指導(dǎo)下進(jìn)行的研究工作及取得的研究成果。盡我所知，除了文中特別加以標(biāo)注和致謝中所羅列的內(nèi)容以外，論文中不包含其他人已經(jīng)發(fā)表或撰寫過的研究成果，也不包含為獲得北京郵電大學(xué)或其他教育機構(gòu)的學(xué)位或證書而使用過的材料。與我一同工作的同志對本研究所做的任何貢獻(xiàn)均已在論文中作了明確的說明并表示了謝意。申請學(xué)位論文與資料若有不實之處，本人承擔(dān)一切相

2、關(guān)責(zé)任。本人簽名： 日期： 關(guān)于論文使用授權(quán)的說明學(xué)位論文作者完全了解北京郵電大學(xué)有關(guān)保留和使用學(xué)位論文的規(guī)定，即：研究生在校攻讀學(xué)位期間論文工作的知識產(chǎn)權(quán)單位屬北京郵電大學(xué)。學(xué)校有權(quán)保留并向國家有關(guān)部門或機構(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)的Prolo

3、g編譯器摘 要Prolog程序語言是一種建立在邏輯學(xué)理論基礎(chǔ)之上的語言，最初Prolog程序語言被應(yīng)用在自然語言等研究領(lǐng)域?，F(xiàn)在它可以用來建造專家系統(tǒng)、智能知識庫、自然語言理解等廣泛的人工智能的研究中，同時它也可以幫助到一些常用應(yīng)用程序的編寫。這是因為Prolog的編程方法更像是使用邏輯語言來描述程序，它能夠比其他語言更快速地開發(fā)程序。隨著人工智能的興起，越來越多的人開始探索各種人工智能技術(shù)。其中Prolog程序語言作為較早的代表，更是受人追捧。傳統(tǒng)的Prolog編譯器只能按照程序的書寫順序從上到下匹配，如果寫在上面的謂詞十分難解，而非常好解的謂詞卻寫在了下面，那么Prolog解這個程序就需要

4、一些時間。這也就是傳統(tǒng)Prolog編譯器的短板。如果在Prolog編譯器中加入Prolog匹配的“指導(dǎo)思想”告訴Prolog編譯器應(yīng)該選哪個謂詞，進(jìn)而Prolog在尋找答案的時候就不會僅憑程序員的個人習(xí)慣和概率來左右其得到答案的效率了。本文主要研究工作如下：首先本文大致討論人工智能和專家系統(tǒng)的定義和Prolog語言的組成特點。其次講述Prolog編譯器的開發(fā)方法。本文采用Flex詞法分析器用于Prolog的詞法開發(fā)，用正則表達(dá)式識別需要傳遞給語法分析器的記號。采用Bison用于其語法開發(fā)并在Bison中使用自頂向下的LL(1)文法。使用哈希這種數(shù)據(jù)結(jié)構(gòu)來組織符號表，并用拉鏈法來處理符號表中遇到

5、的沖突。由于本文要用到Flex和Bison的結(jié)合使用，而且是要識別一整個程序，所以詞法分析器Flex和語法分析器Bison結(jié)合的特殊性也在研究范圍之內(nèi)。最后針對Prolog匹配出現(xiàn)的一些缺點，提出了利用UCB策略改進(jìn)其匹配方式，試圖使其高效率得出最優(yōu)解。關(guān)鍵詞：Prolog 編譯器 程序語言 UCB 自適應(yīng)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課題的研究內(nèi)容21.3課題的意義21.3.1人工智能的概念及研究意義21.3.2專家系統(tǒng)的概念及

13、研究意義21.3.3Prolog程序語言的重要性31.4論文主要工作3第二章Prolog理論基礎(chǔ)4第三章詞法分析的實現(xiàn)63.1正則表達(dá)式83.2有限自動機93.3Flex93.4用Flex實現(xiàn)Prolog的詞法分析113.5小結(jié)13第四章語法分析的實現(xiàn)144.1上下文無關(guān)文法144.2句型分析184.3Bison234.4用Bison實現(xiàn)Prolog的語法分析244.5詞法分析器Flex和語法分析器Bison的結(jié)合274.6二義性沖突274.7小結(jié)30第五章語義分析的實現(xiàn)315.1語義分析315.1.1靜態(tài)語義檢查315.1.2屬性文法325.2符號表335.2.1符號的主要屬性及作用345.

14、2.2符號表的總體組織395.2.3符號表項的排列395.3符號表的實現(xiàn)425.4小結(jié)43第六章Prolog知識庫的搜索引擎的實現(xiàn)446.1Prolog基本運算方法446.1.1深度優(yōu)先算法446.1.2合一446.1.3回溯446.2存儲組織和匹配算法456.2.1棧式動態(tài)存儲分配456.2.2簡單的棧式存儲分配的實現(xiàn)466.3小結(jié)51第七章Prolog編譯器的改進(jìn)527.1UCB527.1.1馬爾科夫決策過程527.1.2蒙特卡羅537.1.3蒙特卡羅規(guī)劃547.1.4多臂匪徒模型557.2小結(jié)57第八章總結(jié)和展望58參考文獻(xiàn)60致 謝62攻讀學(xué)位期間發(fā)表的學(xué)術(shù)論文63 59 第1章 緒論

15、1.1 研究背景比爾蓋茨曾經(jīng)預(yù)言未來家家都有機器人，未來人工智能將會飛速的發(fā)展。人工智能是一個含義很廣的詞語，具有不同學(xué)科背景的人工智能學(xué)者在其發(fā)展過程中對它有著不同的理解并提出了一些不同的觀點。從能力的角度看，相對于人類自有的自然智能，人工智能是指在機器上用人工的方法實現(xiàn)的智能；從學(xué)科的角度看，作為一個學(xué)科的名稱來定義人工智能。所謂人工智能是一門研究如何構(gòu)造智能機器或智能系統(tǒng)，使它能夠模擬、延伸和擴展人類智能的學(xué)科1。關(guān)于人工智能研究的目標(biāo)，到目前為止還沒有一個統(tǒng)一的看法。1978年索羅門(A. Sloman)對人工智能給出了三個主要目標(biāo)：1)對智能行為進(jìn)行有效解釋的理論分析；2)解釋人類自

16、有智能；3)構(gòu)造智能的人工產(chǎn)品。經(jīng)過幾十年的發(fā)展，人工智能有了不小的進(jìn)步，現(xiàn)在人工智能已經(jīng)從單一的方向擴展到定理證明、專家系統(tǒng)、機器學(xué)習(xí)、自然語言理解、智能檢索、自動程序設(shè)計、機器人學(xué)、模式識別、組合調(diào)度問題、機器視覺各個方向。目前能夠研究人工智能的技術(shù)平臺就是計算機，用計算機來模擬人的某些行為和思維過程。在60年代出現(xiàn)了Prolog程序語言，它是建立在邏輯學(xué)理論基礎(chǔ)之上，最初Prolog程序語言被應(yīng)用在自然語言等研究領(lǐng)域。現(xiàn)在它可以用來建造專家系統(tǒng)、智能知識庫、自然語言理解等廣泛的人工智能的研究中，同時它也可以幫助到一些常用應(yīng)用程序的編寫。這是因為Prolog的編程方法更像是使用邏輯語言來描

17、述程序，它能夠比其他語言更快速地開發(fā)程序?，F(xiàn)階段的Prolog使用深度優(yōu)先搜索的策略。它從給它提出的問題即“當(dāng)前目標(biāo)”開始，在搜索過程中系統(tǒng)保存著這個當(dāng)前目標(biāo)，并且“從左至右”的完成目標(biāo)。系統(tǒng)總是首先完成第一個子目標(biāo)，如果第一個子目標(biāo)完成不了，整個問題就沒有答案，而第二個子目標(biāo)根本不會去嘗試。當(dāng)解決一個特定的子目標(biāo)時，對事實和規(guī)則的試探總是自頂向下的。簡單的說：Prolog總是從上到下從左到右以深度優(yōu)先為主工作的。在Prolog的規(guī)則中也有析取和合取的問題（合取關(guān)系用“，”表示，析取關(guān)系用“；”表示），現(xiàn)階段的Prolog運算時間和人工輸入有很大關(guān)系，假設(shè)一個合取關(guān)系中有為假的合取項，而且它是

18、規(guī)則體的第一子目標(biāo)，那么計算它耗費時間就相對要少。若要是這一個為假的合取項不是規(guī)則體的第一個子目標(biāo)，而且規(guī)則體第一個子目標(biāo)很難解，這就使整個程序要花費一段時間才能得到答案。也就是說現(xiàn)在Prolog的一個大問題是深度優(yōu)先搜索的效率問題。1.2 課題的研究內(nèi)容本課題立足于Prolog編譯器的開發(fā)，在人工智能的大背景下，著重詳細(xì)論述了一個可擴展的Prolog編譯器的實現(xiàn)，其中包括了詞法分析、語法分析、語義分析，以及Prolog知識庫的搜索引擎的實現(xiàn)，包括深度優(yōu)先搜索算法、合一算法、匹配算法等關(guān)鍵模塊。論文也討論了改進(jìn)Prolog知識庫的搜索方法。其中詞法分析和語法分析使用Flex和Bison工具開發(fā)

19、，在匹配問題中使用的是樹的匹配，搜索方法由原來的深度優(yōu)先改進(jìn)為最優(yōu)優(yōu)先搜索。1.3 課題的意義1.3.1 人工智能的概念及研究意義所謂的“人工智能”是指人們通過計算機模擬或?qū)崿F(xiàn)的智能2。很遺憾因為人工智能還在被人們探索和研究所以到現(xiàn)在為止人工智能還沒有像其他成熟學(xué)科一樣形成一套比較完整的理論體系，經(jīng)過發(fā)展現(xiàn)在有一些技術(shù)已經(jīng)開始應(yīng)用人工智能，比如推理技術(shù)、搜索技術(shù)、聯(lián)想技術(shù)等。人工智能語言是一類適應(yīng)于人工智能和知識工程領(lǐng)域的、具有符號處理和邏輯推理能力的計算機程序設(shè)計語言3。能夠用它來編寫程序求解非數(shù)值計算、知識處理、推理、規(guī)劃、決策等具有智能的各種復(fù)雜問題。在未來人工智能領(lǐng)域會改變?nèi)藗兊纳罘?/p>

20、式，許多大的企業(yè)，如谷歌、微軟和蘋果都在努力探索人工智能領(lǐng)域。1.3.2 專家系統(tǒng)的概念及研究意義專家系統(tǒng)（Expert System）是一種用計算機程序來模擬人類專家解決某些特定領(lǐng)域問題的系統(tǒng)4。因為某個領(lǐng)域大量的專家水平的知識與經(jīng)驗被記錄到專家系統(tǒng)內(nèi)部，所以系統(tǒng)能夠通過運用人類專家的專業(yè)知識和解決專業(yè)問題的方法，模擬人類專家判斷推理和決策過程，來解決該領(lǐng)域的復(fù)雜問題。自從1965年在美國斯坦福大學(xué)第一個專家系統(tǒng)問世以來，專家系統(tǒng)在人工智能應(yīng)用研究中表現(xiàn)的最廣泛和最活躍?，F(xiàn)如今存在著許多種不同的專家系統(tǒng)，這些專家系統(tǒng)已影響著各個專業(yè)領(lǐng)域并且獲得很大的成功。專家系統(tǒng)按任務(wù)分類可分為：診斷型、解

21、釋型、調(diào)試型、教育型、預(yù)測型、規(guī)劃型、控制型、設(shè)計型、監(jiān)測型。1.3.3 Prolog程序語言的重要性Prolog語言屬于一種人工智能語言，21世紀(jì)注定是屬于人工智能的時代。在經(jīng)過了幾十年的發(fā)展，雖然Prolog語言已經(jīng)在例如機器定理證明和專家系統(tǒng)等方面體現(xiàn)了重要的作用，但是幾乎主流的Prolog編譯器除了界面和編寫語言不同之外，沒有什么實質(zhì)性的創(chuàng)新，它們都是隨機的選取合一的謂詞進(jìn)行深度優(yōu)先的計算，有時由于隨機出的謂詞很難得到結(jié)果而影響到編譯器的效率。本文提出的方法是更改Prolog編譯器的搜索引擎，使其由原來的深度優(yōu)先變成最有優(yōu)先算法，進(jìn)而提高其計算效率。1.4 論文主要工作本文從開發(fā)傳統(tǒng)P

22、rolog編譯器開始，包括從詞法分析器的組織到最后匹配算法。本文的組織結(jié)構(gòu)如下：第一章 緒論。對論文研究背景對論文的主要研究工作做以概述，并闡明整篇文章的組織結(jié)構(gòu)。第二章 理論基礎(chǔ)。闡述Prolog語言的組成部分，為下文做鋪墊。第三章 詞法分析的實現(xiàn)。首先介紹什么是詞法分析，詞法分析的原理及程序中哪些記號需要被分析出來，然后用Flex詞法編輯器來實現(xiàn)Prolog編譯器的詞法分析部分。第四章 語法分析的實現(xiàn)。首先介紹了語法分析在整個編譯過程中的位置，然后介紹本文要用到的文法規(guī)則，最后用Bison語法分析器來實現(xiàn)Prolog編譯器的語法分析部分。第五章 語義分析的實現(xiàn)。首先說明了語義分析需要檢查的

23、定義，然后介紹了符號表的作用及組織方法，最后論述了符號表的實現(xiàn)。第六章 Prolog知識庫的搜索引擎的實現(xiàn)。首先論述Prolog基本運算方法包括深度優(yōu)先搜索算法、合一算法、匹配算法等關(guān)鍵模塊，然后存儲組織和匹配算法在最后論述。第七章 Prolog編譯器的改進(jìn)。通過馬爾科夫決策、蒙特卡羅法、蒙特卡羅規(guī)劃和多臂匪徒模型引出了UCB決策策略，UCB算法是自適應(yīng)Prolog編譯器的核心部分，有了它才可以使Prolog編譯器知道應(yīng)該選擇匹配哪個謂詞。第八章 總結(jié)與展望。對論文工作進(jìn)行總結(jié)，并對下一步工作方向做出展望。第2章 Prolog理論基礎(chǔ)Prolog的基本語句有：事實、規(guī)則、目標(biāo)這三種類型語句5。

24、它們都用一種叫做“謂詞”的形式表示，所謂謂詞就是由一個謂詞名和一些參數(shù)組成。因為謂詞清楚簡單，語句類型少，因而文法簡捷，程序邏輯性強，清晰易懂。Prolog是陳述性語言，只要必要的事實和規(guī)則提交，它不需要在程序中列出詳細(xì)的求解步驟就能使用內(nèi)部的演繹推理機制自動求解程序給定的目標(biāo)。Prolog程序語言的基本語句說明如表2-1所示語句組成方式例子說明事實事實是一種用來說明問題中已知的對象和它們之間關(guān)系的謂詞，在Prolog程序中，事實由謂詞名及用小括號括起來的一個或幾個對象組成例如eat(alex，apple).表示是一個名為eat的關(guān)系，表示alex吃蘋果這個事實。規(guī)則規(guī)則是由幾個謂詞或者說簡單

25、句組成并且他們之間有依賴性存在，事實與事實間的類似于依賴的關(guān)系被規(guī)則所描述。規(guī)則的組成很簡單，它一般由兩部分組成：左邊是規(guī)則頭，表示結(jié)論，而右邊是規(guī)則體，表示條件的前提。例如bird(X):-animal(X),has(X,feather).表示凡是有羽毛的動物就是鳥。目標(biāo)目標(biāo)即是詢問，一旦事實和規(guī)則被寫進(jìn)Prolog程序中之后，Prolog就準(zhǔn)備好被詢問有關(guān)問題了，這個時候程序的運行目標(biāo)就是用戶詢問的問題。目標(biāo)分內(nèi)、外兩種，外部目標(biāo)需要在程序運行時手工鍵入，內(nèi)部目標(biāo)需要寫在程序中。目標(biāo)的結(jié)構(gòu)與事實或規(guī)則一樣，它可以是多個謂詞的組合，或者是一個簡單的謂詞。例如?-student(alex).表

26、示“alex是學(xué)生嗎？”Prolog可以在知道一些已知的事實的前提下通過邏輯推理得出一些未直接給出的事實。一個Prolog程序在典型情況下并不是一個動作序列，它是通過聚合在一起的事實和規(guī)則，由規(guī)則從那些事實中得出結(jié)論。表2-1 Prolog程序語言基本組成Prolog的基本組成理論是研究開發(fā)Prolog編譯器的基礎(chǔ)，只有了解其組成才能根據(jù)其特點來開發(fā)適合的編譯器。第3章 詞法分析的實現(xiàn)詞法分析是編譯工作的第一個階段。詞法分析器的主要任務(wù)是從左到右將讀入源程序的輸入字符組成詞素。所謂詞素是源程序中的一個字符序列，它和某個詞法單元的模式匹配，并被詞法分析器識別為該詞法單元的一個實例6。在組成詞素后

27、，詞法分析器生成并輸出一個詞法單元序列即TOKEN，每個詞法單元對應(yīng)于一個詞素。然后語法分析器對這個詞法單元序列進(jìn)行語法分析。詞法分析階段將讀入源程序的輸入字符組成詞素。詞素類似于自然語言的單詞，單詞可以分為名詞、動詞和形容詞等不同類型，詞素也可以用一些規(guī)則進(jìn)行劃分，我們把劃分詞素的規(guī)則稱為模式。模式和詞素組成了詞法單元。詞法單元有一個詞法單元名。詞素、模式和詞法單元之間的關(guān)系可以如表3-1所示詞法單元模式的非正式描述詞素舉例number任何數(shù)值常數(shù)3.14159，10relation，=或或=string在兩個”之間，除”之外的任何字符“Hello World”separator(，)，,(

28、或)或,date方括號內(nèi)的字符序列2008-01-01 15:30:00表3-1詞素、模式和詞法單元的關(guān)系詞法分析器除了識別詞法單元之外，還要完成其他的一些任務(wù)，比如：進(jìn)行詞法檢查發(fā)現(xiàn)錯誤要報告所發(fā)現(xiàn)的錯誤；為了后續(xù)語法分析發(fā)現(xiàn)錯誤之后能給出正確的位置，詞法分析器需要提交詞法單元的位置；識別字符復(fù)合而成的算符和邊界符，并把它們合并成完整的單詞符號；略去沒用過的空白字符等。根據(jù)詞法分析器與語法分析器協(xié)同的方式不同，詞法分析器在整個詞法分析階段有不同的工作方式：1) 詞語法分析器并行工作，詞法分析器將記號提交到一個隊列中供語法分析器調(diào)用。其工作方式如圖3-1所示：圖3-1并行工作方式2) 詞法分析

29、器單獨工作，這種方式就是詞法分析器單獨進(jìn)行一遍掃描，這期間語法分析器不會工作，詞法分析器識別出各個單詞并轉(zhuǎn)換成語法分析器需要的記號，然后將記號作為語法分析器的輸入供語法分析器調(diào)用，它的工作方式如圖3-2所示： 圖3-2詞法分析器獨立工作3) 這種方式中詞法分析器是語法分析器的子程序，詞法分析器先分析出一個記號，然后記錄斷點，并把記號提供給語法分析器調(diào)用，當(dāng)語法分析器分析完當(dāng)前的記號之后，它就會給詞法分析器一個信號，使詞法分析器從斷點處繼續(xù)分析記號然后供語法分析器調(diào)用。這中工作方式如圖3-3：圖3-3 作為子程序的詞法分析器的工作方式正規(guī)式和有限自動機是描述詞法規(guī)則的有效工具。3.1 正則表達(dá)式

30、我們用叫做“模式”的規(guī)則來描述字符串集合。這里用正則表達(dá)式來表示規(guī)則。正則式是一種十分有效的工具，尤其是描述詞素的組成結(jié)構(gòu)。正則表達(dá)式通過使用元語言(metalanguage)來表達(dá)編程人員想要匹配的模式。它一般使用標(biāo)準(zhǔn)的文本字符，其中一部分代表模式而另外一部分則代表他們自身。在正則表達(dá)式中有特殊意義的字符為： 如果它是正則表達(dá)式的第一個字符就匹配行首。它也被用于方括號中表示補集。 字符類(character class)，可以匹配方括號中的任意一個字符。如果字符類中的第一個字符是抑揚符號()，則改變?yōu)槠ヅ涑嚼ㄌ杻?nèi)字符以外的任何字符。字符類里的破折號表示字符的范圍，例如，0-9意味著1234

31、56789而a-z則表示任意小寫字母。$ 如果它是正則表達(dá)式的最后一個字符就匹配行尾。 當(dāng)花括號中帶有一個或者兩個數(shù)字時，它表示前一個模式可以匹配的最小和最大次數(shù)。例如，A1,3匹配一到三個字母A，而05匹配00000.當(dāng)花括號中帶有名字時，它指向以這個名字命名的模式。 用來表示元字符自身和一部分常用的C語言轉(zhuǎn)義序列。例如，n表示換行符，而*則是字面意義上的星號。* 匹配零個或者多個緊接在前面的表達(dá)式。例如， t*可以匹配任意多個空格和tab，也就是空白字符，它能夠匹配” ”、”或者一個空字符串。+ 匹配一個或者多個緊接在前面的表達(dá)式。例如，0-9+可以匹配數(shù)字字符串，像1,1111或者123

32、4，但不能是一個空字符。? 匹配零個或者一個緊著在前面的表達(dá)式。例如，-?0-9+匹配一個有符號數(shù)字，它帶有一個可選的前置負(fù)號。| 選擇操作符，匹配緊著在前面的表達(dá)式或者緊跟在后面的表達(dá)式。“” 所有引號中的字符將基于字面意義被解釋。不屬于C轉(zhuǎn)義序列的元字符將失去它的特殊意義。() 把一系列的正則表達(dá)式組成一個新的正則表達(dá)式。例如，(01)匹配字符序列01，而a(bc|de)匹配abc或者ade。/ 尾部上下文，匹配斜線前的正則表達(dá)式，但是要求其后緊跟著斜線后的表達(dá)式。例如，0/1匹配字符串01中的0，但是不會匹配字符串0或者02.斜線后匹配的內(nèi)容不會被“消耗掉”，它們會返還給輸入以便于繼續(xù)匹

33、配。每個模式只允許一個尾部上下文操作符。正確識別正則式的方法有幾種，我們可以使用有限自動機(Finite Automata)來識別，也可以使用Lex（Flex）詞法分析器來識別。3.2 有限自動機用有限自動機識別正則式只能對每個字符串回答” Yes ” or “ No ”。我們使用狀態(tài)圖來直觀圖示有限自動機。狀態(tài)圖是有向圖，它由一組矢量線連接的有限個結(jié)點組成。結(jié)點用圓圈表示，代表識別單詞后詞法分析器所處的狀態(tài)，狀態(tài)的名字或者編號寫在圓圈中。有限自動機有一個初始態(tài)和多個終態(tài)，終態(tài)通常用雙圓圈表示，以示和其他狀態(tài)的區(qū)別。狀態(tài)之間由稱為“邊”的帶箭頭的弧連接，我們在邊上寫上指示輸入字符的標(biāo)記，通常標(biāo)

34、記用一個字符表示，它表示當(dāng)詞法分析器所處的狀態(tài)可能會引入該邊的結(jié)點時可能會掃描到的字符，當(dāng)詞法分析器進(jìn)入了這個結(jié)點，則會有邊指示下一個狀態(tài)。如果有些情況出現(xiàn)需要回退一個結(jié)點時，我們就在終態(tài)的右上角加一個” * ” 。從一個狀態(tài)轉(zhuǎn)換圖的初態(tài)出發(fā)到某一個終態(tài)，遍歷這個路徑可以識別一定的字符串。如圖3-4表示了由字母開頭后跟數(shù)字或者字母組成的標(biāo)示符的轉(zhuǎn)換圖圖3-4 標(biāo)示符的狀態(tài)轉(zhuǎn)換圖有限自動機可以分為確定的有限自動機(Deterministic Finite Automata, DFA)和不確定的有限自動機(Nondeterministic Finite Automata, NFA) 7。它們的區(qū)別

35、就在于自動機在識別過程中下一個狀態(tài)是否是確定的。如果對于同一個字符有若干個下一個狀態(tài)，那么這就是不確定的有限自動機；如果只有一個下一個狀態(tài)，那么就是確定的有限自動機。不確定的有限自動機可以轉(zhuǎn)換成等價的確定有限自動機。3.3 Flex詞法分析器Flex通過識別正則表達(dá)式然后將輸入流分解為若干個記號(token)提供給程序使用。Flex程序由定義部分、規(guī)則部分和用戶子例程三部分構(gòu)成。這三部分被由兩個百分號組成的行分隔。其中前兩個部分是必須的、一定要有的，但它們的內(nèi)容可以為空。它們的基本格式如下所示：.定義部分.%.規(guī)則部分.%.用戶子例程.其中，定義部分包含文字塊、選項、開始條件、定義和轉(zhuǎn)換等。規(guī)

36、則部分包括C代碼和模式行。處于%和%之間的內(nèi)容或者直接以空白字符開始則被認(rèn)為是C代碼，它們會被原樣不動地拷貝到y(tǒng)ylex()例程中，yylex()例程與調(diào)用記號(token)有關(guān)，大多數(shù)包含F(xiàn)lex詞法分析器的程序為了方便語法分析器的處理都使用詞法分析器來獲得一個記號流。每次當(dāng)程序需要一個記號時，yylex()就會被調(diào)用來讀取一小部分輸入，然后返回相應(yīng)的記號。當(dāng)程序需要下一個新記號時，yylex()會被再次調(diào)用并返回記號。那些出現(xiàn)在規(guī)則部分開頭的C代碼也會相應(yīng)出現(xiàn)在yylex()的開頭，它可以包含詞法分析器中需要使用的變量的聲明，以及每次調(diào)用yylex()所需要運行的代碼。當(dāng)Flex詞法分析器

37、運行時，每次它發(fā)現(xiàn)一個符合規(guī)則部分模式的匹配，和這個模式所關(guān)聯(lián)的C代碼就會被執(zhí)行。如果模式后面緊跟的不是C代碼而是一個豎線的話，這個模式就會使用它下面模式的C代碼。當(dāng)任何模式與輸入字符無法匹配時，詞法分析器就認(rèn)為它匹配了一個動作代碼為ECHO的模式（宏ECHO是用來把記號輸出到當(dāng)前的輸出文件yyout中），相應(yīng)的，詞法分析器輸出該記號8。Flex詞法分析器器原樣拷貝用戶子例程的內(nèi)容到C文件。這個部分通常包含規(guī)則中所需要調(diào)用的例程。Flex的工作流程如圖3-5所示：圖3-5 Flex的工作流程本課題詞法分析擬用Flex（GNU下的Lex）來實現(xiàn)。3.4 用Flex實現(xiàn)Prolog的詞法分析根據(jù)P

38、rolog的定義以及本課題自身的情況特點，在詞法分析階段Flex詞法分析器需要識別出由大寫字母開頭的變量、小寫字母及單引號開頭的常量、整數(shù)、浮點數(shù)、特殊字符等。本課題在Flex定義部分除了必要的C代碼和與語法分析器Bison連接的代碼之外，為了方便管理還把一些過長的正則式用簡短的名字代替，如變量variable：(A-Z(_|A-Z|0-9|a-z)*)|_常量name：(a-z(_|A-Z|0-9|a-z)*)|(.*)整數(shù)natural_number: -+?0-9+空格whitespace： t+浮點數(shù)float_number：-+?0-9+.0-9+回車換行EOL：n在規(guī)則部分寫出了詞

39、法分析器需要識別出的符號，它們?nèi)绫?-2所示：詞法符號C代碼表示的意義+return PLUS;識別標(biāo)準(zhǔn)符號-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;識別規(guī)則符號?-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();結(jié)束.printf(bad input character %s at line %dn,yytext,yylineno);表3-2詞法分析器需要識別出的符號Flex和Bison配合使用有兩個問題要解決：一個是它們的銜接問題，F(xiàn)lex怎么把找到的元素傳給Bison用于語法分析，Bison如何通知Flex繼續(xù)尋找元素；第二個問題就是如何使它們可以重入。就Flex這部分

42、來說，在定義部分要包含Bison的頭文件，F(xiàn)lex詞法分析器需要識別的元素也不需要在Flex定義階段給出，它們而是由Bison語法分析器定義。為了使Flex詞法分析器支持可重入，需要在定義部分加入可以使可重入詞法語法分析器相兼容的文件，使可重入的詞法分析器的調(diào)用方法可以和Bison兼容。由于詞法分析器只是整個編譯器的一部分，所以它的用戶子例程部分為空。3.5 小結(jié)本章節(jié)先講述了詞法分析的理論以及Flex詞法分析器的特點，然后論述了根據(jù)Prolog語言的詞法特點用Flex詞法分析器開發(fā)Prolog編譯器的詞法分析部分。第4章 語法分析的實現(xiàn)闡明語法的一個工具是文法。文法G定義為四元組（VN,VT

43、,P,S）。其中，VN是一個非空有限非終結(jié)符集；VT是一個非空有限終結(jié)符集；P是規(guī)則（）的有限集合，VNVT*被稱為規(guī)則的左部，VNVT*被稱為規(guī)則的右部，S是開始符號必須至少要在某個規(guī)則中作為左部出現(xiàn)。VNVT=，即VN和VT不含公共的元素。詞法分析的問題實際上是識別正則表達(dá)式的問題。語法分析的主要任務(wù)是在詞法分析的基礎(chǔ)上判斷表達(dá)式的語法結(jié)構(gòu)是不是符合文法規(guī)則。語法分析器從詞法分析器獲得一個由詞法單元組成的串，并驗證這個串是否可以由源語言的文法生成9，如圖4-1所示。有些表達(dá)式雖然能滿足詞法分析的要求，但是不符合文法規(guī)則，這樣的表達(dá)式就不能構(gòu)成有效的表達(dá)式。我們期望語法分析器報告的語法錯誤能

44、夠易于理解，我們還期望語法分析器能夠從一些常見的錯誤中回復(fù)過來并且能夠繼續(xù)處理程序剩下的部分。圖4-1編譯器模型中語法分析器的位置4.1 上下文無關(guān)文法上下文無關(guān)文法（Content-free Grammar）是程序設(shè)計語言的語法分析常用的文法規(guī)則，上下文無關(guān)文法在命名慣例和運算上與正則表達(dá)式極為類似10。上下文無關(guān)文法區(qū)別于正則表達(dá)式是它使用遞歸的規(guī)則，例如，while語句結(jié)構(gòu)中可以嵌套其他的while語句，這在正則表達(dá)式中是不允許的。由于這個區(qū)別，上下文無關(guān)文法識別的結(jié)構(gòu)類別要多于正則表達(dá)式識別的結(jié)構(gòu)類。因為上下文無關(guān)文法必須使用遞歸調(diào)用或者顯式管理的分析棧，所以上下文無關(guān)文法用作識別這些

45、結(jié)構(gòu)的算法也與掃描算法差別很大。上下文無關(guān)文法經(jīng)常使用的基本結(jié)構(gòu)是語法樹（syntax tree）。有這樣一個上下文無關(guān)文法G=（E，+，*，i，(，)，P，E）其中P為:EiEE+EEE*EE(E)這里的非終結(jié)符E表示一類算術(shù)表達(dá)式。i表示程序設(shè)計語言中的“變量”，該文法定義了由變量、+、*、(和)組成的算術(shù)表達(dá)式的語法結(jié)構(gòu)，即：變量也是算術(shù)表達(dá)式；如果E1和E2是算術(shù)表達(dá)式，那么E1*E2、E1+E2和E1也都是算術(shù)表達(dá)式。當(dāng)然，上面的文法也可以寫成Ei|E+E| E+E|(E)。文法G=（VN,VT,P,S）給定，對于G的任何句型我們都能構(gòu)造相關(guān)聯(lián)的語法樹，語法樹應(yīng)該滿足下面4個條件：1

46、) S是樹根2) 每個結(jié)點都有一個V的符號作為標(biāo)記3) 如果一個結(jié)點n除它自己外還有至少一個有標(biāo)記A的子孫，那么A肯定在VN中4) 若結(jié)點n的直接子孫從左到右的次序是n1，n2，nk，并且對應(yīng)的標(biāo)記分別為A1,A2,Ak，那么P中一定有產(chǎn)生式AA1A2Ak。再看一個上下文谷關(guān)文法的例子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)的推導(dǎo)樹從這課語法樹知頂端結(jié)點S是樹根，a，A和S這三個結(jié)點是它的直接子孫，樹的第1、2層表示的是產(chǎn)生式SaAS。類似于S，結(jié)點A除它自己外還有別的子

47、孫，所以A肯定是非終結(jié)符。圖非常直觀自然的描述文法G的句型aabbaa的推導(dǎo)過程，即語法樹的葉子結(jié)點。由于語法樹只表示出了在推導(dǎo)過程中哪有非終結(jié)符使用哪個產(chǎn)生式，它并沒有產(chǎn)生式的使用順序。對文法G的句型aabbaa的推導(dǎo)可以有3個不同推導(dǎo)過程：1) S aAS aSbAS aabAS aabbaS aabbaa2) S aAS aAa aSbAa aSbbaa aabbaa3) S aAS aSbAS aSbAa aabAa aabbaa第一個推導(dǎo)過程在推導(dǎo)中使用產(chǎn)生式替換當(dāng)前串中的最左非終結(jié)符，使用產(chǎn)生式的順序是1、2、4、5、4。而第二個推導(dǎo)過程使用產(chǎn)生式替換當(dāng)前串中的最右非終結(jié)符，使用產(chǎn)

48、生式的順序是1、4、2、5、4。如果對于句型、，在推導(dǎo)中都是替換的最左非終結(jié)符，那么這種推導(dǎo)就是最左推導(dǎo)。上述第1個推導(dǎo)即為最左推導(dǎo)。同理，替換的都是最右非終結(jié)符那就是最右推導(dǎo)。例如上述第1個推導(dǎo)。最右推導(dǎo)又叫做規(guī)范推導(dǎo)，所到的句型叫做規(guī)范句型。有時候同一個文法會有不同的語法樹，比如文法G=（E，+，*，i，(，)，P，E）中句型i*i+i就可以有兩個不同的最左推導(dǎo)：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這兩個推導(dǎo)對應(yīng)的語法樹如圖4-3、4-4圖4-3 推導(dǎo)1的語法樹圖4-4 推導(dǎo)2的語法樹如果在一個文法中有

49、某個或者某些句子對應(yīng)不止一棵語法樹，那么這個文法是二義的。二義文法是分析程序表示的一個嚴(yán)重問題，因為它不能準(zhǔn)確的指出程序的語法結(jié)構(gòu)。二義性被認(rèn)為是一種語言語法不完善的說明，應(yīng)該避免它。解決二義性有兩個基本方法，第一個是在每個二義性情況下設(shè)置一個規(guī)則，用規(guī)則指出哪一個語法樹是正確的。我們把這樣的規(guī)則稱作消除二義性規(guī)則11。消除二義性規(guī)則的好處在于，有時候文法很復(fù)雜，它不需要修改文法就可以消除二義性。它的缺點是文法不能單獨提供語言的語法結(jié)構(gòu)。另一種方法是強制改變文法，把它改變成一個正確的語法樹。4.2 句型分析句型分析，就是識別一個符號串是否是某個文法的句型。句型分析的問題就是如何知道所給定的符號

50、串是文法的句型，是否是某個推導(dǎo)的構(gòu)造過程。句型分析是一個過程，該過程識別輸入符號串是否是語法上正確的程序。句型分析分為自頂向下分析和自底向上分析兩種方法。自頂向下分析：自頂向下的分析算法的分析順序是由根節(jié)點到葉子結(jié)點。常用的自頂向下的語法分析方法有兩種，這兩種方法是LL（1）分析法和遞歸子程序法。一、 LL（1）分析之所以叫LL（1），是因為第一個L指的是由左向右的處理輸入，第2個L是它使用的是最左推導(dǎo)，而括號中的數(shù)字1表示它使用輸入中的一個符號來預(yù)測分析的方向，總之用一句話總結(jié)LL（1）分析法的基本思想，就是在從左到右掃描源程序的同時從識別符號生成句子的最左推導(dǎo)，并且只要向前查看一個輸入符號

51、。LL（1）分析要求計算First集合Follow集。LL（1）分析法的分析程序由一個總控程序、一個符號棧S和一個分析表M構(gòu)成。不同的LL（1）分析法分析的文法程序，它們總控程序都是相同的，但是分析表M是不同的。文法的符號由符號棧S存放。當(dāng)文法和待分析符號串確定后，隨著語法分析過程符號棧的內(nèi)容也在不斷變化。由預(yù)先根據(jù)文法G設(shè)計的分析表M和符號棧S控制整個語法分析的過程。事實上并不是所有的上下文無關(guān)文法都可以用LL（1）進(jìn)行語法分析，如果想要用LL（1）分析，必須滿足幾個條件：第一，文法必須是不含有多余規(guī)則的文法；第二，文法不能有回溯；第三，文法不能有左遞歸。所以，有些文法想要滿足LL（1）文法

52、的要求就要經(jīng)過一些等價變換。變換操作包括去掉多余規(guī)則，消除能夠產(chǎn)生回溯的間接左遞歸，消除文法的直接左遞歸等。我們用符號串的推導(dǎo)的終結(jié)頭符號集First（x）和文法符號的后跟符號集Follow（U）來判斷一個文法是否是LL（1）文法。除了First和Follow集，還有一個表示First集或者First集和Follow集并集運算結(jié)果的Select集。判定文法是否是LL（1）文法可以分為兩種情況：一種是當(dāng)空符號串不屬于First集，只要每一條規(guī)則的不同右部的First集兩兩無交集這個條件滿足，那么可以判定這個文法是LL（1）文法。第二種就是當(dāng)空符號串屬于First集，空符號串ZFirst（x），如

53、果文法滿足該文法符號的Follow集與First集無交集和同一非終結(jié)符的右部的First集兩兩無交集的話，那么該文法也是LL（1）文法。A. 計算First集計算First集大致上分為兩種方法：第一種是根據(jù)First集的定義，第二種是由關(guān)系圖求First。1) 根據(jù)First集的定義計算的步驟有如下幾步對每一個文法符號XV由First集的定義計算First（X）。(1) 若XVT，那么First（X）=X。(2) 若XVN，且有產(chǎn)生式Xa，aVT，則aFirst（X）。(3) 若XVN，X，則First（X）。(4) 若X，Y1，Y2，Yn都屬于VN，而有產(chǎn)生式XY1Y2Yn。當(dāng)Y1，Y2，Y

54、i-1都*時，其中1in，則First（Y1）-，F(xiàn)irst（Y2）-，F(xiàn)irstYi-1-，F(xiàn)irstYi都包含在First（X）中。(5) 當(dāng)(4)中i=1,2，n時，所有Yi*，則First（X）=First(Y1)FirstY2FirstYn。反復(fù)使用上述2至5步直到每個符號的First集不再增大為止。若符號串V*，=X1X2Xn，當(dāng)X1*，則First（）=First（X1）。若對任何j（1ji-1，2in）First（Xj）；First（Xi），則First（）=j=1i-1（FirstXj-）First（Xi）。當(dāng)所有First（Xj）（1jn）都含有時，則First（）=j=1n(FirstXj)。2) 由關(guān)系圖法求文法符號的First集的步驟有如下幾步：(1) 文法圖中的每個結(jié)點代表一個文法符號，對應(yīng)非終結(jié)符的結(jié)點用First（S）來標(biāo)記，其