有没有可能设置规则优先级来避免“最长最早”匹配模式?(关于IT技术)

18

还有一个简单的问题:有没有办法告诉flex优先匹配短规则而不是长规则?我找不到任何好的相关文档。

这就是为什么我需要它的原因:我解析一种伪语言的文件,其中包含一些对应控制指令的关键字。我希望它们成为绝对优先级,以便它们不被解析为表达式的一部分。实际上,我需要这个优先级的原因是因为我不必为我的项目编写完整的语法(在我的情况下,这将是完全过度的,因为我对解析的程序执行结构分析,不需要知道细节...),因此我无法使用精细的语法调整来确保那些块不会被解析为表达式。

任何帮助将不胜感激。

这是一个示例文件:

If a > 0 Then read(b); Endif
c := "If I were...";
While d > 5 Do d := d + 1 Endwhile

我只想收集有关Ifs、Thens、Endifs等方面的信息... 其他内容对我没有影响。这就是为什么我希望优先考虑与Ifs、Thens等相关的规则,而无需编写语法。


请您能否展示一个示例文件?您的伪语言和其“控制指令”是什么样子的?您所说的“作为表达式的一部分”是什么意思?如果发现了“控制指令”,您会怎么做?那么文件的其余部分该怎么处理?这些文件是要解析文本文件还是二进制文件? - kol
1个回答

16

来自《龙书第二版》第3.5.3节“Lex中的冲突解决”:

We have alluded to the two rules that Lex uses to decide on the proper lexeme
to select, when several prefixes of the input match one or more patterns:
    1. Always prefer a longer prefix to a shorter prefix.
    2. If the longest possible prefix matches two or more patterns, prefer the
       pattern listed first in the Lex program.

这个规则同样适用于Flex。以下是 Flex手册(第7章:匹配输入)中的说明。

When the generated scanner is run, it analyzes its input looking for strings 
which match any of its patterns. If it finds more than one match, it takes the 
one matching the most text (for trailing context rules, this includes the length 
of the trailing part, even though it will then be returned to the input). If it 
finds two or more matches of the same length, the rule listed first in the flex 
input file is chosen.

如果我理解正确,您的词法分析器将像 Endif 这样的关键字视为标识符,因此在之后会被认为是表达式的一部分。如果这是您的问题,只需将关键字规则放在规范的顶部即可,例如以下内容:(假设大写单词是对应令牌的预定义枚举)

"If"                      { return IF;         }
"Then"                    { return THEN;       }
"Endif"                   { return ENDIF;      }
"While"                   { return WHILE;      }
"Do"                      { return DO;         }
"EndWhile"                { return ENDWHILE;   }
\"(\\.|[^\\"])*\"         { return STRING;     }
[a-zA-Z_][a-zA-Z0-9_]*    { return IDENTIFIER; }

由于规则2的限制,关键字会始终优先于标识符匹配。

编辑:

感谢您的评论,kol。我忘记添加字符串规则了。但我认为我的解决方案并没有错。 例如,如果有一个名为If_this_is_an_identifier的标识符,规则1将应用,因此标识符规则将发挥作用(因为它是最长的字符串)。 我编写了一个简单的测试用例,并没有发现问题。这是我的lex.l文件:

%{
  #include <iostream>
  using namespace std;
%}

ID       [a-zA-Z_][a-zA-Z0-9_]*

%option noyywrap
%%

"If"                      { cout << "IF: " << yytext << endl;         }
"Then"                    { cout << "THEN: " << yytext << endl;       }
"Endif"                   { cout << "ENDIF: " << yytext << endl;      }
"While"                   { cout << "WHILE: " << yytext << endl;      }
"Do"                      { cout << "DO: " << yytext << endl;         }
"EndWhile"                { cout << "ENDWHILE: " << yytext << endl;   }
\"(\\.|[^\\"])*\"         { cout << "STRING: " << yytext << endl;     }
{ID}                      { cout << "IDENTIFIER: " << yytext << endl; }
.                         { cout << "Ignore token: " << yytext << endl; }

%%

int main(int argc, char* argv[]) {
  ++argv, --argc;  /* skip over program name */
  if ( argc > 0 )
    yyin = fopen( argv[0], "r" );
  else
    yyin = stdin;

  yylex();
}

我使用以下测试用例测试了我的解决方案:

If If_this_is_an_identifier > 0 Then read(b); Endif
    c := "If I were...";
While While_this_is_also_an_identifier > 5 Do d := d + 1 Endwhile

它给了我以下输出(忽略与你提到的问题无关的其他输出。)

IF: If
IDENTIFIER: If_this_is_an_identifier
......
STRING: "If I were..."
......
WHILE: While
IDENTIFIER: While_this_is_also_an_identifier

lex.l程序是基于flex手册示例进行修改的(该示例使用相同的方法从标识符中匹配关键字)。

此外,还可以参考ANSI C语法,Lex规范

我也在我的个人项目中使用了这种方法,目前没有发现任何问题。


这个不起作用。例如,“If”模式不仅会在“If”关键字的情况下被找到,还会在包含子字符串“ If”的标识符和字符串中被找到。 - kol
+1 我删掉了我的回答,因为它过于复杂。你帮助我理解了即使只需要识别关键字,添加标识符规则也是有用的 - 谢谢。 - kol
1
感谢您花时间撰写这个答案,但是有两点需要指出:1)lex 不会优先选择最早匹配的模式,而是会优先选择最长匹配的模式,这就是规则2的含义。2)这一点在您的测试用例中已经体现了出来。我想要避免的正是这种情况:我希望在标识符和字符串中,If 能够被返回为 Ifs。 - m09
@Mog 那我需要提高我的英语水平。:-) 我稍后会努力想明白的。 - Lei Mou
@Mog,当我再次阅读您的帖子时有些困惑。您究竟想要实现什么?收集所有关键字出现的情况(以及可能还有其他内容),然后分析程序的结构?请您提供一个例子,说明在什么情况下您的程序会失败。 - Lei Mou
1
其实这更像是一个“想知道是否可能”的问题,因为我通过在表达式中添加要求(无空格)来解决了我的问题,这样我的伪语言就不难解析了。我承认我在kol问一个问题时给出的示例真的很糟糕,对此我感到抱歉。我会给你赏金并让这个问题消失,因为似乎不可能解决。谢谢你的时间! - m09

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接