fre*_*low 37 c# c++ compiler-construction parsing lexer
每次我写一个简单的词法分析器和解析器时,我都会遇到同样的问题:词法分析器和解析器应该如何通信？我看到四种不同的方法:
词法分析器急切地将整个输入字符串转换为标记向量.完成此操作后,向量将被提供给解析器,解析器将其转换为树.这是迄今为止最简单的实现方案,但由于所有令牌都存储在内存中,因此浪费了大量空间.
每次词法分析器找到一个标记时,它会在解析器上调用一个函数,并传递当前标记.根据我的经验,这只有在解析器可以自然地实现为像LALR解析器这样的状态机时才有效.相比之下,我认为它对于递归下降解析器根本不起作用.
每次解析器需要一个令牌时,它会向词法分析器询问下一个令牌.由于yield关键字,这在C#中很容易实现,但在C++中却很难实现.
词法分析器和解析器通过异步队列进行通信.这在"生产者/消费者"这个标题下是众所周知的,它应该简化词法分析器和解析器之间的通信.它是否也优于多核上的其他解决方案？或者lexing太琐碎了？
我的分析听起来不错？还有其他我没有想过的方法吗？在现实世界的编译器中使用了什么？如果像Eric Lippert这样的编译器编写者可以对这个问题有所了解,那真的很酷.
Sam*_*ell 12
虽然我不会将上述大部分内容归类为错误,但我确实认为有些项目具有误导性.
在运行解析器之前对整个输入进行翻译与其他选项相比具有许多优势.实现方式各不相同,但一般而言,此操作所需的内存不是问题,尤其是当您考虑可用于报告编译错误的信息类型时.
语言实现说明:这是我的首选策略,因为它会产生可分离的代码,最适合转换为实现该语言的IDE.
解析器实现说明:我使用此策略试验了ANTLR v3关于内存开销的问题.C目标每个令牌使用超过130个字节,Java目标每个令牌使用大约44个字节.通过修改后的C#目标,我发现可以完全表示每个令牌只有8个字节的标记化输入,这使得该策略对于相当大的源文件也很实用.
语言设计说明:我鼓励设计新语言的人以允许这种解析策略的方式这样做,无论他们是否最终选择它作为参考编译器.
看起来你已经描述了一个"推"版本,我通常认为它描述的是像#3中的"拉"解析器.我的工作重点一直是LL解析,所以这对我来说不是一个真正的选择.如果超过#3有好处,我会感到惊讶,但不能排除它们.
最具误导性的部分是关于C++的陈述.在C++中正确使用迭代器使其非常适合这种类型的行为.
队列看起来像是中间人#3的重演.虽然抽象独立操作在模块化软件开发等领域具有许多优势,但可分发产品的词法分析器/解析器对对性能高度敏感,而这种类型的抽象消除了对数据结构和内存布局进行某些类型优化的能力. .我鼓励使用选项#3.
作为关于多核解析的附加说明:单个编译单元的编译的初始词法分析器/解析器阶段通常不能并行化,也不需要考虑在不同的编译单元上简单地运行并行编译任务是多么容易(例如,每个源文件上有一个词法分析器/解析器操作,跨源文件并行化,但只对任何给定文件使用单个线程).
关于其他选项:对于旨在广泛使用(商业或其他)的编译器,通常实现者选择解析策略和实现,其在目标语言的约束下提供最佳性能.有些语言(例如Go)可以使用简单的LR解析策略快速解析,并且使用"更强大"的解析策略(读取:不必要的功能)只会减慢速度.其他语言(例如C++)使用典型算法极难挑战或无法解析,因此使用速度较慢但功能更强大/更灵活的解析器.
我认为这里没有黄金法则.要求可能因案例而异.因此,合理的解决方案也可能不同.让我根据自己的经验评论你的选择.
"代币矢量".此解决方案可能占用大量内存.想象一下,使用大量头文件编译源文件.存储令牌本身是不够的.错误消息应包含文件名和行号的上下文.lexer可能会依赖于解析器.合理的例子:">>" - 这是一个移位运算符还是关闭了2层模板实例？我会投票给这个选项.
(2,3)."一部分称为另一部分".我的印象是,更复杂的系统应该称为不太复杂的系统.我认为lexer更简单.这意味着解析器应该调用词法分析器.我不明白为什么C#比C++好.我实现了C/C++ lexer作为子程序(实际上这是一个复杂的类),它是从基于语法的解析器调用的.这个实现没有问题.
"沟通过程".这在我看来有点矫枉过正.这种方法没有错,但也许保持简单更好？多核方面.编译单个文件是一种相对罕见的情况.我建议用自己的文件加载每个核心.
我没有看到将词法分析器和解析器组合在一起的其他合理选项.
我写了这些笔记,考虑编译软件项目的来源.解析一个简短的查询请求是完全不同的事情,原因可能会有很大的不同.我的答案是基于我自己的经验.其他人可能会有不同的看法.
| 归档时间： |
|
| 查看次数： |
3041 次 |
| 最近记录： |