介绍与词法语法分析相关的概念。

简介 #

可以通过 yum install flex flex-devel bison 安装 Linux 中的 flex 以及 bison 包。

BNF #

也就是 Backus-Naur Form 巴科斯范式，由 John Backus 和 Peter Naur 首先引入的，用来描述计算机语言语法的符号集，现在，几乎每一位新编程语言书籍的作者都使用巴科斯范式来定义编程语言的语法规则。

其推到规则通过 ::= 定义，左侧为非终结符，右侧为一个表达式；表达式由一个符号序列，或用 '|' 分隔的多个符号序列构成，从未在左端出现的符号叫做终结符。

"..."  : 术语符号，表示字符本身，用double_quote用来代表双引号
< >    : 必选项
[ ]    : 可选项，最多出现一次
{ }    : 可重复0至无数次的项
|      : 左右两边任选一项，相当于OR
::=    : 被定义为

如下是 Java 中的 For 语句实例：

FOR_STATEMENT ::=
"for" "(" ( variable_declaration |
( expression ";" ) | ";" )
[ expression ] ";"
[ expression ] ";"
")" statement

其中 RFC2234 定义了扩展的巴科斯范式 (ABNF)。

上下文无关文法 #

简单来说就是每个产生式的左边只有一个非终结符；首先，试着用汉语来稍微解释一下。

本来这个进球就是违例的，但你不肯承认也没办法
我有一本来自美国的花花公子杂志
拿我的笔记本来

如果汉语是上下文无关文法，那么我们任何时候看见 "本来" 两个字，都可以把它规约为一个词；可惜汉语不是上下文无关文法，所以能否归约为一个词，要看它的上下文是什么。如上的示例中，只有第一句可以规约为一个词。

参考 #

关于最原始的论文，可以参考 Lex - A Lexical Analyzer Generator (本地)，以及 Yacc: Yet Another Compiler-Compiler (本地)。

对于 Lex 和 Yacc 来说，比较经典的入门可以参考 Lex & Yacc Tutorial，其中包括了如何编写一个计算器，以及相关的调试等信息；也可以参考 本地文档，以及相关的 源码 。

关于总体介绍可以参考 Lex and YACC primer，或者 本地文档，也可以查看中文翻译 如何使用 Lex/YACC，以及 本地，以及 示例源码 ；以及 Bison-Flex 笔记、Flex/Bison Tutorial 。

关于调试方法可以参考 Understanding Your Parser，这个是 Bison Offical Documents 文档的一部分；更多可以参考 dinosaur.compilertools.net 查看相关的资料。