c - 是否有正则表达式为某种编程语言生成所有整数

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，它会溢出!”。但是有一些技术可以检测到:

• How to detect integer overflow?

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

但是无论如何，当 C 标准库中已经内置了一个函数可以为您完成这项工作时，您就不必费心了: strtol 功能!引用手册:

The strtol() function returns the result of the conversion, unless the value would underflow or overflow. If an underflow occurs, strtol() returns LONG_MIN. If an overflow occurs, strtol() returns LONG_MAX. In both cases, errno is set to ERANGE. Precisely the same holds for strtoll() (with LLONG_MIN and LLONG_MAX instead of LONG_MIN and LONG_MAX).

为什么会很大？这是因为正则表达式是一个查看字符流的自动机。当有一场比赛时，你沿着自动机移动。基本上，您需要:

• 匹配任何 10 个字符的字符串，或者只有以 - 开头的 11 个字符
• 只包含数字，
• 如果它以 2 开头，则只能后跟 0 或 1，
• 如果它以 2 开头，后跟 1，则只能后跟 0、1、2、3或4
• 如果它以 2 开头，后跟 1，然后是 4，则只能后跟 1, 2, 3, 4 ... 7
• …
• 如果它以 2 开头，后跟 … 并以 7 结尾，但如果它以 - 开头，然后a 2，它需要以 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 时间，
• 燃烧电力，
• 燃烧(燃料|煤|天然气|铀)，
• 污染地球，
• 杀死一只小海豹

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

因此，如果您不想因为糟糕的编程而杀死一只小海豹，请不要将正则表达式用于并非其设计目的的东西。

---

资源

为了更好地理解什么是自动机、正则表达式是如何工作的、什么时候使用它是个好主意以及什么时候它是小海豹杀死的，我只能建议你看以下类(class):

• 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
• 关于该主题的另一个答案:How to find all possible regex matches in python?
• 关于 strtol 的边缘情况的很好的回答:Does strtol("-2147483648", 0, 0) overflow if LONG_MAX is 2147483647?

---

这是@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