上下文无关文法的可视化描述

何 锫，黄 海，张远平

（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