c - c编译器类型检查算法和语义分析

Question

是否有任何建议的算法来查找 c 代码中的变量类型？

我正在编写一小部分 c 语言的编译器。它现在处理 int 和 float 类型，但它应该处理任何可能的合法 c 类型（在函数中，int 和 float）。（例如 int ** (*fp)(int, int) 等。）由于存在任意数量的可能性，因此不可能使用任何类型的枚举或哈希表。

那么这个问题通常是如何解决的呢？

这种声明可以用 LL1 解析器完成吗？

Answer 1

这是一个太深奥的问题，在这里无法完全回答。但是，大多数编译器使用图形数据结构来表示类型。（很多年前，为了节省空间，图被精心编码以节省空间，但现在没有必要了。）C 的图节点是递归类型（就像大多数图节点一样），大致如下：

typedef enum { 
  VOID, INT, CHAR, DOUBLE, ENUM, POINTER, ARRAY, STRUCT, UNION, FUNCTION,
} KIND;

typedef struct type_s {
  KIND kind;
  union {
    struct enumeration_s {
      int n_values;
      struct enum_value_s *values;
    } enumeration;
    struct pointer_s {
      struct type_s *to_type;
    } pointer;
    struct array_s {
      struct type_s *of_type;
      size_t n_elements;
    } array;
    struct struct_or_union_s {
      size_t n_fields;
      struct field_s *fields;  // Variable-sized array of fields.
    } struct_or_union;
    struct function {
      struct type_s *return_type;
      size_t n_args;
      struct field_s *args;    // Variable-sized array of args.
    } function;
  } u;
} TYPE;

typedef struct enum_value_s {
  char *name;
  int value;
} ENUM_VALUE;

typedef struct field_s {
  char *name;
  struct type_s *type;
} FIELD;

如果您已经构建了编译器，那么您应该知道抽象语法树是什么。这只是类型的 AST。您应该能够轻松绘制int ** (*fp)(int, int).

是的（除了众所周知的 typedef 歧义，您可能已经在处理）在 LL(1) 或 LR(1) 解析器中生成这些类型图并不难。