c-如何制作函数式语言编译器

Question

我正在考虑作为一个夏季项目为它编写一种语言和编译器，并且很难找到关于如何使用解析树或BNF/EBNF来编程编译器的信息。总体目标是编写一个编译器，将简化的函数语言语法解析为c。我目前正计划用c语言编写这个编译器，但如果有人认为这是一个更好的主意，我不介意用其他语言编写。(不过，我确实想在不使用LEX等工具的情况下手动完成(

例如，如果我想创建语言ADD并将其语法定义为(+ 3 4)，那么很容易为其生成EBNF：

    Program   -> {Function}
    Function  -> Operator Integer Integer
    Operator  -> +
    Integer   -> Digit {Digit}
    Digit     -> 0|1|2|3|4|5|6|7|8|9 

而且制作解析树更容易：

         Function
             |
     -------------------
     |       |         |
  Operator  Integer  Integer

但你会怎么做：

1. 用C表示EBNF或解析树
2. 使用此数据获取有效的C代码

我觉得如果我能看到一个非常简单的工作例子，就足以让我朝着正确的方向开始。我有一种感觉，你们中的许多人都会建议我阅读Dragon Book(似乎是编译器的标准资源(，所以我想让你们知道它已经订购并发货了

提前感谢您为此事提供的任何线索

-vikingsheepman

Answer 1

取自dragon book，表示EBNF的一种方法是使用枚举对节点的类型进行分组。例如：

typedef enum { StmtK , ExpK} NodeKind;
typedef enum { IfK, AssignK, ... } StmtKind;
typedef enum { OpK, ConstK} ExpKind;
typedef enum { Void, Integer } ExpType;

并以此方式定义树的节点

typedef struct treeNode {
    struct treeNode * child[MAXCHILDREN];
    struct treeNode * sibling;
    int lineNo;
    NodeKind nodekind;
    union { StmtKind stmt; ExpKind exp; } kind; //Use union to save space
    union { TokenType op;
            int val;
            char * name; } attr;
    ExpType type; //To verify expression types
} TreeNode;

生成C代码还有很长的路要走，但本质上你需要对生成的树(语法、语义…(进行一些检查，然后生成代码。如何执行取决于您正在构建的编译器的类型(一次或多次(。如果你订购了龙书，你肯定会在那里找到所有这些。