创建词法分析器的最有效方法是什么？

Question

我目前正在尝试学习如何手动创建自己的词法分析器.我一直在使用Flex(和Bison一起)练习并学习它如何在内部工作,但我目前至少看到了3种不同的解决方案来开发我自己的.

1. 使用RE列表,遍历每个RE,当一个匹配时,只需返回相关的令牌(参见关于RE的python文档)
2. 从RE创建DFA(例如Flex;基于RE,创建一个大型状态机)
3. 用很多switch case或if语句创建我自己的'状态机'(我认为Lua就是这样做的)

我相信我可以尝试每种解决方案,但是:

• 是否存在一种解决方案无法解决的问题？
• 在什么情况下你会使用一个解决方案而不是另一个？
• 正如标题所说:哪一个产生最有效的代码？

提前致谢!

Answer 1

当且仅当您设法编写状态机和灵活词汇描述而没有任何错误时,第二个和第三个替代方案将是等效的.YMMV,但我的经验是,编写(和阅读)flex词汇描述要容易得多.

第一种选择可能不等同,在一般情况下使其等效并不是微不足道的.

问题是如果多个模式与正则表达式匹配会发生什么.(这个问题在编写如上所述的大量switch语句时也会导致细微的错误.)普遍接受的词法策略是在这种情况下使用"最大munch"规则:选择导致最长匹配的模式,如果有更多比一个这样的模式,选择在词汇定义中首先出现的模式.

作为此规则重要的一个简单示例,请考虑使用具有关键字do和的关键字的语言double.观察到理想的行为是:

do {         => First token is keyword do
double d;    => First token is keyword double
doubt = 0.9; => First token is identifier doubt

在标准(f)lex文件中,这将实现为:

"do"       {  return T_FOR; }
"double"   {  return T_FOREACH; }
[[:alpha:]_][[:alnum:]_]*  { yyval.str = strdup(yytext); return T_ID; }

(F)将法产生完全相同的扫描仪,如果前两个规则碰巧在不同的顺序,虽然第三规则肯定必须结束.但是能够重新排序前两个规则更不容易出错.当然,有些人会写自己的词法规则与按字母顺序排列的关键字,如上述,但其他人可能会选择通过组织句法功能的关键字,以便do与混为一谈for,while,done等,并double用int,char等用在后一种组织中,程序员很难确保重叠的关键字以任何特定的顺序出现,因此flex不关心它是有用的; 在这种情况下(如在许多其他情况下)选择最长匹配肯定是正确的.

如果您创建的正则表达式的列表,只要选择第一场比赛,你需要确保正则表达式的相反顺序匹配长度,使其中最长的关键字匹配的排在最前面.(这是double之前的do,所以按字母顺序排列的关键字会失败.)

更糟糕的是,可能不会立即明显哪个正则表达式具有最长匹配.很显然,对于关键字 - 你可以反向排序长度文字图案 - 但在一般情况下,最大适合规则可能不会超过正则表达式偏序:这可能是这种情况,对于一些道理,一个常规表达式具有最长匹配,而另一个正则表达式为不同的标记提供更长的匹配.

作为替代方案,您可以尝试所有正则表达式并跟踪具有最长匹配的表达式.这将正确实现最大的munch(但见下文),但它的效率更低,因为每个模式必须与每个标记匹配.

您链接到的Python文档中使用的实际代码实际上通过|在各种正则表达式之间插入运算符,从提供的模式创建单个正则表达式.(这使得无法使用带编号的捕获,但这可能不是问题.)

如果Python正则表达式具有Posix最长匹配语义,这将等同于最大munch,但它不会:Python更改将更喜欢第一个匹配,除非需要以后的匹配来继续正则表达式:

>>> pat = re.compile("(wee|week)(night|knight)")
>>> pat.match("weeknight").group(1)
'wee'
>>> pat.match("weekknight").group(1)
'week'

为了做到这一点,你必须小心谨慎,以确保你的正则表达式正确排序,并且不会干扰彼此的匹配.(并非所有正则表达式库的工作方式与Python相同,但很多都可以.您需要查看文档,并可能进行一些实验.)

简而言之,对于一种单独的语言,如果你准备将一些工作放入其中,你将能够手工构建"正确"工作的词法分析器(假设语言坚持最大的咀嚼,就像大多数标准化语言一样),但这绝对是一件苦差事.而且不只是为了您:对于想要理解或验证您的代码的任何人来说,这将是额外的工作.

因此,在编写代码(包括调试)的效率方面,我会说像(f)lex这样的词汇生成器是一个明显的赢家.

有一个长期以来的模因,手工制作(或开放编码)的词法生成器更快.如果你想试验一下,可以尝试使用re2c,它可以生成高度优化的开放式编码词法扫描仪.(通过开放编码,我的意思是他们不使用转换表.)对于给定的一组词法规则,该理论可能会或可能不会,因为基于表格的词法分析器(由(f)lex生成)是通常,代码大小要小得多,因此可以更有效地使用处理器缓存.如果选择flex的快速(但更大)表选项,则扫描程序的内循环非常短并且只包含一个条件分支.(但是对该单个分支的分支预测不会非常有效).相比之下,开放式编码扫描器在循环中具有大量代码,其中包含大量条件分支,其中大部分都相当容易预测.(并不是执行路径更长;而是内部循环不够短,无法缓存.)

无论哪种方式,我认为可以合理地说,差异不会打破银行,我的建议总是与lexer一起使用,这对其他人来说更容易阅读,特别是如果你曾经计划寻求帮助的话SO :-)