使用正则表达式与lex实现词法分析器

编译器中的词法分析阶段是将源语言的每个符号转化成一个对应的词法单元，例如：

int square(int x)
{
    return x * x;
}

词法分析器将上述代码分解成一个个的词法单元(token):

INT ID(square) LPAREN INT ID(x) RPAREN
LBRACE
RETURN ID(x) TIMES ID(x)
RBRACE

LPAREN, RPAREN代表左右圆括号, LBRACE, RBRACE代表左右花括号。
词法分析器的自动生成工具:
词法分析器的生成工具有很多, C通常用lex, java通常用antlr, lex只是一个词法分析的生成器，通常需要跟yacc结合来完成编译器的前端。本文主要使用lex。
lex使用正则表达式来完成词法分析器的功能。lex解析后生成一个lex.yy.c文件可以和其他文件一起编译成可执行文件。

lex的语法规则:

%{
/* 要插入的C声明的代码，例如要包含的头文件，
　要定义的宏等
*/
%}
/*可以插入一些正则表达式的简写形式和状态 */

/* 分隔符 */
%%

/*包含正则表达式和匹配成功执行的动作

%%
/* 插入原封不动的C代码,通常插入一些函数和main
　函数，这样对于某些小程序，就不用另起一个文件
　来书写main函数了
*/

用上述C代码为例，写一个lex程序.

/* file name: exam.l */
%option noyywrap
%{
#include "token.h"
char *String(char *str)
{
    char *s;
    s = malloc(strlen(str));
    strcpy(s, str);
    return s;
}

%}

%%

int {return INT;}
"(" {return LPAREN;}
")" {return RPAREN;}
"{" {return LBRACE;}
"}" {return RBRACE;}
[a-zA-Z_][0-9a-zA-Z_]* {yylval.id = String(yytext); return ID;}
[\n\t ]        {continue; /*忽略回车和空白*/}

/* token.h */

#ifndef _TOKEN_H
#define _TOKEN_H
enum {
    ID = 258, INT, LPAREN, RPAREN, LBRACE, RBRACE,
};
union {
    char *id
} yylval;
#endif

/* main.c */
#include <stdio.h>
#include <stdlib.h>
#include "token.h"

extern int yylex();

int main(void)
{
    int tok = 1;
    while (tok) {
        tok = yylex();
        switch (tok) {
        case ID:
            printf("ID(%s)", yylval.id);
            break;
        case INT:
            printf("INT");
            break;
        case LPAREN:
            printf("LPAREN");
            break;
        case RPAREN:
            printf("RPAREN");
            break;
        case LBRACE:
            printf("LBRACE");
            break;
        case RBRACE:
            printf("RBRACE");
            break;
        default:
            printf("unknown token");
            break;
        }
    }
}

将上述文件逐个编译:
$ lex exam.l 
$ gcc lex.yy.c main.c -o lexer
就完成了这个简单的词法分析器。

引用: 
Modern Compiler Implementation in C    Andrew W .Appel
Flex & Bison    John Levine