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

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

（1.武漢科技大學 計算機科學與技術學院，武漢 430081；2.武漢大學 計算機學院，武漢 430072）

0 引 言

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

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

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

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

1.1 編譯原理過程分析

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

1）詞法分析。

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

圖1 編譯過程示意圖

表1 詞法分析結果表

2）語法分析。

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

圖2 語法分析示意圖

3）語義分析。

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

1.2 自然語言處理過程分析

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

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

1）分詞與詞性標注。

以中文語言信息為例，現在，中文分詞與詞性標注技術已趨于成熟，且在自然語言處理領域的任何工作當中都有使用[9]。我們以jieba分詞[10]為例，簡要分析中文分詞與詞性標注的原理。

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

（2）詞性標注：jieba 詞性標注主要基于規則和統計的方法工作，且通過HMM 算法來進行詞性標注。

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

2）句法分析。

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

圖3 語法分析結果

3）語義角色標注。

語義角色標注的任務是找出句子中謂詞的相應語義角色成分，包括核心語義角色（如施事、受事等）和附屬語義角色（如地點、時間、方式、原因等），在句法分析構造的句法樹的基礎上，分析判斷句法樹結點的語義角色，是常規的解決思路[12]。

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

圖4 語義角色標注示例圖

2 實驗對齊

2.1 詞法分析與詞性標注

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

表2 詞法分析與詞性標注（常用）詞性類別對齊表

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

表3 詞法分析與詞性標注核心算法對齊表

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

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

綜上所述，二者聯系緊密又有不同，可將二者進行實驗對齊學習，如圖5 所示。

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

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

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

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

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

圖6 語法分析方法

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

由此可見，兩者存在聯系又有不同，可進行實驗對齊，達到彼此認知理解的目的。

2.3 語義分析與語義角色標注

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

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

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

圖8 語義分析過程圖

圖9 LSGN 算法流程圖

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

2.4 實驗對齊仿真平臺

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

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

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

3 結 語

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

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

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