我们将要开发一种新的小型语言，它包含以下结构 - 赋值、变量声明、if 和 while 语句等。我们不打算直接编译我们的程序，而是让 GCC 来完成必要的操作并生成机器代码。让我们给我们的语言起个名字。我给它取名为 "demo"，因为它展示了如何开发一个新的编译器。我选择的语法是 Pascal 和 C 的结合，以便熟悉这两种语言的程序员都能理解。
我们的角色是清晰地指定我们语言的语法，并为该语言创建一个树结构。我们将从树结构创建 RTL。之后，由后端负责生成优化的输出。我们将只专注于树结构的创建和 rtl 转换。
将指定许多用于处理树和 rtl 的函数和宏。还会简要描述每个函数和宏的作用。正在解释的语言只处理整数值，这样我们可以避免不必要的类型转换复杂性。
让我从我们语言的基本单元，表达式开始。在这里，我们只需要执行树结构的创建。这可以通过一个名为 'build' 的函数来实现。
build(PLUS_EXPR, type, left, right) 返回一个用于加法运算的树。这里 left 和 right 是我们提供的两个用于加法的树。我们只有一种类型 - 整数类型。所以在这方面没有混淆。
类似地，我们有 build1 用于像求反这样的运算，如下所示
build1(NEGATE_EXPR,type,expression)，其中 expression 是要取反的树。它用于一元运算符的情况。
最后，我们可以为简单的整数创建树，如下所示
build_int_2(int num, num >=0 ? 0 : -1) 为特定数字创建一个树。实际上，传递的两个参数是 HOST_WIDE_INT 类型的低值和高值。但让我们这样理解它 - 我们必须设置函数的第二个参数来显示正确的符号。这实际上是一个调用函数 build_int_2_wide 的宏。
现在我们对创建树来构建表达式有了一个概念。让我们直接编写用于表达式树创建的解析段。
exp: NUM { $$ = build_int_2 ($1, $1 >= 0 ? 0 : -1); }
| exp '+' exp { $$ = build (PLUS_EXPR, integer_type_node, $1, $3); }
| exp '-' exp { $$ = build (MINUS_EXPR, integer_type_node, $1, $3); }
| exp '*' exp { $$ = build (MULT_EXPR, integer_type_node, $1, $3); }
| exp '/' exp { $$ = build (TRUNC_DIV_EXPR, integer_type_node, $1, $3); }
| exp '%' exp { $$ = build (TRUNC_MOD_EXPR, integer_type_node, $1, $3); }
| '-' exp %prec NEG { $$ = build1 (NEGATE_EXPR, integer_type_node, $2); }
| '(' exp ')' { $$ = $2; }
现在我直接给出 demo 语言所需的词法文件。由于其简单性，不提供解释。
%%
[ \n\t] ; // white space
[0-9]+ {yylval.ival = atoi(yytext); return NUM;} // integers
var {return VAR;} // variable declaration
return {return RETURN;} // return
if {return IF;} // if
then {return THEN;} // then
else {return ELSE;} // else
endif {return ENDIF;} // endif
while {return WHILE;} // while
endwhile {return ENDWHILE;} // endwhile
begin {return BEGIN;} // begin
end {return END;} // end
"<" {return LT;} // less than
">" {return GT;} // greater than
"==" {return EQ;} // equal to
[a-zA-Z]+ {yylval.name = strdup(yytext); return NAME;}
// function/variable name
. {return yytext[0];} // match all single characters
%%
让我们也展示我们将要开发的语法，这样我就不必总是重复它了。
%union{
tree exp; //Tree node developed by us.
int ival; //Integer value for constants.
char *name; //Name of function or variables.
}
input: fndef body ;
fndef: NAME '(' ')';
body: BEGIN declarations compstmts END;
declarations: /*empty */
| declarations VAR NAME
compstmts: /*empty */
| compstmts statements;
statements: exp
| assignstmt
| ifstmt
| whilestmt
| returnstmt;
assignstmt: NAME '=' exp;
whilestmt: head loopbody;
head: WHILE exp
loopbody: compstmts ENDWHILE
ifstmt: ifpart thenpart elsepart;
ifpart: IF exp;
thenpart: THEN compstmts;
elsepart: ELSE compstmts ENDIF;
returnstmt: RETURN exp;
exp: NUM
| exp '+' exp
| exp '-' exp
| exp '*' exp
| exp '/' exp
| NAME;
我将以逐步的过程开发我们的 "demo" 语言。从表达式开始，我们将稳步前进到最后。在每个阶段，都会在语言中引入一个新的结构。因此，在最后阶段，"demo" 语言在所有方面都遵守上述语法。
在上面的 bison 代码中，我没有为产生式提供语义动作。当我们学习开发树和 rtl 转换时，将会介绍它们。
同样，在每个阶段，我只会提供您所需的 bison 段。您可以查看上面的语法以了解整体工作原理。
让我们将表达式插入到一个函数中。对于一个函数，需要调用大量的步骤。范围从设置参数到声明我们的声明。所需的树和 rtl 函数将在下面逐步描述。大多数处理树的函数都以 'build' 开头，并将返回一个树结构。（我并没有在任何地方明确给出这个事实。您应该通过使用树的函数的方式来理解它。）我们将使用 GCC 提供的函数来构建树。使用树结构，我们将创建 rtl。
对于 GCC 提供的函数，只有在具有相对重要性时才会解释参数。
让我们编写函数处理的例程。给定的代码构建一个名为 "name" 的函数。
build_function_decl (char *name)
{
tree param_list; //param_list is of type tree. Similarly others.
tree param_type_list;
tree fntype;
tree fndecl; // Consider it as a global value.
// It will be required quite often.
/*首先，我们必须安排函数中涉及的参数。假设，我们有 "hello(int a, int b)"，那么 a 和 b 构成参数。 a 和 b 必须对函数可用。但由于这是我们的第一次尝试，我们假设该函数不涉及任何参数。因此，param_list 被设置为 NULL_TREE（它是 tree 类型的 NULL）。 */
param_list = NULL_TREE;
/*接下来是参数的类型。函数总是接受固定数量的参数。由于在当前示例中我们没有任何参数，因此我们调用函数 tree_cons，如下所示。第一个字段是用途字段，最后一个字段是链字段（用于将不同的类型（如整数）链接在一起）。当我们传递一些参数时，我们将更多地解释这一点。 */
param_type_list = tree_cons(NULL_TREE, void_type_node, NULL_TREE);
/*好的，我们已经完成了参数。即参数和类型。我们不必为此烦恼。现在让我们看看函数。第一件事是函数的类型。它取决于返回类型和参数类型。我们将我们的函数视为返回整数值的函数。因此，build_function 的第一个参数是 integer。第二个参数处理参数。参数的类型在 param_type_list 中给出。 */
fntype = build_function_type(integer_type_node, param_type_list);
/*接下来是函数声明。可以使用函数 build_decl 来实现。第一个参数说明它是一个函数声明。第二个参数涉及一个函数 get_identifier。它返回一个树，其名称为 "name"。如果先前已引用具有该名称的标识符，则返回相同的树节点。由于这是我们第一次使用它，因此返回一个新的树节点。最后一个参数处理函数的类型。 */
fndecl = build_decl(FUNCTION_DECL, get_identifier(name), fntype);
/*这里是标志。它们通过下面给出的特殊宏调用*/
/*如果非零，则表示外部引用。不需要分配存储空间。在其他地方有定义。但我们需要在这里本身进行定义，因此为零。 */
DECL_EXTERNAL(fndecl) = 0;
/* 非零表示可以从模块外部访问该函数。*/
TREE_PUBLIC(fndecl) = 1;
/* 非零表示函数已被定义而不是声明。 */
TREE_STATIC(fndecl) = 1;
/* 它声明函数的参数（存储在 param_list 中）*/
DECL_ARGUMENTS(fndecl) = param_list;
/* 它为返回值声明声明。*/
DECL_RESULT(fndecl) =
build_decl(RESULT_DECL, NULL_TREE, integer_type_node);
/*它声明结果的上下文。即我们通知结果，其作用域是 fndecl。*/
DECL_CONTEXT( DECL_RESULT( fndecl)) = fndecl;
/*为函数声明创建 rtl。第一个参数给出函数声明的树。第二个参数处理汇编器符号名称。我们不需要它在这里。我们将其设为 NULL。稍后查看第三个和第四个参数。感兴趣的读者可以参考 toplev.c */
rest_of_decl_compilation (fndecl, NULL_PTR, 1, 0);
/*这给出了关于声明在源代码中的位置的想法 */
DECL_SOURCE_FILE( fndecl) = input_filename; DECL_SOURCE_LINE( fndecl) = 1;
/* 此函数仅用于在需要时在 stderr 上打印函数 "name" 的名称 */
announce_function( fndecl);
/* 让 GCC 知道正在编译的函数的名称。*/
current_function_decl = fndecl;
/* 它保存绑定的树。只是一种用于在此处制作部分树的方法。不要为此烦恼。 */
DECL_INITIAL( fndecl) = error_mark_node;
/* 所有树和 rtl 都分配在临时内存中。每个函数使用。 */
temporary_allocation();
/*pushlevel 在回调中解释。在这里，它需要在任何函数开始时进行推送。 */
pushlevel(0);
/*为函数定义创建函数 rtl。 */
make_function_rtl( fndecl);
/*为函数 fndecl 的开始生成 rtl。第二个和第三个参数表示文件和行 */
init_function_start(fndecl, input_filename, 1);
/*让我们为新函数启动 rtl。它还设置用于发出 rtl 的变量。第二个参数表明没有与之关联的清理。如果将其设置为非零，则在遇到 return 语句时将运行清理。 */
expand_function_start(fndecl, 0);
/*它生成用于进入新绑定级别的 rtl 代码。*/
expand_start_bindings(0); } //end of build_function_decl
当进入函数时，会调用上面提到的所有函数。当我们离开函数时，必须完成其他一些事情。这些在下面的代码中进行了解释。
build_function() {
/*让我们构建树并为 return 语句发出 rtl。为了避免额外的树变量，我将树创建和 rtl 转换包含在一个语句中。首先为 'fndecl' 构建类型为 result 的树。我总是从我们的简单函数返回零。如果您打算返回任何其他值，请用其他相应的树结构替换 integer_zero_node。 expand_return 为树创建 rtl。 */
expand_return (build (MODIFY_EXPR, void_type_node, DECL_RESULT(fndecl),
integer_zero_node));
/*为绑定的结束发出 rtl。就像开始绑定一样 */
expand_end_bindings (NULL_TREE, 1, 0);
/* 我们已经推送了。所以不要忘记弹出 */
poplevel (1, 0, 1);
/*为函数的结束发出 rtl。就像开始一样 */
expand_function_end (input_file_name, 1, 0);
/*编译函数，输出汇编代码，释放树存储空间。 */
rest_of_compilation (fndecl);
/*我们现在自由了 */
current_function_decl=0;
/* 释放临时存储中的所有内容。参数 1 表明，我们刚刚完成编译一个函数 */
permanent_allocation (1); }
我们已经理解了函数和表达式的工作原理。让我们为函数和表达式添加所需的语义动作。
input: fndef body { build_function(); };
fndef: NAME '(' ')' { build_function_decl ($1); };
exp: NUM { $$ = build_int_2 ($1, $1 >= 0 ? 0 : -1); }
| exp '+' exp { $$ = build (PLUS_EXPR, integer_type_node, $1, $3); }
| exp '-' exp { $$ = build (MINUS_EXPR, integer_type_node, $1, $3); }
| exp '*' exp { $$ = build (MULT_EXPR, integer_type_node, $1, $3); }
| exp '/' exp { $$ = build (TRUNC_DIV_EXPR, integer_type_node, $1, $3); }
| exp '%' exp { $$ = build (TRUNC_MOD_EXPR, integer_type_node, $1, $3); }
| '-' exp %prec NEG { $$ = build1 (NEGATE_EXPR, integer_type_node, $2); }
| '(' exp ')' { $$ = $2; }
foo()
begin
1+2*3
end
我们目前的状况如何？我们拥有一个函数和一个表达式，但它们毫无用处。如果我们的语言中存在可以赋值和返回的变量，它将会更加出色。
因此，下一步是声明变量。像往常一样，我们必须构建树并将其转换为 rtl。当我们进行变量声明时，例如
var a; // I prefer PASCAL syntax. Just a matter of taste.
我们必须存储 'a' 的值，因为当稍后在表达式中使用它时，例如 a+1，我们必须使用相同的 'a'。
我们可以定义我们自己的两个数组 var_name[ ] 和 var_decls[ ]，如下所示。
char *var_name[100]; //global array ie. initialized to zero. tree var_decls[100]; //global array
我希望读者已经理解，第一个用于存储 "demo" 中变量的名称，第二个用于存储构建的相应树结构。
让我们直接查看代码。
void add_var(char *name)
{
int i;
/*Add the name given, as the last name in the array */
for(i=0;var_name[i];i++);
/* Store the name */
var_name[i] = name;
/*Build the tree structure for the variable declared
All the parameters are explained before.
Thus we have name of the variable stored in var_name[] and
tree stored in var_decls[ ]*/
var_decls[i] =
build_decl (VAR_DECL, get_identifier(name), integer_type_node);
/* Explained before*/
DECL_CONTEXT (var_decls[i]) = fndecl;
/*We are just making the initial value of the variable declared
as zero. This is a matter of taste. */
DECL_INITIAL (var_decls[i]) = integer_zero_node;
/*push to the current scope. Explained before*/
pushdecl (var_decls[i]);
/* Emit the rtl for the variable declaration*/
expand_decl (var_decls[i]);
/* Emit the rtl for the initialization. ie. Initialized to zero*/
expand_decl_init (var_decls[i]);
}
从现在开始，我不会完整地给出 bison 文件。我只会提供每个阶段我们修改的段。如有任何疑问，请参考上面提供的 bison 文件。
变量声明的 bison 段由下式给出
declarations: /*empty */
| declarations VAR NAME { add_var($3); };
将变量声明与上述函数和表达式的语法相结合，我们有另一个 "demo" 程序的示例。
foo()
begin
var a
var b
1+2*3-1
end
一个接一个的变量和表达式对我们做任何有用的事情没有任何帮助。为此，我们需要赋值。让我们研究赋值的树结构构建和 rtl 转换。
赋值语句的一般格式是 "a = 10"。它所需的操作是将值 10 存储在 'a' 中。我们在变量声明时创建了 'a' 的树结构并将其存储在 var_decls[] 中。因此，我们的职责是检索 'a' 的树结构并在其中赋值，例如 10。
我们寻求名为 "get_var" 的函数的帮助来检索变量的树结构。代码如下
tree get_var(char *name)
{
int i;
/*Search for the name "name" in the variable name table, var_name[]
for(i=0;var_name[i];i++)
/*If found, return the corresponding tree structure of "name"
if( !strcmp (var_name[i], name))
return var_decls[i];
}
上面的函数为我们获取了变量的树结构。剩下的唯一任务是构建赋值的树结构和 rtl 转换。这可以通过以下函数实现。
make_assign (tree vartree, tree valtree)
{
tree assign;
/* Create the tree. Explained before.
assign =
build (MODIFY_EXPR, integer_type_node, vartree, valtree);
/*Non zero values means that there is a side effect and re evaluation
of the whole expression could produce a different value. The
optimization phase takes this into consideration.
*/
TREE_SIDE_EFFECTS (assign) = 1;
/* Indicates that the tree node is used */
TREE_USED (assign) = 1;
/* Emit the rtl for the assign tree */
expand_expr_stmt (assign);
}
我们还研究了赋值结构的树创建和 rtl 转换。现在是时候在 bison 文件中为赋值提供语义动作了。
assignstmt: NAME = exp { make_assign ( get_var($1), $3); };
我们现在使用的表达式只能处理数字。即我们可以给出诸如 "1+2"、"1+2*3" 等表达式。但我们无法处理变量名，例如 "a+1"、"b+a-5" 等。
让我们修改我们的表达式以也包含变量名。包含的任务很简单。我们必须获取变量名的树结构。我们手头有一个函数 "get_var"，它可以做到这一点。
所以让我们看看这个的语义动作
exp: NAME { $$ = get_var ($1); };
hello()
begin
var i
var j
var k
i = 10
j = 20
k = i + j
end
如果我们可以返回计算出的总和，上面的程序将会更加出色。因此，我们的下一步将是包含 return 结构。
当我解释 'function' 时，我已经提到了 'return' 的树创建。但当时我们只返回了零。现在让我们在零的位置返回一个表达式。
ret_stmt (tree expr)
{
tree ret;
/* build the tree node for return. The arguments are explained
before. 'fndecl' is the global variable that we have defined
before, for our function.
*/
ret =
build (MODIFY_EXPR, integer_type_node, DECL_RESULT(fndecl),
expr);
/*emits the rtl */
expand_return (ret);
}
让我们直接看 bison 段
returnstmt: RETURN exp { ret_stmt ($2) ; };
hello()
begin
var i
var j
var k
i = 10
j = 20
k = i + j
return k
end
在 'if' 结构的情况下，我们的任务与上面不同。我们必须清楚地向 GCC 提供关于 if 结构从哪里开始，'else' 部分从哪里开始以及 if 结构在哪里结束的信息。
GCC 为我们提供了 rtl 语句，这些语句能够执行上述任务。 rtl 语句如下
expand_start_cond (tree cond, int exitflag)
它为 if-then 的开始生成 rtl。 'cond' 是要检查其真值的表达式。将 exitflag 视为零。
expand_start_else () expand_end_cond ()
这些分别导致为 'else' 的开始和 'if 结构' 的结束生成 rtl 代码。
现在我们可以在我们的 bison 文件中使用上述函数。
ifstmt : ifpart thenpart elsepart { expand_end_cond (); };
ifpart : IF exp { expand_start_cond ($2, 0); };
thenpart: THEN compstmts { expand_start_else (); };
elsepart: ELSE compstmts ENDIF ;
example()
begin
var x
var y
x = 100
if (x) then
y = 1
else
y = 0
endif
return y
end
循环与条件语句相同。我们必须提供循环的开始、循环的结束以及要检查真值的表达式。
用于上述操作的 rtl 语句是
struct nesting *expand_start_loop (int exit_flag) expand_exit_loop_if_false (struct nesting *whichloop, tree cond) expand_end_loop()
第一个表示循环开始的 rtl。 'exit_flag' 为零。返回类型是 struct nesting *，在第二个语句中使用。第二个语句用于生成条件跳转以退出当前循环（如果 'cond' 的计算结果为零）。第三个语句是循环结束的 rtl。它生成一个跳回到循环顶部的跳转。这些想法将在 bison 文件中更清晰。
whilestmt: head loopbody { expand_end_loop(); };
head : WHILE exp { struct nesting *loop;
loop = expand_start_loop (0);
expand_exit_loop_if_false (loop, $2);
};
loopbody: compstmts ENDWHILE ;
test()
begin
var i
i = 100
while (i)
i = i-1
endwhile
return i
end