阅读过Flex/Lex等主题的类似问题：正则表达式匹配双精度字符和Is there a difference between [ABCDEFGH] and [A-H] on flex?我想不出一种方法来匹配在{2,8}长度的字符串中包含重复字母[A-Z]的字符串。
当我在Windows 11（WSL 2.0）中运行lex my_pgrogram.l时，我的代码将冻结编译，而在Mac OS中，它将在第19、21、23、24和26行中返回无法识别的规则：

/* <IMPORTS> */
    %{
    %}
    /* </IMPORTS> */
    
    /* <RULES AND TOKENS> */
    point (?i:point)
    line (?i:line)
    triangle (?i:triangle)
    square (?i:square)
    pentagon (?i:pentagon)
    hexagon (?i:pehagon)
    heptagon (?i:heptagon)
    octagon (?i:octagon)
    /* </RULES AND TOKENS> */
    
    /* <RULES> */
    %%
    ^[ \t]*({point}|{line}|{triangle}|{square}|{pentagon}|{hexagon}|{heptagon}|{octagon})[ \t]*$ printf("You forgot to enter the geometric entity's name e.g. triangle ABC. Please try again.\n\n");
    ^[ \t]*([A-Z]{1,8})[ \t]*$ printf("You forgot to enter a geomteric entity e.g. triangle. Please try again.\n\n");
    {point}|{line}|{triangle}|{square}|{pentagon}|{hexagon}|{heptagon}|{octagon} printf("--> %s: is a geometric entity.\n", yytext);  /* geometric entity is recognised! */
    
    ^[ \t]*({point}|{line}|{triangle}|{square}|{pentagon}|{hexagon}|{heptagon}|{octagon})[ \t]*[A-Z]*([a-z])+[A-Z]*([a-z])*[ \t]*$ printf("Only Capital letters allowed for geometric entity's name. Please try again with characters from A to Z.\n\n");
    {point}[ \t]*[A-Z]{2,}|{line}[ \t]*[A-Z]{1}|{line}[ \t]*[A-Z]{3,}|{triangle}[ \t]*[A-Z]{1,2}|{triangle}[ \t]*[A-Z]{4,}|{square}[ \t]*[A-Z]{1,3}|{square}[ \t]*[A-Z]{5,}|{pentagon}[ \t]*[A-Z]{1,4}\n|{pentagon}[ \t]*[A-Z]{6,}|{hexagon}[ \t]*[A-Z]{1,5}|{hexagon}[ \t]*[A-Z]{7,}|{heptagon}[ \t]*[A-Z]{1,6}|{heptagon}[ \t]*[A-Z]{8,}|{octagon}[ \t]*[A-Z]{1,7}|{octagon}[ \t]*[A-Z]{9,} printf("Invalid geometric entity's name. Please try again.\n\n");
    
    [A-Z]*A[A-Z]*A[A-Z]*|[A-Z]*B[A-Z]*B[A-Z]*|[A-Z]*C[A-Z]*C[A-Z]*|[A-Z]*D[A-Z]*D[A-Z]*|[A-Z]*E[A-Z]*E[A-Z]*|[A-Z]*F[A-Z]*F[A-Z]* printf("Oops! You entered some letter twice. Please try again: %s\n", yytext);
    
    [A-Z]{1,8} printf("--> %s: is a geometric entity's name.\n\n", yytext);   /* geometric entity's name is recognised! */
    
    [ \t\n]+
    .+
    %%
    /* </RULES> */
    
    int main(){
        yylex();
    }

/* Returns true if the token is OK (all unique chars) * Otherwise false. */ bool all_unique(const char* token) { char seen[256] = {0}; for (const char* p = token; *p; ++p) { /* Even if you don't expect eight-bit characters, you * don't want to blow up if you get one. */ unsigned index = (unsigned char)*p; if (seen[index]) return false; /* Found a dupe */ seen[index] = true; } return true; /* No duplicates. Could be other problems. */ }

1条答案

按热度按时间

mw3dktmi1#

正则表达式--至少是（f）lex实现的正则表达式，它不实现捕获--并不是您想要用来回答令牌是否包含重复字符的工具。
在一定程度上，你可以做到这一点，因为很容易编写一个正则表达式来检查一个特定的字符是否重复，而且你可以合并检查字母表中的每个字符。如果你没有太多不同的字符，这将工作正常。但它不能伸缩。因为所得到的状态机的大小与不同字母的数量成指数关系。（另外，由于Flex在扩展其内部表时不使用标准的指数重分配算法，所以一旦表变大，Flex所做的一切就是一遍又一遍地复制它们，以便稍微增加它们的长度。）
对26个字母做这样的测试是完全不现实的;我估计它需要大约160亿个状态，但基本上要花很长时间才能找到答案，我的耐心在A-O上耗尽了，花了20分钟;我估计A-P需要两个小时，等等，不管怎样，我可能没有足够的RAM来完成整个字母表，即使我愿意等待完成（或者修改代码以实现更明智的重新分配策略）。
我顺便指出，最终的状态机可以很容易地被最小化以适应RAM，但是（f）lex不做状态最小化，而且无论如何，等待子集构造完成违背了目的;你需要一个非常不同的算法来完成NFA-〉DFA转换。
所以你需要找到一个更可行的策略;最好的办法是，一旦flex识别出令牌，就扫描它，看看它是否包含重复项（您还可以确保它的长度正确）。
如果你关注效率，你可以做得比下面更好，但是初始化256个布尔值而不是26个布尔值的小效率在学生练习中并不明显，所以我建议类似下面的简单代码：

赞(0）回复(0）举报 2023-01-01

C语言 Flex/Lex：不包含重复字母[A-Z]的输入字符串

1条答案

相关问题

热门标签

最新问答