1



我正在考虑为它编写一种语言和编译器作为一个夏季项目，并且很难找到有关如何使用解析树或 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（似乎是编译器的标准资源），所以我想让您知道它已经订购并发货。

预先感谢您对此提供的任何启示！

-维京绵羊人

4

1 回答 1

1

取自龙书，表示 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 代码还有很长的路要走，但本质上您需要对生成的树（语法、语义...）进行一些检查，然后生成代码。如何做到这一点取决于您正在构建的编译器的类型（一次或多次）。如果您订购了龙之书，那么您肯定会在那里找到所有这些。

于 2013-05-23T00:52:00.233 回答