是否有一个正则表达式来生成某种编程语言的所有整数

Question

假设我正在构建一个编译器,我希望词法分析器识别C语言的整数,我可以指定例如整数应该在-2,147,483,648和2,147,483,647之间,长整数可以是64位吗？我觉得我的问题很愚蠢,但我想知道它是否可行......谢谢

Answer 1

简短的回答

是的,可以做到,但你不应该这样做!

剧透警报:你应该更好地使用strtol,我告诉你为什么在长的答案.

答案很长

它可以用一个古怪制作的正则表达式(最差的一个是与MIN和MAX之间的所有整数列表中选择一个正则表达式)来完成,但是你不希望做这样的事情.

这是因为这样的任务意味着对正则表达式进行大量处理,而该测试可以用您喜欢的语言进行很少的处理(将以下内容视为伪代码):

if (str_to_int(s) > CMIN && str_to_int(s) < CMAX)

好吧,实际上你可能会告诉我" 但如果它是一个int,它会溢出! ".但有技术可以检测到:

• 如何检测整数溢出？

他们都没有使用正则表达式!

但无论如何,你不需要遇到这么多麻烦,当C标准库中已经有一个功能为你完成这项工作时:strtol功能!引用手册:

strtol()函数返回转换结果,除非该值会下溢或溢出.如果发生下溢,strtol()将返回LONG_MIN.如果发生溢出,strtol()将返回LONG_MAX.在这两种情况下,errno都设置为ERANGE.对于strtoll()(LLONG_MIN和LLONG_MAX而不是LONG_MIN和LONG_MAX)也是如此.

它为什么会很大？这是因为正则表达式是一个查看字符流的自动机.当有匹配时,你沿着自动机移动.基本上,你需要:

• 匹配任何10个字符的字符串,或者仅当它以a开头时为11 -
• 只包含数字,
• 如果它以a开头2,则只能跟着0或者1,
• 如果它有一个开始2,随后1,只能跟着0,1,2,3或者4
• 如果它有一个开始2,随后1再一个4,只能跟着一个1,2,3,4...7
• ...
• 如果它以a开头2,后面跟着...并以a结束7,但是如果它以a开头-,然后是a 2,则需要以a结束6(所以基本上你必须将所有先前的条件复制到另一个以该结尾的子图中)
• 对于任何其他角色来说,这是一场比赛.

这看起来有点像下面这样:

^(
  (
   \d|\d\d|\d\d\d|\d\d\d\d|\d\d\d\d\d|\d\d\d\d\d\d|
   \d\d\d\d\d\d\d|\d\d\d\d\d\d\d\d|\d\d\d\d\d\d\d\d\d|
   [0-2][0-1][0-4][0-7][0-4][0-8][0-3][0-6][0-4][0-8]
  )|
  -(
    \d|\d\d|\d\d\d|\d\d\d\d|\d\d\d\d\d|\d\d\d\d\d\d|
    \d\d\d\d\d\d\d|\d\d\d\d\d\d\d\d|\d\d\d\d\d\d\d\d\d|
    [0-2][0-1][0-4][0-7][0-4][0-8][0-3][0-6][0-4][0-7]
   )
 )$

由以下自动机直观表示(点击要播放的图像):

我不确定会有多正确,因为我可能错过了边缘情况,但我希望我明确表示它与你喜欢的语言相比如何.如果你实际解析这么大的自动机,它会:

• 刻录CPU时间,
• 燃烧电力,
• 燃烧(燃料|煤| gaz |铀),
• 污染地球,
• 杀了一个小海豹

所有这些都不是做一些可以在使用正则表达式做同样事情的复杂性的1/100的操作中完成的事情.

因此,如果您因为编程错误而不想杀死一个小海豹,请不要使用正则表达式来处理它未设计的内容.

资源

为了更好地理解什么是自动机,regexps如何工作,什么时候使用它是个好主意,当它是一个小密封杀死它时,我只能建议你看看以下课程:

• http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-045j-automata-computability-and-complexity-spring-2011/lecture-notes/MIT6_045JS11_lec04.pdf
• http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-005-elements-of-software-construction-fall-2011/lecture-notes/MIT6_005F11_lec05.pdf
• http://www.saylor.org/site/wp-content/uploads/2012/01/CS304-2.1-MIT.pdf
• 关于这个主题的另一个答案:如何在python中找到所有可能的正则表达式匹配？
• 关于边缘情况的好答案strtol:如果LONG_MAX是2147483647,strtol(" - 2147483648",0,0)是否会溢出？

这是@ Andie2302答案的可视化:

-\b(?:
     214748364[0-8]|21474836[0-3][0-9]|2147483[0-5][0-9]{2}|
     214748[0-2][0-9]{3}|21474[0-7][0-9]{4}|2147[0-3][0-9]{5}|
     214[0-6][0-9]{6}|21[0-3][0-9]{7}|20[0-9]{8}|1[0-9]{9}|
     [1-9][0-9]{1,8}|[0-9]|-0
 )\b|
 \b(?:
     214748364[0-7]|21474836[0-3][0-9]|2147483[0-5][0-9]{2}|
     214748[0-2][0-9]{3}|21474[0-7][0-9]{4}|2147[0-3][0-9]{5}|
     214[0-6][0-9]{6}|21[0-3][0-9]{7}|20[0-9]{8}|1[0-9]{9}|
     [1-9][0-9]{1,8}|[0-9]|-0
 )\b

通过其匹配的自动机:

还是不相信？

HTH