如何阻止Flex词法分析器拆分非法Token？

问题场景 #

当前使用Flex实现C语言子集的词法分析，对应的.l文件如下：

/*definitions*/
%{
    #include <stdio.h>
    int yylex(void);
%}
/*rules*/
%%
"int"                   {printf("TYPE_INT %s\n",yytext);}
"float"                 {printf("TYPE_FLOAT %s\n",yytext);}
"char"                  {printf("TYPE_CHAR %s\n",yytext);}
"bool"                  {printf("TYPE_BOOL %s\n",yytext);}
"while"                 {printf("WHILE %s\n",yytext);}
"do"                    {printf("DO %s\n",yytext);}
"for"                   {printf("FOR %s\n",yytext);}
"printf"                {printf("PRINTF %s\n",yytext);}
"scanf"                 {printf("SCANF %s\n",yytext);}
"if"                    {printf("IF %s\n",yytext);}
"elif"                  {printf("ELIF %s\n",yytext);}
"else if"               {printf("ELSE_IF %s\n",yytext);}
"else"                  {printf("ELSE %s\n",yytext);}
"true"                  {printf("TRUE %s\n",yytext);}
"false"                 {printf("FALSE %s\n",yytext);}
"void"                  {printf("VOID %s\n",yytext);}
"main"                  {printf("MAIN %s\n",yytext);}
"return"                {printf("RETURN %s\n",yytext);}
[a-zA-Z_][a-zA-Z0-9]*   {printf("IDENTIFIER %s\n",yytext);}
[-+]?(([1-9][0-9]*)|0)  {printf("INTEGER %s\n",yytext);}
[-+]?[0-9]+\.[0-9]+      {printf("FLOAT %s\n",yytext);}
\"[^\\"\n]*\"            {printf("STRING %s\n",yytext);}
","                     {printf("COMMA %s\n",yytext);}
";"                     {printf("SEMICOLON %s\n",yytext);}
"{"                     {printf("LEFT_BRACE %s\n",yytext);}
"}"                     {printf("RIGHT_BRACE %s\n",yytext);}
"("                     {printf("LEFT_PAREN %s\n",yytext);}
")"                     {printf("RIGHT_PAREN %s\n",yytext);}
"["                     {printf("LEFT_BRACKET %s\n",yytext);}
"]"                     {printf("RIGHT_BRACKET %s\n",yytext);}
"-"                     {printf("MINUS %s\n",yytext);}
"+"                     {printf("PLUS %s\n",yytext);}
"*"                     {printf("MULTIPLY %s\n",yytext);}
"/"                     {printf("DIVIDE %s\n",yytext);}
"\\"                    {printf("BACKSLASH %s\n",yytext);}
"%"                     {printf("MODULUS %s\n",yytext);}
"=="                    {printf("EQUALS %s\n",yytext);}
"!="                    {printf("NOT_EQUALS %s\n",yytext);}
"<"                     {printf("LESS_THAN %s\n",yytext);}
">"                     {printf("GREATER_THAN %s\n",yytext);}
"<="                    {printf("LESS_THAN_OR_EQUAL %s\n",yytext);}
">="                    {printf("GREATER_THAN_OR_EQUAL %s\n",yytext);}
"="                     {printf("ASSIGN %s\n",yytext);}
"&&"                    {printf("LOGICAL_AND %s\n",yytext);}
"||"                    {printf("LOGICAL_OR %s\n",yytext);}
"!"                     {printf("LOGICAL_NOT %s\n",yytext);}
[" "|\t|\n|\f|\v]       {printf("WHITESPACE\n");}
.                       {printf("UNRECOGNIZED_CHARACTER %s\n",yytext);}
%%

/*for when we use multiple input files*/
int yywrap(void){
    return 1;
}

/*main driver function that takes */
int main(int argc, char *argv[]){
    if(argc<2){
        printf("Usage: %s <input_file_name>\n",argv[0]);
        return 1;
    }
    FILE *fp = fopen(argv[1], "r");
    if(fp == NULL){
        printf("Error opening input file.\n");
        return 1;
    }
    yyin = fp;
    yylex();
    fclose(fp);
    return 0;
}

遇到的问题：输入90.s3和232a3这类非法序列时，Flex不会按最后一条规则识别为UNRECOGNIZED_CHARACTER，而是拆分成多个合法token：

• 232a3被拆分为：

  INTEGER 232
  IDENTIFIER a3
  

• 90.s3被拆分为：

  INTEGER 90
  UNRECOGNIZED_CHARACTER .
  IDENTIFIER s3
  

解决方案 #

Flex的匹配逻辑是优先选择最长的匹配文本；若多个规则匹配相同长度的文本，则选择最先定义的规则。要阻止非法序列被拆分，需要在现有合法规则之前，添加匹配这类非法序列的规则，让Flex优先识别它们为未识别字符。

修改后的.l文件规则部分如下（关键修改已标注）：

/*rules*/
%%
// 新增：匹配数字后跟字母/下划线的非法序列
[-+]?[0-9]+[a-zA-Z_][a-zA-Z0-9]*   {printf("UNRECOGNIZED_CHARACTER %s\n", yytext);}
// 新增：匹配数字后跟点再跟字母/下划线的非法序列
[-+]?[0-9]+\.[a-zA-Z_][a-zA-Z0-9]* {printf("UNRECOGNIZED_CHARACTER %s\n", yytext);}

"int"                   {printf("TYPE_INT %s\n",yytext);}
"float"                 {printf("TYPE_FLOAT %s\n",yytext);}
"char"                  {printf("TYPE_CHAR %s\n",yytext);}
"bool"                  {printf("TYPE_BOOL %s\n",yytext);}
"while"                 {printf("WHILE %s\n",yytext);}
"do"                    {printf("DO %s\n",yytext);}
"for"                   {printf("FOR %s\n",yytext);}
"printf"                {printf("PRINTF %s\n",yytext);}
"scanf"                 {printf("SCANF %s\n",yytext);}
"if"                    {printf("IF %s\n",yytext);}
"elif"                  {printf("ELIF %s\n",yytext);}
"else if"               {printf("ELSE_IF %s\n",yytext);}
"else"                  {printf("ELSE %s\n",yytext);}
"true"                  {printf("TRUE %s\n",yytext);}
"false"                 {printf("FALSE %s\n",yytext);}
"void"                  {printf("VOID %s\n",yytext);}
"main"                  {printf("MAIN %s\n",yytext);}
"return"                {printf("RETURN %s\n",yytext);}
[a-zA-Z_][a-zA-Z0-9]*   {printf("IDENTIFIER %s\n",yytext);}
[-+]?(([1-9][0-9]*)|0)  {printf("INTEGER %s\n",yytext);}
[-+]?[0-9]+\.[0-9]+      {printf("FLOAT %s\n",yytext);}
\"[^\\"\n]*\"            {printf("STRING %s\n",yytext);}
","                     {printf("COMMA %s\n",yytext);}
";"                     {printf("SEMICOLON %s\n",yytext);}
"{"                     {printf("LEFT_BRACE %s\n",yytext);}
"}"                     {printf("RIGHT_BRACE %s\n",yytext);}
"("                     {printf("LEFT_PAREN %s\n",yytext);}
")"                     {printf("RIGHT_PAREN %s\n",yytext);}
"["                     {printf("LEFT_BRACKET %s\n",yytext);}
"]"                     {printf("RIGHT_BRACKET %s\n",yytext);}
"-"                     {printf("MINUS %s\n",yytext);}
"+"                     {printf("PLUS %s\n",yytext);}
"*"                     {printf("MULTIPLY %s\n",yytext);}
"/"                     {printf("DIVIDE %s\n",yytext);}
"\\"                    {printf("BACKSLASH %s\n",yytext);}
"%"                     {printf("MODULUS %s\n",yytext);}
"=="                    {printf("EQUALS %s\n",yytext);}
"!="                    {printf("NOT_EQUALS %s\n",yytext);}
"<"                     {printf("LESS_THAN %s\n",yytext);}
">"                     {printf("GREATER_THAN %s\n",yytext);}
"<="                    {printf("LESS_THAN_OR_EQUAL %s\n",yytext);}
">="                    {printf("GREATER_THAN_OR_EQUAL %s\n",yytext);}
"="                     {printf("ASSIGN %s\n",yytext);}
"&&"                    {printf("LOGICAL_AND %s\n",yytext);}
"||"                    {printf("LOGICAL_OR %s\n",yytext);}
"!"                     {printf("LOGICAL_NOT %s\n",yytext);}
[" "|\t|\n|\f|\v]       {printf("WHITESPACE\n");}
.                       {printf("UNRECOGNIZED_CHARACTER %s\n",yytext);}
%%

原理说明 #

新增的规则会优先匹配232a3、90.s3这类不符合C语言语法的非法序列，因为它们的匹配长度比拆分后的多个token更长（比如232a3长度为5，拆分后是3+2，最长匹配是5），同时这些规则定义在合法规则之前，所以Flex会优先选择这些规则，将整个非法序列识别为UNRECOGNIZED_CHARACTER，避免拆分。

内容的提问来源于stack exchange，提问作者Ian K