上下文無關文法的可視化描述

何 锫，黃 海，張遠平

（1.廣州大學計算機科學與教育軟件學院，廣東 廣州 510006；2.長沙理工大學計算機與通信工程學院，湖南長沙 410114；3.廣東第二師范學院計算機科學系，廣東 廣州 510303）

上下文無關文法的可視化描述

何 锫1，2，黃 海3，張遠平1

（1.廣州大學計算機科學與教育軟件學院，廣東 廣州 510006；2.長沙理工大學計算機與通信工程學院，湖南長沙 410114；3.廣東第二師范學院計算機科學系，廣東 廣州 510303）

上下文無關文法借助有限規則集和遞歸手段實現語言生成問題的刻畫.這一形式系統多以符號串集形式呈現，并因遞歸技術的應用而漸變復雜，晦澀難懂.文章探討其可視分析問題，涉及文法到有限狀態變遷系統的構造、理論證明和應用方法.這項工作不僅有助形式系統各要素間的關系的直觀刻畫，而且為結構化推導分析、語義重用奠定基礎.

上下文無關文法；可視分析；有限狀態變遷系統

句法分析一直是自然語言處理研究的重點和難點［1］.較為常見的描述方法有喬姆斯基所提出的形式文法系統［2-7］.他把自然語言與符號語言作為整體進行考量，以為人們交流過程實際是不斷使用有限規則和遞歸技術來生成語言的，就此得到了至今影響深遠的革命性語言研究成就.

喬姆斯基從語言生成角度把語言分為4類，每類都有1組生成規則（也叫產生式），通常記為A→α形式.當對規則依次增強限制條件，就得到了所謂的0、1、2、3型文法.在這一分類意義下，2型文法（上下文無關文法）是應用極為廣泛的，在自然語言處理、程序語言描述方面有著廣泛應用［3-10］.

然而2型文法通常以符號串集形式呈現，了解系統描述的語言對象時又得依賴樹結構來交流和刻畫.加之遞歸技術的使用，系統推演的動態特性很難清楚明了的把握.如規則間有什么關系？所有推導序列集是否封閉和有律可循？樹結構的比對可否線性化為簡單的串比較？帶著這些疑問，筆者提出文法的可視分析方法.

可視分析法關注以下3個事實：①借助有限狀態轉換圖，建立等價的可視形式分析框架；②證明2型文法所刻畫的任意句法，存在相應的可視驗證路徑；③示意應用方法.

1 上下文無關文法

上下文無關文法也叫短語結構語法.在詳細介紹系統可視分析原理前，筆者先做些符號約定，給出相關術語和定義［3-7］.

定義1（C*） 設C是一個有限符號集，則C*稱為C的閉包，表示一切C中符號拼接形成的符號串集合.

定義1（上下文無關文法） 一個上下文無關文法G＝（N，T，S，P）是如下定義的四元式：

N：非終結符集合，用于表示待擴展的概念；

T：非空的終結符集合，代表詞匯表；

S：一個特殊的非終結符，代表系統的開始狀態；

P：產生式集合，代表一組語言的生成規則.每個產生式通常表示為A→α，其中A∈N，α是N與T中符號拼接形成的符號串，習慣記為α∈（N∪T）*.

定義2（直接推導） 給定文法G＝（N，T，S，P）如上.設αAγ，αβγ均為（N∪T）*中的串，且A→β∈P，則稱αβγ是αAγ相對產生式A→β的一個直接推導，記為αAγαβγ.特別地，當A是出現在αAγ中的最左非終結符時，推導記為或，稱作最左推導.而A不在δ中時＝ δ，稱0-推導.

類似地，可以定義最右推導.值得指出的是，為簡化處理，程序語言的生成和識別多據最左或最右推導原則進行.因此無特別說明情況下，以下都指最左推導.

2 變遷狀態描述模型

上節介紹的形式文法利用有限規則概括了語言的生成原理與方法，整個過程有賴于符號替換，但并未直接揭示規則或產生式間的關系，因而不便于系統的深入分析與應用.這里筆者嘗試其可視化分析，用等價的有限狀態變遷圖來刻畫語言、句型與規則的關系，概括語言的生成.這一工作可為形式文法的結構分析奠定基礎.

為構造變遷圖，針對文法的每條產生式A→α引入2種結點標識SA和，再計算標識間的關聯即關聯函數即可.

定義5（標識集） 給定上下文無關文法G＝（N，T，S，P），其左標識集SL和右標識集SR分別如下：

a）SL＝｛Sx|x是G的某產生式的左部非終結符｝；

定義6（后繼集） 給定上下文無關文法G＝（N，T，S，P），Follow：N→2N叫后繼集函數，定義如下：

Follow（X）＝｛Y|…XY…是G的句型｝.

定義7（關聯集） 給定上下文無關文法G＝（N，T，S，P），LMC：SR→2SL是如下定義的一個映射，叫關聯集函數：

定義8（等價關聯） 給定上下文無關文法G＝（N，T，S，P）和SR上的關聯函數LMC：SR→2SL.如果對X，Y∈SR有LMC（X）＝LMC（Y），則說X，Y等價關聯，記為X≌Y.

算法1（模型構造）

輸入：上下文無關文法G＝（N，T，S，P）

輸出：等價的有限狀態變遷圖（模型）

1）依據文法G構造標識集合SL和SR.

2）a.對每個X∈N計算后繼集Follow（X）；

我國刑法第285條第二款非法獲取計算機數據罪、非法控制計算機系統罪規定：“違反國家規定，侵入前款規定以外的計算機信息系統或者采用其他技術手段，獲取該計算機信息系統中存儲、處理或者傳輸的數據，或者對該計算機信息系統實施非法控制，情節嚴重的，處三年以下有期徒刑或者拘役，并處或者單處罰金；情節特別嚴重的，處三年以上七年以下有期徒刑，并處罰金。”

3）據步驟2）的結果對右標識集SR進行等價關聯的劃分.

4）a.對每個X∈SL，畫一標識為X的結點；

6）為以上步驟得到的每個結點作自身到自身的ε箭弧.

7）以上所得有向圖即為G的模型LM（G），其中SS∈SL為開始狀態.

定義9（通路序列） 給定上下文無關文法G＝（N，T，S，P）及相應的模型，由通路上標記拼接形成的序列叫通路序列.

i）歸納基始：對0-推導或任意產生式S→α∈P，由算法1易見命題成立.

例1 給定上下文無關文法G＝（N，T，S，P）：

圖1 例1文法的模型Fig.1 Grammar model of example 1

例2 給定上下文無關文法G＝（N，T，S，P）［11］，求其相應的模型.

圖2 例2文法的模型Fig.2 Grammar model of example 2

3 討 論

以上所述方法源自筆者前期的程序驗證工作［12］.眾所周知，程序的形式驗證是十分困難的議題，為充分利用既有證明結論，本文對構件集進行建模，得到了類似模型檢測意義上的狀態變遷系統［12］.該思想再應用于推導序列集的描述，便有文法的可視描述模型［14-15］.本文工作主要專注模型的優化，除探尋結點集規模的壓縮外，還旨在語言學基礎研究中拋磚引玉.這一系列結果不僅有助揭示產生式間的關系，實現推導的高效計算及文法的優化，而且已在演化計算等優化算法領域得到了應用［13-15］.模型方法呈現的優勢是：推導以及繁瑣的語法樹的解析可以轉化為正規語言問題來探討；樹意義上的對比、檢索實質是正規語言的對比；樹的結構化構造、重用將因正規式的引入而成為可能.

4 結束語

本文介紹了形式文法的可視分析原理，給出了由文法到有限狀態變遷系統的轉換方法和理論證明思想.從實例和相關應用來看，這是一項應用前景美好、值得深入探究的工作.未來工作重心是：模型優化，串模式的結構分析以及語言文字相關信息處理問題.

［1］ 孫茂松，劉挺，姬東鴻，等.語言計算的重要國際前沿［J］.中文信息學報，2014，28（1）：1-8.SUN M S，LIU T，JI D H，et al.Frontiers of language computing［J］.J Chin Inform Proces，2014，28（1）：1-8.

［2］ CHOMSKY N.Syntactic structures［M］.2nd ed.Berlin：Mouton de Gruyter，2002.

［3］ AHO A V，LAM M S，SETHI R，et al.Compilers：Principles，Techniques，and Tools［M］.2nd ed.Beijing：Pearson Edu，Inc，2007.

［4］ HOPCROFT J E，MOTWANI R，ULLMAN J D.Automata theory，languages，and computation［M］.3rd ed.Beijing：Pearson Education，Inc，2008.

［5］ 陳火旺，劉春林，譚慶平，等.程序設計語言編譯原理［M］.北京：國防工業出版社，2005.CHEN H W，LIU C L，TAN Q P，et al.Programming language：Compiler principle［M］.Beijing：National Defense Industry Press，2005.

［6］ 蔣立源，康慕寧.編譯原理［M］.西安：西北工業大學出版社，2000.JIANG L Y，KANG M N.Compiler principle［M］.Xi'an：Northwestern Polytechnical University Press Co Ltd，2000.

［7］ 張素琴，呂映芝，蔣維杜，等.編譯原理［M］.第2版.北京：清華大學出版社，2011.ZHANG S Q，LU Y Z，JIANG W D，et al.Compiler principle［M］.2nd ed.Beijing：Tsinghua University Press，2011.

［8］ 扎西加.上下文無關文法與藏語句分析［J］.西藏大學學報：自然科學版，2013，28（2）：37-42.TASHI GYANL.Analysis on Tibetan syntax and context free grammar［J］.J Tibet Univ：Nat Sci Edi，2013，28（2）：37-42.

［9］ 趙國榮，王文劍.一種處理結構化輸入輸出的中文句法分析方法［J］.中文信息學報，2015，29（1）：139-145.ZHAO G R，WANG W J.A Chinese parsing method based on interdependent and structured input and output spaces［J］.J Chin Inform Proces，2015，29（1）：139-145.

［10］烏蘭，達胡白乙拉，關曉炟，等.蒙古語短語結構樹的自動識別［J］.中文信息學報，2014，28（5）：162-169，181.WU L，DABHURBAYAR，GUAN X D，et al.Phrase structure prasing of Mongolian［J］.J Chin Inform Proces，2014，28（5）：162-169，181.

［11］姚明曉.淺談喬姆斯基《句法結構》［J］.現代語文：學術綜合版，2013，11：156-157.YAO M X.A brief comment on the syntactical structure by Chomsky［M］.Modern Chin：Acad Edi，2013，11：156-157.

［12］HE P，KANG L S，COLIN G，et al.Hoare logic-based genetic programming［J］.Sci China：Inform Sci，2011，54（3）：623-637.

［13］HARMAN M，MANSOURI S A，ZHANG Y.Search-based software engineering：Trends，techniques and applications［J］.ACM Comput Surv，2012，45（1）：11：1-11，61.

［14］HE P，DENG Z L，WANG H F，et al.Model Approach to Grammatical Evolution：Theory and case study［J］.Soft Comput，2015.

［15］HE P，COLIN G J，WANG H F.Modeling grammatical evolution by automaton［J］.Sci China：Inform Sci，2011，54（12）：2544-2553.

Visualized description of context-free grammar

HE Pei1，2，HUANG Hai3，ZHANG Yuan-ping1
（1.School of Computer Science and Educational Software，Guangzhou University，Guangzhou 510006，China；2.School of Computer and Communication Engineering，Changsha University of Science and Technology，Changsha 410114，China；3.Department of Computer Science，Guangdong University of Education，Guangzhou 510303，China）

Context-free grammar is a formal framework delineating language generating in light of a finite set of rules and recursions.It appears in string forms and is employed on the basis of recursions，therefore becoming complex and difficult to understand.In this paper，we will elaborate on the visualized counterpart of the formal system，discussing transformation of grammar into finite state transition system，theoretical proofs and applications.This work not only contributes much to intuitive grasp of relationships between various factors of the concerned grammar，but also lays the foundation for structured derivation analysis and semantic reuse.

context-free grammar；visualized analysis；finite state transition system

TP 310

A

1671-4229（2016）01-0008-05

【責任編輯：陳 鋼】

2015-12-26；

2016-01-08

國家自然科學基金資助項目（61170199）；廣東省自然科學基金資助項目（2015A030313501）；廣東省教育廳青年創新人才資助項目（2015KQNCX109）.

何 锫（1963-），教授，博士.E-mail：bk_he＠126.com