记 C 语言词法分析中的贪心法

很早以前就知道,编译器做的工作,首先就是读入源码,而后进行词法分析(有预处理的语言,还要先经过预处理器)。但是,一直没有对 C 语言的词法分析过程进行过深入了解。今天又拿起 Koenig 的《C 陷阱与缺陷》,才又读到相关的说明。

说明

所谓词法分析,就是编译器将源码中的字符串切分,变成一个个记号(token)的过程。所谓的记号,就相当于是英文中单词的地位;因此也有翻译将它译作单词。这个过程,其实很简单:无非就是顺序读入源码文件,而后挨个切分就好了。但是,看似简单的问题,往往就会有意料之外的事情发生。

举一个简单的例子。在 C 语言中,- 是一个记号,它表示「负号」或者「减号」;同时 > 也是一个记号,它表示「大于号」。麻烦之处在于,-> 也是一个记号,它是「成员运算符」;那么,当编译器遇到 -> 的时候,是将它作为一个记号 -> 呢?还是作为两个记号 -> 呢?回答这个问题,应当是不难的。答案显而易见,它应当被看做是一个完整的成员运算符,而不是一个减号紧接着一个大于号。

然而,这个答案背后的原理,值得思考:编译器遇到此类可能存在歧义的情况,适用怎样的规则,以保证行为的一致性呢?C 编译器采用了所谓的贪心法(或者,大嘴法)来处理这些情况:

  • 读入一个字符:
    • 如果它是一个单字符记号,并且不能与其它字符组成记号,那么将它作为记号加入队列,继续读入下一个字符;
    • 如果它是一个单字符记号,而且可能与其它字符组成记号,那么先读入下一个字符:
      • 如果它能与先前读入的字符组成记号,那么将它们一起作为记号加入队列,继续读入下一个字符;
      • 如果它不能与先前读入的字符组成记号,那么:
        • 如果至今为止尚未组成记号的字符,也不能作为其他记号的组成部分,则将先前读入的字符作为单字符记号加入队列,并依先例,继续处理当前字符;
        • 否则,继续读入下一个字符,尝试拼接更长的符号。

或者,简单来说就是如果输入流截至某个字符,之前的字符都已经被分解为一个个记号,那么下一个记号,应该是从这个字符起可能组成记号的最长字符串对应的记号

例子

  • a---b 表示 (a--) - b
  • y = x/*p 表示 y = x[注释开始]p,而不是 y = x / (*p)

启发

这个来自编译器词法分析器的陷阱应当引起注意,对于程序员来说,写代码应该养成良好的习惯:合理使用空格、括号,以避免可能的歧义造成难以排查的错误。

不好好些空格、括号的程序员,都应该拉出去打屁屁。


您的鼓励是我写作最大的动力

俗话说,投资效率是最好的投资。 如果您感觉我的文章质量不错,读后收获很大,预计能为您提高 10% 的工作效率,不妨小额捐助我一下,让我有动力继续写出更多好文章。


撰写评论

写了这么多年博客,收到的优秀评论少之又少。在这个属于 SNS 的时代也并不缺少向作者反馈的渠道。因此,如果你希望撰写评论,请发邮件至我的邮箱并注明文章标题,我会挑选对读者有价值的评论附加到文章末尾。