摘要：針對編譯原理課程中的詞法分析，介紹相關(guān)原理，重點(diǎn)探討詞法分析技術(shù)在非編譯系統(tǒng)中的廣泛應(yīng)用。通過實(shí)際應(yīng)用的分析，加深學(xué)生對理論知識(shí)的理解，提高學(xué)生對編譯原理課程重要性的認(rèn)識(shí)，調(diào)動(dòng)學(xué)生的學(xué)習(xí)積極性和主動(dòng)性。

關(guān)鍵詞：編譯原理；詞法分析；實(shí)際應(yīng)用

1.詞法分析概述

詞法分析是編譯過程的第一個(gè)階段，其主要任務(wù)是對構(gòu)成源程序的字符流進(jìn)行掃描和分解，把它識(shí)別為一個(gè)個(gè)具有獨(dú)立意義的最小語法單位，即單詞，從而產(chǎn)生一個(gè)個(gè)的單詞序列，用于語法分析。執(zhí)行詞法分析的程序稱為詞法分析程序或掃描程序，它按構(gòu)詞規(guī)則識(shí)別單詞，將作為字符串的源程序改造成為單詞符號(hào)串。單詞一般采用形如<單詞類別，單詞自身值>的二元組形式表示，其中單詞類別是語法分析需要的信息，而單詞自身值則是其他編譯階段需要的信息。編譯程序是在單詞的級(jí)別上來分析和翻譯源程序的，因此詞法分析是整個(gè)編譯的基礎(chǔ)。詞法分析程序除了識(shí)別單詞這個(gè)基本任務(wù)外，還可完成以下任務(wù)：對源程序進(jìn)行處理，如組織源程序的輸入、刪除注釋、空格及無用符號(hào)；行、列計(jì)數(shù)；列表打印源程序；發(fā)現(xiàn)并定位詞法錯(cuò)誤；建立、查填符號(hào)表。

詞法分析程序與語法分析程序的接口方式有兩種，如圖1所示。（1）詞法分析作為獨(dú)立的一遍，將字符流的源程序變?yōu)閱卧~序列輸出到中間文件上，此中間文件作為語法分析的輸入繼續(xù)編譯；（2）詞法和語法分析在同一遍，即將詞法分析作為語法分析的一部分，把詞法分析程序設(shè)計(jì)為一個(gè)子程序，每當(dāng)語法分析程序需要單詞時(shí)，就調(diào)用該子程序。為了使整個(gè)編譯程序的結(jié)構(gòu)更簡潔、清晰和條理化，便于使用自動(dòng)構(gòu)造工具，提高編譯效率，以及增強(qiáng)編譯程序的可移植性，通常采用第1種接口方式，即把詞法分析從語法分析中獨(dú)立出來。

程序設(shè)計(jì)語言的詞法描述機(jī)制是正規(guī)表達(dá)式，識(shí)別機(jī)制是有窮自動(dòng)機(jī)。詞法分析程序可以通過手工編寫和自動(dòng)生成兩種方式來構(gòu)造：手工編寫需要借助狀態(tài)圖來實(shí)現(xiàn)；而自動(dòng)生成的原理是將正規(guī)式轉(zhuǎn)換為有窮自動(dòng)機(jī)，即首先將單詞描述成正規(guī)式，然后把正規(guī)式轉(zhuǎn)換為一個(gè)NFA（不確定有窮自動(dòng)機(jī)），進(jìn)而轉(zhuǎn)換為相應(yīng)的DFA（確定有窮自動(dòng)機(jī)）。Lex（Lexical Analyzer）是美國Bell實(shí)驗(yàn)室研制的一個(gè)詞法分析程序的自動(dòng)生成工具，此后，GNU工程推出的Flex（Fast Lex）對Lex進(jìn)行了擴(kuò)充，使用它們可以很方便地構(gòu)建詞法分析程序。

2.詞法分析的典型應(yīng)用

詞法分析技術(shù)在軟件工程、信息安全、計(jì)算機(jī)測評、網(wǎng)絡(luò)管理與協(xié)議解析、自然語言處理以及數(shù)據(jù)采集與處理等領(lǐng)域得到了廣泛應(yīng)用，見表1。

2.1軟件工程

詞法分析的主要任務(wù)是對構(gòu)成源程序的字符流進(jìn)行掃描，然后根據(jù)構(gòu)詞規(guī)則識(shí)別單詞符號(hào)，這正是源代碼逆向分析過程中必不可少的一步。因此，詞法分析被廣泛應(yīng)用于軟件逆向工程中的源代碼逆向分析，以獲得逆向分析后續(xù)工作所需的單詞符號(hào)的各類信息。

利用詞法分析可以實(shí)現(xiàn)B/S構(gòu)架應(yīng)用系統(tǒng)和三層構(gòu)架應(yīng)用系統(tǒng)中超文本鏈接的自動(dòng)測試。超文本詞法分析主要根據(jù)超文本的詞法和關(guān)鍵詞，分析查找超文本文件的鏈接類和應(yīng)用類鏈接關(guān)鍵詞，確定超文本的調(diào)用關(guān)系，完成各類鏈接分析（href、src、cite和background），并將分析結(jié)果存儲(chǔ)到數(shù)據(jù)庫中。測試時(shí)對設(shè)定的目錄進(jìn)行分析處理，列出根目錄下的文件和目錄結(jié)構(gòu)，并對目錄下的HTML文件進(jìn)行詞法分析，接著對分析后的鏈接標(biāo)記進(jìn)行分類、字符解析與轉(zhuǎn)換等處理，然后進(jìn)行鏈接的分析預(yù)驗(yàn)證，最后統(tǒng)計(jì)頁面文件大小和生成不同的分析報(bào)告?；诔谋驹~法分析的超文本鏈接自動(dòng)測試不僅可提高鏈接測試的覆蓋率，而且可有效提高測試驗(yàn)證的效率和準(zhǔn)確性，降低超文本鏈接的測試驗(yàn)證工作量。

2.2信息安全

C/C++語言中許多庫函數(shù)存在安全漏洞，攻擊者常常利用這些函數(shù)產(chǎn)生的漏洞來進(jìn)行緩沖區(qū)溢出、格式化字符串溢出和競爭條件等攻擊。源代碼審核技術(shù)通過對軟件代碼進(jìn)行分析，從特征數(shù)據(jù)庫里抽取感興趣的內(nèi)容進(jìn)行上下文分析，并對可能存在危險(xiǎn)的代碼位置進(jìn)行報(bào)警，從而能在編碼階段及時(shí)發(fā)現(xiàn)和修正軟件源代碼中存在的安全漏洞。詞法分析能夠完成自動(dòng)化的快速漏洞檢測，是源代碼審核中的一項(xiàng)重要技術(shù)，它通過對自定義的漏洞模型與根據(jù)待分析源程序確定的程序模型進(jìn)行分析比較，驗(yàn)證程序模型是否滿足漏洞模型的條件。其實(shí)質(zhì)是訪問包含在危險(xiǎn)函數(shù)數(shù)據(jù)庫中的函數(shù)（如gets、strcpy、scanf、printf、sprintf、snprinff等）來尋找可能存在的危險(xiǎn)，當(dāng)有潛在危險(xiǎn)符合數(shù)據(jù)庫特征時(shí)，就會(huì)發(fā)出警告。目前最具代表性的詞法檢測工具包括ITS4、Rats和FlawFinder等。

某些嵌入網(wǎng)頁的病毒通過插入無效的字符即可得到病毒變種，利用Lex和Yacc等工具可以得到查殺此類病毒的有限自動(dòng)機(jī)軟件，即虛擬機(jī)。這種方式的查病毒虛擬機(jī)在進(jìn)行詞法規(guī)則分析時(shí)對“空格、注釋”等信息置之不理，因此不會(huì)影響對病毒代碼的定位。

在業(yè)務(wù)監(jiān)控系統(tǒng)中可通過報(bào)警規(guī)則來描述用戶所提出的報(bào)警條件，并結(jié)合詞法分析技術(shù)在系統(tǒng)運(yùn)行過程中對報(bào)警規(guī)則進(jìn)行匹配。如基于銀行業(yè)務(wù)系統(tǒng)的網(wǎng)絡(luò)安全審計(jì)和監(jiān)控系統(tǒng)，采用報(bào)警規(guī)則設(shè)計(jì)和詞法分析方法，能夠快速、準(zhǔn)確地判斷是否為可疑交易和大額交易。

2.3計(jì)算機(jī)測評

利用自動(dòng)化的手段將已有試題文檔導(dǎo)入在線考試系統(tǒng)時(shí)，為保證錄入試題的準(zhǔn)確性和保密性，提高試題錄入的效率，可通過詞法分析將試題文本打斷為孤立的單詞，進(jìn)而將各個(gè)單詞進(jìn)行歸類和封裝（包括單詞種類、行號(hào)、起始位置、內(nèi)容等信息）。之后，利用封裝后的單詞對象，使用預(yù)定義的語法樹進(jìn)行匹配和驗(yàn)證。同時(shí)，單詞表對整個(gè)過程涉及的臨時(shí)數(shù)據(jù)進(jìn)行存儲(chǔ)和必要支持。

在程序設(shè)計(jì)自動(dòng)評分系統(tǒng)中，當(dāng)考生的程序不能成功運(yùn)行時(shí)說明程序存在語法錯(cuò)誤，可先對考生的源程序進(jìn)行詞法分析，即掃描源程序，生成單詞文件；然后根據(jù)此文件進(jìn)行語法分析，在保證不對考生程序正確部分產(chǎn)生破壞的前提下，盡最大可能將考生程序修改正確，并對新程序進(jìn)行編譯鏈接和測試，從而避免考生因編程中的很小失誤而導(dǎo)致大量丟分的問題。如果仍不能編譯運(yùn)行，則可依據(jù)正規(guī)表達(dá)式描述的知識(shí)要點(diǎn)進(jìn)行匹配，使得即使錯(cuò)誤嚴(yán)重或結(jié)果不正確的程序也能得到應(yīng)得的分?jǐn)?shù)，從而使評分結(jié)果更接近于人工閱卷。

此外，對某類文本范疇的試題，在一定復(fù)雜度范圍內(nèi)通過對文本的詞法掃描、文法定義、語義分析、等價(jià)替換等技術(shù)將標(biāo)準(zhǔn)答案與錯(cuò)誤答案按特定文法規(guī)則進(jìn)行語義轉(zhuǎn)換后產(chǎn)生唯一等價(jià)表達(dá)式，通過對轉(zhuǎn)換后的規(guī)范表達(dá)式進(jìn)行比較，檢查考生答案是否與標(biāo)準(zhǔn)答案等價(jià)。

2.4網(wǎng)絡(luò)管理與協(xié)議解析

在網(wǎng)絡(luò)管理系統(tǒng)中，不同運(yùn)營商通常對網(wǎng)絡(luò)設(shè)備有不同的實(shí)際需求，如對于網(wǎng)管設(shè)備告警信息的內(nèi)容和格式有不同的要求。如果針對這些不同的需求開發(fā)不同的網(wǎng)管版本，會(huì)成倍增加軟件開發(fā)和運(yùn)行維護(hù)的成本。為靈活適應(yīng)各種需求，網(wǎng)管軟件通常給出一套腳本語言，用戶把特定的需求用腳本語言寫入—個(gè)腳本文件中，然后網(wǎng)管軟件在運(yùn)行時(shí)動(dòng)態(tài)分析腳本文件，獲取用戶的特定需求并把結(jié)果顯示在界面上。實(shí)現(xiàn)這一方案的關(guān)鍵是腳本文件中關(guān)鍵字的識(shí)別，這可以利用Flex等工具生成的詞法分析器來完成。網(wǎng)管軟件只需要定義腳本文件中用到的所有關(guān)鍵字，并在程序中實(shí)現(xiàn)對于關(guān)鍵字的處理即可，從而可以減少網(wǎng)管軟件設(shè)計(jì)和編碼的工作量，提高網(wǎng)管編程的效率。

在通信協(xié)議解析與處理中，可以借鑒自動(dòng)生成詞法分析器的實(shí)現(xiàn)思想，先將通信協(xié)議采用正規(guī)式集的方式進(jìn)行形式化描述，然后由一個(gè)狀態(tài)圖生成程序產(chǎn)生對應(yīng)這些正規(guī)式的狀態(tài)圖，最后由一個(gè)主控程序根據(jù)狀態(tài)轉(zhuǎn)換圖對接收到的數(shù)據(jù)幀進(jìn)行分析識(shí)別，輸出用戶希望的數(shù)據(jù)格式。采用形式化描述的方法對協(xié)議進(jìn)行描述，可以實(shí)現(xiàn)與協(xié)議無關(guān)的協(xié)議解析和處理，避免針對不同通信協(xié)議均要編寫相應(yīng)的解析和處理程序，從而使協(xié)議的解析和處理具有更好的靈活性和普適性。如利用PCCTS工具中的DLG根據(jù)詞法描述文件生成詞法分析程序，從輸入的字符流中識(shí)別詞法描述文件中定義的記號(hào)；再利用其中的ANTLR根據(jù)語法描述文件定義的語法規(guī)則生成語法分析程序，在此過程中調(diào)用DLG生成的詞法分析程序來識(shí)別具體的記號(hào)，從而實(shí)現(xiàn)SIP、MGCP和H.248/GEGACO等通信協(xié)議的解析和處理。

2.5自然語言處理

詞法分析是各種自然語言處理系統(tǒng)中首要的源語言分析模塊，是進(jìn)行句法分析、語義分析的基礎(chǔ)。

詞法分析是自然語言檢索中一項(xiàng)十分重要的工作，它同時(shí)應(yīng)用于用戶提問分析和源文本處理。詞法分析首先對文本、網(wǎng)頁等進(jìn)行詞語切分，然后通過詞頻統(tǒng)計(jì)和詞出現(xiàn)位置的判斷，在文本和網(wǎng)頁中提取主題詞和概念詞。之后利用多個(gè)關(guān)鍵詞的布爾邏輯運(yùn)算構(gòu)成檢索式，在索引庫中逐個(gè)進(jìn)行匹配。由于它能夠根據(jù)詞的位置關(guān)系發(fā)掘出詞的修飾限定關(guān)系，因此與傳統(tǒng)基于關(guān)鍵詞的檢索方法相比，其檢索內(nèi)容的相關(guān)度更高。

借助計(jì)算機(jī)信息技術(shù)，按照中華古典詩詞一些聲韻格式要求對提交的詩詞作品進(jìn)行可有限追溯的詞法分析，可以實(shí)現(xiàn)自動(dòng)智能審查辨別，并反饋訂正建議，從而幫助詩詞創(chuàng)作者更好地運(yùn)用計(jì)算機(jī)工具創(chuàng)作出符合格律的好作品，進(jìn)一步弘揚(yáng)中華詩詞文化傳統(tǒng)。

通過詞法分析可以從語素中獲得許多語言學(xué)信息，比如在維吾爾文詞根與附加成分切分法的基礎(chǔ)上，通過分析維吾爾文詞的詞法結(jié)構(gòu)和音節(jié)結(jié)構(gòu)，可以實(shí)現(xiàn)對維吾爾語元音弱化現(xiàn)象的算法處理。

自動(dòng)詞法學(xué)習(xí)通過機(jī)器學(xué)習(xí)等方法從語料中自動(dòng)獲取計(jì)算機(jī)算法能使用的構(gòu)詞和構(gòu)形的規(guī)律。詞法分析利用自然語言中形態(tài)學(xué)的規(guī)律對給出的句子進(jìn)行詞匯級(jí)處理，隨后自動(dòng)詞法學(xué)習(xí)方法能從未經(jīng)加工的文本中學(xué)習(xí)詞法分析處理的數(shù)據(jù)，從而很容易地獲得目標(biāo)語言中的各種形態(tài)變化規(guī)律，并把這些規(guī)律用形式化的語言表示成各種正則表達(dá)式的形式。

詞法分析是機(jī)器翻譯的第一階段，當(dāng)源語言文本送人計(jì)算機(jī)后，首先要進(jìn)行詞法分析，即對送人的文本進(jìn)行斷句、切分，識(shí)別出單詞、標(biāo)點(diǎn)、數(shù)字等句子的基本成分，并確定它們的形態(tài)和詞性。這也是完成計(jì)算機(jī)翻譯過程的基礎(chǔ)和關(guān)鍵階段，它為后續(xù)句法分析和目標(biāo)語生成創(chuàng)造了條件，其準(zhǔn)確程度的高低直接影響著句法分析的準(zhǔn)確率和譯文的準(zhǔn)確性。

2.6數(shù)據(jù)采集與處理

數(shù)據(jù)采集的主要工作是獲取設(shè)備上傳的文件，根據(jù)預(yù)先定義的格式進(jìn)行解碼，然后把解碼成功得到的數(shù)據(jù)存人數(shù)據(jù)庫。在此過程中會(huì)遇到數(shù)據(jù)格式跨平臺(tái)、需求變更等問題。針對數(shù)據(jù)格式的通用和跨平臺(tái)問題，可采用XDR（ExternalData Representation Standard，外部數(shù)據(jù)描述標(biāo)準(zhǔn)）等跨平臺(tái)的數(shù)據(jù)格式來解決；針對需求變更問題，可以使用針對XDR等數(shù)據(jù)描述語言的詞法分析器把對數(shù)據(jù)描述的解析變成動(dòng)態(tài)的。這樣，對于經(jīng)常變化的數(shù)據(jù)格式描述，通過動(dòng)態(tài)解析的方式避免了編譯和靜態(tài)鏈接，同時(shí)把業(yè)務(wù)邏輯的概念變得更通用，將原先的給定數(shù)據(jù)描述解析數(shù)據(jù)變?yōu)楝F(xiàn)在的解析數(shù)據(jù)描述和數(shù)據(jù)，從而使數(shù)據(jù)采集的功能更通用。

利用詞法分析的良好識(shí)別性可以較好地解決非結(jié)構(gòu)化文本庫到結(jié)構(gòu)化關(guān)系數(shù)據(jù)庫的關(guān)鍵詞庫的建立問題。例如，中草藥資源信息的原始著錄數(shù)據(jù)形式非常復(fù)雜，文本數(shù)據(jù)不僅是變長的，而且其對象的詞描述不是簡單的關(guān)鍵詞而是長句或短文，這種數(shù)據(jù)的非結(jié)構(gòu)化不利于數(shù)據(jù)的查詢和統(tǒng)計(jì)。為此，可利用詞法分析對原始著錄數(shù)據(jù)項(xiàng)進(jìn)行拆分，提取有關(guān)關(guān)鍵詞，采用建立關(guān)鍵詞庫的方法來建立中草藥數(shù)據(jù)庫，從而實(shí)現(xiàn)數(shù)據(jù)的自動(dòng)提取和關(guān)鍵詞庫的建立，并提高中草藥著錄數(shù)據(jù)的規(guī)范化存儲(chǔ)效率和數(shù)據(jù)查詢效率。

為解決RTI（RunTime Infrastructure，運(yùn)行時(shí)間基礎(chǔ)設(shè)施）中FED（Federation Execution Data，聯(lián)邦執(zhí)行數(shù)據(jù)）文件的解析效率和可重用性問題，可以將解析程序的數(shù)據(jù)提取模塊與解析處理模塊分離，同時(shí)在數(shù)據(jù)提取模塊中應(yīng)用詞法分析和語法分析技術(shù)對FED文件進(jìn)行解析優(yōu)化。首先，用正則表達(dá)式將FED文件中所涉及的單詞符號(hào)進(jìn)行形式化描述，定義出FED文件的詞法規(guī)則；同時(shí)，用LALR（1）文法表示符合相關(guān)標(biāo)準(zhǔn)的FED語法的所有狀態(tài)轉(zhuǎn)換，完成FED文件的語法規(guī)則；然后，借助Flex和Bison生成詞法分析程序和語法分析程序，再結(jié)合定義的解析處理規(guī)則最終生成解析程序。采用這種方案，可以將繁雜的解析處理程序的編寫簡化為可讀性較強(qiáng)的詞法分析文檔和語法分析文檔的編寫，提高程序的可讀性和可維護(hù)性，并且對于不同的解析要求，可以重用現(xiàn)有的大部分代碼；同時(shí)，對各種要求的FED解析處理程序只需掃描一次FED文件即可完成整個(gè)解析過程。此外，只需根據(jù)Flex和Bison的版本要求簡單修改詞法分析文檔和語法分析文檔，即可實(shí)現(xiàn)異構(gòu)平臺(tái)的移植。因此，其效率、穩(wěn)定性、可維護(hù)性、可重用性以及可移植性都明顯優(yōu)于通常的FED文件解析方案。

Lex/Flex詞法分析工具除了構(gòu)造編譯器的詞法分析程序外，還可以針對具有結(jié)構(gòu)化輸入的程序構(gòu)建輸入識(shí)別程序。例如，生物信息基本數(shù)據(jù)庫數(shù)量極多，數(shù)據(jù)存儲(chǔ)格式各異，處理方式也有所不同，因此常規(guī)的處理方法工作量極大。為此，利用詞法分析技術(shù)，針對不同格式的生物數(shù)據(jù)文件，只要構(gòu)造相對應(yīng)的正則表達(dá)式就可以使用Lex/Flex構(gòu)建相應(yīng)的識(shí)別程序，對文件中的數(shù)據(jù)進(jìn)行檢索和分析。

為保證航班計(jì)劃編排的正確性，可以航班計(jì)劃編排規(guī)則為依據(jù)，采用詞法分析和語法分析技術(shù)對航班計(jì)劃編排結(jié)果進(jìn)行自動(dòng)檢查。將航班計(jì)劃等視為按民航特定規(guī)則編寫出來的“語言”，其中航班號(hào)、起止時(shí)間、起止地點(diǎn)、機(jī)型、機(jī)組等基本信息是該“語言”中的關(guān)鍵字，則可以首先采用詞法分析掃描航班計(jì)劃字符流，按照詞法規(guī)則識(shí)別出航班計(jì)劃中的各類單詞符號(hào)，檢查這些關(guān)鍵字是否符合其組成規(guī)則，并產(chǎn)生用于語法分析的符號(hào)序列，告訴語法分析這些單詞的組織順序。隨后按照語法規(guī)則，采用語法分析對詞法分析的結(jié)果進(jìn)行處理，識(shí)別詞法分析給出的單詞符號(hào)序列是否為給定文法的正確句子，進(jìn)而檢查其是否按照規(guī)定的詞序及格式編排，是否表達(dá)了正確的涵義，從而實(shí)現(xiàn)航班計(jì)劃編排規(guī)則的句法檢查。

3.結(jié)語

在編譯原理課程的詞法分析教學(xué)中，通過介紹詞法分析技術(shù)在軟件工程、信息安全、計(jì)算機(jī)測評、網(wǎng)絡(luò)管理與協(xié)議解析、自然語言處理以及數(shù)據(jù)采集與處理等非編譯領(lǐng)域中的廣泛應(yīng)用，有助于提高學(xué)生對課程的重視程度和學(xué)習(xí)的積極性與主動(dòng)性，加深學(xué)生對理論知識(shí)的理解，培養(yǎng)學(xué)生理論聯(lián)系實(shí)際的能力，激發(fā)學(xué)生的創(chuàng)造性思維，從而切實(shí)有效地提高學(xué)生的專業(yè)素質(zhì)。