Как создать компилятор функционального языка

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. Представляют EBNF или дерево разбора в C
2. Используйте эти данные, чтобы получить код действителен Ĉ

Я чувствую, что если бы я мог видеть очень простой рабочий пример, было бы достаточно, чтобы я начал в правильном направлении , У меня такое чувство, что многие из вас будут рекомендовать, чтобы я прочитал Dragon Book (кажется, это стандартный ресурс для компиляторов), поэтому я хочу сообщить вам, что он уже заказан и отправлен.

Благодарим вас за любой свет, который вы можете пролить на это!

-vikingsheepman

Answer 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, но по сути вам нужно сделать некоторые проверки над сгенерированным деревом (синтаксис, семантика ...) и затем сгенерировать код. Как это сделать, зависит от типа создаваемого вами компилятора (один или несколько проходов). Если вы заказали книгу Дракона, вы наверняка найдете все это.