編譯原理與自然語言處理的實驗對齊研究

劉茂福，畢健旗，熊 瑩，何炎祥

（1.武漢科技大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，武漢 430081；2.武漢大學(xué) 計算機學(xué)院，武漢 430072）

0 引 言

在各大高校的計算機專業(yè)核心課程中，編譯原理占有舉足輕重的地位，它融合了眾多領(lǐng)域的知識，理論性與綜合性十足[1]，如詞法分析、語法分析、語義分析等。正因如此，為了使其課程內(nèi)容更容易理解，諸多相關(guān)研究人員也在探討全新的編譯原理課程實驗設(shè)計方案[2]。于建偉等設(shè)計了用于編譯原理經(jīng)典實驗逐個講解分析的演示模塊[3]；褚文杰等設(shè)計了支持自定義語言的可視化編譯教學(xué)輔助工具[4]，在編譯原理展示工具上做出了較大貢獻(xiàn)。目前，在編譯原理理論與技術(shù)方法的實用性引導(dǎo)方面，還有所欠缺。

隨著人工智能技術(shù)的發(fā)展，人們在諸多領(lǐng)域都有了新的理解[5]，自然語言處理（NLP）自20世紀(jì)40 年代至今，發(fā)展得也是如火如荼[6]，許多有關(guān)自然語言處理的課程也如雨后春筍一般，且都取得了不錯的成效[7]?，F(xiàn)如今，NLP 用于處理語言信息的技術(shù)已日漸成熟，其中包含幾個基本概念，如分詞與詞性標(biāo)注、句法分析、語義角色標(biāo)注等。

綜上所述，近年來研究人員對編譯原理課程實驗與自然語言處理的研究熱情仍然十分高漲，但其實不難發(fā)現(xiàn)對兩者的相通性的研究卻很少。我們提出根據(jù)兩者的相通性，將NLP 工具作為編譯原理課程實驗的輔助工具的實驗方法：課上首先講解同學(xué)們更易接受的NLP 在處理語言信息時的演示過程，并通過NLP 處理與編譯過程的高度對齊，使學(xué)生對編譯原理的核心算法原理及應(yīng)用有一個新的理解，即實驗對齊。

1 編譯原理與自然語言處理過程分析

1.1 編譯原理過程分析

將高級程序設(shè)計語言，如C、C++、Java 等，翻譯成計算機可以執(zhí)行的機器指令代碼流的過程，即是編譯的過程。編譯過程一般分為6 個步驟[8]，即詞法分析、語法分析、語義分析、中間代碼生成、中間代碼優(yōu)化、目標(biāo)代碼生成。詞法分析將一段代碼中的每個可識別的單詞提取出來；語法分析用來匹配規(guī)則；語義分析用來判斷邏輯，整個編譯過程可理解為將高級程序設(shè)計語言的源代碼，轉(zhuǎn)換為機器可識別的“0”與“1”的目標(biāo)代碼，并且按照高級程序設(shè)計語言的約束條件、運行邏輯等來判斷源代碼的可執(zhí)行性。編譯程序?qū)υ创a的編譯過程如圖1 所示。

1）詞法分析。

詞法分析作為編譯過程的第一個階段，通過讀入源程序輸入的字符實現(xiàn)：①將輸入字符組成詞素，生成并輸出一個詞法單元序列；②過濾掉源程序中的注釋和空白；③將編譯器生成的錯誤消息與源程序的位置關(guān)聯(lián)起來。如表達(dá)式“sum=3+2;”，經(jīng)過詞法分析后結(jié)果見表1。

圖1 編譯過程示意圖

表1 詞法分析結(jié)果表

2）語法分析。

語法分析作為編譯過程的第二個階段，將分析從詞法分析器中提取出的單詞序列是否符合相應(yīng)語言語法的約束，如輸入序列中包含左括號“（”，則語法分析器會在“（”后找尋是否存在匹配的右括號“）”，若不存在則提示語法錯誤，如圖2 所示。

圖2 語法分析示意圖

3）語義分析。

語義分析作為編譯過程的第三個階段，一般分為靜態(tài)語義和動態(tài)語義兩種。語義分析的作用是在程序語法正確的前提下，分析關(guān)于語法結(jié)構(gòu)含義及使用的規(guī)則，如C 語言中，加法運算要求“+”左右操作數(shù)為整型數(shù)，若出現(xiàn)類似“1 +false”的表達(dá)式，語法無誤但為語義錯誤。

1.2 自然語言處理過程分析

自然語言處理過程即計算機識別人類語言的過程，在各個領(lǐng)域的應(yīng)用都十分廣泛[6]，如文本分類、信息抽取、語音識別、信息檢索等[7]。為了使計算機可以識別語言符號，必須對語言符號進(jìn)行一定的處理、變換或標(biāo)注，其中的技術(shù)包括分詞與詞性標(biāo)注、句法分析、語義角色標(biāo)注等。

NLP 技術(shù)在語言符號序列處理過程中包含最重要的這三種工作，這三種工作與編譯的詞法分析、語法分析、語義分析三部曲十分相似，所以我們單獨對此三種工作進(jìn)行了簡單分析，為后續(xù)實驗做鋪墊。

1）分詞與詞性標(biāo)注。

以中文語言信息為例，現(xiàn)在，中文分詞與詞性標(biāo)注技術(shù)已趨于成熟，且在自然語言處理領(lǐng)域的任何工作當(dāng)中都有使用[9]。我們以jieba分詞[10]為例，簡要分析中文分詞與詞性標(biāo)注的原理。

（1）中文分詞：jieba 分詞主要基于統(tǒng)計詞典工作，簡單來說即是對可能出現(xiàn)的詞語進(jìn)行概率匹配，概率越大的詞被劃分出來的可能性越大。

（2）詞性標(biāo)注：jieba 詞性標(biāo)注主要基于規(guī)則和統(tǒng)計的方法工作，且通過HMM 算法來進(jìn)行詞性標(biāo)注。

對于一段中文序列，如“我想去湖北武漢玩”，中文分詞即是將該句話分成“我”“想”“去”“湖北”“武漢”“玩”6 組詞語；詞性標(biāo)注則是標(biāo)注已被分出的詞的詞性，如“我/r ”“想/v”“ 去/v”“ 湖北/ns”“ 武漢/ns”“ 玩/v”。

2）句法分析。

句法分析分為句法結(jié)構(gòu)分析和依存句法分析。句法結(jié)構(gòu)分析通過分析計算概率來確定語法樹；依存句法分析通過分析句子語言單位內(nèi)層元素、成分元素之間的依存關(guān)系，認(rèn)為句子中核心詞是支配其他成分的中心成分[11]，它同樣會將句子分析成一棵類依存句法樹，描述出各個詞語之間的依存關(guān)系。例如，句子“我想去湖北武漢”的短語語法樹與依存句法結(jié)構(gòu)圖如圖3所示。

圖3 語法分析結(jié)果

3）語義角色標(biāo)注。

語義角色標(biāo)注的任務(wù)是找出句子中謂詞的相應(yīng)語義角色成分，包括核心語義角色（如施事、受事等）和附屬語義角色（如地點、時間、方式、原因等），在句法分析構(gòu)造的句法樹的基礎(chǔ)上，分析判斷句法樹結(jié)點的語義角色，是常規(guī)的解決思路[12]。

語義角色標(biāo)注方法一般包括：①角色剪枝：通過制定的一些啟發(fā)式規(guī)則，過濾掉不可能擔(dān)當(dāng)角色的成分，如“在”“了”等；②角色識別：在剪枝的基礎(chǔ)上，構(gòu)建一個二元分類器，即識別其是或不是給定謂詞的語義角色；③角色分類：對那些是語義角色的成分，進(jìn)一步采用多元分類器，判斷其角色類別，例如：“小明昨天晚上在公園遇到了小紅”，“遇到”是謂詞（Predicate，通常簡寫為“Pred”），“小明”是施事者（Agent），“小紅”是受事者（Patient），“昨天”是事件發(fā)生的時間（Time），“公園”是事情發(fā)生的地點（Location），如圖4 所示。

圖4 語義角色標(biāo)注示例圖

2 實驗對齊

2.1 詞法分析與詞性標(biāo)注

編譯過程中的詞法分析與自然語言處理中的分詞與詞性標(biāo)注處理步驟相同且詞性類別與分詞算法原理相似，具有強相通性，見表2。

表2 詞法分析與詞性標(biāo)注（常用）詞性類別對齊表

詞法分析與中文詞性標(biāo)注處理的對象為代碼段與中文句子，它們將待處理序列切分為表1 中所述類別的對象集合。此外，兩者均對待處理序列進(jìn)行預(yù)處理，區(qū)別在于前者會去掉代碼段的注釋與空白，后者會去掉非中文部分以及統(tǒng)計高頻字等，見表3。

表3 詞法分析與詞性標(biāo)注核心算法對齊表

在算法層面，前者采用的算法較為簡單，即基于狀態(tài)轉(zhuǎn)換圖的識別算法，它基于有窮自動機的設(shè)計思想，對輸入串逐字符地判斷。在輸入預(yù)處理后的代碼段后，該算法首先構(gòu)造一個符合規(guī)則的狀態(tài)轉(zhuǎn)換圖；其次根據(jù)轉(zhuǎn)換圖從代碼段的開頭開始逐字符掃描，若該字符是字母，則將其與包含標(biāo)識符、保留字、運算符、界符的字符庫對比，若此字母在字符庫中匹配成功，則繼續(xù)匹配下一個字符，否則提示錯誤。若該字符不是字母則將判斷其是否是常數(shù)，若是常數(shù)則匹配成功，繼續(xù)匹配下一個字符，否則提示錯誤；后者采用的算法較多且相對復(fù)雜，但基于字符串(規(guī)則)的最大匹配算法目前比較普遍。該算法設(shè)詞典中出現(xiàn)頻率最高的詞的詞長為m，首先從左至右將中文句子分為m 個字符串，其次將m 個字符串分別與詞典中的詞進(jìn)行匹配，若匹配成功則進(jìn)行分詞，否則將該字符串的第一個或最后一個字符去掉，將新串重新匹配，重復(fù)以上步驟直到m 個字符串均匹配結(jié)束，最后輸出結(jié)果。

在輸出的結(jié)果形式上，前者為詞素與屬性值構(gòu)成的<詞素，屬性值>二元組，如，<常數(shù)，128>；后者為中文詞與詞性構(gòu)成的<中文詞，詞性>二元組，如，<我，nr>。

綜上所述，二者聯(lián)系緊密又有不同，可將二者進(jìn)行實驗對齊學(xué)習(xí)，如圖5 所示。

圖5 詞法分析算法和中文分詞算法對比

2.2 語法分析與(依存)句法分析

編譯過程的語法分析與自然語言處理中的(依存)句法分析具有相通性，原因有三：①待處理序列相似；②中間步驟相似；③作用遞進(jìn)。

編譯過程的語法分析基于詞法分析產(chǎn)生的詞，進(jìn)一步分析其語法是否符合語言規(guī)則，主要流行的算法為自頂向下或自底向上的語法樹生成與分析算法。兩種算法首先根據(jù)待分析式提取對應(yīng)的既定規(guī)則（文法），自頂向下的分析算法從文法的開始符號開始推導(dǎo)，并將推導(dǎo)出的終結(jié)符與待分析式進(jìn)行比較，若相同則繼續(xù)推到下一個非終結(jié)符，若不同則回溯，循環(huán)步驟至所有非終結(jié)符均推導(dǎo)結(jié)束；自底向上的分析算法將輸入串字符逐個移入后進(jìn)先出棧，若移入的棧內(nèi)非終結(jié)符可以推導(dǎo)，則將推導(dǎo)出的終結(jié)符與待分析式對比，若與待分析式相同則出棧，若不同則回溯，循環(huán)步驟至所有字符都進(jìn)棧至少一次。其次兩者均將推導(dǎo)出的葉子結(jié)點對應(yīng)的值與待分析式比較，若不相同則提示語法錯誤，如圖6 所示。

自然語言處理的句法分析同樣基于分詞產(chǎn)生的詞單元，進(jìn)一步分析該句話的各部分之間的依賴關(guān)系，在一定程度上可看作是語法分析的更深層次處理。語法分析僅用于分析語句是否成立，而句法分析不僅可判斷語句是否成立，還可以判斷如主謂關(guān)系、動賓關(guān)系等，其中間步驟也同樣使用到了樹與圖的算法，目前比較流行的算法為基于CFG 或PCFG 的分析算法、基于圖（生成式）的依存句法分析[13]、基于轉(zhuǎn)移的依存句法分析等。我們就PCFG 與基于圖（生成式）的分析算法作簡要描述：PCFG 算法首先根據(jù)建立好的語料庫以及待分析式，提取相應(yīng)文法推導(dǎo)式和概率，其次根據(jù)文法推導(dǎo)式生成所有可能產(chǎn)生的語法結(jié)構(gòu)樹，最后將每個樹中所有的概率相乘得到整體概率，整體概率最大的樹被選為最佳的語法樹結(jié)構(gòu)?；趫D（生成式）的分析算法流程如圖7 所示，不再贅述。

圖6 語法分析方法

圖7 基于圖的（生成式）依存句法分析算法流程圖

由此可見，兩者存在聯(lián)系又有不同，可進(jìn)行實驗對齊，達(dá)到彼此認(rèn)知理解的目的。

2.3 語義分析與語義角色標(biāo)注

編譯過程的語義分析與自然語言處理中的語義角色標(biāo)注具有相通性，原因有：作用遞進(jìn)。

編譯過程的語義分析用來判斷某段代碼是否符合既定規(guī)則，如“+”運算要求左右操作數(shù)為整型數(shù)時才可以進(jìn)行加法運算。完成語義分析一般來說需要5 個步驟：變量引用的消解、類型名稱的消解、類型定義檢查、表達(dá)式的有效性檢查、靜態(tài)類型檢查。一般來說語義分析采用遞歸下降等算法達(dá)到生成中間代碼的目的，遞歸下降算法將語句結(jié)束符為節(jié)點，遞歸地逐段判斷代碼是否符合既定的規(guī)則，最后的輸出結(jié)果有諸多種表達(dá)方式，如三地址式、四地址式、逆波蘭式等，如圖8 所示。

自然語言處理的語義角色標(biāo)注用來標(biāo)注一句話中含有語義信息的“角色”，由于“角色”的不同組合，相同的詞在不同句話的語義可能不同。語義角色標(biāo)注任務(wù)可以判斷相同詞在不同語句中的含義，作用可理解為：一句話想要表達(dá)某種含義，需用到哪些“角色”，是編譯語義分析的深層理解。目前公認(rèn)的效果較好的模型是LSGN，如圖9 所示。

圖8 語義分析過程圖

圖9 LSGN 算法流程圖

在輸出的結(jié)果形式上，語義分析可表達(dá)為三地址代碼（op,arg1,arg2），如對于x=（a+b）*（c+d）式子，三地址代碼為：①（+,a,b）、②（+,c,d）、③（*,①,②）、④（=,x,③）；語義角色標(biāo)注則為形如<中文詞，語義角色>的二元組，如：小紅<施事者>。綜上，我們認(rèn)為可將語義分析與語義角色標(biāo)注工作進(jìn)行對齊理解。

2.4 實驗對齊仿真平臺

為了更好地展示NLP工具與編譯過程，我們提供了實驗對齊仿真平臺，它基于Python 語言開發(fā)，Django 作為開發(fā)框架，集合了jieba、pkuseg 等開源第三方庫。頁面布局上，我們選擇將NLP 工具演示放在前端，編譯過程放在后端，目的是為了實驗課程的流程更加清晰，即先使用NLP 工具，使同學(xué)們理解簡單的中文分詞、句法分析、語義角色標(biāo)注在做什么，然后再由淺入深講解編譯原理。

自然語言處理仿真可從多種不同的工具中獲得結(jié)果，增強趣味性。

學(xué)生在實驗課上，首先在自然語言處理過程部分輸入框內(nèi)輸入一段文字，并選擇對應(yīng)的NLP處理工具；其次點擊分析按鈕即可，如圖10 所示。自然語言處理部分輸出結(jié)果共有4 項：分詞、詞性標(biāo)注、句法分析、依存句法分析，如圖11（a）所示。對應(yīng)的，編譯部分的輸出結(jié)果有3 項：詞法分析、語法分析、語義分析，如圖11（b）所示。

3 結(jié) 語

當(dāng)前在各個領(lǐng)域的技術(shù)日趨成熟的條件下，如何將其互相融合用來產(chǎn)生新的想法顯得十分重要。特別是在計算機教育當(dāng)中，如何將原本枯燥的教學(xué)方式、抽象的教學(xué)內(nèi)容靈活化、簡單化、智能化是一個有價值的，且有待深入研究的課題。

基于NLP 的編譯原理課程實驗對齊方法使用一個簡單、智能的網(wǎng)絡(luò)平臺，將NLP 與編譯原理課程實驗結(jié)合在一起，對齊理解。因NLP處理的對象為中文句子，其內(nèi)容更易被同學(xué)們接受，且我們將編譯原理原本抽象的方法與自然語言處理方法進(jìn)行對照，使同學(xué)們可根據(jù)兩者的相通性，從淺入深地理解編譯原理，還可以激發(fā)同學(xué)們對NLP 的研究興趣，使同學(xué)們了解自然語言處理，一舉兩得。通過此類對齊實驗，可使同學(xué)們對編譯原理的內(nèi)在實用性有一個新的認(rèn)知。

在未來，我們還將繼續(xù)挖掘編譯原理課程內(nèi)容與其他前沿知識的相通性，使同學(xué)們更加注重課本知識與其內(nèi)在原理，且在學(xué)習(xí)編譯原理的同時盡量入門一些前沿領(lǐng)域，擴大知識面。此外，我們還將繼續(xù)完善實驗對齊仿真平臺，使同學(xué)們切身實際地體會對齊實驗。