regex - Flex 中的非贪婪正则表达式匹配

Question

我刚刚开始使用 Flex，似乎不知道如何匹配以下表达式:

"Dog".*"Cat"
------------------
Input :
Dog Ca Cat Cc Cat
------------------
Output:
Dog Ca Cat Cc Cat

但我想要一个非贪婪匹配，输出如下:

Output:
Dog Ca Cat

如何在 Flex 上实现这一点？

编辑

尝试了以下方法:

%%
Dog.*Cat/.*Cat  printf("Matched : ||%s||", yytext);
dog.*cat        printf("Matched : ||%s||", yytext);
dOg[^c]*cAt     printf("Matched : ||%s||", yytext);
DOG.*?CAT       printf("Matched : ||%s||", yytext);
%%

输入:

Dog Ca Cat Cc Cat
dog Ca cat Cc cat
dOg Ca cAt Cc cAt
DOG CA CAT CC CAT

输出:

Matched : ||Dog Ca Cat Cc Cat||
Matched : ||dog Ca cat Cc cat||
Matched : ||dOg Ca cAt|| Cc cAt
Matched : ||DOG CA CAT CC CAT||

还收到警告:

lex4.l:2: warning, dangerous trailing context

Flex 版本:

flex 2.5.35 Apple(flex-31)

Answer 1

这是使用 lex/flex 工具的一个常见问题，困扰着初学者(有时甚至是非初学者)。该问题有两种解决方案，需要工具的两种不同的高级功能。像 dog ... cat 这样的短语与各种编程语言中的匹配注释的问题非常相似，例如 C 注释形式 /* ... */ 甚至'comment' ... 'tnemmoc'。它们具有与您的示例完全相同的特征。考虑以下C代码:

/* This is a comment */ "This is a String */"

贪婪的词法匹配会匹配错误的注释终止符(顺便说一句，这是对学生词法分析器的一个很好的测试!)。

一些大学编译器类(class)提供了建议的解决方案。解释得很好的是 here (at Manchester) 。其中引用了几本也涵盖了这些问题的好书:

• J.Levine、T.Mason 和 D.Brown:Lex 和 Yacc(第二版)
• M.E.Lesk 和 E.Schmidt:Lex - 词法分析器生成器

所描述的两种技术是使用Start Conditions明确指定状态机，或 manual input直接读取字符。

对于您的猫...狗问题，可以通过以下方式对其进行编程:

启动条件

在此解决方案中，我们需要多个状态。关键字dog导致其进入DOG状态，该状态一直持续到遇到字母c为止。然后进入LETTERC状态，后面必须跟一个字母a，如果不是，则继续DOG状态；字母 a 会导致进入 CAT 状态，该状态后面必须跟有字母 t，这会导致整个短语匹配并返回INITIAL 状态。 yymore 导致整个 dog ... cat 文本被保留以供使用。

%x DOG LETTERC CAT
d [dD]
o [oO]
g [gG]
c [cC]
a [aA]
t [tT]
ws [ \t\r\n]+
%%

<INITIAL>{d}{o}{g} {
        BEGIN(DOG);
        printf("DOG\n");
        yymore();
        }
<DOG>[^cC]*{c} {
        printf("C: %s\n",yytext);
        yymore();
        BEGIN(LETTERC);
        }
<LETTERC>{a} {
       printf("A: %s\n",yytext);
       yymore();
       BEGIN(CAT);
      }
<LETTERC>[^aA] {
        BEGIN(DOG);
        yymore();
        }
<CAT>{t} {
        printf("CAT: %s\n",yytext);
        BEGIN(INITIAL);
        }
<CAT>[^tT] {
        BEGIN(DOG);
        yymore();
        }
<INITIAL>{ws}  /* skip */ ;

手动输入

手动输入法仅匹配起始短语dog和输入的C代码，该代码会吞噬输入字符，直到出现所需的cat序列。遭遇。 (我没有理会大小写字母)。此解决方案的问题在于，很难在 yytext 中保留输入文本值以供以后在解析器中使用。它会丢弃它，如果构造是注释，那么这就没问题，但否则就没那么有用了。

d [dD]
o [oO]
g [gG]
ws [ \t\r\n]+
%%
{d}{o}{g}   {
   register int c;

                     for ( ; ; )
                         {
                         /* Not dealt with upper case .. left as an exercise */
                         while ( (c = input()) != 'c' &&
                                 c != EOF )
                             ;    /* eat up text of dog */

                         if ( c == 'c' )
                             {
                              if ( ( c = input()) == 'a' )
                                     if ( (c = input()) == 't' )
                                 break;    /* found the end */
                             }
                        if ( c == EOF )
                             {
                             REJECT;
                             break;
                             }
                         }
            /* because we have used input() yytext always contains "dog" */
            printf("cat: %s\n", yytext);
       }
{ws}  /* skip */ ;

(这两种解决方案都经过测试)