为完成一个HTTP请求的解析器做准备

前言

在做CMU-15-441(计算机网络)的第一个作业的第二部分时，要用到lex和yacc完成对HTTP请求的解析器，由于没有学过编译原理，所以对lex和yacc一窍不通，所以先学习它们的使用

flex 和 bsion 简介

flex和bison是用来生成程序的工具，它们所生成的程序能够处理结构化输入。最初flex和bsion是用来生成编译器的，但在其他领域也非常有用。

词法分析和语法分析

词法分析：lexical analysis + 把输入分割成一个个有意义的词块，称为记号(token)

语法分析：syntax analysis + 确定这些记号是如何彼此关联

例如

alpha = beta +　gamma;

词法分析器把这段代码分解成：alpha、=、beta、+、gamma、；。

接着语法分析器确定beta+gamma是一个表达式，而这个表达式被献给alpha。

第一个flex程序：类wc

%{
int chars = 0;
int words = 0;
int lines = 0;
%}
%%
[a-zA-Z]+   { words++; chars += strlen(yytext); }
\n          { chars++; lines++; }
.           { chars++; }
%%
main(int argc, char **argv)
{
    yylex();
    printf("%8d%8d%8d\n", lines, words ,chars);
}

整个flex程序包含三个部分： 1. 声明和选项设置 + %{ 和 %}之间的代码 2. 模式和动作 + 每个模式处在第一行的开头，接着是模式匹配时所需要执行的C代码(用{}括住) + 注意，模式必须在行首出现，flex认为以空白开始的行都是代码而把它们照抄到生成的C代码中 + [a-zA-Z]+ 匹配一个单词 + \n 匹配换行符 + . 匹配任意一个字符 + 在任意一个flex动作中，变量yytext总是被设为指向本次匹配的输入文本 3. 会被拷贝到生成的词法分析器里面的C代码 + 最后的C代码是主程序，负责调用flex提供的词法分析例程yylex()，并输出结果

$ flex wc.l
$ gcc lex.yy.c -lfl
$ ./a.out < lex.yy.c
    1754    6601   44324

结合bison

calcultor.l

%{
#include "calculator.tab.h"
%}
%%
"+"     { return ADD; }
"-"     { return SUB; }
"*"     { return MUL; }
"/"     { return DIV; }
"|"     { return ABS; }
"("     { return OP; }
")"     { return CP; }
"//".*  { }
[0-9]+  { yylval = atoi(yytext); return NUMBER; }
\n      { return EOL; }
[ \t]   { }
.       { printf("Mystery character %s\n", yytext); }
%%

大多数词法分析器用来获得一个记号流，这样可以方便语法分析器处理。每当一个程序需要一个记号时，它调用yylex()来读取一小部分输入然后返回相应的记号。如果一个模式不能够产生一个用于调用程序且不可以返回的记号时，词法分析器会在这次yylex()的调用中继续分析接下来的输入字符。

calcultor.y

%{
#include <stdio.h>
%}

%token NUMBER
%token ADD SUB MUL DIV ABS
%token EOL
%token OP CP

%%
calclist:
    | calclist exp EOL { printf("= %d\n", $2); }
    ;

exp: factor
    | exp ADD factor { $$ = $1 + $3; }
    | exp SUB factor { $$ = $1 - $3; }
    ;

factor: term
    | factor MUL term { $$ = $1 * $3; }
    | factor DIV term { $$ = $1 / $3; }
    ;

term: NUMBER
    | ABS term { $$ = $2 >= 0 ? $2 : -$2; }
    | OP exp CP { $$ = $2; }
    ;
%%
main(int argc, char **argv)
{
    yyparse();
}
yyerror(char *s)
{
    fprintf(stderr, "error: %s\n", s);
}

bison程序包含了与flex程序相同的三部分结构： 1. 声明部分 + 会被原样拷贝到目标分析程序开头的C代码 + %token记号声明告诉bison在语法分析程序中记号的名称(一般用大写字母) 2. 规则部分 + 利用BNF定义的规则，”:“为”是”，”|“为”或者” 3. C代码部分

每个bison规则中的语法符号都有一个语义值，目标符号(冒号左边的语法符号)的值在动作中代码用$$代替，右边语法符号的语义值依次为$1、$2，直到这条规则结束。

当词法分析器返回记号时，记号值总是存储在yyval里，其他语法符号的语义值则在语法分析器的规则里进行设置

编译运行

Makeifle：

CC=gcc
LEX=flex
YACC=bison
OBJECT=calculator

$(OBJECT): lex.yy.c calculator.tab.c
	$(CC) lex.yy.c calculator.tab.c -o $(OBJECT) -lfl

lex.yy.c: calculator.l
	$(LEX) calculator.l

calculator.tab.c: calculator.y
	$(YACC) -d calculator.y

clean:
	rm -rf $(OBJECT) *tab* lex.yy.c

$ make
flex calculator.l
bison -d calculator.y
gcc lex.yy.c calculator.tab.c -o calculator -lfl
$ ./calculator 
10 + 20 - 1
= 29
a - 2
Mystery character a
error: syntax error

总结

现在我已经大概了解了flex和bison，感觉不难，由于和C语言结合的很紧，所以很容易上手，接下来就准备着手完成HTTP请求的解析器了