符号表、词表和解析器是如何在现代设计中协同工作的？

Question

为了学习目的，我正在创建自己的脚本语言。我一直在阅读“龙书”，对于符号表，以及构成标识符的字符串的实际驻留位置和所有权，我有些不清楚。我认为大部分的混乱是由于这本书使用了较旧的技术，而我则希望使用C++11。

据我所知：

1. SymbolTable将是某种类型的hash_map，使用_lexeme_s作为密钥。即string类型。我自己确定了它的值将是一个包含SYMBOL_TYPE的元组和一个指针/引用/查找第二个array，其中包含这个SYMBOL_TYPE所需的附加信息。也就是说，SymbolTable中的一个条目可以是<SYMBOL_TYPE::VARIABLE,3>，这意味着索引3处的Variables数组将使用这个变量type + value + attributes。然后，我将对其他标识符，如程序等进行同样的处理。
2. 每次请求下一个Lexer时，Token都会遍历字符，直到产生最长的词汇为止。问题1:这些预先存在的词汇居住在哪里？例如，如果符号表预先填充了关键字、标点符号、运算符等，那么是谁预先填充的呢？SymbolTable本身是否预先填充了关键字+标点符号+运算符的列表？那么，我是否可以尝试匹配符号表中的每个条目(从最长的第一项开始)？问题2:当Lexer生成一个令牌时，它是否向符号表中添加了新的标识符？它如何知道这应该是SYMBOL_TYPE::FUNCTION还是SYMBOL_TYPE:::VARIABLE？或者，它只是使用SYMBOL_TYPE::ID填充它，并允许Parser在确定标识符使用情况后更新条目？我认为不能把它留给Parser，因为当{出现时启动一个新范围时，Lexer需要向堆栈中添加一个新的SymbolTable，否则它返回给Parser的Token将指向错误的条目.但是，不能期望Lexer也将type和value信息添加到Variables或Procedures数组中。
3. Parser依次从Lexer请求每个Token。问题3:返回的Token类型到底需要什么？目前，只有SYMBOL_TYPE + SymbolTable中的索引。然后，SymbolTable链接到对应的该SYMBOL_TYPE的附加list。但是它应该是SYMBOL_TYPE以外的东西，比如TOKEN_TYPE，允许Parser添加到SymbolTable而不是Lexer吗？因为Lexer无法确定标识符是variable还是procedure。因为Lexer需要根据不同的作用域添加它们，那么Parser是否放弃了Lexer添加的内容并添加了自己的？

我不知道谁拥有SymbolTable的创建和管理，以及其中的标识符是否应该与Lexer和Parser之间传递的标识符相同。

在我看来，让Lexer只返回Tokens会更简单一些，它确定它是否是一个已知的关键字/操作符/标点符号(每个关键字都有自己的TOKEN_TYPE) +组成它的string (如果需要的话)，然后Parser会在需要时向SymbolTable和后续数组(比如Variables数组)添加条目。必要时，它还会看到一个{，并在堆栈中添加一个新的SymbolTable。

我是不是误解了SymbolTable的目标？

Answer 1

通常，符号表并不包括源代码的所有字符串。相反，符号表表示程序的静态环境，即可见变量及其类型。在解析和编译期间，符号表的当前状态指示哪些变量是可见的。

某些语言(如C++ )可以具有不同类型的符号--变量和类型名称。这些通常保存在不同的符号表中。然而，这是一个相当罕见的情况。大多数实现只跟踪符号表中的变量名。

例如，假设这个类似C的程序：

1: int i = 42;
2: {
3:   char c = 'a';
4:   print_int_char(i, c);
5: }

符号表以print_int_char函数开始：{ "print_int_char": void (*) (int, char) }。让我们假设这个符号表将名称映射到类型。在解析过程中，状态更改如下：

1. { "print_int_char": void (*) (int, char), "i": int } --添加了i符号。
2. { "print_int_char": void (*) (int, char), "i": int } -输入一个嵌套范围。
3. { "print_int_char": void (*) (int, char), "c": char, "i": int } --添加了c符号。
4. { "print_int_char": void (*) (int, char), "c": char, "i": int } -从符号表中检索符号print_int_char、c和i以便于类型检查。
5. { "print_int_char": void (*) (int, char), "i": int } -嵌套作用域左边，该作用域中定义的所有符号都被丢弃。

运算符、关键字和语法片段(如大括号)不是符号表的一部分，符号表用于实现语言语义，例如词法作用域或静态类型。当遇到符号表中找不到的变量时，我们可以立即发出编译器错误。

这些属性使得符号表在单通道语言(如C )中特别流行，但是当每个符号必须在解析时在符号表中找到时，我们就不能在没有预声明的情况下拥有函数。因此，许多现代语言将符号表的构造推迟到对整个编译单元进行解析，然后再进行第二次传递，断言所有符号都可以被解析并进行类型检查。

嵌套作用域可以通过两种策略来实现：

• 输入新范围时复制符号表。保留作用域后，将恢复旧的符号表。
• 符号表是链表或表堆栈。在符号解析期间，范围链向上移动，直到找到符号，或者到达列表的末尾。每个作用域链条目将只包含在该作用域中定义的符号。由于它更优雅，并且避免了不必要的副本，这种方法通常更常见。

在添加符号时，类型是如何知道的？

• 有些语言没有静态类型信息，例如Python。在这里，符号表将只跟踪符号的存在。
• 在其他语言(如C )中，精确的类型总是在声明时知道的:语句int x;声明一个类型为int的变量x。
• 在具有复杂类型推理规则的ML/OCaml/Haskell等语言中，变量的类型在声明时不会立即知道。但是，该类型保证在编译单元的末尾已知。在这里，符号表将变量名映射到全局唯一类型变量，一旦它们的具体类型已知，这些变量将被分配。可能会有另一个表映射类型变量到类型。阅读算法W，了解更多有关这方面的信息。

符号表被用作语义分析的一部分，而不是词汇分析的一部分。但是，有些语言或实现可能会将它们混合在一起。特别是，C的设计使得整个编译包括。解析、语义分析(例如类型检查)和代码生成可以在一次过程中发生。C++的语法要求在解析期间可以使用符号表来消除变量中的类型歧义。在其他语言中，解析器没有必要创建符号表。相反，表可以由后续编译器从生成的抽象语法树中传递来生成。

如果存在，则永远不需要触摸符号表。词法只用作解析器的简化，但从来不是语言实现的必要部分。C类语言中的词汇通常会返回标记，如<KW_FOR>或<IDENT:int>或<IDENT:i>，而不是<TYPENAME:int>或<VARIABLE:i>，然后解析器根据它们在语法中的位置对它们进行进一步分类。作为有必要这样做的例子，考虑：

typedef int III;
III III = 42;
printf("%d", III);

在这里，符号III同时引用类型和变量，但它们位于两个不同的名称空间(=两个不同的符号表)中。然而，每个对这个符号的引用都是明确的，因为它的句法上下文。