构造c语言的上下文无关文法,正则文法和上下文无关文法

对于文法G=(V, T, S, P)，如果产生式的形式如下：

A -> xB

A -> x

其中A, B属于V，x属于T*，则称为右线性文法；相似的，如果产生式的形式如下：

A -> Bx

A -> x

则称为左线性文法。右线性文法和左线性文法统称为正则文法。

正则表达式的表达能力等价于正则文法，正则表达式的定义如下：

字母表中的任意字母是正则表达式，空串和空集也是正则表达式；

如果r, s是正则表达式，那么r|s, rs, r*, (r)也是正则表达式。

正则表达式的扩展：

r+：一个或多个重复

.  ：任意字符

[a-z]：字符范围

[^abc]：不在给定集合中的任意字符

r?：可选

正则表达式只能使用终结符(字母表中的字符)，因而很容易变得复杂又难懂，实际中，经常使用正则描述，正则描述允许使用非终结符定义表达式，很像EBNF，但是它限制在未完全定义之前，不能使用非终结符，也就是说不允许递归或自嵌套。

像正则表达式的表达能力等价于正则文法一样，BNF范式的表达能力等价于上下文无关文法。BNF是“Backus Naur Form”的缩写。John Backus和Peter Naur首次引入一种形式化符号来描述给定语言的语法。

BNF的元符号：

::=表示“定义为”，有的书上用-->|表示“或者”< &g