flex介绍

flex是一个词法分析器的生成工具，它可以利用正则表达式来生成匹配相应字符串的C语言代码，其基本语法格式同lex相同。flex通过读取一个有规定格式的源文件，输出一个C语言源程序，即词法分析器。

flex源文件结构

flex源文件被%%分成三个部分：

1
2
3
4
5
定义
%%
规则
%%
用户代码

定义

定义部分包含了词法单元名和它的正则规范。一个已有的词法单元可通过{}被其它词法单元的正则规范使用。如果需要引入C语言头文件或者定义C语言全局变量与函数，需要用%{ %}括起来后定义在该部分。例如：

1
2
3
4
5
6
7
8
9
10
11
12
13
%{
#include <stdio.h>
#include <stdlib.h>

int idNum = 0;
int numNum = 0;
%}

WHITE [\t\r\n ]
DIGIT [0-9]
LETTER [a-zA-Z]
NUMBER {DIGIT}*|{DIGIT}*"."{DIGIT}{DIGIT}*
ID {LETTER}{LETTER}*{DIGIT}*

需要注意，该部分中定义的词法单元名与相应的正则规范并不是必须的，它类似于C语言中的宏定义#define，仅起到对某个词法单元取别名的作用，flex识别一个词法单元是依据其正则规范。

规则

规则部分用来定义词法分析器分析到一个词法单元时其需要执行的相关动作。该部分包含多个规则条目，每个条目的格式为：

1
pattern action

pattern是一个词法单元正则规范，也可以是定义部分中已定义的词法单元名。action是当flex扫描识别到该词法时需要执行的操作，是一个使用{}括起来的C语言程序片段。action中可使用flex内部定义的变量，如yytext与yyleng：

  • yytext：char*类型，指向当前识别到的词法单元的内容
  • yyleng：int类型，被赋值为当前识别到的词法单元内容的长度

每当词法分析器识别到一个新的词法单元，这两个变量均会更新。flex中默认的action为内置ECHO，即输出yytext.

1
2
3
4
clear {numNum = idNum = 0;printf("clear!");}
{NUMBER} {numNum++; printf("NUMBER %s\n", yytext);}
{ID} {idNum++; printf("ID %s %d\n", yytext, yyleng);}
{WHITE} ;

这里定义了三个规则条目：

  • 当识别到clear时，numNum和idNum被赋值为0，此时pattern为词法单元的正则规范。
  • 当识别到{NUMBER}时，numNum变量自增1，并输出内容，此时pattern为词法单元名，需要使用{}，下同
  • 当识别到{ID}时，idNum变量自增1，并输出内容与长度
  • 当识别到{WHITE}时，跳过

注意，flex生成的词法分析器采用最长匹配策略，而当扫描到的某个词法单元匹配多个pattern，且长度相同时，将会优先匹配最先定义的规则条目。因此，clear规则需要定义在{NUMBER}规则之前。

用户代码

该部分用户可添加实现自定义功能的代码，代码将会被复制到flex输出文件lex.yy.c中。通常需要编写main()，作为词法分析器的main()：

1
2
3
4
5
6
7
8
9
10
int main(int argc, char const *argv[])
{
    if(argc != 2 || !(yyin = fopen(argv[1],"r"))){
        printf("ERROR: Illegal Input File\n");
        exit(1);
    }
    yylex();
    printf("%d NUMBERs and %d IDs are recorded\n", numNum, idNum);
    return 0;
}

命令行参数指定输入文件，最后输出整数/浮点数、标识符的统计数。程序出现的flex定义的变量与函数：

  • yyin ：FILE*类型，指向flex的输入文件，默认为标准输入；与之对应的是yyout，指向flex输出文件，默认为标准输出
  • yylex()：flex的扫描程序，它将从yyin指向的文件首部开始扫描，识别每一个词法单元，直到EOF。规则部分中每个词法单元的action将会添加到该函数中，从而实现了执行词法单元对应的操作。action部分可添加return语句，作为yylex()的返回值。如果yylex()因为执行return语句而停止，词法分析器将重新调用yylex()继续扫描。如果要接收yylex()的每一次返回值，需要借助while语句

词法分析器会调用yywrap()来支持多个文件输入，当函数返回值为0时，表示继续读取yyin所指向的文件；返回值为1时，表示读取完一个文件后结束程序。该函数默认由用户定义。

1
2
3
int yywrap(){
    return 1;
}

如果没用定义该函数，gcc在编译时会报错undefined reference to 'yywrap'。也可以在定义部分添加%option noyywrap，词法分析器将不会调用yywrap()。

生成词法分析器

将上述实现计数器功能的flex程序命名为counter.l，在命令行输入

1
flex counter.l

生成lex.yy.c，这就是词法分析器的源文件。使用gcc等编译器编译，最后运行可执行文件，输入文件为input.txt

C Minus词法分析

C Minus惯用的词法

  1. 下面是语言的关键字：
    1
    else if int float return void while
  2. 下面都是专用符号
    1
    + - * / < <= > >= == != = ; , . ( ) [ ] { } /* */
  3. 其它标记是ID和NUM，通过下列正则表达式定义：
    1
    2
    3
    4
    ID = letter letter*
    NUM = digit digit*
    letter = a|..|z|A|..|Z
    digit = 0|..|9
  4. 空格由空白、换行符和制表符组成。空格通常被忽略，除了它必须分开ID和NUM关键字。
  5. 注释通常是C语言符号/*.....*/围起来。注释可以放在任何空包出现的位置上，且可以超过一行。注释不能嵌套。

词法分析

C Minus的词法分析要求实现识别C Minus的合法Token，并且其相关信息，包括：

  • 词法单元类型（int整数）
  • 第一次出现时所在行
  • 在一行中的开始位置
  • 在一行中的结束位置

Token定义

使用一个枚举类定义所有词法单元类型

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
typedef enum cminus_token_type {
    //运算
    ADD = 259,
    SUB = 260,
    MUL = 261,
    DIV = 262,
    LT = 263,
    LTE = 264,
    GT = 265,
    GTE = 266,
    EQ = 267,
    NEQ = 268,
    ASSIN = 269,
    //符号
    SEMICOLON = 270,
    COMMA = 271,
    LPARENTHESE = 272,
    RPARENTHESE = 273,
    LBRACKET = 274,
    RBRACKET = 275,
    LBRACE = 276,
    RBRACE = 277,
    //关键字
    ELSE = 278,
    IF = 279,
    INT = 280,
    FLOAT = 281,
    RETURN = 282,
    VOID = 283,
    WHILE = 284,
    //ID和NUM
    IDENTIFIER = 285,
    INTEGER = 286,
    FLOATPOINT = 287,
    ARRAY = 288,
    LETTER = 289,
    //others
    EOL = 290,
    COMMENT = 291,
    BLANK = 292,
    ERROR = 258
} Token;

声明和选项设置

在第一部分声明和选项设置中引用头文件，并定义全局变量：

  • lines：表示某个词法单元第一次出现时所在行
  • pos_start：表示词法单元在改行开始位置
  • pos_end：表示词法单元在该行结束位置
1
2
3
4
5
6
7
8
9
10
11
12
13
%option noyywrap
%{
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "lexical_analyzer.h"

int lines;
int pos_start;
int pos_end;

%}

词法单元规则

此部分用于定义C Minus的词法单元的规则，模式采用正则表达式表示，注意当词法单元的pattern中包含特殊字符时，需要使用转义字符\。动作使用C语言描述，确定每个Token在每行的开始位置和结束位置，并且返回该词法单元类型。该返回值为yylex()的返回值。例如：

1
2
\+ { pos_start = pos_end;pos_end++;return ADD;}


有几个特殊的词法单元需要注意：

  • End Of Line
    当词法分析器扫描到换行符时（Windows下为\r\n，Linux下为\n，Mac下为\r），行数lines自增，pos_start与pos_end更新

    1
    [\n] { pos_start = 1;pos_end = 1;lines++;return EOL;}

  • 注释
    由于flex生成的词法分析器采用最长匹配策略，且注释/**/包含正则的通配符，正则规范较为复杂。当识别到一个注释时，需要考虑词法单元开始位置和结束位置变化，且多行注释要修改lines.

    1
    2
    3
    4
    5
    6
    7
    8
    \/\*([*]*(([^*/])+([/])*)*)*\*\/ { 
        for (int i = 0; i < strlen(yytext); ++i){
            pos_end++;
            if( yytext[i] == '\n' ){
                lines += 1;pos_end = 1;
            }
        }
        return COMMENT;}

  • 错误的词法单元
    当扫描到错误的词法单元，仅返回ERROR

    1
    . {return ERROR;}

分类处理词法单元

在同一个输入文件或输入流中，每识别到一个词法单元，将会调用一次yylex()，即词法分析器循环调用yylex()，直到EOF。因此我们要对每一个不同的Token，即yylex()的返回值进行讨论。

对于空白符、注释、EOL，跳过即可；对于错误单元，输出其错误信息；对于其它词法单元，将其信息保存到存储结构中。存储词法单元时使用的数据结构是链表Token_Stream，接口如下：

1
2
3
4
5
6
// 初始化词法单元流
void Token_Stream_Init(Token_Stream* token_stream);
// 加入一个新的词法单元，成功返回0
int append_Token(Token_Stream* Token_Stream, char* text, int token, int lines, int pos_start, int pos_end);
// 遍历词法单元流
void traversal_Token_Stream(const Token_Stream* token_stream);

词法单元的分类处理过程：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
while(token = yylex()){
        switch(token){
            case COMMENT:
                break;
            case BLANK:
                break;
            case EOL:
                break;
            case ERROR:
                printf("[ERR]: unable to analysize %s at %d line, from %d to %d\n", yytext, lines, pos_start, pos_end);
            default :
                append_Token(token_stream, yytext, token, lines, pos_start, pos_end);
        }
    }

结果

完整代码见仓库。flex生成的词法分析器将会将词法单元的类型、所在行、开始位置与结束位置输出。C语言测试案例如下：

1
2
3
4
5
6
7
/*test.c*/
int main(){
    int a = 1, b = 2;
    if(a < b)
        a = b;
    return 0;
}

输出结果如下：

参考