Bison的基本概念

#一、语言和上下文无关文法

Bison只能解析上下文无关文法描述的语言。这说明你要指定一个或多个句法群Semantic Groups并且给出构造他们的相关规则。比如说，在c语言中，有一种Semantic Groups叫做“expression”。构件表达式的一个规则可能是：”一个表达式可以由一个减号和其他表达式构成“。另一个规则可能是”一个表达式可以是一个整数“。你可以看出，规则常常是递归的，但是至少要有一个规则可以终止递归。

最常见的用人类可读的方式表达这种规则的描述范式叫 Backus-Naur Form or “BNF” (巴科斯-范式)，它是为了描述 Algol 60 语言而开发出来的。任何用BNF表达的语法都是上下文无关的语法。输入到Bison的代码本质上是机器可读的BNF。

当然，并不是所有的上下文无关语言都可以被Bison处理，只有LALR（1）/*Look Ahead 1 and left-to-right Rightmost derivation 左递归最右推导前窥1 */语法才可以被Bison接受。简单的说，它必须能够在只多读取一个字符的前提下知道如何去解析输入字符串的任何一个部分。严格的说，它是一个LR(1)语法的描述，LALR(1)文法有许多额外的宪制很难简单的解释清楚;但是在实践中很少能找到一个不是LALR(1)文法的LR(1)语法。

在正式的文法规则中，每种syntactic unit或者grouping 是用一个 symbol标示的。那些用来根据语法规则构建更小的语法结构的符号被称为nonterminal symbols 非终结符；那些不能再切分的符号被叫做 terminal symbols 终结符 或者 token types。我们把输入串中的一个终结符叫做token，把一个非终结符叫做grouping。We call a piece of input corresponding to a single terminal symbol a token,and a piece corresbonding to a single nonterminal symbol a grouping.

我们可以用c语言为例子来说明 符号，终结符和非终结符的意义。 c语言的记号token分为 identifiers,constants(numeric and string),和一系列关键词，算数运算符和标点符号；C语言的终结符包括了 ‘identifier’,’number’,’string’,加上每一个关键词的符号，还有运算符和标点符号：’if’,’return’,’const’,’static’,’int’,’char’,’plus-sign’,’open-brace’,’close-brace’,’comma’ 等等。（这些记号可以被分成单个字符，但是这是一个词法学问题，不是语法问题。）

这里有一个简单的C函数切分成记号的例子：

1
2
3
4
5
6
7
8
int 			/* keyword 'int'*/
square(x) 		/* identifier,open-paren, */
				/* identifier,close-paren*/
int x;			/* keyword 'int',identifier,semicolon*/
{ 				/* open-brace */
	return x*x; /* keyword 'return',identifier,*/
				/* asterisk,identifier,semicolon */
}				/* close-brace */

C语言的语法分组(syntactic groupings)包含了：expression,statement,delcaration,function definition.这在c语言的语法中被表示成非终结符 ‘expression’,’statement’,’declaration’,’function definition’。完整的语法使用了几十种其他的语言规则（每一个都有自己的非终结符）用来表示上面四个的意义。在上面的例子中，是一个函数定义，它包含了一个声明和一个定义。在定义中，每一个x是一个表达式，’x*x’也是一个表达式。

没一个非终结符必须有相应的语法规则来说明它是如何用其他简单的语法构件来组合的。例如，一种c语言语句return,这可能用（非正式的）语法规则描述成下面这种形式：

A ‘statement’ can be made of a ‘return’ keyword, an ‘expression’ and a ‘semicolon’.

还有其它许多种表示语句的规则，每个规则对应了一种c语言语句.

一个非终结符必须区别于一个特殊的完全的语言中的话语定义。one nonterminal symbol must be distinguished as the special one whick defines a complete utterance in the language. 它被称作 start symbol。在一个编译器里，这表示一个完整的输入程序。在c语言中，非终结符 ‘sequcence of definitions and declarations’扮演了这个角色；

例如，’1+2’是一个合法的c语言expression–c语言的一个合法部分—但是它在整个c程序里面不合法。在上下文无关文法中，这遵从了一个事实：’expression’不是一个起始符start symbol.

Comments

⬆︎TOP