何 锫，黃 海，張遠(yuǎn)平

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

上下文無關(guān)文法的可視化描述

何 锫1，2，黃 海3，張遠(yuǎn)平1

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

上下文無關(guān)文法借助有限規(guī)則集和遞歸手段實(shí)現(xiàn)語言生成問題的刻畫.這一形式系統(tǒng)多以符號串集形式呈現(xiàn)，并因遞歸技術(shù)的應(yīng)用而漸變復(fù)雜，晦澀難懂.文章探討其可視分析問題，涉及文法到有限狀態(tài)變遷系統(tǒng)的構(gòu)造、理論證明和應(yīng)用方法.這項工作不僅有助形式系統(tǒng)各要素間的關(guān)系的直觀刻畫，而且為結(jié)構(gòu)化推導(dǎo)分析、語義重用奠定基礎(chǔ).

上下文無關(guān)文法；可視分析；有限狀態(tài)變遷系統(tǒng)

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

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

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

可視分析法關(guān)注以下3個事實(shí)：①借助有限狀態(tài)轉(zhuǎn)換圖，建立等價的可視形式分析框架；②證明2型文法所刻畫的任意句法，存在相應(yīng)的可視驗證路徑；③示意應(yīng)用方法.

1 上下文無關(guān)文法

上下文無關(guān)文法也叫短語結(jié)構(gòu)語法.在詳細(xì)介紹系統(tǒng)可視分析原理前，筆者先做些符號約定，給出相關(guān)術(shù)語和定義［3-7］.

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

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

N：非終結(jié)符集合，用于表示待擴(kuò)展的概念；

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

S：一個特殊的非終結(jié)符，代表系統(tǒng)的開始狀態(tài)；

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

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

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

2 變遷狀態(tài)描述模型

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

為構(gòu)造變遷圖，針對文法的每條產(chǎn)生式A→α引入2種結(jié)點(diǎn)標(biāo)識SA和，再計算標(biāo)識間的關(guān)聯(lián)即關(guān)聯(lián)函數(shù)即可.

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

a）SL＝｛Sx|x是G的某產(chǎn)生式的左部非終結(jié)符｝；

定義6（后繼集） 給定上下文無關(guān)文法G＝（N，T，S，P），F(xiàn)ollow：N→2N叫后繼集函數(shù)，定義如下：

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

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

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

算法1（模型構(gòu)造）

輸入：上下文無關(guān)文法G＝（N，T，S，P）

輸出：等價的有限狀態(tài)變遷圖（模型）

1）依據(jù)文法G構(gòu)造標(biāo)識集合SL和SR.

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

我國刑法第285條第二款非法獲取計算機(jī)數(shù)據(jù)罪、非法控制計算機(jī)系統(tǒng)罪規(guī)定：“違反國家規(guī)定，侵入前款規(guī)定以外的計算機(jī)信息系統(tǒng)或者采用其他技術(shù)手段，獲取該計算機(jī)信息系統(tǒng)中存儲、處理或者傳輸?shù)臄?shù)據(jù)，或者對該計算機(jī)信息系統(tǒng)實(shí)施非法控制，情節(jié)嚴(yán)重的，處三年以下有期徒刑或者拘役，并處或者單處罰金；情節(jié)特別嚴(yán)重的，處三年以上七年以下有期徒刑，并處罰金?！?/p>

3）據(jù)步驟2）的結(jié)果對右標(biāo)識集SR進(jìn)行等價關(guān)聯(lián)的劃分.

4）a.對每個X∈SL，畫一標(biāo)識為X的結(jié)點(diǎn)；

6）為以上步驟得到的每個結(jié)點(diǎn)作自身到自身的ε箭弧.

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

定義9（通路序列） 給定上下文無關(guān)文法G＝（N，T，S，P）及相應(yīng)的模型，由通路上標(biāo)記拼接形成的序列叫通路序列.

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

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

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

例2 給定上下文無關(guān)文法G＝（N，T，S，P）［11］，求其相應(yīng)的模型.

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

3 討 論

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

4 結(jié)束語

本文介紹了形式文法的可視分析原理，給出了由文法到有限狀態(tài)變遷系統(tǒng)的轉(zhuǎn)換方法和理論證明思想.從實(shí)例和相關(guān)應(yīng)用來看，這是一項應(yīng)用前景美好、值得深入探究的工作.未來工作重心是：模型優(yōu)化，串模式的結(jié)構(gòu)分析以及語言文字相關(guān)信息處理問題.

［1］ 孫茂松，劉挺，姬東鴻，等.語言計算的重要國際前沿［J］.中文信息學(xué)報，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］ 陳火旺，劉春林，譚慶平，等.程序設(shè)計語言編譯原理［M］.北京：國防工業(yè)出版社，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］.西安：西北工業(yè)大學(xué)出版社，2000.JIANG L Y，KANG M N.Compiler principle［M］.Xi'an：Northwestern Polytechnical University Press Co Ltd，2000.

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

［8］ 扎西加.上下文無關(guān)文法與藏語句分析［J］.西藏大學(xué)學(xué)報：自然科學(xué)版，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］ 趙國榮，王文劍.一種處理結(jié)構(gòu)化輸入輸出的中文句法分析方法［J］.中文信息學(xué)報，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］烏蘭，達(dá)胡白乙拉，關(guān)曉炟，等.蒙古語短語結(jié)構(gòu)樹的自動識別［J］.中文信息學(xué)報，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］姚明曉.淺談喬姆斯基《句法結(jié)構(gòu)》［J］.現(xiàn)代語文：學(xué)術(shù)綜合版，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

【責(zé)任編輯：陳 鋼】

2015-12-26；

2016-01-08

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

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