compiler-construction - Bison 中的语义类型检查分析

Question

我一直试图到处寻找例子，但它是徒劳的。

我正在尝试编写一个基本的 Ruby 解释器。为此，我编写了一个 flex 词法文件，其中包含标记识别语句和一个语法文件。

我希望我的语法包含语义类型检查。

我的语法文件包含，例如:

arg : arg '+' arg 

这应该是整数和浮点数的有效规则。

根据我读过的内容，我可以为 arg 等非终端指定类型，如下所示:

%type <intval> arg

其中“intval”在类型联合中，对应于 int C 类型。

但这仅适用于整数，我不确定如何使规则对浮点数有效。
我想过有两种不同的规则，一种用于整数，另一种用于浮点数，例如:

argint : argint '+' argint
argfloat : argfloat '+' argfloat

但我确信有一种更好的方法可以做到这一点，因为这种暴行需要我有规则来允许浮点数和整数之间的加法。

我发现的所有示例都只有一种类型(通常是类似计算器的示例中的整数)。

如何指定诸如加法之类的规则可以将整数和浮点数作为参数？

非常感谢你。

Answer 1

这不是您希望的答案。我认为您没有看到您想要的示例的原因是在语法文件(.y)中强制执行输入规则是不切实际的；相反，开发人员在程序 .c 或 .cpp 代码中完成此操作。通常，无论如何您都会对已解析的输入进行一些分析，因此执行语义规则是您这样做的副产品。

顺便说一句，鉴于您在问题中重现的语法片段，我不太了解您是如何解析表达式的。

这就是为什么我声称这是不切实际的。 (1) 您的类型信息必须渗透到语法的所有非终结符中。 (2) 更糟糕的是，它必须反射(reflect)在变量名中。

考虑这个解析可以使用标识符、数字常量和四个桌面计算器运算符的简单赋值语句的玩具示例。 NUMBER 标记可以是像 42 这样的整数或像 3.14 这样的浮点数。假设 IDENTIFIER 是一个字母 A-Z。

%token IDENTIFIER NUMBER

%%

stmt : IDENTIFIER '=' expr
     ;

expr : expr '+' term
     | expr '-' term
     | term
     ;

term : term '*' factor
     | term '/' factor
     | factor
     ;

factor : '(' expr ')'
       | '-' factor
       | NUMBER
       | IDENTIFIER
       ;

现在让我们尝试引入打字规则。我们将 NUMBER token 分为 FLT_NUMBER 和 INT_NUMBER。我们的 expr , term , 和 factor非终端也分为两部分:

%token IDENTIFIER FLT_NUMBER INT_NUMBER

stmt : IDENTIFIER '=' int_expr
     | IDENTIFIER '=' flt_expr
     ;

int_expr : int_expr '+' int_term
         | int_expr '-' int_term
         | int_term
         ;

flt_expr : flt_expr '+' flt_term
         | flt_expr '-' flt_term
         | flt_term
         ;

int_term : int_term '*' int_factor
         | int_term '/' int_factor
         | int_factor
         ;

flt_term : flt_term '*' flt_factor
         | flt_term '/' flt_factor
         | flt_factor
         ;

int_factor : '(' int_expr ')'
           | '-' int_factor
           | INT_NUMBER
           | int_identifier
           ;

flt_factor : '(' flt_expr ')'
           | '-' flt_factor
           | FLT_NUMBER
           | flt_identifier
           ;

int_identifier : IDENTIFIER ;

flt_identifier : IDENTIFIER ;

由于我们的语法在这一点上存在冲突:解析器无法判断是否将 IDENTIFIER 识别为 int_identifier。或 flt_identifier .所以不知道要不要减 A = B如 IDENTIFIER = int_expr或 IDENTIFIER = flt_expr .

(这就是我对 Ruby 的理解有点软的地方:) Ruby(像大多数语言一样)不提供在词汇级别确定标识符的数字类型的方法。将此与老式 BASIC 进行对比，其中 A 表示数字，A$ 表示字符串。换句话说，如果你发明了一种语言，例如，A# 表示整数，A@ 表示浮点数，那么你就可以做到这一点。

如果您想允许有限的混合类型表达式，例如 int_term '*' flt_factor ，那么你的语法会变得更加复杂。

可能有一些方法可以解决这些问题。使用 yacc/bison 以外的技术构建的解析器可能会更容易。至少，也许我的草图会给你一些进一步追求的想法。