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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2）a.對(duì)每個(gè)X∈N計(jì)算后繼集Follow（X）；

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

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

4）a.對(duì)每個(gè)X∈SL，畫(huà)一標(biāo)識(shí)為X的結(jié)點(diǎn)；

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

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

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

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

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

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

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

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

3 討 論

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

4 結(jié)束語(yǔ)

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

［1］ 孫茂松，劉挺，姬東鴻，等.語(yǔ)言計(jì)算的重要國(guó)際前沿［J］.中文信息學(xué)報(bào)，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è)計(jì)語(yǔ)言編譯原理［M］.北京：國(guó)防工業(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］ 扎西加.上下文無(wú)關(guān)文法與藏語(yǔ)句分析［J］.西藏大學(xué)學(xué)報(bào)：自然科學(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］ 趙國(guó)榮，王文劍.一種處理結(jié)構(gòu)化輸入輸出的中文句法分析方法［J］.中文信息學(xué)報(bào)，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)曉炟，等.蒙古語(yǔ)短語(yǔ)結(jié)構(gòu)樹(shù)的自動(dòng)識(shí)別［J］.中文信息學(xué)報(bào)，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)代語(yǔ)文：學(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

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

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