第三章語言翻譯

第三章語言翻譯程序結(jié)構(gòu)語法程序是什么樣的BNF(上下文無關(guān)文法)–一種非常有用的描述語法的表示法。語義執(zhí)行行為靜態(tài)語義

–語義在編譯時(shí)確定：varA:integer; A的類型和存儲(chǔ)intB[10]; 數(shù)組

B的類型和存儲(chǔ)floatMyProcC(float

x;floaty){...}; 函數(shù)屬性動(dòng)態(tài)語義

–語義在執(zhí)行時(shí)確定：X=``ABC‘’ SNOBOL4語言的例子:X是一個(gè)字符串X=1+2; X是一個(gè)整數(shù):(X) X是一個(gè)地址；轉(zhuǎn)移到標(biāo)號為

X的地方主要內(nèi)容程序語言的語法語法的一般準(zhǔn)則、次要（或二級）準(zhǔn)則語法的基本元素程序-程序的組織結(jié)構(gòu)程序的翻譯源程序分析：詞法分析（掃描）、語法分析、語義分析目標(biāo)程序的綜合翻譯模型BNF、正則文法（有限狀態(tài)自動(dòng)機(jī)）、下推自動(dòng)機(jī)PERL概述3.1語言的語法語法：單詞的組織方式，用來展示單詞之間的關(guān)系單詞作為語句中的元素語法描述了構(gòu)成有效程序的符號序列。如C中，x=y+z是有效的符號序列，而xy+－則不是。語法提供了理解程序的含義所需的信息，也提供了大量的從源程序到目標(biāo)程序翻譯所需的信息。語言的語法（2）單靠語法并不足以無二義地刻劃語句的結(jié)構(gòu)。如：x=2.45+3.67，語法并不能告訴我們x是否被聲明過或是否聲明為實(shí)數(shù)。x=5,6或6.12均是可能的。因此，對語言的完整描述單靠語法結(jié)構(gòu)是不夠的，還需涉及語義。如：聲明的使用、操作、順序控制和引用環(huán)境等影響變量性質(zhì)的一些屬性，并不總是由語法決定。語言的語法（3）雖然如此，語法仍是語言描述中的重要屬性。現(xiàn)在，語法描述已是一個(gè)解決了的問題，源程序的語法理解階段是相當(dāng)機(jī)械的，YACC等工具可自動(dòng)生成給定程序的語法描述。返回語法的一般準(zhǔn)則語法的主要目的是為程序員和語言處理器間通訊提供一套注記方法。而選擇特殊的語法結(jié)構(gòu)主要是為了傳遞特殊的信息項(xiàng)。例如：某特定變量有類型實(shí)數(shù)，可以用多種方式表達(dá)?？梢允秋@式聲明或隱含的命名約定，等。語法細(xì)節(jié)的選擇大部分是基于第二準(zhǔn)則，如可讀性，它和通訊的主要目標(biāo)無關(guān)。有很多二級準(zhǔn)則，通?？砂雌淠繕?biāo)分類，分為：易讀、易寫、易翻譯、無二義等目標(biāo)。這些目標(biāo)間有時(shí)會(huì)有沖突。易讀性（Readabitity）程序是易讀的：如果程序表示的算法和數(shù)據(jù)的結(jié)構(gòu)可以很容易從程序文本中了解到。一個(gè)易讀的程序，通常稱為自成文檔的（不需其他用于理解的輔助文檔）。增加易讀性的方式：自然的語句格式、結(jié)構(gòu)化語句、關(guān)鍵字和噪音字的自由使用、嵌入式注釋機(jī)制、不限長標(biāo)識符、助記符、自由域格式、完全的數(shù)據(jù)聲明等。不同的語法應(yīng)反映不同語義，做相似事的程序結(jié)構(gòu)是相似的。做不同事的程序其結(jié)構(gòu)需有明顯不同。語言如只提供了少數(shù)不同語法結(jié)構(gòu)，通常導(dǎo)致程序易讀性差。如APL，SNOBOL4等，只提供一種語句格式，賦值、子程序調(diào)用、簡單GOTO、子程序返回，多路條件分支、及其它常見程序結(jié)構(gòu)的差異只能通過個(gè)別操作算子的不同來反映。易讀性（Readabitity）易讀性并不能由語言設(shè)計(jì)保證，最好的設(shè)計(jì)也可能由于糟糕的編程而破壞。當(dāng)然，語法設(shè)計(jì)也可能使好程序員寫出難理解的程序，如APL。COBOL強(qiáng)調(diào)易讀，但其代價(jià)是犧牲了易寫和易翻譯。易寫性易寫性（使用簡明的、規(guī)則的語法結(jié)構(gòu)）通常和易讀性（冗余結(jié)構(gòu)是有幫助的）相沖突。隱含的語法約定允許聲明和操作不需預(yù)先刻劃，從而使程序更短、更易寫，但不易讀。有些語法冗余性有用的，因它允許程序易讀，并允許翻譯時(shí)錯(cuò)誤檢測。缺點(diǎn)是不易寫。語法稱為冗余的，如果以多種方式傳達(dá)同樣的信息。大多數(shù)缺省規(guī)則（針對語言結(jié)構(gòu)含義）試圖減少冗余，而刪去了某些顯式的含義陳述，因?yàn)檫@些含義可從語境中導(dǎo)出。例，F(xiàn)ortran中約定，I-N打頭的變量為整型，其他為實(shí)數(shù)，這樣不需聲明，但缺點(diǎn)是有副作用，如：拼寫錯(cuò)誤不能被編譯器檢測到，例如：INDEX被寫成INDX→則變成新變量。易寫性對兩個(gè)目標(biāo)均有增強(qiáng)的一些特征：如結(jié)構(gòu)化語句、簡單自然語句格式、助記符、未限制標(biāo)記符等通常使程序易寫通過允許在程序中直接表示問題的算法和數(shù)據(jù)的自然結(jié)構(gòu)。易驗(yàn)證性和易讀、易寫相關(guān)的概念是程序正確性或程序驗(yàn)證。多年經(jīng)驗(yàn)表明，理解每條程序語言語句是容易的，創(chuàng)建正確程序的整個(gè)過程卻是困難的。因此，需有技術(shù)，使得能數(shù)學(xué)地證明程序是正確的。易翻譯性即易于翻譯成可執(zhí)行形式。易讀性和易寫性是面向程序員的需要。易翻譯性（關(guān)鍵是結(jié)構(gòu)的正則性）是面向翻譯器（處理被寫成的程序）的需要。如LISP程序，不易讀、也不易寫、但易于翻譯，主要由于其語法簡單且正則。當(dāng)特殊語法結(jié)構(gòu)增加，將導(dǎo)致翻譯困難，如COBOL，它允許大量的語句和聲明形式。無歧義性含混性是語言設(shè)計(jì)中的一個(gè)中心問題。一個(gè)語言定義應(yīng)盡可能地為每個(gè)語法結(jié)構(gòu)提供唯一的意義。而含混性結(jié)構(gòu)允許兩個(gè)或多個(gè)不同解釋。通常不是由個(gè)體程序元素的結(jié)構(gòu)產(chǎn)生，而是由于不同結(jié)構(gòu)的交迭。例如：ifBooleanexpthenstatement1elsestatement2.IfBooleanexpthenstatement1當(dāng)兩種形式組合時(shí)，有可能出現(xiàn)二義情況。Fortran中，A（I，J）可能是數(shù)組元素，也可能是函數(shù)調(diào)用。事實(shí)上，上面提到的含混在語言中均有解決方案。條件語句的兩種不同解釋歧義性的解決方法例：因組合而形成的懸空else：IfBooleanexp1thenifBooleanexp2thenstat1elsestat2Algol解決方案：改變語法，引入分界符begin…end。Ada解決方案：每個(gè)if語句必須以endif分界符結(jié)尾。C和Pascal解決方案：從二義結(jié)構(gòu)中任選一種解釋。對本例而言，最后的else總是和最近的then配對。FORTRAN中函數(shù)調(diào)用和數(shù)組引用的二義性由規(guī)則解決：A(I,J)被視為函數(shù)調(diào)用，如果沒有數(shù)組A的聲明。但這個(gè)假定只能在程序裝載、鏈接時(shí)被檢查。Pascal中區(qū)分二者的方法是使用不同的括號，如：[…]用于界定數(shù)組參數(shù)，(…)用于界定函數(shù)調(diào)用的參數(shù)。返回語言的語法元素（1/7）語言的語法風(fēng)格由各種基本語法元素的選取所決定。字符集字符集的選擇是語言設(shè)計(jì)的第一件事。已有一些標(biāo)準(zhǔn)字符集，如：ASCII碼。通常是選擇一個(gè)標(biāo)準(zhǔn)的字符集。 但也有不標(biāo)準(zhǔn)的，如APL。字符集的選擇對確定可被用于語言實(shí)現(xiàn)的I/O設(shè)備的類型是非常重要的。如：C的字符集可用于大多數(shù)I/O設(shè)備。而APL的字符集則不能直接用于大多數(shù)I/O設(shè)備。通常用8位來表示字符（60年代早期用6位），這似乎是足夠的。但是，隨著計(jì)算機(jī)產(chǎn)業(yè)的國際化進(jìn)程，可能16位表示是必需的（可有65536個(gè)字符）。語言的語法元素（2/7）標(biāo)識符字和數(shù)字串，以字母開頭——常用的選擇。也可能使用特殊字符，如用.或-來改善易讀性和長度限制。操作符符號+，-，*，/表示基本算法操作。通常簡單操作可完全使用特殊符號。當(dāng)然，也可以使用標(biāo)識符來表示簡單操作，如LISP中的PLUS、TIMES。大多數(shù)語言采用二者的組合。語言的語法元素（3/7）關(guān)鍵字和保留字關(guān)鍵字——用于語句語法中固定部分的標(biāo)識符。保留字——不能被程序員使用的關(guān)鍵字。大多數(shù)語言使用保留字以改善翻譯器的錯(cuò)誤檢測能力，使語法分析更為容易。噪聲字可選的字，被插入語句中以改善易讀性。如：COBOL中Go語句可寫為GOTO語言的語法元素（4/7）注釋是文檔中的重要部分，幾種注釋方式：1、分開的注釋行，F(xiàn)ortran2、特殊標(biāo)志界定，/**/，界定字符丟失可能導(dǎo)致大面積出錯(cuò)。3、在行中任意地方開始，但在行末結(jié)束，如C++的//空白（空格）語言中常使用空白規(guī)則，通常都是作為分隔符。也有的語言中空格有其他用途。語言的語法元素（5/7）界定符（分界符）和括號用于標(biāo)記語法單位的開始和結(jié)束，如{}括號是一對分界符。自由和固定域格式自由域——語句可寫在任何地方固定域——在輸入行中通過位置來傳遞信息。Fortran是典型例子。當(dāng)前固定域越來越少。語言的語法元素（6/7）表達(dá)式訪問程序中數(shù)據(jù)對象并反回值，是基本的語法建筑塊。在命令型語言中，表達(dá)式形成基本操作，狀態(tài)被語句所改變。在作用型語言中，表達(dá)式形成了驅(qū)動(dòng)程序執(zhí)行的基本順序控制。語言的語法元素（7/7）語句是命令型語言中最主要的語法部件。語句的語法對語言整體的正則性、易讀性和易寫性有著關(guān)鍵影響。有的語言采用單一語句格式，強(qiáng)調(diào)正則性；而其它語言對不同語句類型使用不同語法，著重于易讀性。語句結(jié)構(gòu)中的一個(gè)更重要的差異是：結(jié)構(gòu)性（或嵌套）語句和簡單語句。返回程序結(jié)構(gòu)分開的子程序定義Fortran中，每個(gè)子程序定義被處理為分開的語法單元，每個(gè)子程序被分別編譯，被編譯程序在裝載時(shí)鏈接。這種組織方式主要是針對這樣一種情況：每個(gè)子程序均需含所有數(shù)據(jù)元素的完整數(shù)據(jù)聲明，即使是對那些在COMMON塊中的或與其它子程序共享的數(shù)據(jù)。需要這些聲明主要是由于分開編譯的需要?；镜淖映绦騿卧糜诒硎灸撤N能提供相關(guān)功能的結(jié)構(gòu)。分開的數(shù)據(jù)定義把所有操作于給定數(shù)據(jù)對象之上的操作組合在一起，如C++中類。主要是基于數(shù)據(jù)抽象的原則。嵌套的子程序定義如PASCAL，子程序定義在主程序中作為聲明出現(xiàn)，子程序本身又可含有其他子程序定義。其目標(biāo)是強(qiáng)調(diào)結(jié)構(gòu)化的語句，但事實(shí)上產(chǎn)生了不同用途。結(jié)構(gòu)化語句的引入主要是為算法結(jié)構(gòu)的常見的層次劃分提供一種自然的注記方式，但嵌套子程序定義為編譯時(shí)定義的子程序提供了非局部的作用環(huán)境。從而允許靜態(tài)類型檢查，和有效的可執(zhí)行代碼的生成。嵌套的另一好處是作用域管理。允許子程序名具有較少的作用域。分開的接口定義FORTRAN的結(jié)構(gòu)使得編譯分開子程序變得非常容易，但缺點(diǎn)是不同子程序共享的數(shù)據(jù)可能有不同的定義，而這種不同是編譯器在編譯時(shí)無法檢測到的。PASCAL允許編譯器訪問所有這樣的定義以幫助發(fā)現(xiàn)錯(cuò)誤，缺點(diǎn)是全部程序，即使其有上千條語句，必須在每次修改后重新編譯。結(jié)合上面的技術(shù)可以改善編譯行為。程序?qū)崿F(xiàn)由幾個(gè)相互交互的子程序構(gòu)成，這些部件稱為模塊，將被連接在一起以創(chuàng)建可執(zhí)行程序，但每次只有修改的模塊被重編譯。而在一個(gè)部件中的過程間傳送的數(shù)據(jù)必須具有公共聲明，從而允許編譯器的高效檢查。為了在分開的編譯模塊間傳遞數(shù)據(jù)，引入了規(guī)約部件，如C中.h文件。Ada中的Package（接口定義規(guī)約+實(shí)現(xiàn)體）。數(shù)據(jù)描述和可執(zhí)行語句分離COBOL包含了早期的部件結(jié)構(gòu)形式。在COBOL中，所有子程序的數(shù)據(jù)聲明和可執(zhí)行語句被分入不同的程序中，即數(shù)據(jù)段和過程段，而用環(huán)境段包含關(guān)于外部操作環(huán)境的聲明。一個(gè)程序的過程段被組織為子單元，以對應(yīng)子程序體，但所有數(shù)據(jù)對所有子程序均是全局的，沒有東西對應(yīng)于通常子程序中的局部數(shù)據(jù)。中心化數(shù)據(jù)段的優(yōu)點(diǎn)是：強(qiáng)迫形成數(shù)據(jù)格式和過程段中算法的邏輯獨(dú)立性，數(shù)據(jù)結(jié)構(gòu)的細(xì)小修改可只修改數(shù)據(jù)段而不需修改過程段。同時(shí)將數(shù)據(jù)描述搜集到一個(gè)地方，而不是散布在子程序中也是方便的方式。這適合于大量數(shù)據(jù)的處理。在某種意義是，數(shù)據(jù)庫應(yīng)用是這種形式的擴(kuò)展。未分離的子程序定義不分開主程序和子程序語句，如SNOBOL4中，程序是一個(gè)語句表。子程序間沒有語法分隔，函數(shù)調(diào)用開始新的子程序執(zhí)行，返回語句結(jié)束該子程序。程序的行為是動(dòng)態(tài)的。事實(shí)上，任意語句可以同時(shí)是主程序的一部分，也可以是子程序的一部分。這體現(xiàn)在該語句可在主程序的執(zhí)行中某點(diǎn)被執(zhí)行，而后又在某子程序的執(zhí)行中某點(diǎn)被執(zhí)行。這種混沌結(jié)構(gòu)僅僅對允許運(yùn)行時(shí)翻譯和相對簡單的新語句和子程序執(zhí)行機(jī)制具有價(jià)值。返回3.2翻譯的階段邏輯上，翻譯可分為兩個(gè)主要部分（輸入源程序的分析，可執(zhí)行目標(biāo)程序的綜合），兩個(gè)階段又可細(xì)分。大多數(shù)翻譯器的中這些邏輯階段不是可以明確劃分開的，而是混合在一起使得分析和綜合交替進(jìn)行（通常逐條語句進(jìn)行）。翻譯的階段編譯器通常對源程序掃描兩遍第一遍將程序分解為部件并從程序中導(dǎo)出信息。第二遍根據(jù)這些收集的信息生成目標(biāo)程序。如果編譯速度是重要的考慮（如教學(xué)用編譯器），一遍掃描是常用方式，在程序被分析時(shí)，立即被翻譯為目標(biāo)代碼。如果執(zhí)行速度是重要考慮，三遍甚至更多遍掃描也是可能的。第一遍分析源程序。第二遍使用各種定義好的優(yōu)化算法將源程序重寫為更多效的形式。第三遍生成目標(biāo)代碼。返回翻譯的階段源程序的分析（1/3）詞法分析將源程序字符流分隔、分組，成為一些基本的構(gòu)成成分，如： 標(biāo)識符、分界符、操作符、數(shù)、關(guān)鍵字、噪音字、空白、注釋等。這些稱為詞法項(xiàng)，Token（語言符號）。源程序的分析（2/3）語法分析（parsing）標(biāo)識大的程序結(jié)構(gòu)（語句，聲明、表達(dá)式等）（基于前面得到的語言符號）。通常語法分析和語義分析交替進(jìn)行（使用棧作為通訊工具）。語法分析器向棧中輸入各種語法單元元素，語義分析器檢索并處理。需要高效的語法分析技術(shù)，主要基于形式化文法的應(yīng)用。源程序的分析（3/3）語義分析——翻譯的中心階段處理語法分析器識別的語法結(jié)構(gòu)，并開始形成可執(zhí)行目標(biāo)碼的結(jié)構(gòu)，語義分析是分析和綜合間的橋梁。這階段的工作包括一些重要工作，如符號表維護(hù)、大多數(shù)錯(cuò)誤檢測，宏擴(kuò)展以及編譯時(shí)語句的執(zhí)行。在簡單情況下，語義分析器直接生成可執(zhí)行代碼，但大多數(shù)情況下，是產(chǎn)生最終可執(zhí)行程序的某種內(nèi)部格式，然后被優(yōu)化處理。語義分析器可分為一些小的語義分析器，各自處理一特殊類型的程序結(jié)構(gòu)。它們之間通過存放在各種數(shù)據(jù)結(jié)構(gòu)、特別是中心符號表中的信息而進(jìn)行交互。常見的語義分析功能（1/4）1、符號表維護(hù)符號表（最早由詞法分析形成）含有對程序中不同標(biāo)識符的表項(xiàng)（不僅含標(biāo)識符，還包含涉及標(biāo)識符屬性的附加數(shù)據(jù)，如：標(biāo)識符類型，值類型，引用環(huán)境等。）語義分析器在處理聲明、子程序頭、語句等時(shí)，填入相關(guān)信息。編譯型語言的符號表在翻譯結(jié)構(gòu)后通常丟棄。但有的語言在執(zhí)行時(shí)仍保留，如：允許運(yùn)行時(shí)創(chuàng)建新標(biāo)識符的語言（ML、LISP等，符號表是運(yùn)行時(shí)的中心數(shù)據(jù)結(jié)構(gòu)），以及輔助調(diào)試（dbx使用運(yùn)行時(shí)符號表來調(diào)試C程序）。常見的語義分析功能（2/4）2、隱含信息的插入在源程序中，有的信息經(jīng)常是隱含的，必須在低級目標(biāo)程序中顯式化。這類隱含信息包括：一些缺省約定信息，類型推導(dǎo)信息等。常見的語義分析功能（3/4）3、錯(cuò)誤檢測語法和語義分析器必須能夠處理不正確的和正確的程序。語法分析器可能會(huì)接收到和當(dāng)時(shí)語境不相容的詞法項(xiàng)，如：表達(dá)式中出現(xiàn)分界符，語句序列中出現(xiàn)聲明等。更微妙的錯(cuò)誤有：實(shí)數(shù)變量出現(xiàn)在需要整數(shù)的地方，對聲明只有二維的數(shù)組出現(xiàn)三維下標(biāo)引用等。屬語義錯(cuò)。語義分析器不僅需要能夠識別這樣的錯(cuò)誤并產(chǎn)生適當(dāng)?shù)某鲥e(cuò)消息，還必須能夠在大多數(shù)情況下，確定合適的方式以繼續(xù)剩余程序的語法分析工作。常見的語義分析功能（4/4）4、宏處理和編譯時(shí)操作并非所有語言具有宏特征和編譯時(shí)操作。但如果具備，通常在語義分析中處理。語義分析器必須識別宏調(diào)用并處理宏替換。通常，該任務(wù)需要中斷詞法和語法處理，而讓它們?nèi)ヌ幚砗牦w中的字符流。另一個(gè)方法是宏體可能已預(yù)先被部分翻譯，語義分析器可以直接處理，在繼續(xù)源程序分析前插入適當(dāng)?shù)哪繕?biāo)碼并建立合適的表項(xiàng)。用于控制翻譯。編譯時(shí)操作是在翻譯中完成的操作，用于控制源程序的翻譯。C中提供了大量這樣的操作。如：#define允許常量或表達(dá)式在程序被編譯前計(jì)值。#ifdef允許不同的代碼序列被編譯，根據(jù)某些變量的存在與否。這些設(shè)施允許程序員修改被編譯的語句序列。返回目標(biāo)程序的綜合翻譯的最后階段是根據(jù)語義分析的結(jié)果，構(gòu)造可執(zhí)行程序。優(yōu)化語義分析器通常以某種中間形式來產(chǎn)生可執(zhí)行程序，中間形式可以是操作符和操作數(shù)的串，也可以是操作符和操作數(shù)序列的表。在代碼生成前，對中間形式進(jìn)行優(yōu)化處理是必要的。代碼生成在中間形式被優(yōu)化后，必須產(chǎn)生最后的輸出結(jié)果：可執(zhí)行程序。它可能是匯編語言語句、機(jī)器代碼序列或其它目標(biāo)形式。它可能能夠直接執(zhí)行，也可能需要鏈接裝載后才可執(zhí)行。連接和裝載形成最終可運(yùn)行程序。返回3.3形式化翻譯模型編譯器理論的語法識別部分是相當(dāng)標(biāo)準(zhǔn)的，通?；谏舷挛臒o關(guān)理論。語言語法的形式定義通常稱為文法（grammar）一個(gè)文法由一個(gè)規(guī)則集合組成，規(guī)則被稱為產(chǎn)生式，刻劃了形成允許程序的字符序列。一個(gè)形式文法是用嚴(yán)格定義的記號體系刻劃的文法。編譯技術(shù)中常用兩類文法。BNF文法（上下無關(guān)文法）正則文法BNF文法Backus-NaurForm。JohnBackus開發(fā)，用于Algol語言的語法定義。PeterNaur是開發(fā)Algol委員會(huì)的主席。幾乎同時(shí)，語言學(xué)家NoamChomsky設(shè)計(jì)了上下文無關(guān)文法來定義自然語言的語法。在能力上，二者是等價(jià)的，差異只是符號體系不同。BNF文法的語法表示BNF文法規(guī)定的語言、以及語句的理解和結(jié)構(gòu)化表示—語法分析樹BNF文法的二義性BNF文法—語法BNF文法包含一個(gè)BNF文法規(guī)則的有限集合，它定義了一個(gè)語言。語法僅僅涉及形式而不涉及含義，一個(gè)語言從語法上考慮，由一個(gè)語法正確的程序集合構(gòu)成，每個(gè)程序只簡單地是一個(gè)字符序列。語法正確的程序不一定有語義，即可能不一定計(jì)算出什么結(jié)果，甚至沒有結(jié)果。不考慮語義，語言是任意有限字符串的集合，這些字符選自某固定符號集。BNF文法—語法下面均為語言1、所有C中賦值語句的集合2、所有C程序的集合3、所有LISP原子的集合4、a、b.構(gòu)成的序列的集合，所有a在所有b之前。語言可包含有限的串集合，也可能包含無限的串集合?？紤]上面例子，可發(fā)現(xiàn)用自然語言描述語言帶來了一些問題，如：4例中，b是否是語言的成員？是否串上必須有a？因此，描述并不完整。解決這個(gè)問題的方法：給出形式的數(shù)學(xué)規(guī)則集合，準(zhǔn)確地確定語言中的串是什么。BNF文法—語法非終結(jié)符:符號的有限集:<sentence><subject><predicate><verb><article><noun>終結(jié)符:符號的有限集:the,boy,girl,ran,ate,cake開始符:一種非終結(jié)符:<sentence>規(guī)則

(產(chǎn)生式):替換規(guī)則的有限集：

<sentence>::=<subject><predicate> <subject>::=<article><noun> <predicate>::=<verb><article><noun> <verb>::=ran|ate <article>::=the <noun>::=boy|girl|cake替換操作:用任一規(guī)則右邊的值替換任意非終結(jié)符

(寫作

)BNF文法—語法最簡單的文法規(guī)則是列出有限語言的所有元素，如：<digit>:=0|1|2|3…8|9這里<digit>表示一個(gè)非終結(jié)符或語法范疇，0－9為終結(jié)符。一旦定義了基本的語法非終結(jié)符集合，可以構(gòu)造更復(fù)雜的串，如：<conditionalstatement>::= if<Booleanexp>then<statement>else<statement>|if<Booleanexp>then<statement>規(guī)則定義的非終結(jié)符可本身被用在規(guī)則中，從而形成遞歸規(guī)則。<unsignedinteger>::=<digit>| <unsignedinteger><digit>返回語法分析樹（parsetree）給定文法，可使用替換規(guī)則生成語言的串。如：下面文法生成平衡的括號序列：

S→SS|（S）|（）一個(gè)推導(dǎo)過程：

S→（S）→（SS）→（（）S）→（（）（））推導(dǎo)中的每個(gè)項(xiàng)稱為句型。語言是句型的集合，其中的巨型只含有終結(jié)符(即句子)，并可從文法的初始符號推導(dǎo)出來。語言即句子的集合。為了確定一個(gè)字符串是否是由文法所定義的語言所規(guī)定的語法上合格的程序，我們必須使用文法規(guī)則去構(gòu)造該字符串的語法分析樹，如分析成功，則是該語言的程序。語法分析樹BNF文法將一個(gè)結(jié)構(gòu)賦給語言中的每個(gè)串。被賦的結(jié)構(gòu)實(shí)質(zhì)上是一棵樹，這是由于BNF文法的限制。樹的葉節(jié)點(diǎn)是單個(gè)字符或詞法項(xiàng)，中間的分叉點(diǎn)是一個(gè)語法范疇，由非終結(jié)符標(biāo)記，根節(jié)點(diǎn)是表示整個(gè)語言的非終結(jié)符。分析樹為程序提供了大部分的直覺的語義結(jié)構(gòu)。語法分析樹賦值語句W=Y*(U+V)的語法分析樹：語法分析樹不能用BNF文法定義的語法是那些涉及上下文依賴的語法，如：如下限制不能用BNF刻劃。同樣的標(biāo)識符不能在相同塊中聲明兩次。每個(gè)標(biāo)識符必須聲明在包括其使用點(diǎn)的塊中。一個(gè)用二維聲明的數(shù)組不能用三個(gè)下標(biāo)引用。此類限制必須用對顯式化BNF的補(bǔ)遺來定義。返回文法的二義性一種文法是有歧義的，如果某個(gè)句子有兩種不同的分析樹。歧義性通常是文法中的問題，而不一定是語言的問題。如：G1：S→SS|0|1具有二義性。如果對給定語言的每個(gè)文法均是含混的，則稱語言是固有含混的。然而上面G1文法描述的語言不是含混的，因?yàn)榭梢詾樗鼘懗霾缓斓奈姆ā2：T→0T|1T|0|1返回有限狀態(tài)自動(dòng)機(jī)語言由語言符號（Token）構(gòu)成。語言符號具有簡單的結(jié)構(gòu)，有限狀態(tài)自動(dòng)機(jī)或狀態(tài)機(jī)是一種有效的識別語言符號的工具。有限狀態(tài)自動(dòng)機(jī)例如：識別奇數(shù)個(gè)1構(gòu)成的串的FSA。輸入100101的機(jī)器操作如下處理：輸入當(dāng)前狀態(tài)接受串否？Null A no1 B yes10 B yes100 B yes1001 A no10010 A no100101 B yes有限狀態(tài)自動(dòng)機(jī)通常，F(xiàn)SA有一個(gè)開始狀態(tài)，一個(gè)或多個(gè)終態(tài)，以及一組從狀態(tài)到狀態(tài)的變遷。任何串，只要能使機(jī)器從初態(tài)變遷到終態(tài)（通過一系列變遷），則該串為機(jī)器所接受。例如：識別帶符號整數(shù)。非確定型有限自動(dòng)機(jī)確定型FSA——對其每個(gè)狀態(tài)，每個(gè)輸入符號，有唯一的變遷到相同或不同狀態(tài)。非確定型FSA具有：

1、一個(gè)狀態(tài)集合

2、一個(gè)初始狀態(tài)

3、一個(gè)終止態(tài)集合

4、一個(gè)輸入符號集合

5、一個(gè)從狀態(tài)到狀態(tài)的變遷集合，每個(gè)變遷接受來自輸入符號集的一個(gè)元素。非確定性是指：從一個(gè)狀態(tài)有多個(gè)具有相同標(biāo)記的弧線連出，從而必須作出選擇。一個(gè)串稱為可接受的，如果存在從初始結(jié)點(diǎn)到終止結(jié)點(diǎn)之一的路徑，即使其他路徑可能不能到達(dá)某終態(tài)。FSA和NDFSA的等價(jià)性將NDFSA的狀態(tài)的子集作為DFSA的狀態(tài)。記住所有能遷移進(jìn)入的子集的蹤跡。任意從

{A}到

{D}或

{CD}的字符串都表示原NDFSA中一條從A到

D的路徑。正則文法正則文法是BNF文法的特例，等價(jià)于FSA，形式為：

<nontrerminals>::=<terminal><nonterminal>|<terminal>例：A→0A|1A|0產(chǎn)生以0為結(jié)尾的01串。正則表達(dá)式正則表達(dá)式是語言定義的另一種形式，等價(jià)于FSA和正則文法。操作：串聯(lián)(連接)或

(|，有時(shí)也寫成

)Kleene

閉包

(*-0或多個(gè)實(shí)例)定義：1、單個(gè)終結(jié)符是正則表達(dá)式2、如a、b是正則表達(dá)式，則ab,ab,(a),a*也是正則表達(dá)式。3、除1、2外，沒有其他是正則表達(dá)式。正則表達(dá)式可以用正則表達(dá)式來表示任何用正則文法或FSA定義的語言，雖然將任意FSA轉(zhuǎn)換為正則表達(dá)式并不總是明顯的。下面兩圖為到FSA的轉(zhuǎn)換：返回下推自動(dòng)機(jī)PushdownAutomataPDA是類似于FSA的抽象模型機(jī)，等價(jià)于BNF文法，它具有有限個(gè)狀態(tài)，有一個(gè)下壓棧，其移動(dòng)規(guī)劃如下：1、讀輸入符號，并讀棧項(xiàng)符號2、基于兩個(gè)輸入，機(jī)器進(jìn)入一個(gè)新狀態(tài)，并寫0個(gè)或多個(gè)符號在棧頂。3、如果?？?，則串被接受（或PDA處于終態(tài)）易于看出PDA比FSA具有更強(qiáng)大的能力。如：anbn不能被FSA識別，但可以被PDA識別。PDA接受的語言等價(jià)于上下文無關(guān)語言。下推自動(dòng)機(jī)考慮產(chǎn)生串的最左推導(dǎo)的過程，在這種情形，句型存放在棧中，PDA的操作如下：1、如棧頂是終結(jié)符，將其和下一輸入比較，如相同，則彈出棧。如不相匹配，則出錯(cuò)。2、如棧頂是非終結(jié)符X，用串а替代X，а是產(chǎn)生式X→а的右端。這樣PDA模擬了上下文無關(guān)文法的最左推導(dǎo)，這種構(gòu)造實(shí)際上形成了一個(gè)非確定型PDA，等價(jià)于對應(yīng)的BNF文法。在第二步中，可能有多個(gè)X→α樣式的規(guī)則，規(guī)則的選用需人來選擇。確定型PDA和非確定型PDA確定型PDA和非確定型PDA是不一樣的。例如：考查下面的回文文法

S0S0|1S1|2我們可以用一個(gè)確定型PDA來識別該語言中的字符串：1.當(dāng)讀到0和1時(shí)，都壓入棧中；2.當(dāng)讀到2時(shí)，進(jìn)入一個(gè)新的狀態(tài)；3.此后，總是比較棧頂和新輸入的字符，并彈出棧頂元素。但是，如果回文文法如下：

S0S0|1S1|0|1則不可能知道到底哪兒是回文字符串的中間。要識別這類回文，自動(dòng)機(jī)只能猜測回文的中間在哪兒

(這樣就出現(xiàn)了所謂的非確定性)。PDA的例子給定回文

011010110，PDA必須猜測回文的中間在哪兒：

堆棧: 猜測的中間: 等待匹配的字符串: 0 11010110 0 1 1010110 01 1 010110 011 0 10110

0110 1 0110 01101 0 110 011010 1 10 0110101 1 0 01101011 0只有第五種猜測才能使得字符串被正確地識別。如果某種猜測能導(dǎo)致輸入串被完整地分析出來，則說該字符串是符合文法的。常用語法分析算法文法描述語言是自頂向下，而語法分析則是自底向上，從個(gè)體字符開始。一般的分析策略：每種類型的形式文法總是和某類型的自動(dòng)機(jī)緊密相關(guān)。自動(dòng)機(jī)是一種抽象機(jī)，讀一個(gè)輸入帶，產(chǎn)生一個(gè)輸出帶。然而，BNF文法可能是含混的，因此，自動(dòng)機(jī)必須是非確定的。通過使用猜測策略，非確定型下推自動(dòng)機(jī)能識別任何上下文無關(guān)文法。對語言翻譯而言，不需猜測的確定型自動(dòng)機(jī)是需要的。對正則文法，總有對應(yīng)的確定型自動(dòng)機(jī)。對BNF文法則沒有，除非文法無二義并滿足某些其他限制。文法和機(jī)器的等價(jià)性已經(jīng)證實(shí)：正則文法

=FSA=NDFSA上下文無關(guān)文法

=NDPDA但

NDPDA并不等價(jià)于

DPDA上下文有關(guān)文法=非確定型LBA（線性受限自動(dòng)機(jī)）無限制文法

=TM（圖靈機(jī)）=NDTM但現(xiàn)在還不知道NDLBA=DLBA？文法與機(jī)器的等價(jià)性常用語法分析算法對無二義BNF文法，已找到直接的語法分析技術(shù)。最早的技術(shù)是遞歸下降法。主要的進(jìn)展是Knuth的LR文法（lefttorightparsingalgorithms），可描述所有可用確定型下推自動(dòng)機(jī)識別的BNF文法。確定型PDA等價(jià)于LR（