递归对形式文法教学的作用范文

《福建电脑杂志》2014年第十二期

1文法的形式化描述

本节详细给出文法的形式化定义，首先给出字母表∑的定义：定义1.1：字母表∑是一个非空符号的集合，集合中的符号是原子的，不可分。有限长度的符号序列称为字符串。常见的字母表如二十六个字母及数字构成程序语言的基本字母表，{0，1}等。字符串w的长度为w中符号的个数，记为|w|，长度为0的字符串称为空串，常用ε表示。令w1=a1a2…an，w2=b1b2…bm，则字符串w1、w2的连接运算记为w=w1w2=a1a2…anb1b2…bm，εw=wε，另外n个字符串w构成的字符串可简记为wn。下面给出语言的定义。根据Chomsky文法分类模型，文法可分为0-型文法、1-型文法、2型文法和3型文法，各种文法的详细讨论，请参看相关文献[4]。从0-型文法开始，文法复杂度递增，表达能力递增，但相应文法语言的分析越困难。综合表达能力和分析困难程度，编译原理重点在2-型文法和3-型文法的分析，根据两种文法的特点，这两种文法分别称为上下文无关文法和线性文法。上下文无关文法产生式的左部为单个非终结符号。下文的方法围绕上下文无关文法展开，由于3-型文法是2-型文法的子集，因此下文所讨论的方法同样适应于3-型文法。

2基于递归方法的文法分析

本节将在上节的基础上，阐述递归分析方法在文法中的作用，包括两方面的作用：如何利用递归方法计算形式化文法的语言；如何利用递归方法定义语言，并从递归定义的语言产生文法。在编译原理的教学实践中，对于文法所产生语言的描述主要基于集合论的基础，特殊的情况，例如3-型文法的语言可以用正则式进行描述。但这些方法在实际使用中有着明显的不足：基于集合的描述方法不是一种构造性和过程性的描述，复杂文法的语言集合描述需要复杂的数学对象的构造说明，不便于自动化，算法化处理；而正规式的表达能力则限制了它的使用。例如，下面的文法。该文法形式简单，读者很容易理解，马上能得出该文法所产生的语言。该语言非形式的描述为：((L))L((L))或(((L)))L(((L)))，显然，这种描述及其模糊不清，不能准确描述其所对应的语言。递归性是体现文法复杂性最重要的构造性特征，基于递归的描述方法是数学中用于定义复杂数学对象的常用方法。这种方法具有构造性及过程性的特点，且具有强大的描述能力，在离散数学课程中有所涉及。以上文法所表示的语言很容易用下面的方法描述，该方法表现为一规则序列，令L为该语言。其中，规则（1）为基础规则，（2）和（3）为扩展规则，规则（4）确保语言L的最小性。这种基于规则的语言定义基于文法的递归结构。反之，引进非终结符号S，很容易构造出相应规则所定义语言的文法。但是，所产生的文法只具有递归性结构的语法特点，要体现其余的语法要素，则规则中需要相应的规则对应。对于复杂语言的描述，这种基于规则的方法自然、容易理解，又具有严谨性。下面讲述如何从已知的文法采用递归的方法计算文法的语言，同样以下面的表达式文法为例进行说明。对于文法任意一个产生式：A→αBβ，其中A和B是非终结符号。则根据产生式可得L(A)勐L(α)L(B)L(β)，其中L(A)和L(B)分别表示A和B作为开始符号相关文法的语言，L(α)和L(β)分别表示字符串α和β直接或间接推理出得句子的集合。当A→γ1｜γ2｜…｜γn包含某文法中所有左部为A的产生式，则L(A)=L(γ1)∪L(γ2)∪…∪L(γn)。下面基于以上的讨论计算文法G2的语言。上式已经消去了所有的中间文法符号，是个复杂的可递归展开的式子，可采用类似的不动点的计算方法，但展开过程较为繁琐，此处不进行详细的展开。根据上式的结构，采用规则定义的方法给出语言的描述，这样可以灵活地结合上面语言的递归计算及基于规则的语言递归定义方法。

3结论

针对编译原理课程中形式文法教学过程中存在的问题，提出了基于递归方法的语言定义方法和语言计算方法。这种方法丰富了教学内容和教学方法，有利于培养学生抽象而严谨的思维能力，提高使用基础数学知识解决实际问题的能力。

作者：陈冬火单位：苏州大学计算机科学与技术学院