提供了 Flex 和 Bison 两种工具用于编译器开发。如果您对它们有大致的了解，则可以跳过接下来的两节，因为我没有什么新的内容要说。
Flex 是一个快速的词法分析器生成器。如前所述，构建编译器的第一阶段是词法分析。Flex 是一个用于对文本执行模式匹配的有效工具。在没有 Flex 的情况下，我们将不得不编写自己的例程来从输入文本中获取标记。
但是有了 flex，我们可以提供要匹配的正则表达式以及找到完全匹配时要采取的动作。我们的文件将具有扩展名 .l，这表明它是一个有效的 lex 文件。flex 的输出是一个名为 lex.yy.c 的文件。它定义了一个例程 yylex()。文件 lex.yy.c 可以被编译并与 '-lfl' 库链接以生成可执行文件。
一个或两个示例将使事情更清楚。创建一个小文件，例如 lex.l，内容如下。
%%
"good" { printf("bad"); }
%%
使用以下命令生成可执行文件
lex lex.l cc lex.yy.c -lfl
运行可执行文件。我们发现，对于每次出现的字符串 "good"，都会替换为字符串 "bad"。对于任何其他输入，输入只是被回显。这里我们得到了第一个教训 - 默认操作只是将输入复制到输出。
flex 文件的通用结构是
definitions %% rules %% user code
定义可能包含“名称定义”。例如，
DIGIT [0-9]
它将 "DIGIT" 定义为一个正则表达式，该表达式匹配单个数字。名称定义的主要目的是简化扫描器规范。
接下来是 flex 文件的“规则”部分。通用形式是
pattern action
其中模式可以是正则表达式。动作应与模式在同一行。模式和动作将在下面描述。
在“规则”部分中，允许使用用 %{ } 括起来的变量声明。它应该出现在第一个规则之前。它们是扫描例程的局部变量。
让我们看一个例子。
%{
#define WHILE 1
#define IF 2
%}
%%
while {return WHILE; }
if {return IF; }
%%
main()
{
int val;
while (val = yylex())
printf("%d",val);
printf("final =%d\n", val);
}
在上面的程序中，对于 "while" 和 "if" 的出现，会打印相应的整数值。最后，对于 EOF，程序通过返回零来终止。
在这里，我只提到了在我们的编译器构建中通常需要的模式。有关完整列表，请参阅手册页。
`x' match the character x.
`.' any character except the newline.
`[xyz]' either an `x' or a `y' or a `z'.
`[a-z]' either an `a' or a `b' ... or a `z'.
`[^A-Z]' any character except an uppercase letter.
`r*' zero or more r's.
`r+' one or more r's.
`r?' zero or one r's.
`{name}' the expansion of the "name" description.
(As explained above).
`\x' if x is an `a', `b', `f', `n', `r', `t' or `v'
then the ANSI C representation of \x. Otherwise
a literal `x'.
`\0' the NULL character.
`(r)' match an r.
parentheses to override precedence.
`rs' concatenation of r and s.
`r|s' either an r or an s
上面提到的正则表达式按优先级降序排列。最顶层的优先级最高。如果遇到任何混淆，您可以使用括号来明确表达您的意思。
通常，我们脑海中出现的第一个问题将是 - 当找到多个匹配项时会发生什么。在这种情况下，扫描器选择长度最大的那个。也就是说，如果我们有一个文件，
%%
"ab" {printf("first"); }
"abc" {printf("second"); }
%%
并且我们提供输入 "abcd"，那么有两种可能性：“firstcd” 和 “secondd”。扫描器仅偏爱第二个。
但是考虑长度相同的情况。那么文件中首先给出的规则将优先于另一个规则。
一旦明确定义了匹配项，就可以执行提供的相应操作。与匹配项对应的文本在 'yytext' 中可用，其长度在 'yyleng' 中可用，两者都是全局值。最好避免以 'yy' 开头的局部名称，因为它被扫描器和解析器广泛使用。避免使用它也有助于提高可读性。
%%
[0-9]+ {printf("The value of first yytext is %s\n",yytext);}
[a-z]+ {printf("The value of sec yytext is %s\n",yytext);}
%%
我们发现，对于 lex 文件中给出的每个模式，它都有一个关联的动作。该动作可以是任何任意的 C 代码。可以使用像 'return' 这样的结构将值返回给 yylex 的调用者。在我们的编译器中，我们只需要简单的动作，任何具有一些 C 语言知识的人都可以理解这些动作。
上面提到的细节对于我们的编译器来说已经足够了。对于初学者，强烈建议尝试各种示例并检查正则表达式的不同变体。在继续下一节之前，您应该对 Flex 有一个基本的了解。
一旦我们习惯了词法分析器，我们就准备好迎接它最好的伙伴 - 解析器生成器 Bison。给定 LALR(1) 上下文无关文法的描述，Bison 的职责是生成一个 C 程序来解析该文法。如前所述，编译器构建的第二阶段是解析。我们从 lex 获取标记。我们必须为一种语言定义语法，并查看给定的输入是否有效。
在继续之前，让我们看看什么是上下文无关文法，以及我们所说的终结符和非终结符是什么意思。
上下文无关文法是有限的非终结符集合，每个非终结符代表一种语言。非终结符代表的语言是根据彼此以及借助称为终结符的原始符号递归定义的。
因此，简单来说，终结符是那些不能进一步细分的符号，而非终结符是由较小构造的分组形成的。可以细分非终结符。
例如，考虑以下文法
注意：在本例中，我没有使用 bison 语法。
A -> Ab A -> b
它表示所有只有一个或多个 b 的字符串。这里 A 是一个非终结符，因为它可以使用给定的产生式进一步划分。但是 b 是一个终结符，因为它不能进一步划分。
假设我们得到一个字符串 "bbb"。我们必须检查它是否被上述产生式接受。假设起始符号是 'A'。
A -> Ab {rule -1}
-> Abb {rule -1}
-> bbb {rule -2} and thus accepted.
在 Bison 中，通常终结符用大写字母表示，例如 := NUM（例如，表示数字）或使用字符文字，例如 '+'。正如我们所期望的那样，非终结符使用小写字母表示。例如 := exp。（当我们切换到 Bison 示例时，我们将遵守此规则）。
Flex 和 Bison 以完美的相互理解工作。Bison 语法规则可能会说“表达式由一个数字后跟一个加号，然后再跟一个数字组成”。flex 每当看到数字时，都会通知 bison 它找到了一个数字。也就是说，它将标记的存在通知解析器。
语法规则只关心给定的输入是否遵守规则。假设我们得到一个终结符 NUM。语法规则不再关心我们是否有一个值 1 作为 NUM，或者该值是否为 100。对于语法来说，所有数字都只是终结符 NUM。但我们可能肯定对 NUM 的值感兴趣。这就是“语义值”和“语义动作”的重要性所在。
与每个语法规则相关联，解析器允许我们定义某些动作。对于上面的例子，
A -> b { printf("We have found a `b'\n"); }
在大多数情况下，动作可能不像上面的那么简单。假设我们正在实现一个小型计算器，语义动作可能是执行加法运算。
语法中存在的终结符和非终结符可以具有关联的值。该值使用符号 '$n' 提取，其中 n 是一个整数。规则可以具有语义值。（实际上，它是该规则表示的非终结符的值）。它使用符号 '$$' 定义。
例如，
exp: exp '+' exp {$$ = $1 + $3;}
它代表 exp -> exp '+' exp。{ } 的内容表示语义动作。语义动作通常由 C 语句组成。在上面的例子中，考虑产生式的右侧。第一个 exp 用 '$1' 表示。终结符 '+' 用 '$2' 表示，最后一个 exp 用 '$3' 表示。我们在这里发现，像 '+' 这样的终结符可能没有关联的语义值。与语法关联的值是 '$$'，它是第一个和第三个标记的总和。
假设我们还有一个规则，
exp: NUM {$$ = $1;}
假设给定的输入是 '1 + 2'。那么标记 1 和 2 将匹配 NUM。由于相应的语义动作，规则 exp: exp '+' exp 的语义值将为 3。
bison 解析器文件的通用形式是
%{
C DECLARATIONS
%}
BISON DECLARATIONS
%%
GRAMMAR RULES
%%
ADDITIONAL C CODE
C 声明通常包含 #include 和其他声明。bison 声明处理终结符和非终结符。上面部分中解释的产生式构成语法规则。附加的 C 代码包含程序其余部分（如果需要）。
这些想法将通过一个例子变得更清晰。考虑一个能够获取表达式行并返回其值的小语法。
给出了词法文件 lex.l。没有给出文件的解释。如有任何疑问，请参阅 Flex 部分。
%{
#include"parse.tab.h"
#include<stdio.h>
%}
%%
[0-9]+ {yylval=atoi(yytext);return NUM;}
"+" {return '+';}
"*" {return '*';}
"-" {return '-';}
"\n" {return '\n';}
"/" {return '/';}
%%
还给出了解析器文件 parse.y。
%{
#include<stdio.h>
%}
%token NUM
%left '+' '-'
%left '*' '/'
%start line
%%
line:
/* empty */
|line exp '\n' {printf("%d\n",$2);}
| error '\n';
exp: exp '+' exp {$$ = $1 + $3;}
| exp '*' exp {$$ = $1 * $3;}
| exp '-' exp {$$ = $1 - $3;}
| exp '/' exp { if ($3 == 0)
$$ = 0;
else
$$ = $1/$3;}
| NUM {$$ = $1;};
%%
yyerror()
{
printf("Error detected in parsing\n");
}
main()
{
yyparse();
}
让我们逐行探索该程序。 также让我们看看该程序如何与词法文件一起工作。
C 声明部分很简单。这里我们只使用了 stdio.h。如果需要，也可以包含其他头文件。bison 文件的第二部分由 bison 声明组成。文件中使用的每个终结符都必须在此处声明。隐式终结符（例如字符文字）不需要提及。这里我们只处理一个名为 NUM 的终结符。其他的是字符文字，例如 '\n'、'+' 等。
%token NUM
完成声明。
在表达式中，我们将处理许多运算符，例如 '+'、'-'、'*' 和 '/'。不同的运算符具有不同的优先级。（例如，'/' 的优先级将高于 '+'。“+”和“-”具有相同的优先级）。此外，运算符将具有不同的结合性。我们代码中的所有运算符都是左结合的。此信息通过以下声明传递给解析器
%left -> for left associative. %right -> for right associative.
声明的顺序定义了优先级。行号越高，优先级越高。如果我们在 "%left '+'" 下声明 "%left '/'", 则 '/' 将具有更高的优先级。正如预期的那样，同一行上的声明表示相同的优先级。
"%start" 向解析器提供有关起始符号的信息。如果未定义，则将第一个产生式作为起始产生式。
现在让我们继续语法规则。第一个规则声明一行可以是空的。没有与此相关的语义动作。第二个规则
line: line exp '\n' {printf("%d\n",$2); }
是重要的一个。它表示一行可以是表达式后跟换行符。规则中使用的左递归只是一种用于解析多行文本的技术。如果您只对解析单行文本感兴趣，可以避免使用它。与上述规则关联的语义动作是打印表达式的值。
规则 - line : error '\n' 将在稍后解释。
表达式的规则很简单。它只是表明表达式可以是表达式后跟任何给定的运算符和表达式。规则 exp: NUM 提供了一种跳出递归规则的方法。语义动作只是执行各种操作。
bison 文件的最后一部分定义了其他 C 声明。我们只包含了两个函数。main 函数只是调用解析器；yyerror 例程打印错误消息。每当解析器遇到解析错误时，都会调用函数 yyerror。规则
line: error '\n'
包含在内是为了检测错误并将错误视为另一个规则。如果我们不包含产生式，解析器将在遇到错误时立即终止。非终结符 'error' 在解析器中隐式声明，我们可以使用它们而无需任何声明。
现在让我们看一下解析器和扫描器的工作原理。假设我们提供输入 "1+2"。扫描器每当找到数字时都会返回标记 NUM。并且该值也存储在扫描器的全局变量 'yylval' 中。解析器检查输入是否有效（根据提供的规则），如果有效，则使用提供的语义值执行相应的动作。
但问题是终结符 NUM 仅在解析器文件中声明。它必须在词法文件中使用。通过使用命令可以避免此问题
bison -d parse.y
它导致创建文件 parse.tab.h，其中包含所有必需的声明。我们可以将其包含在词法分析器中。
测试并理解扫描器和解析器的工作原理。创建上面给出的文件，并使用以下命令生成可执行文件
lex lex.l bison -d parse.y cc parse.tab.c lex.yy.c -lfl
上面提到的示例是一个简单的示例，只能识别简单的表达式行。但是我们即将处理的是一个小编程语言的编译器创建。虽然基本思想相同，但我们必须获得更多关于解析器的理解才能使用编程语言。考虑到这一点，让我们看另一个例子。
我们创建一种新语言，其中包含以下构造 - 变量声明、赋值和打印语句。词法文件或多或少与旧文件相同。但是解析器文件是不同的。给出了两个文件 - lex.l 和 parse.y。
lex.l
%{
#include"parse.tab.h"
#include<stdio.h>
#include<string.h>
%}
%%
[0-9]+ {yylval.val=atoi(yytext);return NUM;}
"print" {return PRINT;}
"declare" {return DECL;}
[a-z]([0-9]|[a-z])* {yylval.str= strdup(yytext);return NAME;}
"+" {return '+';}
"*" {return '*';}
"-" {return '-';}
"\n" {return '\n';}
"/" {return '/';}
"=" {return '=';}
%%
parse.y
%{
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
struct node{
char *name;
int value;
};
static struct node* sym_table[100];
%}
%union{
char *str;
int val;
}
%token <val> NUM
%token <str> NAME
%token PRINT
%token DECL
%left '+' '-'
%left '*' '/'
%type <val> exp
%start input
%%
input: /* empty */
| input line ;
line:
exp '\n' {}
| DECL NAME '\n' {return_value($2);}
| NAME '=' exp '\n' {assign_value($1,$3);}
| PRINT NAME '\n' {printf("%d\n",return_value($2));}
| error ;
exp: exp '+' exp {$$ = $1 + $3;}
| exp '*' exp {$$ = $1 * $3;}
| exp '-' exp {$$ = $1 - $3;}
| exp '/' exp { if ($3 == 0)
$$ = 0;
else
$$ = $1/$3;}
| NUM {$$ = $1;}
| NAME {$$ = return_value($1);};
%%
yyerror()
{
printf("Error detected in parsing\n");
}
int assign_value(char *s,int symvalue)
{
char *symname;
int len,i;
len=strlen(s) + 1;
symname=malloc(sizeof(char *) * len);
strcpy(symname,s);
for(i=0;sym_table[i];i++)
if(!strcmp(symname,sym_table[i]->name)){
sym_table[i]->value=symvalue;
return symvalue;
}
sym_table[i]=malloc(sizeof(struct node));
sym_table[i]->name=symname;
sym_table[i]->value=symvalue;
return symvalue;
}
int return_value(char *s)
{
char *symname;
int len,i;
len=strlen(s) + 1;
symname=malloc(sizeof(char *) * len);
strcpy(symname,s);
for(i=0;sym_table[i];i++)
if(!strcmp(symname,sym_table[i]->name))
return sym_table[i]->value;
sym_table[i]=malloc(sizeof(struct node));
sym_table[i]->name=symname;
sym_table[i]->value=0;
return 0;
}
main()
{
yyparse();
}
在解析器文件中，我们找到了一个新的声明 %union。它用于定义所有可能的类型列表。在第一个示例中，我们只需要处理整数。但是这里的值可以有多种类型。此信息通过 %union 声明传递。由于存在多种类型，因此必须为语法规则中使用其语义值的所有终结符和非终结符指定类型信息。它显示在尖括号中。在示例中，我们使用了 NAME 和 NUM 的语义值，但没有使用 PRINT 和 DECL 的语义值。词法文件中也对 'yylval' 进行了类似的更改。
%type <val> exp
用于定义非终结符并指定类型。
文件的其余部分很容易理解。每当我们看到一个新的标识符时，我们都会将其插入符号表。对于新的标识符，初始值设置为零。赋值语句导致指定的值存储在符号表中。函数 assign_value 和 return_value 用于符号表操作。