第1个回答 2022-07-01
首先 ，什么是上下无关文法？
上下无关文法 → 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 | ε