文法(syntax)是一种描述编程语言结构的规则，比如，程序由语句块(block)组成，语句块又是由语句构成，语句又由表达构成，表达又是由词法记号(token)构成
文法可以使用上下文无关的文法(context-free grammars)或者BNF(Backus - Naur Form)范式来描述
分析器(parser)：从图中可以看出，parser获取词法记号流(tokens)，并分析它是否可以由源程序的文法产生(也就是说，按照一定的规则，是否可以产生出这样的输入字符串)
parser可以报告源程序中的任何语法错误，parser输出分析树的某种表示
还有一些任务，需要放在稍后进行处理，也就是在"前端的其余部分"进行处理，产生中间表示，这里说的任务可能有：把各种记号的信息收入符号表，完成类型检查和其他的语意检查
另外注意，分析树不一定会真正生成
正规表达式是一个和token有关的概念，因此有些串是无法用正规式表示的，比如：配对括号构成的串，语言的嵌套结构等。为此，我们这里引入了一个新的用于描述串集合(语言)的方法，也就是上下文无关文法
1. 上下文无关文法
上下文无关文法 G 是一个四元组(Vt, Vn, S, P)，其中：
1) Vt是一个非空有限集合，其元素称为终结符。注意，通常来说记号是终结符的同义词
2) Vn是一个非空有限集合，其元素称为非终结符。Vn 满足 Vn ∩ Vt 为空集
3) S是非终结符，称为开始符号。它定义的终结符串就是文法定义的语言
4) P是产生式的有限集合，在这里的产生式是形如 A -> α 的式子，其中A属于非终结符，α 为终结符和非终结符的任意组合，α 也可以为 ε
举例：
文法 ( {id, +, *, (, )}, {expr,op}, expr, P )，其中P为一下产生式：
expr -> expr or expr
expr -> (expr)
expr -> -expr
expr -> id
op -> +
op -> *
注意一下，我们通常使用大写字母或者多个小写字母，来表示非终结符，其中用S表示开始符号，比如：
expr 多个小写字母，表示非终结符
A 大写字母，表示非终结符
我们把终结符和非终结符，统一叫做文法符号，用X,Y,Z 等处于字符表后的大写字母表示
终结符号串，指的是由任意多个终结符组成的串(可以为ε)，常用 u,v,w,x,y,z 等处于字符表后的小写字母表示
符号串，指的是由任意多个终结符和非终结符组成的串(可以为ε)，常用希腊字母表示，比如：α
对于 A -> α1 |α2 |α3 ... αk ，这里称α1，α2，α3，α4...αk是A的选择
基于上面的约定，我们可以这样来写前面的例子：
S -> SAS | (S) | -S | id
A -> * | +