纯函数编译器如何用类型信息注释AST？ [英] How do purely functional compilers annotate the AST with type info?

问题描述

在语法分析阶段，命令式编译器可以从已经包含类型字段的节点构建AST，该字段设置为 null ，然后在语义分析阶段，通过将声明/推断类型分配到类型字段中来填充类型。 p>

纯函数式语言如何处理这个问题，你没有奢侈的任务？是否将非类型AST映射到不同的类型富集AST？ 这是否意味着我需要为每个AST节点定义两个类型，一个用于语法阶段，一个用于语义阶段？

是否有纯粹的函数式编程技巧，编译器写这个问题？

解决方案

像处理关系数据库时一样，

特别是，可能没有一个AST的数据结构。

最有可能的是，将存在表示解析表达式的数据结构。处理类型信息的一种可能的方式是在解析期间已经在树的每个节点上分配唯一标识符（如整数），并且具有将那些节点id与类型相关联的一些合适的数据结构（如散列图）。然后，类型推断的作业只是创建此地图。

In the syntax analysis phase, an imperative compiler can build an AST out of nodes that already contain a type field that is set to null during construction, and then later, in the semantic analysis phase, fill in the types by assigning the declared/inferred types into the type fields.

How do purely functional languages handle this, where you do not have the luxury of assignment? Is the type-less AST mapped to a different kind of type-enriched AST? Does that mean I need to define two types per AST node, one for the syntax phase, and one for the semantic phase?

Are there purely functional programming tricks that help the compiler writer with this problem?

解决方案

Like in the case when dealing with relational databases, in functional programming it is often a good idea not to put everything in a single data structure.

In particular, there may not be a data structure that is "the AST".

Most probably, there will be data structures that represent parsed expressions. One possible way to deal with type information is to assign a unique identifier (like an integer) to each node of the tree already during parsing and have some suitable data structure (like a hash map) that associates those node-ids with types. The job of the type inference pass, then, would be just to create this map.

这篇关于纯函数编译器如何用类型信息注释AST？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！