第四部分GCC语法与语义分析程序

1、第四部分：GCC语法与语义分析程序琚 小 明浙江大学信息与通信工程学系 2002年8月 一、语法与语义分析程序的主要功能语法分析是编译过程的第二个阶段。语法分析的任务是在词法分析的基础上将单词序列分解成各类语法短语，如“程序”，“语句”，“表达式”等等。一般这种语法短语也称为语法单位，可表示成语法树。（一）语法分析程序的主要功能语法分析所依据的是语言的语法规则，即描述程序结构的规则。通过语法分析确定整个输入串是否构成一个语法上正确的程序。在GCC中采用自底向上（bottom-up）最右规约的语法分析方法进行分析的，因为GCC的语法分析程序是由语法分析程序自动产生器（Yacc或bison）生成，

2、LR方法是YACC设定的语法分析方法。语义分析是审查源程序有无语义错误，为代码生成阶段收集类型信息。例如语义分析的一个工作是进行类型审查，审查每个算符是否具有语言规范允许的运算对象，当不符合语言规范时，编译程序应报告错误。词法分析和语法分析本质上都是对源程序的结构进行分析。但词法分析的任务仅对源程序进行线性扫描即可完成，例如识别标识符，因为标识符的结构是字母打头的字母和数字串，这只要顺序扫描输入流，遇到既不是字母又不是数字字符时，将前面所发现的所有字母可数字组合在一起而构成单词标识符。但这种线性扫描不能用于识别的递归定义的语法成分，比如不能用此办法去匹配表达式中的括号。（二）语法分析程序自动产

3、生器（YACC）简介由于GCC中的语法分析程序是由YACC产生的，故在此对YACC的工作原来作一简要的介绍。YACC的工作示意图如图1：（有关YACC的详细资料见YACC的说明文档）YACC源程序YACC单词符号串（终结符）语法分析的输出语法分析程序 yyparse输入串词法分析程序 yylex图1 YACC工作示意图。YACC源程序是用户按要求对要处理语言的语法描述，经YACC产生语法分析程序yyparse。图中的词法分析程序是GCC提供的，它的输出作为语法分析程序的输入。在图中YACC源程序是用户用YACC提供的一种类似BNF的语言写的要处理的语言的语法描述。YACC会自动的将这个源程序转

4、换成用LR方法进行语法分析的语法分析程序yyparse，YACC的宿主语言是c，因此yyparse是一个c语言的程序，用户在主程序中通过调用yyparse进行语法分析。语法分析必须建立在词法分析的基础之上，所以生成的语法分析程序还要有一个词法分析程序与它配合工作。yyparse要求这个词法分析程序的名字为yylex。用户写yylex时可以借助于LEX，也可以人工编写。在YACC源程序中除了语法规则外，还要包括当这些语法规则被识别出来时，即用它们进行归约时要完成的语义动作，语义动作是用c语言写的程序段。语法分析的输出可能是一颗语法树，或生成的目标代码，或者就是关于输入串是否符合语法的信息。需要什

5、么样的输出都是由语义动作和程序部分的程序段来实现的。（三）语法分析程序的文件构成语法分析程序尽管是由YACC自动产生的，但其语义动作是由用户自己编写的c代码，构成语法分析程序的文件有：c-parse.y，tree.h，tree.def, c-tree.h，tree.c，c-decl.c，c-typeck.c， stmt.c等。其中c-parse.y是根据YACC的规范要求对c语言文法进行的语法描述文件，即YACC源程序，经YACC可产生相应的c文件c-parse.c。相关的文件有c-lex.h，input.h，c-iterate.c，varasm.c，c-common.c，c-lex.c, m

6、achmode.h, machmode.def, obstack.h, real.h, rtl.h。等二、语法与语义分析程序的流程图及其说明（一）语法分析程序的主要工作原理由YACC产生的语法分析程序是由放在栈中的有限状态机构成的，它同时能够读取并记住下一个输入的单词（token），有时也叫这样的单词为向前看字符（lookahead token）。有限状态机的状态是用一个整数表示的，这与词法、语法分析程序中的单词是相似的。在初始时，机器处在0状态，此时仅仅栈中包含了状态0，而没有向前看字符被读入。有限自动机在语法分析程序中可执行相应的动作，以决定下一步的动作。语法分析可执行的动作（action

7、）共有4个，它们分别是：移进（shift）、归约（reduce）、接受（accept）和错误（error）。语法分析程序的运行如下：1根据当前状态，语法分析程序决定是否需要一个向前看字符以决定将要执行什么动作。如果需要一个单词但还没有读入时，语法分析程序将调用yylex获得下一个单词。2用当前状态和向前看字符（如果需要的话），语法分析程序决定它的下一个动作（action），并且执行这个动作。这样将导致状态被压入或被弹出栈，以及向前看字符是被处理了还是放在一边待用的不同变化。以下分别说明4种语法动作：移进动作（shift action）是语法分析程序采用的最平常的动作。根据当前栈的状态和向前看字

8、符，语法分析程序查动作表（action表），以决定将采取什么动作。对于移进动作，不论何时采用移进动作，都有一个向前看字符，不然移进动作将无法执行对单词的清除处理。而对应的状态却被压入了状态栈，从而造成错误。归约（reduce action）是用语法规则的左边代替其右边的过程。当语法分析程序已经看到某语法规则的右边，并且确定右边是语法规则的一个实例时，归约动作将被采用。通常语法分析程序在采用归约动作时是不需要查看向前看字符的。归约动作能防止栈无限增大，因为大多数情况下归约动作是将状态弹出栈，减少占用的栈空间。归约动作取决于语法规则左边的符号（非终结符）和右边的符号（终结符和非终结符）数。归约动作

9、首先根据语法规则右边的符号数决定将被弹出栈的状态数，然后将状态从栈中弹出，使栈中的其它的状态被显露出来。事实上，被弹出的状态就是在识别此规则右边单词时压入栈的状态，规则一旦被识别，这些状态将不再有用。将这些状态弹出之后，在状态栈中处在栈顶的状态是语法分析程序开始处理此规则之前的状态。使用弹出之后的状态和规则左边的符号，将获得一个新状态（查状态转换表即goto表得到）。将此新状态压入栈，语法分析继续。处理左边符号和普通的单词移进是有明显的不同的。把对左边符号的移进动作叫做状态转换动作（goto action），尤其不同的是，当执行移进时，向前看字符是被清除的，但在执行状态转换动作时，向前看字符是

10、不受影响的。（事实上，归约动作在语法分析过程中好像是时间倒转，将状态从栈中弹出回到规则右边刚开始看到时的状态。当一条规则被识别时，语法分析程序好似在那时看到了规则的左边。）如果规则的右边是空的，没有状态被弹出栈，也就是栈中被显露出来的状态就是栈中的当前状态。归约在处理用户提供的动作和值时也是重要的。当一条规则被识别并被归约时，在栈被调整以前，由规则提供的代码（code）将被执行。语法分析程序使用两个栈：一个是拥有状态的栈，即上文提到的栈；另一个是与之并行运行的值栈（value stack），这个栈拥有从词法分析程序和动作返回的值。当移进时，外部变量yylavl被拷贝到值栈。从用户码（user

11、code）返回后，归约被执行。当状态转换动作被执行后，外部变量yylval被拷贝到值栈。在YACC中，用伪变量$1，$2等来代表值栈的值，而$代表左边非终结符的值。另外两个语法动作相对来说比较简单。接受动作（accept action）表明整个输入都已经看到并且匹配语法规则，这个动作只有当向前看单词是endmarker（文件结束符，在GCC中是以EOF为文件结束符的）才被采用，表明语法分析程序已经成功地完成语法分析工作。报错动作（error action）说明根据规则在某处语法分析程序不能再继续语法分析了。当输入的单词已经被看到，同时还有向前看字符，但后面不能跟随可导致合法输入的任何东西，此时

12、语法分析程序报告一个错误，并且试图恢复状况（situation），试图接着进行语法分析。（二）语法分析程序yyparse的主要流程说明在语法分析过程中，YACC语法分析器主要使用两个栈：一个是状态栈，一个是语义值栈。两套指针：short *yyss, yyssa；YYSTYPE *yyvs, yyvsa。1 初始化状态栈的状态和值栈的单词值。yystate=0；yyerrstatus=0；yynerrs=0；yychar=YYEMPTY； 初始化栈指针：yyssp=yyss-1； yyvsp=yyvs；对于其中主要变量的说明：yychar 是lookahead symbol；yychar1是y

13、ychar的语法分析的内部形式；yylval 是lookahead symbol 的语义值； yyval 是用于从执行程序中返回语义值；yystate 是从执行程序中返回的状态。2yynewstate：将返回的状态yystate压入状态栈，成为新状态。*+yyssp=yystate；3取出产生式号yyn=yypactyystate；如果产生式号yyn为YYFLAG，则转到4（yydefault）。如果yychar为YYEMPTY，则调用词法分析函数得到一个单词（token）,即 yychar=YYLEX。索引表是用单词（token）的内部形式索引的，故将单词转换为内部形式。 当yychar&l

14、t;=0 时：yychar1=0； yychar=YYEOF；当yychar>0时：yychar1=YYTRANSLATE(yychar)；计算yychar1的产生式号：yyn+=yychar1；根据计算的产生式号到表中取出相应的产生式号： 初始化状态和栈指针yynewstate读取向前看单词，并将其转换成语法分析的内部形式；置新状态。计算产生式号，并由此查yytable表得到产生式号yyn移进NYYyyn > 0Nyyn < 0或yyn=0Y成功NY归约Y出错yyn < 0Nyyn是终态？图2 语法分析程序的流程图。语法分析有两个栈：一个是状态栈；一个是值栈。这两个栈

15、在进行语法分析时，它们的栈指针是同步移动的。对于出错情况的处理有两种：一种是处理后继续执行语法分析；一种是中断返回。图中用虚线表示是编译器多数情况下的处理结果。yyn=yytableyyn。yyn是这个token类型在此状态下要做的动作：如果yyn是正数，则移进，而yyn是新状态。如果yychar不是YYEOF，则放弃被移进的token，置yychar=YYEMPTY； *+yyvsp=yylval； yystate=yyn；转到2（yynewstate）；如果新状态是终态，则返回成功而不必移进。4yydefault：执行当前状态的默认产生式。 yyn=yydefactyystate； 5yy

16、reduce：如果yyn是负数，则规约，而-yyn是语法规则号，yyn=-yyn；yylen=yyr2yyn； 如果yylen>0, 则yyval=yyvsp1-yylen；由此实现执行的默认值。6如果yyn是0或者大多数的负数时，则出错。7根据yyn的值确定产生式，并执行相应的动作。8规约后，yyvsp-=yylen；yyssp-=yylen；将单词（token）的语义值赋给语义栈，*+yyvsp=yyval；yychar!=YYEOFyyn>0NY放弃被移进的单词yychar=YYEMPTYY将单词的值压入值栈*+yyvsp=yylval将新状态压入状态栈yystate=yyn

17、yynewstate图3 移进动作的流程图。移进动作较简单，只需将单词放弃，即将yychar置为YYEMPTY。然后将单词的值和新状态分别压入值栈和状态栈。返回到语法分析的开始处。9根据弹出后的状态和被规约的产生式号决定转换到什么状态。yyn=yyr1yyn； yystate=yypgotoyyn-YYNTBASE+*yyssp；当yystate不在yytable表中时，yystate=yytableyystate；否则yystate=yydefgotoyyn-YYNTBASE；转到2（yynewstate）。10yyerrhandle：出错处理。yystate=yyn；转到2（yynewst

18、ate）。或返回1。11yyacceptlab：接受状态，释放栈空间：free(yyss)；free(yyvs)； 并返回0。 对于语法分析时进行归约所要执行的动作在此不作介绍，相关的说明见第四部分的函数功能介绍和语法树结构等内容。归约动作的主要内容是建立语法树，并进行相应的语法和语义分析。yyn<0Y将产生式号取反yyn=-yynyyval=yyvsp1-yylenyylen>0查yyr2表得到归约的长度yylen=yyr2yynN根据yyn的不同完成各种归约动作（详见源代码）根据归约的长度yylen，弹出状态栈和值栈中相应数量的状态和值。yyvsp-=yylen；yyssp-=

19、yylen；将返回的语义值置入值栈*+yyvsp=yyval移进归约的结果yyn=yyr1yyn；根据当前的状态和归约的产生式号，决定转换的状态yystate=yypgotoyyn-YYNTBASE+*yysspyystate>=0&&yystate<=YYLAST&&yycheckyystate=*yyssp查yytable表得到新状态yystate=yytableyystateYN查yydefgoto表得到新状态yystate=yydefgotoyyn-YYNTBASEyynewstate图4 归约动作的流程图。根据产生式号进行相应的归约动作，用

20、产生式的左边代替右边，并将相应的状态和值弹出栈。根据当前状态和产生式号，从转换表（yypgoto）中得到新状态。三、语法与语义分析程序的数据结构及其说明GCC语法分析程序的一个主要任务是建立合理和有效的语法树。为此，GCC定义了由12个数据结构组成的一个联合，这个联合能够描述不同树节点的全部内容。这些不同的树节点是由TREE_CODE来说明的，而TREE_CODE是在文件tree.def中定义的。一个树节点能描述一个数据类型、一个变量、一个表达式或一个语句。每个节点都有一个TREE_CODE用来说明所描述的内容是哪类的。例如常用的codes：INTEGER_TYPE描述的是整型类型；ARRAY

21、_TYPE描述的是指针类型；VAR_DECL描述的是已声明了的变量；INTEGER_CST描述的是整型常量值；PLUS_EXPR描述的是一个和（一个表达式）等。（一） 树节点的类型TREE_CODE的有关说明对TREE_CODE的定义采用如下方法：#define DEFTREECODE(SYM, STRING, TYPE, NARGS) SYM, enum tree_code #include “tree.def”LAST_AND_UNUSED_TREE_CODE；#undef DEFTREECODE文件tree.def是用来定义TREE_CODE的，其形式如下：DEFTREECODE(IDE

22、NTIFIER_NODE, “identifier_node”, “x”, -1)其中的第一个参数是用来定义TREE_CODE的；第二个参数是输出时用的；第三个参数可以是下列参数之一：“x” 用于表示特别的TREE_CODE，它不属于任何一类。“t” 用于表示类型。“b” 用于表示词法的块。“c” 用于表示常量。“d” 用于表示声明。“r” 用于表示访问存储器。“<” 用于表示比较表达式。“1” 用于表示一元算术表达式。“2” 用于表示二元算术表达式。“s” 用于表示固有副作用（side effects）的表达式。“e” 用于表示其他种类的表达式。对应 “r”、“e”、“<”、“1

23、”、“2”、“s”和“x”所表示的节点，第四个元素是表示要分配参数槽的数量，这决定了树节点的大小。TREE_CODE共有11种类别(数字表示可再分类的个数)，总计有125种不同的TREE_CODE用来表示不同的节点，下面所列的是关于对文件tree.def的一个统计，详细的内容见源代码。1. error_mark： 12. identifier： 23. tree_list： 14. tree_vec： 15. block:： 16. datatype： 20 (5 for pascal)7. constant： 58. declaration： 89. reference： 610. cons

24、tructor：111. expression： 79 (4 for pascal)（二） 树节点的有关结构说明对于一个树节点的内容，有些结构成员或字段（fields）是所有节点共享的，同样有些有各自不同特殊用途的字段。在GCC中，为了一致树节点的结构，定义了一个联合（union）tree_node，所有的树节点均可以用此联合来表示。在这个联合中，总共包含了12个结构，其中结构tree_common是一个通用的结构，可以认为是其他11个结构的共有部分。另外11结构是为各种不同的树结构而定义的，但它们在结构定义中都为tree_common结构保留了空间，因此，tree_common结构在联合中始

25、终是存在的，成为所有结构的共享部分。这个联合的定义如下：union tree_node struct tree_common common; /通用结构，是其他11个结构在联合中的共有部分。 struct tree_int_cst int_cst; /整型常量结构 struct tree_real_cst real_cst; /实型常量结构 struct tree_string string; /字符串常量结构 struct tree_complex complex; /复数类型结构 struct tree_identifier identifier; /标识符结构 struct tree_d

26、ecl decl; /声明与定义结构 struct tree_type type; /类型说明结构 struct tree_list list; /列表节点，用于数据结构的描述等 struct tree_vec vec; /矢量结构 struct tree_exp exp; /表达式结构 struct tree_block block; /块结构，用于描述函数体等以及一个重要的结构指针的定义：typedef union tree_node * tree;在GCC中，对节点的结构成员或字段（fields）是不直接存取的，都是通过定义宏的方式来实现这一目的的。例如：#define TREE_COD

27、E(NODE) (enum tree_code)(NODE)->common.code)这些宏的定义都是在文件tree.h中。下面将对联合中的每个结构的主要结构成员作一简要的说明，关于联合中的12个结构的定义详见附录。(1) 结构tree_common主要成员的说明：code：code即指TREE_CODE，说明的是什么类型的节点。Code是在文件tree.def中定义的。type：在所有是表达式的节点中，这是表达式的数据类型；在POINTER_TYPE节点中，这是指针所指向的类型；在ARRAY_TYPE节点中，这是元素的类型。chain：很多情况下节点是通过chain链接起来的，这些节

28、点被链接在一起有很多用途。如：a、类型节点被链接在一起是为输出到debugger调试程序而记录这些类型的； b、在同一范围（scope）的声明节点将被链接在一起以记录此范围的内容；c、连续语句的语句节点通常被链接在一起；d、通常列表（lists）是由被链接在一起的TREE_LIST节点来描述的。(2) 结构tree_int_cst主要成员的说明：在INTEGER_CST节点中，int_cst_low和int_cst_high一起组成一个2字节整数。如果是有符号的数据类型，则整数的值是扩展符号位的2字节数，即使原来的2字节并不是所有位都被使用。如果是无符号的整数常量，则额外的符号位是0。在FAC

29、T_CST节点中，2个长整型用来得到64位数，用于描述分数。(3) 结构tree_real_cst主要成员的说明：在REAL_CST节点中，可以将一个实数值描述成“double”或是字符串。(4) 结构tree_string主要成员的说明length：是字符串的长度，整型。pointer：是指向字符串的字符指针。(5) 结构tree_complex主要成员的说明：real：在COMPLEX_CST节点中real是复数的实部。imag：在COMPLEX_CST节点中imag是复数的虚部。(6) 结构tree_identifier主要成员的说明：这是为某些特殊用途的树节点定义的。length：是标

30、识符的长度。pointer：是指向标识符的字符指针。(7) 结构tree_list主要成员的说明：这些list节点通过TREE_CHAIN链接成列表。purpose：指向参数链的指针。value：(8) 结构tree_vec主要成员的说明：length：是数组元素的个数。a1：是指向数组元素的结构指针。(9) 结构tree_exp主要成员的说明：complexity：operands1：是指向操作数的结构指针。在SAVE_EXPR节点中，用的是operands1, operands2。在RTL_EXPR节点中，用的是operands0, operands1。在CALL_EXPR节点中，用的是o

31、perands2。在CONSTRCTOR节点中，用的是operands1。在通常的表达式节点中，任意一个操作数operandsI都有可能被使用, 同时还有成员complexity。(10) 结构tree_block主要成员的说明：subblocks：包含了一个由BLOCK_CHAIN 链接起来的子块的链。 supercontext： 指向父块（parent block）。 对于一个描述函数最外层范围的块，它指向函数声明节点（FUNCTION_DECL）。 vars： 指向声明节点的链。 type_tags：指向有自己名字的类型的链。 chain： 指向下一个同一级（level）的块，即指前面提

32、到的BLOCK_CHAIN。abstract_origin： 指向起始（original）树节点，当前块是起始数节点的一个实例（instance），或者它为NULL，表明当前块不是其他任何节点的实例。当它为非空（non-NULL）时,它可指向另一个块节点，或者指向一个函数声明节点。abstract_flag： 如果当前块描述的是一个块的起始实例，则它是非0的。(11) 结构tree_type主要成员的说明：size：包含一颗树，这颗树是一个按位计算大小的表达式。 mode：包含这种类型的机器模式的值。 pointer_to：包含了一个类型，用一个指针指向这种类型。如果pointer_to为0，

33、则这种类型的节点还未建立。 next_variant：是用于链接由类型限定修饰词"const" 和 "volatile"修饰的变量的类型。 main_variant：指向上述由TYPE_NEXT_VARIANT链接的链的头指针。 noncopied_parts：是一个 list节点，用于说明这个类型的对象哪一部分是不能通过赋值拷贝的。 每个节点的TREE_PURPOSE 是这部分的偏移量。TREE_VALUE 是这部分以位计的大小。 name：包含为这种类型在程序中使用的名字的信息（为GDB符号表的输出）。它是一个类型定义（typedef）的 TYPE_

34、DECL节点；或者是一个IDENTIFIER_NODE 节点在结构、联合、枚举已知是有标签（tag）的；或者是0，当类型还没有特殊的名字。 context：对类型有一个名字或者已经命名的成员（member）中的任意一种情况，它指向描述给定类型的范围的节点，或者如果此类型具有文件范围（file scope），则它是NULL_TREE。对大多数的类型来说，它将指向一个块（block）节点或是函数声明节点（FUNCTION_DECL），但是它也能够指向函数类型节点（FUNCTION_TYPE），或者是结构类型节点（RECORD_TYPE）和 联合类型节点（UNION_TYPE）。chain：是用于枚

35、举类型（ENUMERAL_TYPE）,结构类型（RECORD_TYPE） 和 联合类型（UNION_TYPE）节点的。(12) 结构tree_decl主要成员的说明：所有与名字有关的都描述为._DECL节点，这些在一个绑定上下文（binding context）的节点通过TREE_CHAIN链接起来。name：包含一个IDENTIFIER_NODE的节点，此节点是给定实体的名字。对labels来说，DECL_NAME为0。context：指向描述此声明作用范围的上下文的节点。对FIELD_DECLs而言，这是定义它的RECORD_TYPE 或是 UNION_TYPE 节点。对VAR_DECL,

36、 PARM_DECL, FUNCTION_DECL, LABEL_DECL, 及CONST_DECL 节点来说，它指向包含它们的FUNCTION_DECL节点。如果给定的声明是文件范围，则它是 NULL_TREE。 abstract_origin：如果非0，它指向起始（original）声明节点，而当前声明节点是它的一个实例（instance）。当相关的时候，TREE_TYPE 拥有对象的数据类型。而LABEL_DECLs 没有数据类型。对TYPE_DECL来说， TREE_TYPE 的内容是一个类型，它的类型名正在被声明，也可以说TREE_TYPE是已声明实体的类型。frame_size,

37、size, 和mode： 存在于声明节点和类型节点，它们在LABEL_DECL, TYPE_DECL 和 CONST_DECL 节点中是没有用的。以下三个字段仅与 FIELD_DECLs 和PARM_DECLs有关：DECL_OFFSET ：拥有相对位偏移的整数值。DECL_VOFFSET： 拥有可变偏移的表达式，它与DECL_VOFFSET_UNIT (一个整数)相乘可得偏移量。initial：拥有对一个变量的初始化的值，或是初始化一个常量的值。对一个函数而言，它指向一个块（block），用一个块来说明函数的binding contour并且包含了函数的语句。对于C 中的 LABEL_DEC

38、L, 它是一个标志（flag），当label的定义已被看见时，此标志为非0。 PARM_DECLs 使用特殊的字段： initial：是参数实际上通过类型检查的类型，此类型可能与它原来在函数中的类型有所不同。FUNCTION_DECLs 使用以下四个特殊的字段： arguments： 拥有一条参数声明PARM_DECL节点的链。 result：拥有一个函数返回值声明的 RESULT_DECL 节点。或者当函数无返回值时，它为0。（在c中，函数返回void即为无返回值） DECL_RESULT_TYPE ：拥有函数实际返回值的类型。这通常与DECL_RESULT的类型是相同的，但这可能是一个宽整

39、型类型；同时为了内联，甚至对函数的编译已经结束，这仍然有效。这是两者的不同之处。frame_size：是一个代码数字（code number），非0时表示是内建函数（built-in function）。它的值是一个枚举类型值，指明了是哪一个内建函数。filename： 拥有一个文件名字符串。linenum：拥有一个行数。abstract_flag：非0时，此声明说明一个声明的抽象实例（abstract instance）。 （三） 建立树节点时的有关栈与数据结构的说明Gcc在处理语法树节点时使用栈存放节点的内容，有关各个栈的详细内容见源代码，下面仅对各栈作一简要的说明：1. permanen

40、t_obstack 存放永久的树节点，如标识符，全局的有关东西，函数定义的参数等。2. maybepermanent_obstack 存放在函数内的初始的RTL和_TYPE节点，通常它们在函数结束时被释放。3. temporay_obstack是用来读全局变量的初始化值的。4. momentary_obstack 存放表达式的树节点，它们在表达式结束时都被释放。5. temp_decl_obstack 存放的树节点，当声明通过语法检查时被释放。6. momentary_level 暂时存放momentary_obstack，以便恢复。7. obstack_stack 时用来选择推进还是弹出ob

41、stack。标识符节点、体外所有的东西和函数定义的参数分配在permanent_obstack中。RTL的初始化，所有在一个函数内的_TYPE节点分配在function_maybepermanent_obstack中，通常它们在函数结束时被释放，但如果函数是内联函数时将被储存，嵌套的函数存放在各自分开的栈中。当前函数定义的内容分配在function_obstack中，在函数结束时全部被释放，嵌套的函数存放在各自分开的栈中。表达式节点分配在temp_decl_obstack中，当声明体通过语法时全部被释放。Struct obstack *saveable_obstack 指向permanent_

42、obstack 或者当前的function_maybepermanent_obstack.Struct obstack *current_obstack 指向permanent_obstack或者当前的function_obstack.在语法和展开期间，Struct obstack *rtl_obstack 与saveable_obstack一样；在优化时它指向当前函数的栈；这是用来产生rtl 对象的栈。Struct obstack *current_obstack指向permanent_obstack 或者当前的function_obstack或者momentary_obstack.对每个b

43、inding contour 分配一个binding _level structure，这个结构记录了定义在那个contour中的names。Contour 包括：全局的contour；每个有参数的内部声明出现的函数定义；复合语句，记录它的声明。struct binding_leveltree names;tree tags;tree shadowed;tree blocks;tree this_block;struct binding_level *level_chain; char parm_flag;char tag_transparent;char subblocks_tag_tran

44、sparent;char keep;char keep_if_subblocks;int n_incomplete;tree parm_order;names：指向所有变量，常量，函数和typedef 类型的_DECL节点的链。这个链是以相反的顺序提供的。tags：指向一个结构，联合和枚举定义的list, 这是一个TREE_LIST 节点的链，每个节点的TREE_PURPOSE 时一个name或者NULL_TREE; 节点的TREE_VALUE时一个RECORD_TYPE,UNION_TYPE,或者是ENUBERAL_TYPE节点。对每一层，当这一层被弹出时，被屏蔽的外层局部定义的list 将

45、被存储。每个link 是一个TREE_LIST, 它的TREE_PURPOSE时一个标识符，它的TREE_VALUE是它原来的定义（-DECL节点）。blocks：对于每一个level，都有一条由块（block）节点组成的链，blocks指向此链。shadowed：对于每一个level，当这个level被弹出时，被屏蔽（shadowed）的外层level的局部定义的list节点将被储存起来。每个list链节点的TREE_PURPOSE是一个标识符，而TREE_VALUESHI 是它老的定义（是_DECL节点）。this_block：这层level的block节点由this_block指向。le

46、vel_chain：binding_level是由level_chain链接在一起的。parm_flag：非0表示此level拥有函数的参数。tag_transparent：非0表示这层level没有tags。parm_order：声明的列表是以相反的参数顺序说明的。定义了三个主要的结构指针，其中current_binding_level是当前有效的操作level；free_binding_level是binding_level的链，用来把释放的binding_level链起来以备重复使用。目的是减少内存堆中的碎块；global_binding_level是最外层的binding_level，

47、它是在编译器开始编译的时候建立的，并在整个运行过程中存在。它们分别定义如下：struct binding_level * current_binding_level;struct binding_level * free_binding_level;struct binding_level * global_binding_level;（四）语法分析时建立的语法树结构对于每个binding contour都将分配一个binding_level节点，用来记录在这个contour这定义的names。Contour包含以下三个方面：1 全局的contour。2 每个函数定义都有一个对应的contou

48、r，参数的内部声明出现在那里。3 每个复合语句对应一个contour，用来记录它的声明。结构指针free_binding_level的用处：当一个binding_level节点被弹出时，并不实际释放内存空间，而是将此节点链入到free_binding_level指向的链中。当需要一个binding_level节点时，首先查看free_binding_level链释放为空。若有就重复使用原来已经存在的节点，否则新建一个节点。supercontextblockcurrent_function_decldecl nodeinitial resultinitial resultinitial resu

49、ltbinding_levelcurrent_binding_levelglobal_binding_levelnames tags blocksnames tags blocksnames tags blockslist nodevalue purposevalue purposevalue purposetype nodecontextcontextcontextblock nodeblock/ current_function_declinitialdecl nodeblock nodetype nodelist nodebinding level node图5 顶层的语法树结构bind

50、ing_level。GCC在进行语法分析时，是以current_binding_level为中心，所有的声明、参数定义和块等都是挂在binding_level上的。图中的虚线箭头表示省略了节点，对与其他图相连的连线和箭头采用不同的颜色加以区别。存储当前level的状态：每当当前level被弹出时，level中的状态将被保存到一个块(block)中。将当前level的names（decls）链入block的vars；将当前level的tags链入block的type_tags；将当前level的blocks链入block的subblocks。然后将当前level节点弹出，同时链入到free_bi

51、nding_level链中，并使下一个level节点成为当前level。parm decl nodeinitial resultinitial resultinitial resultblock nodesupercontextsupercontextcurrent_function_declnamesinitial result type argumentsdecl nodecontexttype valuestype nodetype nodevalue purposevalue purposelist nodevalue purposearg types图6 当前函数声明current_

52、function_decl的语法树结构。initial 指向的block节点包含了函数体的语句；result指向的decl节点是函数的返回值；arguments指向的是参数声明节点的链。TYPE_VALUES是list链，它的 TREE_PURPOSE是名字，TREE_VALUE是值 ( INTEGER_CST节点)。block nodeblockvars type_tags subblocks supercontextcurrent_function_declblockstagsnamesblock nodelist nodevalue purposevalue purposevalue p

53、urposedecl nodeinitial resultinitial resultinitial result图7 块节点block的语法树结构。一个块包含声明、参数、子块等，这些都是挂在同一个块的节点上的。以个块也可能是一个函数体，在图5中，函数声明initial指向的块block就是一个函数体。四、语法与语义分析程序主要函数的功能：void push_obstacks (curren, saveable)struct abstack* current, *saveable;将当前各栈的指针放到obstack_stack 中，然后将current,saveable设置为当前栈。void

54、push_obstacks_nochange ()将当前各栈中的指针存放到obstack_stack中，并使栈指针指向它。void push_momentary ()分配临时存储空间（struct momentary_level） （在c 中，每个复合语句有自己的层次，这个层次在每个语句结束时被释放。所有表达式节点也是分配momentary_stack）。void pop_momentary ()释放momentary_stack。tree make_node (code)enum tree_code code;根据code指向不同的obstack, 在obstack 中创建对应code 的节点，并返回这个节点的指针。Identifier 节点始终是永久的，因为它们在编译器运行中是唯一的，初始化它的id和它的TREE_PERMANENT flag。对decl和type节点，一些其它fields要初始化（如decl_source_line; decl_source_file; decl_source_file 等）。其余的都初始化为0。tree copy_node (node)tree n