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

1、密級(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ā)表或撰寫(xiě)過(guò)的研究成果，也不包含為獲得北京郵電大學(xué)或其他教育機(jī)構(gòu)的學(xué)位或證書(shū)而使用過(guò)的材料。與我一同工作的同志對(duì)本研究所做的任何貢獻(xiàn)均已在論文中作了明確的說(shuō)明并表示了謝意。申請(qǐng)學(xué)位論文與資料若有不實(shí)之處，本人承擔(dān)一切相

2、關(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)書(shū)。非保密論文注釋：本學(xué)位論文不屬于保密范圍，適用本授權(quán)書(shū)。本人簽名： 日期： 導(dǎo)師簽名： 日期： 北京郵電大學(xué)碩士學(xué)位論文 2013一種自適應(yīng)的Prolo

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

4、一些時(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編譯器的開(kāi)發(fā)方法。本文采用Flex詞法分析器用于Prolog的詞法開(kāi)發(fā)，用正則表達(dá)式識(shí)別需要傳遞給語(yǔ)法分析器的記號(hào)。采用Bison用于其語(yǔ)法開(kāi)發(fā)并在Bison中使用自頂向下的LL(1)文法。使用哈希這種數(shù)據(jù)結(jié)構(gòu)來(lái)組織符號(hào)表，并用拉鏈法來(lái)處理符號(hào)表中遇到

5、的沖突。由于本文要用到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)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課題的研究?jī)?nèi)容21.3課題的意義21.3.1人工智能的概念及研究意義21.3.2專家系統(tǒng)的概念及

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

14、2.2符號(hào)表的總體組織395.2.3符號(hào)表項(xiàng)的排列395.3符號(hào)表的實(shí)現(xiàn)425.4小結(jié)43第六章Prolog知識(shí)庫(kù)的搜索引擎的實(shí)現(xiàn)446.1Prolog基本運(yùn)算方法446.1.1深度優(yōu)先算法446.1.2合一446.1.3回溯446.2存儲(chǔ)組織和匹配算法456.2.1棧式動(dòng)態(tài)存儲(chǔ)分配456.2.2簡(jiǎn)單的棧式存儲(chǔ)分配的實(shí)現(xiàn)466.3小結(jié)51第七章Prolog編譯器的改進(jìn)527.1UCB527.1.1馬爾科夫決策過(guò)程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ù)言未來(lái)家家都有機(jī)器人，未來(lái)人工智能將會(huì)飛速的發(fā)展。人工智能是一個(gè)含義很廣的詞語(yǔ)，具有不同學(xué)科背景的人工智能學(xué)者在其發(fā)展過(guò)程中對(duì)它有著不同的理解并提出了一些不同的觀點(diǎn)。從能力的角度看，相對(duì)于人類自有的自然智能，人工智能是指在機(jī)器上用人工的方法實(shí)現(xiàn)的智能；從學(xué)科的角度看，作為一個(gè)學(xué)科的名稱來(lái)定義人工智能。所謂人工智能是一門研究如何構(gòu)造智能機(jī)器或智能系統(tǒng)，使它能夠模擬、延伸和擴(kuò)展人類智能的學(xué)科1。關(guān)于人工智能研究的目標(biāo)，到目前為止還沒(méi)有一個(gè)統(tǒng)一的看法。1978年索羅門(A. Sloman)對(duì)人工智能給出了三個(gè)主要目標(biāo)：1)對(duì)智能行為進(jìn)行有效解釋的理論分析；2)解釋人類自

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

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

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

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

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

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

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

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

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

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

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

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

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

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

30、我們用叫做“模式”的規(guī)則來(lái)描述字符串集合。這里用正則表達(dá)式來(lái)表示規(guī)則。正則式是一種十分有效的工具，尤其是描述詞素的組成結(jié)構(gòu)。正則表達(dá)式通過(guò)使用元語(yǔ)言(metalanguage)來(lái)表達(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)表示字符的范圍，例如，0-9意味著1234

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

32、4，但不能是一個(gè)空字符。? 匹配零個(gè)或者一個(gè)緊著在前面的表達(dá)式。例如，-?0-9+匹配一個(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或者02.斜線后匹配的內(nèi)容不會(huì)被“消耗掉”，它們會(huì)返還給輸入以便于繼續(xù)匹

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

34、記用一個(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í)別一定的字符串。如圖3-4表示了由字母開(kāi)頭后跟數(shù)字或者字母組成的標(biāo)示符的轉(zhuǎn)換圖圖3-4 標(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ū)別

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

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

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

38、rolog的定義以及本課題自身的情況特點(diǎn)，在詞法分析階段Flex詞法分析器需要識(shí)別出由大寫(xiě)字母開(kāi)頭的變量、小寫(xiě)字母及單引號(hào)開(kāi)頭的常量、整數(shù)、浮點(diǎn)數(shù)、特殊字符等。本課題在Flex定義部分除了必要的C代碼和與語(yǔ)法分析器Bison連接的代碼之外，為了方便管理還把一些過(guò)長(zhǎng)的正則式用簡(jiǎn)短的名字代替，如變量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+浮點(diǎn)數(shù)float_number：-+?0-9+.0-9+回車換行EOL：n在規(guī)則部分寫(xiě)出了詞

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

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

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

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

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

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

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

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

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

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

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

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

53、果文法滿足該文法符號(hào)的Follow集與First集無(wú)交集和同一非終結(jié)符的右部的First集兩兩無(wú)交集的話，那么該文法也是LL（1）文法。A. 計(jì)算First集計(jì)算First集大致上分為兩種方法：第一種是根據(jù)First集的定義，第二種是由關(guān)系圖求First。1) 根據(jù)First集的定義計(jì)算的步驟有如下幾步對(duì)每一個(gè)文法符號(hào)XV由First集的定義計(jì)算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都*時(shí)，其中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時(shí)，所有Yi*，則First（X）=First(Y1)FirstY2FirstYn。反復(fù)使用上述2至5步直到每個(gè)符號(hào)的First集不再增大為止。若符號(hào)串V*，=X1X2Xn，當(dāng)X1*，則First（）=First（X1）。若對(duì)任何j（1ji-1，2in）First（Xj）；First（Xi），則First（）=j=1i-1（FirstXj-）First（Xi）。當(dāng)所有First（Xj）（1jn）都含有時(shí)，則First（）=j=1n(FirstXj)。2) 由關(guān)系圖法求文法符號(hào)的First集的步驟有如下幾步：(1) 文法圖中的每個(gè)結(jié)點(diǎn)代表一個(gè)文法符號(hào)，對(duì)應(yīng)非終結(jié)符的結(jié)點(diǎn)用First（S）來(lái)標(biāo)記，其