词法分析器、理解文档、预处理标记

Question

我的目标是为合理的子集 C 构建一个解析器，现在我正处于开始阶段，正在实现词法分析器。类似 question 的答案在同一主题上指向 International Standard用于 C(700 页文档)和 Yacc 语法 webpage .

我欢迎任何有助于理解文档的帮助:文档中的以下图片是否表示语法规则，其中符号 C -> (A, B) 表示所有出现的AB 按顺序被 C 取代？

identifier -> identifier-nondigit | (identifier,identifier-nondigit) | (identifier,digit)
identifier-nondigit -> nondigit | universal-character-name | other
digit -> 0 | 1 | 2 | ... | 9
non-digit -> _ | a | b | ... | z | A | ... | Z 

我觉得我很困惑，因为文档介绍了“预处理标记”，我认为它只是在没有回溯的情况下生成的源中字符序列的标签。

即像这样的东西:

"15647  \n  \t abdsfg8rg \t" -> "DWLDLW"
// D .. digits, W ... whitespace, L ... letters

看起来词法分析器正在做与解析器相同的事情(只是构建一棵树)。引入预处理 token 和 token 的原因是什么？

这是否意味着处理应该“分两次”完成？我期待词法分析器只使用一些正则表达式和一些规则。但似乎词法分析的结果是一系列树，这些树的根可以是 keyword, identifier, constant, string-literal, punctuator。

感谢您的任何澄清。

Answer 1

I think I am confused because the documentation introduces 'preprocessing tokens' which I thought would be just labels of sequences of characters in the source produced without backtracking.

预处理标记是 C 预处理器的输入。在将 C 源代码转换为可执行文件的过程中，预处理标记流和插入的空格首先受到预处理器的操作，然后预处理标记和空格的结果流在转换为(标准的词；也许“重新解释为”更好地传达了这个想法)一串标记。 section 5.1.1.2 of the language standard 中提供了所有这一切的概述。 .

从预处理 token 到 token 的转换是一个非常简单的映射:

• identifier --> identifier 或 enumeration-constant(选择是上下文相关的，但在实践中可以通过避免在语义分析之前进行区分)。
• pp-number --> integer-constant 或 floating-constant，视情况而定(constant 的两个替代项)
• character-constant --> character-constant(constant 的替代方案之一)
• 字符串文字 --> 字符串文字
• 标点符号 --> 标点符号
• 删除预处理指令后剩下的任何其他内容 --> 一个或多个单字符标记

请注意，header-name 预处理标记是一种特殊情况:每种形式的 header-name 与预处理标记的其他可能标记化之间存在歧义。最好避免将任何内容作为 header-name 进行分析，除非是在 #include 指令的上下文中，这样您也不必担心转换 header - 将预处理标记命名为常规标记，因为它们都不会在删除预处理指令后继续存在。

词法分析的更多细节在 section 6.4 of the Standard 中给出。及其小节。

It seems like the lexer is doing the same thing as the parser (just building a tree).

我不明白你是如何得出这个结论的，但词法分析和语法分析之间的区别是人为的，这确实是真的。没有必要以这种方式划分语言分析过程，但事实证明它通常很方便，无论是对于编码还是计算。

What is the reason for introducing the preprocessing tokens and tokens?

标准 C 基本上是两种语言合二为一:一种预处理语言和 C 语言本身。早期，它们由完全不同的程序处理，预处理是可选的。预处理器对它所操作的单元有一个看法，这与 C 语法的分类并不完全一致。 Preprocessing-tokens是预处理程序的语法分析和数据的单位，而tokens是C的语法分析的单位。

Does it mean that the processing should be done 'in two waves'?

从逻辑上讲，是的。在实践中，我认为大多数编译器通过源代码将两个逻辑 channel 集成为一个物理 channel 。