'pos' 在语法树中的含义

Question

刚开始学习SML，对下面的代码感到迷茫：

type pos = int
datatype prog= Prog of statement option
    and statement =... some code..
    and expression =
         VarExp of symbol * pos
         | IntExp of int * pos
         | BoolExp of bool * pos
         | BopExp of exp * oper * exp * pos
         | UopExp of oper * exp * pos

我无法理解的是pos的用法。签名不应该像 BopExp of exp * oper * exp 而不是 BopExp of exp * oper * exp * pos 吗？

Answer 1

自从 John、molbdnilo 和 Tai 已经在评论中回答你说 pos 可能是某种位置，表明句法元素的文本表示位于 pos文件中的第一个字符，这里还有一些想法：

一棵语法树可能会标注各种信息。解析器通常会保留错误报告的位置。静态 type-checker 也是如此，但它也可能保留可以传递给自身或后续 code-generating 阶段的推断类型信息。

你可以做的是参数化你的语法树：

datatype 'a prog = Prog of 'a stmt list
and 'a stmt = AssignStmt of symbol * 'a exp * 'a
            | PrintStmt of 'a exp * 'a
and 'a exp = VarExp of symbol * 'a
           | IntExp of int * 'a
           | BoolExp of bool * 'a
           | BopExp of 'a exp * oper * 'a exp * 'a
           | UopExp of oper * 'a exp * 'a

然后像 x := 2 + true; 这样的程序可能首先被解析并注释为 pos prog:

type pos = int
val hello = Prog [AssignStmt ("x", BopExp (IntExp (2, 6), "+",
                                           BoolExp (true, 10),
                                           6),
                              0)
                 ]

表示在位置0找到赋值，表达式2 + true在位置6找到，整数2在位置 6，布尔值 true 在位置 10。当你到达 type-checking 时，你可能想要一个 (pos × typ) prog:

type typ = Int | Bool | None | Conflict of typ list * typ
val hello = Prog [AssignStmt ("x", BopExp (IntExp (2, (6, Int)), "+",
                                           BoolExp (true, (10, Bool)),
                                           (6, Conflict ([Int, Bool], Int)),
                              (0, None)
                 ]

它保留了正确报告错误的位置信息（如果存在类型错误，这仍然是必需的），但也保留了有关类型冲突位置的信息，例如Conflict ([Int, Bool], Int) 的意思是建议虽然它期望 Int，但由于 Int 和 Bool 类型冲突，它无法推导出来.

然后你只需要一个语法树定义来定义位置、类型、寄存器，任何你能想到的来注释你的语法元素。

'pos' 在语法树中的含义

Meaning of 'pos' in syntax tree

functional-programming

ml

sml

smlnj