首先,什么是上下无关文法?
上下无关文法 → 2型文法 → 见下文
【2型文法】(上下文无关文法)
产生式形式:A→β,A∈VN(终结符) ,β∈V *(VN∪VT,即可为终结符也可为非终结符)
说明:当以β替换A时,与A的上下文环境无关;
大部分程序设计语言近似于2型文法。
*其余3中文法0型文法、1型文法、3型文法的简单说明,可参考:四种文法的类型(编译原理) - 简书
其次,L={ a^m b^n | m >= n >= 0 } 这一大长串是什么?第一眼看下去就是 m次方和n次方,次方怎么就是语言了???还让我构造文法?其实是这样的,如图1所示:语言 L 其实是由一长串a后面跟着一长串b组成的(怎么会有这么奇怪的语言?唉,这个你别管,这是一种抽象表示)。
那a和b分别有几个呢?a和b的次方以及m >= n >= 0已经告诉我们了,m个a后面跟着n个b,而且m和n的个数都是[0, n)个,而且的而且,题目还说了m>=n。所以这一大长串的字符要么为空字符串ε;要么,首字符必须是a,然后就是0到n个连续-连续-连续的a,之后才是0到n个b。
好了,题目大意理解得差不多了,那这个一大长串的L的文法到底要怎么写呢?这个问题确实有点绕,所以我们一步一步来分析:
(0)令文法为G[S],S为文法起始符(一般约定)
(1)字符串可以为空,所以有 S → ε
(2)不为空时,首字符一定是a,但由于m>=n,a的个数和b的个数存在差值,所以,令:k = m - n(k>=0),这样我们就可以单独处理多出来的a了,即{ a^mb^n | m >= n >= 0 } = { a^ka^nb^n | k >= n >= 0 }。所以,我们可以把字符串分成两部分A = a^k, B = a^nb^n,此时有S → AB
(3)继续细化。到这里,大家别忘了哦,根据上下文无关文法的定义,产生式右端如果能写成终结符后面跟着非终结符的话,一定要改成这样的形式哦~所以A → aA | ε (一直在递归这种形式,而且必须要有ε,否则文法停不来)
(4)接着就是B部分。思想类推B → aBb | ε
(5)所以,得文法G[S]:S → AB | ε
A → aA | ε
B → aBb | ε