C#龙书(词法分析)如何处理文字

Question

这个项目是用于教育用途的,我非常清楚已经存在优秀的编译器.

我目前正在通过着名的龙书战斗,并开始实施我自己的Lexer.除文字外,它的效果令人惊讶.我不明白如何使用符号(查找)表处理文字,这本书似乎没有很好地涵盖:

在下面的代码中60是一个数字文字:

int myIdentifier = 60;

龙书说:

从技术上讲,对于lexeme 60,我们应该组成一个像(数字,4)的标记,其中4指向符号表,用于整数60的内部表示[...]

明白了 - 我创建了以下令牌:

<enum TokenType, int lookupIndex> 
//TokenType could be 'number' and lookupIndex could be any int

并将文字存储在这样的字典中:

Dictionary<int literal, int index> 
//literal could be '60' and index could be anything

由于文字本身是字典中的关键字,因此我可以快速检查未来的文字是否已经添加到符号表中(或不是).

然后,Parser从Lexer接收令牌,并且应该能够识别符号表中的文字.

问题:

1. 为什么我的令牌包含查找索引而不是包含文字本身？
   不会那么快......
2. 当lookup-index是字典的值时,Parser如何能够快速找到符号表中的文字值？
   (我不能使lookup-index成为字典键,因为Lexer必须检查字典的值,而且字典的性能也不是很高)
   多索引字典是否可以成为解决方案？我猜不会...
3. 我必须为每种类型的文字创建一个符号表吗？
   铁:Dictionary<int literal, int index>
   和Dictionary<double literal, int index>
   和Dictionary<char literal, int index>等.
4. 也许我完全走错了文字.随意发布任何更好的解决方案.

Answer 1

1. 为什么我的令牌应该包含查找索引而不是包含文字本身？这样不是更快吗？

   当然，可能会更快。但这样每个文字都会有不同的值。现在，大多数程序员都期望，例如，如果他们"this longish string"在同一个程序中使用两次，编译器将足够聪明，只在最终的可执行文件中发出该字符串的单个副本。容我们说，如果当您反编译代码时，您发现常量 273 个不同的存储位置，那也会令人惊讶1，因为编译器每次看到 时a += 1，都会创建一个新常量。

   确保常量文字仅发出一次的最简单方法是将它们保存在由文字值索引的关联容器中。

   正如 @sepp2k 在评论中指出的那样，大多数硬件允许使用小整数常量作为直接操作数，有时甚至允许使用不那么小的常量。所以上面关于常数1的说法有点夸张。您很可能能够以不同的方式处理整数，但可能不值得这么麻烦。

2. 当查找索引是字典的值时，解析器如何能够快速找到符号表中的文字值？

   这在很大程度上取决于您用于文字表的精确数据结构（我不喜欢称之为符号表，但不可否认这些概念是相关的。）在许多语言中，您会发现您的标准库容器并不是完美的匹配对于这个问题，所以你要么需要调整它们以适应目的，要么编写替代品。

   不过，它并不是非常复杂。一种可能性是使用 amap<literalType, int>和 a的组合vector<literalType>的组合。这里，映射将文字值与向量的索引相关联。当您找到新的文字值时，将其输入与向量当前大小关联的映射中，然后将该值推送到向量上（这将使其索引与您刚刚插入映射中的索引相对应。）

   对于像字符串这样的大型常量来说，这并不完全理想，因为在映射中的键和向量中的值之间，常量被存储两次。当你开始时，我建议你抑制住对这种重复的烦恼；以后，如果证明是个问题，你就能找到解决方案。

   如果您使用的是 C++，则可以使用（无序）集而不是映射，并使用对新添加元素的引用（指针）而不是索引。但我认为许多语言都没有这个功能，而且与索引相比，指针有时也很尴尬。在某些语言中，您可以将所有值放入向量中，然后保留一个集合，其键是向量中的索引。这要求可以使用键类型以外的其他方式来查找集合；由于某种原因，很少有数据结构库提供此功能。

   而且，是的，可以使用双索引数据结构，如果您有方便的话。（实际上，地图+向量解决方案是双索引数据结构。）

3. 那么我必须为每种类型的文字创建一个符号表吗？

   或许。你有多少种文字？

   您可能最终会使用类型标记的枚举（“可区分联合”），无论是变量还是常量。（同样，并非所有语言在其标准库中都具有可区分的联合，这确实令人悲伤；如果您的实现语言缺乏此基本功能，则需要实现它。）当然应该可以使用可区分的联合实例作为关联数据结构中的键，因此原则上没有什么可以阻止您将所有文字保存在单个数据结构中。如果您有合适的类型，这绝对是我推荐的，至少在开始时是这样。

   请注意，当您最终将文字作为目标代码发出时，您实际上对它们的位表示和对齐比对它们的语义更感兴趣。如果两个完全不同类型的常量碰巧具有相同的位表示形式，那么您可以为它们使用相同的存储位置。如果您有多种宽度的整数数据类型，那么您可能希望将它们全部保留在单个文字表中，以充分利用此优化。无需存储1每个宽度的 a :)。有时您会发现其他情况，其中两个不同类型的文字具有相同的表示形式，但这种情况可能不够常见，无需您特意处理它。（但是，在 IEEE 硬件上，浮点和整数零具有相同的表示形式，并且通常与 NULL 指针具有相同的表示形式，因此您可能需要特殊情况的零。）

   总而言之，这是一个判断。使用受歧视联合作为密钥有多复杂？通过使用具有特定键类型的关联容器可以节省多少存储空间，这重要吗？您是否想要迭代同一类型的所有文字常量（答案：可能）？这对您的数据结构来说有多容易？

   如果您使用设计良好的内部 API，您将能够改变对文字表的内部表示的看法。所以我会利用这个实验作为尝试良好 API 设计的机会。

4. 还要别的吗？

   祝你的项目好运。学习并享受！