《现代编译原理-C语言描述》（4）- 抽象语法

虎书编译原理

发布日期: 2019-04-09

第四章抽象语法

抽象的(ab-stract):从所有具体实例中提取出来的。
—-韦氏词典

语义动作

语法分析器中的语义动作（semantic action），可以作用于正在分析的短语。

对于递归下降分析器来说，语义动作是分散在实现语法分析的控制流中
对于遵循Yacc说明的语法分析器，语义动作是附带在文法产生式之后的c程序代码

递归下降

对于递归下降语法分析器，语义动作是语法分析函数的返回值，或是语法分析函数的副作用，抑或是兼而有之。

每个非终结符和终结符（type）都关联一种语义值，语义值代表了由这个符号导出的短语。

对于消除左递归的情况，我们通过将左操作数作为参数传递给下一个语法分析函数的方法来解决。

也就是说我们为了消除左递归，必须要引入新的符号，但是新引入的符号的产生式不一定符合运算符的操作规范，于是我们必须要将上一层分析中的左操作数传递到下一层并返回。

Yacc生成的分析器

对于遵循Yacc说明的语法分析器,语法动作是附加在产生式之后的一段c代码。当Yacc利用，某一条规则进行归约时，就会执行其后的语义动作。例如文法3-13Yacc语法分析器：

%{ declarations of yylex and yyerror %}
%union {int num; string id;}
%token <num> INT
%token <id> ID
%type <num> exp
%start exp
%left PLUS MINUS
%left TIMES
%left UMINUS
%%
exp : INT             {$$ = $1;}
    | exp PLUS exp    {$$ = $1 + $3;}
    | exp MINUS exp   {$$ = $1 - $3;}
    | exp TIMES exp   {$$ = $1 * $3;}
    | MINUS exp   %prec UMINUS {$$ = - $2;}

Yacc中语义动作的使用是用$i来引用第i个右部符号的语义值，它为左部非终结符产生的值可以赋给$$。%union说明了各种可能携带的语义值类型，每个非终结符通过<variant>，注释指明该非终结符应该使用哪一个%union声明中的形式。

遵循Yacc说明的语法分析器会维护一个 状态栈 和一个 语义值栈 来实现对语义值的操作，在原来简单分析栈的基础上增添了一个与分析栈符号一一对应的语义值栈。在语法分析器执行一个归约动作时，它会从一个简单栈中弹出k个字符，并将归约得到的非终结符压栈，对于语义值栈的操作也是如此，从语义值栈弹出k个语义值，并将执行语义动作c代码返回的语义值重新压栈。

如下图：

终结符携带的语义值是无意义的占位符。

语义动作的解释器

上面的程序设计语言的例子中，并没有语义动作能够影响全局的副作用，所以右部符号的求值顺序并不能影响最终的结果。

但是我们可以知道，LR分析是自底向上，从左至右的遍历语法分析树，即后序遍历的方式来执行归约和语义动作。利用这一特性，我们可以编写出带有全局副作用的语义动作，并且可以明确了解副作用的发生顺序。

下面的例子是绪论中直线式程序设计的解释器。通过使用一个符号表的全局变量：

%{
typedef struct table *Table_;
Table_ {string id; int value; Table_ tail};
Table_ Table(string id,int value, struct table *tail);
Table_ table=NULL;
int lookup(Table_ table, string id){
  assert(table!=NULL);
  if(id==table.id) return table.value;
  else return lookup(table.tail,id);
}
void update(Table_ *tabptr,string id, int value){
  *tabptr = Table(id ,value, *tabptr);
}
%}
%union {int num;string id;}

%token <num> INT;
%token <id> Id
%token ASSIGN PRINT LPAREN RPAREN
%type <num> exp
%right SEMICOLON
%left PLUS MINUS
%left TIMES DIV
%start prog
%%
prog: stm

stm: stm SEMICOLON stm
stm: ID ASSIGN exp            {update(&table,ID,$3);}
stm: PRINT LPAREN exps RPAREN {printf("\n");}

exps: exp                     {printf("%d",$1);}
exps: exps COMMA exp          {printf("%d", $3);}

exp: INT                      {$$=$1;}
exp: ID                       {$$=lookup(table,$1);}
exp: exp PLUS exp             {$$=$1+$3;}
exp: exp MINUS exp            {$$=$1-$3;}
exp: exp TIMES exp            {$$=$1*$3;}
exp: exp DIV exp              {$$=$1/$3;}
exp: stm COMMA exp            {$$=$3;}
exp: LPAREN exp RPAREN        {$$=$2;}

抽象语法分析树

使用上述的方法实现一个编译器的语法分析器完全可行，但是为了方便维护，建议将语法分析和语义动作（类型检查和翻译成机器代码）分开处理。所以我们使用语法分析器生成语法分析树，编译器在较后的阶段对其进行遍历。这样的一颗语法分析树称为具体分析树（concrete parse tree），表示源语言的具体语法（concrete syntax）。

语法树的结构对文法的依赖程度很高，在消除二义性等过程中引入的新产生式，都因该限制在语法分析阶段。

抽象语法abstract syntax 建立了一个接口，这样语义分析阶段就不受文法二义性的困扰，因为我们提经有了一个语法树

直线式程序设计语言的抽象语法构造器

%{
#include "absyn.h"
%}

%union {int num; string id; A_stm stm; A_exp exp;A_expList expList;}

%token <num> INT
%token <id> ID
%token ASSIGN PRINT LPAREN RPAREN
%type <stm> stm prog
%type <exp> exp
%type <expList> exps
%left SEMICOLON
%left PLUS MINUS
%left TIMES DIV
%start prog
%%
prog: stm {$$=$1;}

stm : stm SEMICOLON stm {$$=A_CompoundStm($1,$3);}
stm : ID ASSIGN exp {$$=A_AssignStm($1,$3);}
stm : PRINT LPAREN exps RPAREN  {$$=A_PrintStm($3);}

exps: exp {$$=A_ExpList($1,NULL);}
exps: exp COMMA exps {$$=A_ExpList($1,$3);}

exp : INT {$$=A_NumExp($1);}
exp : ID {$$=A_IdExp($1);}
exp : exp PLUS exp {$$=A_OpExp($1,A_plus,$3);}
exp : exp MINUS exp {$$=A_OpExp($1,A_minus,$3);}
exp : exp TIMES exp {$$=A_OpExp($1,A_times,$3);}
exp : exp DIV exp {$$=A_OpExp($1,A_div,$3);}
exp : stm COMMA exp {$$=A_EsepExp($1,$3);}
exp : LPAREN exp RPAREN {$$=$2;}

位置

在一个只有一次pass的编译器中，词法分析，语法分析和语义分析，都是同时进行的。词法分析器会保存有一个表示当前位置的全局变量。

但是在使用抽象语法树的编译器中，在语义分析开始的时候，词法分析就已经到达文件尾，所以应当记住抽象语法树的每个节点在源文件中的位置，以防这个节点发生语义错误。

所以抽象语法结构上都带有pos域，pos域指明了导出抽象语法树的字符在源程序中对应的位置。Bison语法分析器可以做到这一点

Tiger的抽象语法

Tiger的抽象语法:

/*
 * absyn.h - Abstract Syntax Header (Chapter 4)
 *
 * All types and functions declared in this header file begin with "A_"
 * Linked list types end with "..list"
 */

/* Type Definitions */

typedef int A_pos;

typedef struct A_var_ *A_var;
typedef struct A_exp_ *A_exp;
typedef struct A_dec_ *A_dec;
typedef struct A_ty_ *A_ty;

typedef struct A_decList_ *A_decList;
typedef struct A_expList_ *A_expList;
typedef struct A_field_ *A_field;
typedef struct A_fieldList_ *A_fieldList;
typedef struct A_fundec_ *A_fundec;
typedef struct A_fundecList_ *A_fundecList;
typedef struct A_namety_ *A_namety;
typedef struct A_nametyList_ *A_nametyList;
typedef struct A_efield_ *A_efield;
typedef struct A_efieldList_ *A_efieldList;

typedef enum {A_plusOp, A_minusOp, A_timesOp, A_divideOp,
         A_eqOp, A_neqOp, A_ltOp, A_leOp, A_gtOp, A_geOp} A_oper;

struct A_var_
       {enum {A_simpleVar, A_fieldVar, A_subscriptVar} kind;
        A_pos pos;
    union {S_symbol simple;
           struct {A_var var;
               S_symbol sym;} field;
           struct {A_var var;
               A_exp exp;} subscript;
         } u;
      };

struct A_exp_
      {enum {A_varExp, A_nilExp, A_intExp, A_stringExp, A_callExp,
           A_opExp, A_recordExp, A_seqExp, A_assignExp, A_ifExp,
           A_whileExp, A_forExp, A_breakExp, A_letExp, A_arrayExp} kind;
       A_pos pos;
       union {A_var var;
          /* nil; - needs only the pos */
          int intt;
          string stringg;
          struct {S_symbol func; A_expList args;} call;
          struct {A_oper oper; A_exp left; A_exp right;} op;
          struct {S_symbol typ; A_efieldList fields;} record;
          A_expList seq;
          struct {A_var var; A_exp exp;} assign;
          struct {A_exp test, then, elsee;} iff; /* elsee is optional */
          struct {A_exp test, body;} whilee;
          struct {S_symbol var; A_exp lo,hi,body; bool escape;} forr;
          /* breakk; - need only the pos */
          struct {A_decList decs; A_exp body;} let;
          struct {S_symbol typ; A_exp size, init;} array;
        } u;
     };

struct A_dec_
    {enum {A_functionDec, A_varDec, A_typeDec} kind;
     A_pos pos;
     union {A_fundecList function;
        /* escape may change after the initial declaration */
        struct {S_symbol var; S_symbol typ; A_exp init; bool escape;} var;
        A_nametyList type;
      } u;
   };

struct A_ty_ {enum {A_nameTy, A_recordTy, A_arrayTy} kind;
          A_pos pos;
          union {S_symbol name;
             A_fieldList record;
             S_symbol array;
           } u;
        };

/* Linked lists and nodes of lists */

struct A_field_ {S_symbol name, typ; A_pos pos; bool escape;};
struct A_fieldList_ {A_field head; A_fieldList tail;};
struct A_expList_ {A_exp head; A_expList tail;};
struct A_fundec_ {A_pos pos;
                 S_symbol name; A_fieldList params;
         S_symbol result; A_exp body;};

struct A_fundecList_ {A_fundec head; A_fundecList tail;};
struct A_decList_ {A_dec head; A_decList tail;};
struct A_namety_ {S_symbol name; A_ty ty;};
struct A_nametyList_ {A_namety head; A_nametyList tail;};
struct A_efield_ {S_symbol name; A_exp exp;};
struct A_efieldList_ {A_efield head; A_efieldList tail;};


/* Function Prototypes */
A_var A_SimpleVar(A_pos pos, S_symbol sym);
A_var A_FieldVar(A_pos pos, A_var var, S_symbol sym);
A_var A_SubscriptVar(A_pos pos, A_var var, A_exp exp);
A_exp A_VarExp(A_pos pos, A_var var);
A_exp A_NilExp(A_pos pos);
A_exp A_IntExp(A_pos pos, int i);
A_exp A_StringExp(A_pos pos, string s);
A_exp A_CallExp(A_pos pos, S_symbol func, A_expList args);
A_exp A_OpExp(A_pos pos, A_oper oper, A_exp left, A_exp right);
A_exp A_RecordExp(A_pos pos, S_symbol typ, A_efieldList fields);
A_exp A_SeqExp(A_pos pos, A_expList seq);
A_exp A_AssignExp(A_pos pos, A_var var, A_exp exp);
A_exp A_IfExp(A_pos pos, A_exp test, A_exp then, A_exp elsee);
A_exp A_WhileExp(A_pos pos, A_exp test, A_exp body);
A_exp A_ForExp(A_pos pos, S_symbol var, A_exp lo, A_exp hi, A_exp body);
A_exp A_BreakExp(A_pos pos);
A_exp A_LetExp(A_pos pos, A_decList decs, A_exp body);
A_exp A_ArrayExp(A_pos pos, S_symbol typ, A_exp size, A_exp init);
A_dec A_FunctionDec(A_pos pos, A_fundecList function);
A_dec A_VarDec(A_pos pos, S_symbol var, S_symbol typ, A_exp init);
A_dec A_TypeDec(A_pos pos, A_nametyList type);
A_ty A_NameTy(A_pos pos, S_symbol name);
A_ty A_RecordTy(A_pos pos, A_fieldList record);
A_ty A_ArrayTy(A_pos pos, S_symbol array);
A_field A_Field(A_pos pos, S_symbol name, S_symbol typ);
A_fieldList A_FieldList(A_field head, A_fieldList tail);
A_expList A_ExpList(A_exp head, A_expList tail);
A_fundec A_Fundec(A_pos pos, S_symbol name, A_fieldList params, S_symbol result,
          A_exp body);
A_fundecList A_FundecList(A_fundec head, A_fundecList tail);
A_decList A_DecList(A_dec head, A_decList tail);
A_namety A_Namety(S_symbol name, A_ty ty);
A_nametyList A_NametyList(A_namety head, A_nametyList tail);
A_efield A_Efield(S_symbol name, A_exp exp);
A_efieldList A_EfieldList(A_efield head, A_efieldList tail);

这里需要注意的几点是：

夹杂在其中的关于位置的表示是用源代码的字符计数来表示的。
Tiger语言将相邻的函数生命看成是（可能会）相互递归的。
没有关于表达式&和|的抽象语法，用if else来表示
词法分析器返回的ID单词携带string类型的值，而抽象语法要求标识符具有symbol值。
程序设计：抽象语法
这次的程序设计，是在上一章作业的基础上添加语义动作。

文件：

absyn.c //Tiger的抽象语法声明
lex.yy.c //替代的词法分析器，可以使用自己的
parse.c //驱动程序，分析Tiger程序
prabsyn.c //抽象语法树输出程序
symbol.c //字符串转化尾字符
table.c //函数声明表支持
tiger.grm //需要编写的grm文件
absyn.h
makefile
parse.h
prabsyn.h
symbol.h
table.h

通过前面我们知道添加语义动作有两种方式。一种是直接添加语义动作，另一种是通过抽象语法的方式来添加，这里vim一下tiger.grm文件我们可以发现作者的意思应该是通过抽象语法来完成这次的设计。这里就在第三章设计的基础上来完成语法抽象。

首先将第四章内缺省的一些文件补全,并将第三章内的tiger.grm复制来

~/chap3$ cp -f parsetest.c util.h util.c tiger.grm ~/chap4

然后为其增加语义动作

%{
#include <stdio.h>
#include "util.h"
#include "errormsg.h"
#include "symbol.h"
#include "absyn.h"

int yylex(void); /* function prototype */

A_exp absyn_root;

void yyerror(char *s)
{
 EM_error(EM_tokPos, "%s", s);
}
%}


%union {
    int pos;
    int ival;
    string sval;
        A_exp exp;
        A_expList explist;
        A_var var;
        A_decList declist;
        A_dec  dec;
        A_efieldList efieldlist;
        A_efield  efield;
        A_namety namety;
        A_nametyList nametylist;
        A_fieldList fieldlist;
        A_field field;
        A_fundecList fundeclist;
        A_fundec fundec;
        A_ty ty;
    }

%token <sval> ID STRING
%token <ival> INT

%token
  COMMA COLON SEMICOLON LPAREN RPAREN LBRACK RBRACK
  LBRACE RBRACE DOT
  PLUS MINUS TIMES DIVIDE EQ NEQ LT LE GT GE
  AND OR ASSIGN
  ARRAY IF THEN ELSE WHILE FOR TO DO LET IN END OF
  BREAK NIL
  FUNCTION VAR TYPE

%type <exp> exp_em exp expseq
%type <explist> actuals  nonemptyactuals sequencing  sequencing_exps
%type <var>  lvalue one oneormore
%type <declist> decs decs_nonempty
%type <dec>  decs_nonempty_s vardec
%type <efieldlist> rec rec_nonempty
%type <efield> rec_one
%type <nametylist> tydec
%type <namety>  tydec_one
%type <fieldlist> tyfields tyfields_nonempty
%type <ty> ty
%type <fundeclist> fundec
%type <fundec> fundec_one

%left SEMICOLON
%nonassoc DO
%nonassoc LOWER
%nonassoc TYPE
%nonassoc FUNCTION
%nonassoc OF
%nonassoc LOW
%nonassoc  ELSE
%right ASSIGN
%left OR
%left AND
%nonassoc EQ NEQ LT LE GT GE
%left PLUS MINUS
%left TIMES DIVIDE
%nonassoc UMINUS
%left DOT LBRACK


%start program

%%

program
    :    exp_em  {absyn_root = $1;};

exp_em
    : exp  {$$=$1;}
    | {$$ = NULL;}
    ;

exp
    : INT      {$$ = A_IntExp(EM_tokPos,$1);}
    | STRING   {$$ = A_StringExp(EM_tokPos,$1);}
    | lvalue   {$$ = A_VarExp(EM_tokPos,$1);}
    | NIL      {$$ = A_NilExp(EM_tokPos);}
    | LPAREN sequencing RPAREN  {$$ = A_SeqExp(EM_tokPos,$2);}
    | exp PLUS exp  {$$ = A_OpExp(EM_tokPos,A_plusOp,$1,$3);}
    |exp MINUS exp  {$$ = A_OpExp(EM_tokPos,A_minusOp,$1,$3);}
    |exp TIMES exp   {$$ = A_OpExp(EM_tokPos,A_timesOp,$1,$3);}
    |exp DIVIDE exp  {$$ = A_OpExp(EM_tokPos,A_divideOp,$1,$3);}
    |exp EQ exp      {$$ = A_OpExp(EM_tokPos,A_eqOp,$1,$3);}
    |exp NEQ exp     {$$ = A_OpExp(EM_tokPos,A_neqOp,$1,$3);}
    |exp LT exp      {$$ = A_OpExp(EM_tokPos,A_ltOp,$1,$3);}
    |exp LE exp      {$$ = A_OpExp(EM_tokPos,A_leOp,$1,$3);}
    |exp GT exp      {$$ = A_OpExp(EM_tokPos,A_gtOp,$1,$3);}
    |exp GE exp      {$$ = A_OpExp(EM_tokPos,A_geOp,$1,$3);}
    |exp AND exp     {$$ =A_IfExp(EM_tokPos,$1,$3,A_IntExp(EM_tokPos,0));}
    |exp OR exp      {$$ =A_IfExp(EM_tokPos,$1,A_IntExp(EM_tokPos,1),$3);}
    |MINUS exp %prec UMINUS {$$=A_OpExp(EM_tokPos,A_minusOp,A_IntExp(EM_tokPos,0),$2);}
    |LPAREN exp_em RPAREN    {$$ = $2;}
    |ID LPAREN actuals RPAREN  {$$ =A_CallExp(EM_tokPos,S_Symbol($1),$3);}
    |lvalue ASSIGN exp         {$$ = A_AssignExp(EM_tokPos,$1,$3);}
    |IF exp THEN exp  %prec LOW  {$$ = A_IfExp(EM_tokPos,$2,$4,NULL);}
    |IF exp THEN exp ELSE exp   {$$ = A_IfExp(EM_tokPos,$2,$4,$6);}
    |WHILE exp DO exp            {$$ = A_WhileExp(EM_tokPos,$2,$4);}
    |FOR ID ASSIGN exp TO exp DO exp  {$$ = A_ForExp(EM_tokPos,S_Symbol($2),$4,$6,$8);}
    |BREAK                            {$$ = A_BreakExp(EM_tokPos);}
    |LET decs IN expseq END           {$$ = A_LetExp(EM_tokPos,$2,$4);}
    |ID LBRACE rec  RBRACE            {$$ = A_RecordExp(EM_tokPos,S_Symbol($1),$3);}
    |ID LBRACK exp RBRACK OF exp      {$$ = A_ArrayExp(EM_tokPos,S_Symbol($1),$3,$6);}
    ;

lvalue
    : ID    {$$ = A_SimpleVar(EM_tokPos,S_Symbol($1));}
    | oneormore  {$$ = $1;}
    ;

oneormore
    : one       {$$ = $1;}
    |oneormore DOT ID   {$$ = A_FieldVar(EM_tokPos,$1,S_Symbol($3));}
    |oneormore LBRACK exp RBRACK   {$$ = A_SubscriptVar(EM_tokPos,$1,$3);}
    ;

one : ID DOT ID  {$$ = A_FieldVar(EM_tokPos,A_SimpleVar(EM_tokPos,S_Symbol($1)),S_Symbol($3));}
    | ID LBRACK exp RBRACK  %prec LOWER  {$$ = A_SubscriptVar(EM_tokPos,A_SimpleVar(EM_tokPos,S_Symbol($1)),$3);}
    ;


rec :  rec_nonempty  {$$ =$1;}
    |  {$$ = NULL;}
    ;

rec_nonempty
    : rec_one {$$ = A_EfieldList($1,NULL);}
    | rec_one COMMA rec_nonempty  {$$ = A_EfieldList($1,$3);}
    ;

rec_one
    :  ID EQ exp   {$$ = A_Efield(S_Symbol($1),$3);}
    ;

sequencing
    : exp SEMICOLON sequencing_exps  {$$ = A_ExpList($1,$3);}
    ;

sequencing_exps
    :  exp          {$$ = A_ExpList($1,NULL);}
    | exp SEMICOLON sequencing_exps  {$$ = A_ExpList($1,$3);}
    ;


actuals
    : nonemptyactuals   {$$ = $1;}
    |  {$$ = NULL;}
    ;

nonemptyactuals
    : exp     {$$ = A_ExpList($1,NULL);}
    | exp COMMA nonemptyactuals {$$ = A_ExpList($1,$3);}
    ;

expseq
    : sequencing_exps  {$$ = A_SeqExp(EM_tokPos,$1);}
    | {$$ = NULL;}
    ;


decs
    :  decs_nonempty  {$$ = $1;}
    | {$$ = NULL;}
    ;

decs_nonempty
    : decs_nonempty_s  {$$ = A_DecList($1,NULL);}
    | decs_nonempty_s decs_nonempty   {$$ = A_DecList($1,$2);}
    ;

decs_nonempty_s
    : tydec  {$$ = A_TypeDec(EM_tokPos,$1);}
    |vardec  {$$ = $1;}
    |fundec  {$$ = A_FunctionDec(EM_tokPos,$1);}
    ;

tydec
    : tydec_one  %prec LOWER  {$$ = A_NametyList($1,NULL);}
    | tydec_one tydec      {$$ = A_NametyList($1,$2);}
    ;

tydec_one
    : TYPE ID EQ ty    {$$ = A_Namety(S_Symbol($2),$4);}
    ;

ty  :   ID    {$$ = A_NameTy(EM_tokPos,S_Symbol($1));}
    | LBRACE tyfields RBRACE  {$$ = A_RecordTy(EM_tokPos,$2);}
    | ARRAY OF ID {$$ = A_ArrayTy(EM_tokPos,S_Symbol($3));}
    ;

tyfields
    : tyfields_nonempty  {$$ = $1;}
    |   {$$ = NULL;}
    ;

tyfields_nonempty
    : ID COLON ID  {$$ =A_FieldList(A_Field(EM_tokPos,S_Symbol($1),S_Symbol($3)),NULL);}
    | ID COLON ID COMMA tyfields_nonempty  {$$ = A_FieldList(A_Field(EM_tokPos,S_Symbol($1),S_Symbol($3)),$5);}
    ;

vardec
    : VAR ID ASSIGN exp  {$$ = A_VarDec(EM_tokPos,S_Symbol($2),S_Symbol(""),$4);}
    | VAR ID COLON ID ASSIGN exp  {$$ = A_VarDec(EM_tokPos,S_Symbol($2),S_Symbol($4),$6);}
    ;

fundec
    :   fundec_one  %prec LOWER {$$ = A_FundecList($1,NULL);}
    |   fundec_one fundec    {$$ = A_FundecList($1,$2);}
    ;

fundec_one
    : FUNCTION ID LPAREN tyfields RPAREN EQ exp  {$$ = A_Fundec(EM_tokPos,S_Symbol($2),$4,S_Symbol(""),$7);}
    | FUNCTION ID LPAREN tyfields RPAREN COLON ID EQ exp  {$$ = A_Fundec(EM_tokPos,S_Symbol($2),$4,S_Symbol($7),$9);}
    ;

几种yacc错误情况的分析

no delacre type

首先检查是否在yacc文件的第二部分中声明了该类型，如果没有声明，补充；
而是检查yacc文件第三部分的$后的数字是否对应了正确的字段

Perhaps you are thinking that only symbols with values are counted. That’s not the case; $n refers to the value of the symbol n in the right-hand side, and is therefore an errorbif that symbol doesn’t have a value.

Note that yacc/bison can’t really tell whether or not a particular terminal has a value or not; all it knows is whether you have told it what the type of that value is.