1、自然語言處理20021109中國科學院計算技術研究所1. 綜述.1.1. 緒論.1.1.1. 背景,目標.. 研究自然語言的動力1 語言是思維的裁體，是人際交流的重要工具。在人類歷史上以語言文字形式記載和流傳的知識占到知識總量的80以上。就計算機的應用而言，據統計用于數學計算的僅占10，用于過程控制的不到5，其余85左右都是用于語言文字的信息處理。在這樣的社會需求下，自然語言理解作為語言信息處理技術的一個高層次的重要方向，一直是人工智能界所關注的核心課題之一。2 由于創(chuàng)造和使用自然語言是人類高度智能的表現，因此對自然語言理解的研究也有助于揭開人類智能的奧秘，深化我們對語言能力和思

2、維本質的認識。.. 什么是計算語言學計算語言學（Computational Linguistics）指的是這樣一門學科，它通過建立形式化的數學模型，來分析、處理自然語言，并在計算機上用程序來實現分析和處理的過程，從而達到以機器來模擬人的部分乃至全部語言能力的目的。 計算語言學（Computational Linguistics）有時也叫計量語言學（Quantitative Linguistics）, 數理語言學（Mathematical Linguistics）, 自然語言理解（Natural Language Understanding）, 自然語言處理（Natural Lan

3、guage Processing）, 人類語言技術（Human Language Technology）。.. 圖靈測驗在人工智能界，或者語言信息處理領域中，人們普遍認為可以采用著名的1950年描述的圖靈試驗(Turing Test )來判斷計算機是否“理解”了某種自然語言。..1. Turing模仿游戲 (Imitation Game)l 場景：男性被試、女性被試、觀察者，3者在3個不同的房間，房間號分別為X, Y, Ol 規(guī)則：觀察者用電傳打字機與被試們通信，男性被試欺騙觀察者、女性被試幫助觀察者。l 目標：觀察者要判斷出X房間里被試的性別。..2

4、. Turing測試 (Turing Test)l 場景：被試人、計算機、觀察者3者在3個不同的房間，房間號分別為X, Y, Ol 規(guī)則：觀察者用“某種方式”與被試人和計算機通信計算機欺騙觀察者、被試人幫助觀察者l 目標：觀察者要判斷出被試人在那個房間..3. 全Turing測試 (Total Turing Test)l 場景：被試對象（人或計算機）、觀察者，觀察者可以看到被試對象l 規(guī)則：觀察者可以任意與被試對象通信l 目標：觀察者要判斷出被試對象是人還是計算機..4. 參考文獻1 A. M. Turing，COMPUTING MACHINERY AND INTE

5、LLIGENCE，/asaygin/tt/ttest.html連接的/departments/cog-sci/courses/1998/cs101/texts/Computing-machinery.html 2 曹存根，AI歷史和問題講義，中科院計算所3 Roland Hausser,Foundations of Computational Linguistics,Springer,19. 研究歷史.. 20世紀50年代NLP于20世紀50年代早期開始于美國，當時美國害怕在空間競賽中落敗

6、，需要翻譯大量俄文科技文獻，于是開發(fā)機器翻譯系統，特別是俄英機器翻譯系統，做法是采用詞到詞的翻譯。由于成本高而效率低，漸漸撤去了資金支持。.. 20世紀60年代60年代開發(fā)的自然語言理解系統，大都沒有真正意義上的語法分析，而主要依靠關鍵詞匹配技術來識別輸入句子的意義。在這些系統中設計者事先存放了大量包含某些關鍵詞的模式，每個模式都與一個或多個解釋(又叫響應式)相對應。系統將當前輸入句子同這些模式逐個進行匹配，一旦匹配成功便立即得到了這個句子的解釋，而不再考慮句子中那些不屬于關鍵詞的成分對句子意義會有什么影響。SIRSIR(Semantic Information Retrieva

7、l)是1968年BRaphael完成的，這是他在美國麻省理工學院的博士論文研究工作的一部分。系統用LISP語言編程。這是一個理解機器的原型，因為它能把用戶通過英語告訴它的事實記住，然后通過對這些事實的演繹來回答用戶提出的問題。SIR有能力接受英語的一個受限子集，它把輸入句子同如下類型的24種關鍵詞模式進行匹配：* is * is part of *Is * * ?How many * does * have ?What is the * of * ?當符號“*”同輸入句子中的一個名詞相匹配時，該名詞前面允許帶有像a，the，every，each等冠詞、量詞或數詞的修飾語。每當匹配到一種模式，便

8、會在程序中觸發(fā)相應的動作。STUDENT1968年美國麻省理工學院的博士研究生DBobrow完成了另一個基于模式匹配的自然語言理解系統STUDEN丁。系統能理解和求解中學代數題。ELIZA1968年，JWeizenbaum在美國麻省理工學院設計的ELIZA系統，或許是這些基于“模式匹配”的自然語言系統中最有名一個。系統模擬一位心理治療醫(yī)生(機器)同一位患者(用戶)的談話。TGNoam Chomsky 創(chuàng)建了generative transformational grammar。機器翻譯中開始使用句法分析。.. 20世紀70年代進入70年代以后，一批采用句法語義分析技術的自然語言理

9、解系統脫穎而出，在語言分析的深度和難度方面都比早期系統有了長足的進步。這個時期的代表作是LUNAR，SHRDLU和MARGIE系統。LUNARLUNAR是第一個允許用普通英語同計算機數據庫對話的人-機接口，是1972年美國BBN公司的WWoods負責設計的。系統用來協助地質學家查找、比較和評價阿波羅11飛船帶回的月球巖石和土壤標本的化學分析數據。SHRDLUSHRDLU系統是1972年Terry Winograd設計的，這是他在美國麻省理工學院的博士學位研究工作。SHRDLU是一個在“積木世界”中進行英語對話的自然語言理解系統。系統模擬一個能操縱桌子上一些玩具積木的機器人手臂，用戶通過人機對話

10、方式命令機器人捏弄那些積木塊，系統則通過屏幕來給出回答并顯示現場的相應情景。這個系統是想說明讓計算機理解語言是可以做到的；MARGIEMARGIE(Meaning Analysis，Response Generation，and lnference on Eng1ish)是由RSchank及其學生們在美國斯坦福大學的人工智能實驗室里建立的一個系統，目的是提供一種自然語言理解過程的直覺模型。.. 20世紀80年代實用化和工程化系統進入80年代以來自然語言理解系統的最大特點就是實用化和工程化。其重要標志就是一批商品化的自然語言人-機接口和機器翻譯系統出現在國際市場上。著名的有美國人工

11、智能公司(AIC)生產的英語人機接口系統Intellect，美國弗雷公司生產的Themis人-機接口，美國加里福尼亞工學院研制的ASK接口；歐洲共同體在美國喬治敦大學開發(fā)的機譯系統SYSTRAN的基礎上成功地進行了英、法、德、西、意、葡等多語對的機器翻譯，加拿大蒙特利爾大學開發(fā)的服務于天氣預報領域的英法機譯系統TAUMMETE0，日本富士通公司開發(fā)的ATLAS英日、日英機譯系統，日本日立公司開發(fā)的HICATS英日、日英機譯系統等等。國內“七五”期間由中國軟件總公司開發(fā)的商品化英漢機譯系統“譯星”(TRANSTAR)，也是這方面的一個范例。語料庫語言學(Corpus Linguistics)“語

12、料庫語言學(Corpus Linguistics)是80年代才嶄露頭角的一門計算語言學的新的分支學科。它研究機器可讀的自然語言文本的采集、存儲、檢索、統計、語法標注、句法語義分析，以及具有上述功能的語料庫在語言定量分析、詞典編纂、作品風格分析、自然語言理解和機器翻譯等領域中的應用”。語料庫語言學(Corpus Linguistics)開始崛起。首先它順應大規(guī)模真實文本處理的需求，提出了以計算機語料庫為基礎的語言學研究及自然語言處理的新思想。這個學派堅持認為語言學知識的真正源泉是大規(guī)?；钌恼Z料，計算語言學工作者的任務是使計算機能自動或半自動地從大規(guī)模語料庫中獲取理解語言所需的各種知識，他們必

13、須客觀地而不是主觀地對庫存的語言事實作出描述。.. 20世紀90年代1990年8月，在赫爾辛基召開的第13屆國際計算語言學大會上，大會組織者首次提出了處理大規(guī)模真實文本的戰(zhàn)略目標，并在會前組織了“大型語料庫在建造自然語言系統中的作用”、“詞典知識的獲取與表示”和“電子詞典”等專題講座，預告了語言信息處理的一個新的歷史階段即將到來。.. 21世紀初.. 21世紀20年代.. 參考文獻1） 石純一、黃昌寧、王家欽，人工智能原理，清華大學出版社2） Chris Manning and Hinrich Schutze，Foundations of

14、 Statistical Natural Language Processing，/fsnlp/3） 周 強，基于語料庫和面向統計學的自然語言處理技術介紹，/research/papers/chinese/collection-2/zqlw6.htm .1.1.3. 研究內容.. 從計算的角度來研究語言的性質所謂從計算的角度來看語言的性質，就是要求將人們對語言的結構規(guī)律的認識以精確的、形式化的、可計算的方式呈現出來，而不是像其他語言學研究那樣，在表述語言的結構規(guī)律時一般采用非形式化

15、的表達形式。.. 將語言作為計算對象來研究相應的算法所謂將語言作為計算對象來研究相應的算法，是研究如何以機械的、規(guī)定了嚴格操作步驟的程序來處理語言對象（主要是自然語言對象，當然也可以是形式語言對象），包括一個語言片斷（比如詞組、句子或篇章）中大小語言單位的識別，該語言片斷的結構和意義的分析（自然語言理解），以及如何生成一個語言片斷來表達確定的意思（自然語言生成），等等.1.1.4. 語言分析的不同層次.. 基于語言構成劃分層次..1. 詞匯..2. 短語..3. 句子..4. 段落..5. 篇章.

16、. 基于語言特征劃分層次..1. 音韻詞與其發(fā)音的關系。..2. 詞法如何用音節(jié)形成詞，如friend-ly。..3. 句法..4. 語義..5. 語用.1.1.5. 應用領域.. 機器翻譯（Machine Translation）和機助翻譯.. 語音識別（Speech Recognition）.. 語音合成（Speech Synthesis）.. 文本分類（Text Classification）.. 信息檢索（Information Re

17、trieval）.. 信息提?。↖nformation Extraction）與自動文摘（automatic summarizing）.. 人機接口（Human-Machine Interface）.. 故事理解與問答系統.1.1.6. 相關學科.. 各學科的交叉.. 哲學一個詞和一個句子怎么會有意義，如何用詞指定世界中的物體。信念、目標、和意圖是什么東西，與語言有什么關系。通過反例的直覺來擴展自然語言；.. 數學..1. 數理邏輯..2. 圖論..3. 概率論.1.1

18、.6.4. 語言學研究語言的結構，詞如何形成短語、短語如何形成句子，什么東西限制一個句子可能的意義等。研究的工具：人類對合適的語法和意義形式的直覺，以及一些數學工具如形式語言理論、模型理論語義學等。.. 心理學研究人類語言產生和理解的過程，人類如何識別句子的正確結構，何時決定一個詞的正確含義，理解過程何時發(fā)生等。研究的方法是：測量人類對象執(zhí)行情況的實驗技術，以及對觀察結果的統計分析。.. 計算機科學..1. 人工智能..2. 機器學習..3. 模式識別.. 信息科學..1. 數據庫.

19、.2. 數據挖掘..3. 數據倉庫..4. 信息提取..5. 自動文摘..6. 信息分類..7. 信息檢索..8. 信息過濾.1.2. 英語的特點.1.3. 漢語的特點2. 音韻3. 詞法4. 句法.4.1. 總論詞如何形成短語，詞和短語如何形成正確的句子，每一個詞在句中在機構方面起什么樣作用。.4.1.1. 句法分析的任務對于自然語言的分析來說，句法分析有以下兩個主要任務：1識別一個語言的句子和確定輸入句子的結構給定文法G和該文法描述的語言L,(1)給定一個字符串S,判定S是否屬于L;(2) 給定一個字符串S

20、,如果S屬于L，給出S對應的樹結構; 3句法結構的規(guī)范化如果我們能把大量可能的輸入結構映射為數量較少的結構，那么后繼的處理(例如語義分析)就得以簡化。下面是幾個結構規(guī)范化的例子：(1) 句子中時常有些成分可以被省略或“零化”；(2) 各種轉換可以把表層結構不同的句子聯系起來，如主動語氣和被動語氣；(3) 正常詞序和所謂分裂結構：That I like wine is evident. It is evident that I like wine.(4) 名詞性結構和動詞性結構： the barbariansdestruction of Rome the barbarians destroyed

21、 Rome等等。這樣一類的轉換使得后繼的處理只需考慮數量少得多的結構。.4.1.2. 句法分析的不同類型1 傳統的非概率分析方法概率方法（PCFG）2 完全句法分析部分句法分析（partial parsing / shallow parsing）3 Top-down句法分析predicative parserBottom-up句法分析shift-reduce parser4 確定性句法分析deterministic parser非確定性句法分析non-deterministic parser.4.1.3. 形式語法陣營 1）TG，GB，MP， 2）LFG，GPSG，HPSG， 3）PATR-I

22、I，DCG，FUG， 4）樹鄰接語法（TAG） 5）鏈語法（Link Grammar） 6）范疇語法（CategorialGrammar） 7）依存語法（Dependency Grammar） 8）詞語法（Word Grammar）.4.1.4. 當代形式語法理論體系的分類GPSGHPSGFUGLFGTG, GB, MPTAGUnification-basedCategory-basedFormal grammatical system(Grammar Formalism)CategorialGrammarDependency GrammarWord GrammarLink GrammarWo

23、rd-based.4.1.5. 形式語法理論體系的演變歷史.4.2. 理論.4.2.1. 形式語言與自動機.. 基本概念..1. 基礎概念..1.1. 字母表由元素組成的非空有限集。我們把字母表中的元素稱為符號，因此字母表也稱為符號集。..1.2. 字（也叫字符串，符號串）與空字(也叫空串)由字母表中的元素所構成的一個有窮序列。在符號串中，符號的順序是很重要的。如果某符號串x中有m個符號，則稱其長度為m表示為|x|m。不包含任何字符的序列，記為。|=0。字母表上的所有字的全體記為*。*稱為字母表上的符號串集合。..1.3.

24、空集不含任何元素的集合，記為。..1.4. 積/閉包/正則閉包*的子集U和V的（連接）積定義為UV=|U & VV自身的n次連接（也稱V的n次方冪）記為Vn=VVV,V的數目為n規(guī)定V0=。令V*= V0V1V2V3稱V*是V的閉包。記V+=V V*,稱V+是V的正（則）閉包。顯然，X=X=X,X為符號串；或X=X=X ，X為符號串集合。..2. 正規(guī)式與正規(guī)集下面是的正規(guī)式與正規(guī)集遞歸定義：1 和都是上的正規(guī)式，它們所表示的正規(guī)集分別為和；2 任何a，a是上的一個正規(guī)式，它所表示的正規(guī)集為a；3 假定U和V都是上的正規(guī)式，它們所表示的正規(guī)集分別記為L(U)和L(V

25、)，那么，（U|V）,(U.V)和(U)*也都是正規(guī)式，它們所表示的正規(guī)集分別為L(U) L(V),L(U)L(V)（連接集）和(L(U)*（閉包）。僅由有限次使用上述步驟而定義的表達式才是上的正規(guī)式，僅由這些正規(guī)式所表示的字集才是上的正規(guī)集。若兩個正規(guī)式U和V所表示的正規(guī)集相同，則認為U和V等價，記為U=V。.. 自動機..1. 狀態(tài)轉換圖狀態(tài)轉換圖是一張有限方向圖。在狀態(tài)轉換圖中，結點代表狀態(tài)，用圓圈表示。狀態(tài)之間用箭弧連接。箭弧上的標記（符號或符號串）代表在射出結（即箭弧始結）狀態(tài)下可能出現的輸入符號或符號串。一張狀態(tài)轉換圖只包含有限個狀態(tài),其中一些被稱為初態(tài)

26、，又有一些被稱為終態(tài)（用雙圈表示）。用狀態(tài)轉換圖可以構造詞法和語法分析程序。但為了分析程序的自動生成，需要對狀態(tài)轉換圖加以形式化。這就產生了自動機理論。..2. -閉包與a弧轉換1） 狀態(tài)集合I的-閉包，表示為-closure(I)，它是一個狀態(tài)集：a)若sI,則s-closure(I)；b) 若sI，則從s出發(fā)經任意條連續(xù)的弧而能到達的狀態(tài)s -closure(I)。2） 狀態(tài)集合I的a弧轉換，表示為move(I，a) ，它是一個狀態(tài)集：令J= move(I，a)，則J是所有那些可從I中的某一狀態(tài)結經過一條a弧而到達的狀態(tài)結的全體。對于狀態(tài)集I和弧a,我們定義Ia=-closu

27、re(J)，其中J= move(I，a)即Ia是狀態(tài)集I的a弧轉換的-閉包。..3. 確定有限自動機（DFA）一個確定有限自動機（DFA）M是一個五元式M=(S, ,f,s0,Z)其中，1S是一個有限集，它的每個元素稱為一個狀態(tài)；2是一個有窮字母表，它的每個元素稱為一個輸入字符。所以也稱為輸入符號字母表；3f是一個從S*到S的(單值)部分映射。f(s,a)=s意味著：當前狀態(tài)為s，輸入字符為a時，將轉換到下一狀態(tài)s。我們把s稱作s的一個后繼狀態(tài)；4s0是S中的一個元素，是唯一的一個初態(tài)，也稱為開始狀態(tài)。4 Z是S的子集，是一個終態(tài)集（可空）。終態(tài)也稱可接受狀態(tài)或結束狀態(tài)。 確定有

28、限自動機（DFA）可以表示成一張（確定的）狀態(tài)轉換圖。..4. 非確定有限自動機（NFA）一個非確定有限自動機（NFA）M是一個五元式M=(S, ,f,S0,Z)其中，1S是一個有限集，它的每個元素稱為一個狀態(tài)；2是一個有窮字母表，它的每個元素稱為一個輸入字符。所以也稱為輸入符號字母表；3f是一個從S*到S的子集的映射。即f: S*2S4S0是S中的一個子集，是非空初態(tài)集。5 Z是S的子集，是一個終態(tài)集（可空）。非確定有限自動機（DFA）可以表示成一張（非確定的）狀態(tài)轉換圖。DFA是NFA的特例。但是，對于每個NFA M存在一個DFA M，使L(M)=L(M)。..

29、5. 確定有限自動機的化簡所謂一個確定的有限自動機M的化簡是指：尋找一個狀態(tài)數比M少的DFA M，使得L(M)=L(M)。我們說一個有窮自動機是化簡了的，即是說，它沒有多余狀態(tài)并且它的狀態(tài)中沒有兩個是互相等價的。一個有窮自動機可以通過消除多余狀態(tài)和合并等價狀態(tài)而轉換成一個最小的與之等價的有窮自動機。所謂有窮自動機的多余狀態(tài)，是指這樣的狀態(tài)：從該自動機的開始狀態(tài)出發(fā)，任何輸入串也不能到達的那個狀態(tài)。假定s和t是DFA M的兩個不同的狀態(tài)，我們稱s和t是等價的：如果從狀態(tài)s出發(fā)能讀出某個字而停于終態(tài)，那么同樣，從t出發(fā)也能讀出同一個字而停于終態(tài)；反之，如果從狀態(tài)t出發(fā)能讀出某個字而停于終態(tài)，那么同

30、樣，從s出發(fā)也能讀出同一個字而停于終態(tài)。如果DFA M的兩個狀態(tài)s和t不等價，則稱這兩個狀態(tài)是可區(qū)別的。我們介紹一個方法，叫做“分割法”，來把一個DFA M(不含多余狀態(tài))的狀態(tài)分成一些不相交的子集，使得任何不同的兩子集的狀態(tài)都是可區(qū)別的，而同一子集中的任何兩個狀態(tài)都是等價的。對DFA M的狀態(tài)集S進行分劃的步驟：1） 把S的終態(tài)和非終態(tài)分開，分成兩個子集，形成基本分化。2） 假定到某個時候已含m個子集，記=I(1),I(2),I(m),并且屬于不同子集的狀態(tài)是可區(qū)別的。然后檢查中的每個I看能否進一步分劃。對于某個I(i),令I(i)=s1,s2,sk,若存在一個輸入字符a使得Ia(i)不全包

31、含在現行的某一子集I(j)中，就將I(i)一分為二：I(i1)和I(i2)，使得I(i1)中的狀態(tài)和I(i2)中的狀態(tài)是可區(qū)別的，這樣就形成了新的分劃。3） 重復2），直到所含的子集數不再增長為止，得到最后的分劃，對于這個中的每一個子集，我們選取子集中的一個狀態(tài)代表其他狀態(tài)，這樣得到的DFA M和原來的DFA M是等價的。..6. NFADFA的轉換定理：設L為一個由不確定的有窮自動機接受的集合則存在一個接受L的確定的有窮自動機。子集法：一種將NFA轉換成接受同樣的語言的DFA的算法。下面詳細介紹：基本思想：該DFA的每一個狀態(tài)對應NFA的一組狀態(tài)。該DFA使用它的狀態(tài)去記錄在N

32、FA讀入一個輸入符號后可能達到的所有狀態(tài)。也就是說，在讀入輸入符號串a1a2an之后，該DFA處在這樣一個狀態(tài)，該狀態(tài)表示這個NFA的狀態(tài)的一個子集T，T是從NFA的開始狀態(tài)沿著某個標記為a1a2an的路徑可以到達的那些狀態(tài)。算法：對于一個NFA Mn=(Sn, n,fn,S0n,Zn),我們按下面的方法構造一個Md=(Sd, d,fd,S0d,Zd)，使得L(Mn)=L(Md)：1) Md的狀態(tài)集Sd由Sn的一些子集組成 (構造Sn的這些子集的算法將在后面給出) 。我們用Sd1，Sd2，Sdj表示Sd的任意一個元素，其中Sd1，Sd2，Sdj是Sn的狀態(tài)。并且約定，狀態(tài)Sd1，Sd2，Sdj

33、是按某種規(guī)則排列的，即對于子集 Sd2，Sd1來說，Sd的狀態(tài)就是 Sd1，Sd2；2) Md和Mn的輸入字母表是相同的，即是d =n；3) 轉換函數fd是這樣定義的：fd (Sd1，Sd2，Sdj，a)-closure(move（Sd1，Sd2，Sdj，a)；4) S0d=-closure(S0n)；5) Zd =Sdp，Sdq，Sdr| Sdp，Sdq，Sdr Sd & Sdp，Sdq，Sdr Zn != 下面給出構造NPA Mn的狀態(tài)Sn的子集的算法。假定所構造的子集族為C,即C=(T1,T2,Ti),其中T1,T2,Ti為狀態(tài)Sn的子集：1開始，令-closure(S0n)為C中唯一成

34、員，并且它是未被標記的；2while(C中存在尚未被標記的子集T)do標記T， for每個輸入字母a （a != ） do U:= -closure (Move(T，a); if U不在C中 tken將U做為未被標記的子集加在C中;例如：把下圖表示的NFA轉換成DFA。.. 文法..1. 規(guī)則也稱重寫規(guī)則（rewriting rule）、產生式規(guī)則（production rule）或生成式，是形如或：的(,)有序對。其中是某字母表V的正閉包V+中的一個符號，是V*中的一個符號。稱為規(guī)則的左部，稱為規(guī)則的右部。..2. 文法一個文法G定義為四元組(VT,

35、VN,S,R),其中，VT為終結符號集，是個非空有限集；終結符是組成語言的基本符號。VN為非終結符號(或語法實體，或變量)集，是個非空有限集；非終結符是用來代表語法范疇的；VTVN =。 S稱作識別符號或開始符號它是一個非終結符號，至少要在一條規(guī)則中作為左部出現；R為產生式(也稱規(guī)則)的集合, 每一個產生式為, ，（VTVN）*，且必須至少包含一個非終結符，并且不能是空字符；R 中至少有一個產生式中的得由S 來充當。通常用V表示VTVN,V稱為文法G的字母表或字匯表。例如：G=( VT =0，1, VN =S,S,R=S0S1,S01)文法的三個作用：1）生成：產生語言L中所有的句子；2）判定

36、：一個字符串（String）是否屬于語言L；3）分析：得到L中句子的結構樹；.. 語言..1. 直接推導/推導/可推導出對于文法G(VT,VN,S,R)，我們稱A直接推導，即A=僅當A是R中的一產生式，且，（VTVN）*。如果1=2=n，則稱這個序列是從1到n的一個推導。若存在一個從1到n的推導，則稱1可推導出n。用1=+=n表示：從1出發(fā)，經一步或若干步，可推導出n；用1=*=n表示：從1出發(fā)，經0步或若干步，可推導出n；..2. 最左推導/最右推導最左推導：任何一步=都是對中的最左非終結符進行替換的。最右推導：任何一步=都是對中的最右非終結符進行替

37、換的。在形式語言中，最右推導常被稱為規(guī)范推導。由規(guī)范推導所得的句型稱為規(guī)范句型。..3. 句型/句子/語言對于文法G(VT,VN,S,R)，如果S=*=，則稱是一個句型。僅含終結符好的句型是一個句子。文法G所產生的句子的全體是一個語言，將它記為L(G)。L(G)= |S=+= &VT*對于文法G1，G2，若L(G1)L(G2)，則稱文法G1和G2是等價的。..4. 遞歸語言和可遞歸枚舉的語言遞歸語言(Recursive langag)如果能編寫一部程序，它在讀入一個符號串后能最終判斷這個串是或不是某種語言的一個句子，就說這種語言是遞歸的?？蛇f歸枚舉的語言(recur

38、sively enumerable language)如果能編寫部程序，使之能以某種順序逐個地輸出(即枚舉)一種語言的句子，就說這種語言是可遞歸枚舉的。.. 形式語言喬姆斯基(Chomsky)于1956年建立形式語言的描述。 喬姆斯基把文法分成四種類型，即o型、1型、2型和3型。這幾類文法的差別在于對產生式施加不同的限制。對于文法G(VT,VN,S,R)， 0）如果G的每個產生式均滿足：（VTVN）*且至少含有一個非終結符，而（VTVN）*，則G是一個0型文法（PSG）。0型文法也稱短語(結構)文法（Phrase Structure Grammars）。一個非常重要的理論結果是，

39、0型文法的能力相當于圖靈機(Turning)?；蛘哒f,任何0型語言都是遞歸可枚舉的；反之，遞歸可枚舉集必定是一個0型語言。但某些語言不是遞歸的。1）設G為0型文法，若G的每一個產生式均滿足|，AVN，且不是，（VTVN）*，則文法G是1型文法或上下文有關文法。這一定義表明：只有A出現在和的上下文中，才允許用取代A。2）設G為0型文法，若G的每一個產生式為A,AVN，（VTVN）*，則文法G是2型文法或上下文無關文法(CFG)，也稱為BNF范式（Backus-Naur Form或Backus Normal Form）。這一定義表明：非終結符的替換可以不必考慮上下文。上下文無關文法對應非確定的下推

40、自動機。3）設G為0型文法，若G的每一個產生式為AB或A, VT*， A，BVN，則文法G是3型文法或正規(guī)文法(RG)或右線性文法。3型文法或正規(guī)文法(RG)另一種定義是：設G為0型文法，若G的每一個產生式為A B或A, VT*， A，BVN，則文法G是3型文法或正規(guī)文法(RG)或左線性文法。很顯然，對任何一個3型文法G，可以設計一個NFA，它能夠且只能夠識別G的語言。四個文法類的定義是逐漸增加限制的，因此每一種正規(guī)文法部是上下文無關的，每一種上下文無關文法都是上下文有關的，而每一種上下文有關文法都是0型文法。稱0型文法產生的語言為0型語言。上下文有關文法、上下文無關文法和正規(guī)文法產生的語言分

41、別稱為上下文有關語言、上下文無關語言相正規(guī)語言。各型文法的判定難度：1）PSG：半可判定對于一個屬于Gtype0的句子L，總可以在確定步內判斷出“是”；但對于一個不屬于Gtype0的句子L，不存在一個算法，可以在確定步內判斷出“否”。 2）CSG：可判定，復雜度：NP完全 。3）CFG：可判定，復雜度：多項式 。4）RG：可判定，復雜度：線性 。.. 正規(guī)式和有限自動機的等價性正規(guī)式和有窮自動機的等價性由以下兩點說明：1對于上的NFA M，可以構造一個上的正規(guī)式R，使得L(R)L(M)；2對于上的每個正規(guī)式R，可以構造一個上的NFA M，使得L(M)L(R)。證明：1）為上的NF

42、A M構造相應的正規(guī)式R。我們把狀態(tài)轉換圖的概念拓廣，令每條弧可用一個正規(guī)式作標記。第一步，在M的狀態(tài)轉換圖上加進兩個結，一個為x結點，一個為y結點。用弧連接到M的所有初態(tài)結點，從M的所有終態(tài)結點用弧連接到y結點。形成一個與M等價的M，M只有一個初態(tài)x和一個終態(tài)y。第二步，逐步消去M中的所有結點，直至只剩下x和y結點。在消結過程中，逐步用正規(guī)式來標記弧。其消結的規(guī)則如下：最后x和y結點間的孤上的標記則為所求的正規(guī)式R。2） 從上的任一個正規(guī)式R構造上的一個NFA M使得L(M)L(R)的方法。a)把正規(guī)式R表示成下圖的拓廣轉換圖：XYYXR或當R=時為:b) 通過對R進行分裂和加新結的辦法，逐

43、步把這個圖轉變成：每條弧標記為的一個字符或。其轉換規(guī)則是反向利用1）中的消結規(guī)則。例如：為R(a|b)*abb構造NFA N，使得L(N)L(R)。.. 正規(guī)文法等價于正規(guī)式，正規(guī)語言等價于正規(guī)集..1. 正規(guī)文法等價于正規(guī)式對任意一個正規(guī)文法，存在一個定義同一個語言的正規(guī)式：反之，對每個正規(guī)式，存在一個生成同一語言的正規(guī)文法。證明：1） 將上的一個正規(guī)式轉換成文法G(VT,VN,S,R)。令其中的VT，確定產生式和VN的元素用如下辦法：a)對任何正規(guī)式r，選擇一個非終結符S生成產生式Sr，并將S定為G的識別符號。 b)若x和y都是正規(guī)式，對形如Axy的產生式，重寫

44、成：AxB，By兩產生式，其中B是新選擇的非終結符，即BVN。 c)對已轉換的文法中的形如Ax*y的產生式，置寫為 AxB Ay BxB By，其中B為一新非終結符。 d)對形如Ax|y的產生式，重寫為：Ax，Ay不斷利用上述規(guī)則做變換，直到每個產生式最多含有一個終結符為止。2） 將正規(guī)文法轉換成正規(guī)式。基本上是上述過程的逆過程。最后只剩下一個開始符號定義的產生式，并且該產生式的右部不含非終結符。正規(guī)文法到正規(guī)式的轉換規(guī)則列于下表：文法產生式正規(guī)式規(guī)則1規(guī)則2規(guī)則3AxB，ByAxA|yAx，AyA=xyA=x*yA=x|y例如：1） 將Ra(a|d)*轉換成相應的正規(guī)文法；2） 將文法G=(

45、VT=a,d,VN=S,A, S,R=SaA,Sa,AaA,AdA,Aa,Ad)轉換成相應的正規(guī)文法；..2. 正規(guī)語言等價于正規(guī)集.. 正規(guī)文法與有限自動機的轉換..1. 正規(guī)文法到有限自動機的轉換從正規(guī)文法G直接構造一個有窮自動機NFA M，使得L(M)L(G)：a)字母表與的終結符集相同；b)為G中的每個非終結符生成M的一個狀態(tài)，(不妨取成相同的名字)。G的開始符號S是開始狀態(tài)S。c)增加一個新狀態(tài)Z，做為NFA的終態(tài)；d)對G中的形如AtB（其中t為終結符或，A和B為非終結符）的產生式，構造M的一個轉換函數f(A，t)B；對G中形如At的產生式

46、構造M的一個轉換函數f(A，t)Z。..2. 有限自動機到正規(guī)文法的轉換從有窮自動機NFA M直接構造一個正規(guī)文法G，使得L(G)L(M)：a)有窮自動機的字母表為文法的終結符號集；b)有窮自動機的初態(tài)對應文法開始符號；c)有窮自動機的轉換規(guī)則非常簡單：對轉換函數f(A，t)B，可寫一產生式： AtB對可接受狀態(tài)Z，增加一產生式：Z.. 詞法詞法分析的主要任務是從左至有逐個字符地對輸入字符串進行掃描，產生一個個單詞序列，用以語法分析。正規(guī)式用于說明(描述)單詞的結構十分簡潔方便。而把一個正規(guī)式編譯(或稱轉換)為一個NFA進而轉換為相應的DFA，這個NPA或DPA正是

47、識別該正規(guī)式所表示的語言的句子的識別器。.0. 上下文無關文法的語法分析上下文無關文法有足夠的能力描述現今程序設計語言的語法結構。目前廣泛使用上下文無關文法作為程序設計語言語法的描述工具。.0.1. 語法樹語法樹也稱推導樹，它是一種描述上下文無關文法的句型推導的直觀方法。對于上下文無關文法G(VT,VN,S,R)的任何句型都能構造與之關聯的語法樹,這棵樹滿足下列4個條件：1每個結點都有一個標記，此標記是（VTVN）*的一個符號； 2根的標記是S；3若一結點n至少有一個它自己除外的子孫，并且有標記A,則A肯定在VN中；4如果結點n(標記為A)的直接子孫，從左到右的次序

48、是結點n1,n2,n3,nk，其標記為A1,A2,A3,Ak，那么AA1,A2,A3,Ak一定是R中的一個產生式。例：對于文法G(S，A， a，b,S,R)，其中R為(1)SaAS(2)ASbA(3)ASS(4)Sa(5)Aba構造句子aabbaa的語法樹。.0.2. 文法的二義性如果一個文法存在某個句子對應兩棵不同的語法樹，則說這個文法是二義的?；蛘哒f，若一個文法中存在某個句子，它有兩個不同的最左(或者最右)推導、則這個文法是二義的。定理：二義性問題是不可判定的。即，不存在一個算法，它能在有限步驟內，確切的判定一個文法是否是二義的。.0.3. 語法分析方法從左到右

49、分析法：即總是從左到右地識別輸入符號串，首先識別符號串中的最左符號，進而識別右邊的一個符號。從右向左分折法：即總是從右到左地識別輸入符號串，首先識別符號串中的最右符號，進而識別左邊的一個符號。自上而下分析法：也稱自頂向下分析法，面向目標的分析方法。從文法的開始符號出發(fā)，反復使用各種產生式，尋找“匹配”于輸入符號串的推導。自頂向下分析法又可分為確定的和不確定的兩種，確定的分析方法需對文法有一定的限制，但由于實現方法簡單、直觀，便于手工構造或自動生成語法分析器，因而仍是目前常用的方法之一。不確定的方法即帶回溯的分析方法，這種方法實際上是一種窮舉的試探方法，因此效率低，代價高，因而極少使用。自下而上

50、分析法：從輸入符號串開始逐步進行“歸約”，直至歸約到文法的開始符從語法樹建立的方式可以很好理解這兩類方法的區(qū)別。自上而下方法是從文法符號開始，將它做為語法樹的根，向下逐步建立語法樹，使語法樹的末端結點符號串正好是輸入符號串；自下而上方法則是從輸入符號串開始，以它做為語法樹的末端結點符號串，自底向上地構造語法樹。下面討論的都是從左到右分析法。.0.4. 自上而下分析法.0.4.1. 問題在自上而下分析方法中，假定要被代換的最左非終結符號是V，且有n條規(guī)則：V1|2|n那么如何確定用哪個右部去替代V呢?有一種解決辦法是從各種可能的選擇中隨機挑選一種，并希望它是正確的。如

51、果以后發(fā)現它是錯誤的，我們必須退回去，再試另外的選擇，這種方示稱為回溯。顯然這樣做代價極高，效率很低，這是我們需要解決的問題。.0.4.2. 遞歸下降分析法.0.5. 自下而上分析法.0.5.1. 基本概念.. 短語/直接短語/句柄令G是一文法，S是文法的開始特號，是文法G的一個句型。如果有：S=*=A且A=+=則稱是句型相對于非終結符A的短語。特別，如有A=則稱是句型相對于規(guī)則A的直接短語(也稱簡單短語)。一個句型的最左直接短語稱為該句型的句柄。.. 規(guī)范規(guī)約.0.5.2. 問題在

52、自下而上的分析方法中，在分析程序工作的每一步，都是從當前串中選擇一個子串，將它歸約到某個非終結符號，我們暫且把這個子串稱為“可歸約串”。問題是，每一步如何確定這個“可歸約串”，也就是說，在每一步如何選擇一個串，使得它是可歸約的，而不是不可歸約的。.0.5.3. 算符優(yōu)先分析法.0.5.4. LR分析器.1. 參考文獻1）陳火旺等，程序設計語言 編譯原理，國防工業(yè)出版社2）編譯原理，清華大學計算機系列教材.4.2.2. 狀態(tài)轉移網絡.. 有限狀態(tài)轉移網絡（FSTN）一個有限狀態(tài)轉移網絡(Finite State Transition Network)由一組狀態(tài)(即結點)和一組弧(用來把一種狀態(tài)連向另一種狀態(tài))所組成：1） 其中的一個狀態(tài)被指定為起始狀態(tài)；2） 在每條弧上都標注著該語法的終結符(包括詞或詞類等等)。它表明必須在輸入句子中找到這樣一個詞，才可以進行這條弧所規(guī)定的轉移；3） 狀態(tài)集中有一個名為結束狀態(tài)的子集。如果輸入句子(或短語)的頭從起始狀態(tài)開始，經過一系列的轉移，句尾恰好達