首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >C#龙书(词汇分析)如何处理文字

问C#龙书(词汇分析)如何处理文字
EN

Stack Overflow用户
提问于 2016-05-07 22:47:24
回答 1查看 302关注 0票数 5

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

我目前正在努力通过著名的龙书,并刚刚开始实现我自己的雷克萨斯。令人惊讶的是,除了文字之外,它工作得很好。我不明白如何使用符号(查找)表来处理文字,这本书似乎没有很好地涵盖:

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

代码语言:javascript
复制
int myIdentifier = 60;

龙书上写着:

从技术上讲,对于词汇60,我们应该构造一个类似于(数字,4)的标记,其中整数60的内部表示的符号表中有4个点.

理解-我创建了以下令牌:

代码语言:javascript
复制
<enum TokenType, int lookupIndex> 
//TokenType could be 'number' and lookupIndex could be any int

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

代码语言:javascript
复制
Dictionary<int literal, int index> 
//literal could be '60' and index could be anything

因为文字本身是字典中的关键,所以我可以快速检查将来的文字是否已经添加到符号表中(或者没有)。

然后,分析器接收来自Lexer的标记,并且应该能够识别符号表中的文字。

问题:

  1. 为什么我的令牌应该包含一个查找索引而不是包含文本本身? 那是不是更快..。
  2. 当查找索引是字典的值时,解析器应该如何快速找到符号表中的文字值? (我无法对字典键进行查找索引,因为这样,Lexer就必须对照字典的值进行检查,而字典的性能也不是很好) 多索引字典能解决问题吗?我想不是..。
  3. 那么,我必须为每种类型的文字创建一个符号表吗? F.e.:Dictionary<int literal, int index> 和Dictionary<double literal, int index> 和Dictionary<char literal, int index>等。
  4. 也许我完全是在错误的轨道上与文字。请随意发布任何更好的解决方案。
EN

回答 1

Stack Overflow用户

回答已采纳

发布于 2016-05-08 00:36:16

  1. 为什么我的令牌应该包含一个查找索引而不是包含文本本身?那不是更快吗? 当然,可能会更快。但是每一个文字都是不同的值。现在,大多数程序员都期望,如果他们在同一个程序中使用两次"this longish string",编译器将足够聪明,只在最终的可执行文件中发出该字符串的一个副本。如果您在解压缩代码时,为常量1找到了273个不同的存储位置,这也会让我们感到惊讶,因为每次编译器看到a += 1时,它都会创建一个新的常量。 确保常量文本只发出一次的最简单方法是将它们保存在一个由文本值索引的关联容器中。 正如@sepp2k在一篇评论中所指出的,大多数硬件允许使用小整数常量作为直接操作数,有时甚至不太小。所以上面关于常量1的声明有点偏离了。您很可能能够以不同的方式处理整数,但这可能不值得麻烦。
  2. 当查找索引是字典的值时,解析器如何能够快速找到符号表中的文字值? 这在很大程度上取决于用于文字表的精确数据结构(我不喜欢称之为符号表,但必须承认,这些概念是相关的)。在许多语言中,您会发现您的标准库容器并不是这个问题的完美匹配,所以您要么需要使它们适应这个目的,要么需要编写替换。 尽管如此,这并不是非常复杂。一种可能是使用map<literalType, int>和vector<literalType>的组合。在这里,映射将文字值和索引关联到向量中。当您找到一个新的文字值时,将其输入到与该向量当前大小相关联的映射中,然后将该值推送到该向量上(这将使其索引与您刚刚插入到映射中的索引相对应)。 对于字符串这样的大常数来说,这并不完全理想,因为在映射中的键和向量中的值之间,常量存储了两次。当您开始工作时,我建议您不要对这种重复感到烦恼;稍后,如果这是一个问题,您可以找到解决方案。 如果您使用的是C++,您可以使用一个(无序)集代替一个映射,并使用一个引用(指针)来引用新添加的元素而不是索引。但我不认为这个特性在许多语言中都是可用的,而且与索引相比,指针有时也有些尴尬。在某些语言中,您可以将所有的值都放入向量中,然后将键是索引的集合保存到向量中。这要求可以使用键类型以外的东西来查找集合;由于某种原因,这个特性在很少的数据结构库中可用。 而且,是的,如果你有这样的数据结构的话,可以使用双索引的数据结构。(实际上,map+vector解决方案是一个双索引的数据结构。)
  3. 必须为每种类型的文字创建一个符号表吗? 也许吧。你有多少种文字? 您可能会对变量和常量使用类型标记枚举(“区分联合”)。(同样,并非所有语言都在其标准库中歧视联合,这确实令人难过;如果您的实现语言缺乏这一基本功能,则需要实现它。)当然,受歧视的联合实例应该可以用作关联数据结构中的一个键,因此原则上没有什么可以阻止您将所有文本保留在一个数据结构中。如果你有合适的类型,那肯定是我推荐的,至少在开始的时候。 请注意,当您最终将文字作为对象代码发出时,您实际上更感兴趣的是它们的位表示和对齐方式,而不是它们的语义。如果两个完全不同类型的常量恰好具有相同的位表示,那么您可以对它们使用相同的存储位置。如果您有多个整数数据类型宽度,那么您可能希望将它们都保存在一个文本表中,这正是为了利用这种优化。不需要存储每个宽度的1 :)。有时,您会发现有两个不同类型的文本具有相同的表示形式,但这种情况可能不常见,无法处理。(但是,在IEEE硬件上,浮点数和整数零具有相同的表示形式,这通常与空指针的表示相同,因此您可能希望使用特殊情况下的零。) 总之,这是一个判断的决定。把受歧视的工会作为关键,有多复杂?通过拥有特定密钥类型的关联容器,您可以节省多少存储空间,这重要吗?您想要迭代相同类型的所有文字常量(答案:可能),这对数据结构来说有多容易呢? 如果您使用设计良好的内部API,您将能够改变对文字表的内部表示的看法。所以我会利用这个实验作为一个机会来尝试好的API设计。
  4. 还有别的吗? 祝你的项目好运。学习和享受!
票数 2
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/37094477

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档