正则表达式匹配不确定数量的前缀

Question

在lex中，应该匹配并捕获以下字符串

semic
semiconductor
semicondu

用c来做，代码可能是这样的：

strlen(str)>=5 && strncmp(str, "semiconductor", strlen(str))==0;

正则表达式或（lex 规则和操作）如何做到这一点？

Answer 1

前缀识别的正则表达式为：

semic(o(n(d(u(c(t(or?)?)?)?)?)?)?)?

这有点吓人，但以编程方式创建很容易。（见下文。）

值得注意的是，像上面这样的 (f)lex 规则只有在伴随着一个回退模式时才有用，该回退模式可以识别所有其他不匹配的 "words"（对于 "word" 的某些定义）。否则，该模式将简单地匹配输入流中下一个碰巧出现的任何单词的最长匹配前缀。

如果您有很多令牌需要以这种方式处理，那么创建上述模式的任务似乎有点令人生畏。但是，用一些脚本语言编写预处理器非常容易，可以在扫描仪定义文件上调用 (f)lex 之前应用。

例如，这是一个简单的 Python 程序，它过滤提供的文件（或标准输入），将分隔符 {: 和 :} 之间的单词替换为 "longest prefix" 上面显示的模式：

文件：prefixify

#!/usr/bin/env python3
import fileinput
import re
from sys import stdout
prefix_pat = re.compile(r'\{:(\w*)(\w):\}')
def prefixify(m):
    return ( ''.join('('+a for a in m[1])
           + m[2] + '?'
           + ')?' * len(m[1])
           )
for line in fileinput.input():
    stdout.write(prefix_pat.sub(prefixify, line))

注意：你必须chmod a+x prefixify。

我选择 {:...:} 因为它极不可能用于 (f)lex 模式或 C/C++ 代码，因此脚本不必尝试验证分隔符出现的上下文。当然，"extremely unlikely"和"impossible"是不一样的。另一种方法是让脚本自己计算出每个关键字的必要前缀应该有多长，也许使用每个关键字的最短唯一前缀和一些最小前缀长度的组合。

例如：

$ cat scanner.l.in
%option noinput nounput noyywrap nodefault
%{
#import "parse.tab.h"
%}

ws    (#.*|[[:space:]])+
%%
{ws}                         /* Ignore whitespace and comments */ ;
resi{:stor:}                 { return T_RESISTOR; }
semi                         { return T_SEMI; }
semic{:onductor:}            { return T_SEMICONDUCTOR; }
tran{:sformer:}              { return T_TRANSFORMER; }
trac{:k:}                    { return T_TRACK; }
[[:alpha:]_][[:alnum:]_]*}   { yylval.str = strdup(yytext); return ID; }
.                            { return *yytext; }

$ # The expected command line, probably in a makefile would be
$ # /path/to/prefixify scanner.l.in > scanner.l
$ # followed by flex -o scanner.c scanner.l
$ ./prefixify scanner.l.in
%option noinput nounput noyywrap nodefault
%{
#import "parse.tab.h"
%}

ws    (#.*|[[:space:]])+
%%
{ws}                         /* Ignore whitespace and comments */ ;
resi(s(t(or?)?)?)?                 { return T_RESISTOR; }
semi                         { return T_SEMI; }
semic(o(n(d(u(c(t(or?)?)?)?)?)?)?)?            { return T_SEMICONDUCTOR; }
tran(s(f(o(r(m(er?)?)?)?)?)?)?              { return T_TRANSFORMER; }
track?                    { return T_TRACK; }
[[:alpha:]_][[:alnum:]_]*}   { yylval.str = strdup(yytext); return ID; }
.                            { return *yytext; }

正则表达式匹配不确定数量的前缀

regular expression to match undetermined number of prefix

regex

lex

文件：prefixify