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

前言

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

flex 和 bsion 简介

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

词法分析和语法分析

词法分析: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

总结

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