正则文法
有时一个正则表达式很复杂，我们希望能够把这个正则表达式用记号记下来，以便以后使用，于是就有了正则定义（Regular Definitions）：
设Σ是符号表，如果有一系列的定义：
d1 → r1
d2 → r2
…
dn→ rn
并且：
任一个di都是一个新的符号，它既不属于Σ，也不属于{d1,d2,d3,…,d(i-1)}
任一个ri都是一个正则表达式，能够由符号表Σ以及{d1,d2,d3,…,d(i-1)}所表示
这样就构成了一组正则表达式定义。
上下文无关文法
组成要素：
- 一个终结符的有限集（A set of terminal symbols），构成文法的最基本的字符就是这个文法的终结符，例如- 一个能够产生个位数的文法规则digit –> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9，则数字0～9就是这个文法的终结符，一个能够产生变量名的文法规则variable –> (‘A’-‘Z’ | ‘a’-‘z’) *((‘A’-‘Z’ | ‘a’-‘z’ | ‘0’-‘9’)，则所有的英文字母和数字就是文法的终结符。
- 一个非终结符的有限集（A set of nonterminals），例如上面的digit、variable就是非终结符。
- 一个产生式的有限集，例如上面的“digit –> …”和“variable –> …”两个规则可以构成一个产生式集
- 一个非终结符作为开始符号，在非终结符集中，必须指定其中一个作为开始符号。
几个问题：
为什么是“上下文无关”而不是“上下文有关”呢？
这是因为在利用一个上下文无关文法生成语言的时候，我们可以随意将文法规则左边的非终结符派生（更换）为右边的终结符或非终结符
正则文法和上下文无关文法的区别？
在正则定义中是不允许递归定义的。例如A → aA|b不是一个正则定义，为其左边的A必须是一个新的符号，也就是说不能在其他地方定义过，但是其右边要求每一个符号都是定义过的，因此这个定义无法满足。而上下文无关文法则没有这个约束，因此A → aA|b是一个上下文无关文法的产生式，但不是正则定义的定义式。