语法分析---上下文无关的文法(context-free grammars)

文法(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 -> * | +