readme.txt

针对“虎书”中的tiger语言写的语法分析器 根据书中对tiger语言的描述写了72条文法

BY:C.J.H

======程序编译、运行环境==================================================================

VC 6.0

======源程序说明===========================================================================

●文法如下所示：
（使用命令"yacc -v tiger.grm"得到文件y.output）

   0  $accept : program $end

   1  program : ID
   2          | STRING
   3          | INT
   4          | NIL
   5          | lvalue
   6          | binary_operation_expr
   7          | assign_expr
   8          | function_expr
   9          | paren_expr
  10          | record_expr
  11          | ID LBRACK program RBRACK OF program
  12          | case_expr
  13          | WHILE program DO program
  14          | FOR ID ASSIGN program TO program DO program
  15          | BREAK
  16          | scope_expr
  17          | LPAREN error RPAREN
  18          | error SEMICOLON program

  19  lvalue  : ID DOT ID
  20          | ID LBRACK program RBRACK
  21          | lvalue DOT ID
  22          | lvalue LBRACK program RBRACK

  23  binary_operation_expr : program OR program
  24                        | program AND program
  25                        | program EQ program
  26                        | program LT program
  27                        | program LE program
  28                        | program GT program
  29                        | program GE program
  30                        | program NEQ program
  31                        | program PLUS program
  32                        | program MINUS program
  33                        | program TIMES program
  34                        | program DIVIDE program
  35                        | MINUS program

  36  assign_expr : lvalue ASSIGN program
  37              | ID ASSIGN program

  38  function_expr : ID LPAREN RPAREN
  39                | ID LPAREN expr_list RPAREN

  40  expr_list : program
  41            | program COMMA expr_list

  42  paren_expr : LPAREN RPAREN
  43             | LPAREN expr_seq RPAREN

  44  expr_seq : program
  45           | program SEMICOLON expr_seq

  46  record_expr : ID LBRACE RBRACE
  47              | ID LBRACE fieldexpr_list RBRACE

  48  fieldexpr_list : ID EQ program
  49                 | ID EQ program COMMA fieldexpr_list

  50  case_expr : IF program THEN program
  51            | IF program THEN program ELSE program

  52  scope_expr : LET dec_list IN END
  53             | LET dec_list IN expr_seq END

  54  dec_list : dec
  55           | dec dec_list

  56  dec : type_dec
  57      | variable_dec
  58      | function_dec

  59  type_dec : TYPE ID EQ type

  60  type : ID
  61       | LBRACE RBRACE
  62       | LBRACE field_list RBRACE
  63       | ARRAY OF ID

  64  field_list : ID COLON ID
  65             | ID COLON ID COMMA field_list

  66  variable_dec : VAR ID ASSIGN program
  67               | VAR ID COLON ID ASSIGN program

  68  function_dec : FUNCTION ID LPAREN RPAREN EQ program
  69               | FUNCTION ID LPAREN RPAREN COLON ID EQ program
  70               | FUNCTION ID LPAREN field_list RPAREN EQ program
  71               | FUNCTION ID LPAREN field_list RPAREN COLON ID EQ program

●冲突的处理：
我们采用冗余的文法和优先级命令（%left、%nonassoc、%right）处理冲突：
其中ELSE OR AND PLUS MINUS TIMES DIVIDE UMINUS LBRACK 为左结合且优先级从低到高排列，EQ,LT,LE,GT,GE,NEQ 为无结合且彼此优先级相同，比AND高，比PLUS和MINUS低。
具体如下：
“
%left ELSE;
%left OR;
%left AND;
%nonassoc EQ,LT,LE,GT,GE,NEQ;
%left PLUS,MINUS;
%left TIMES,DIVIDE;
%left UMINUS;
%left LBRACK;
”
●无害的冲突：
此文法经yacc分析产生了85个移进－归约冲突（shift/reduce conflicts），无归约－归约冲突（reduce/reduce conflicts）。
查看y.output文件可以发现如下提示：
“
State 59 contains 12 shift/reduce conflicts.
State 68 contains 12 shift/reduce conflicts.
State 94 contains 12 shift/reduce conflicts.
State 101 contains 13 shift/reduce conflicts.
State 102 contains 12 shift/reduce conflicts.
State 126 contains 12 shift/reduce conflicts.
State 148 contains 12 shift/reduce conflicts.


46 terminals, 20 nonterminals
72 grammar rules, 157 states
”
在各个状态验证发现都是与以下显示的状态59的冲突类似：
59: shift/reduce conflict (shift 44, reduce 18) on PLUS
59: shift/reduce conflict (shift 45, reduce 18) on MINUS
59: shift/reduce conflict (shift 46, reduce 18) on TIMES
59: shift/reduce conflict (shift 47, reduce 18) on DIVIDE
59: shift/reduce conflict (shift 48, reduce 18) on EQ
59: shift/reduce conflict (shift 49, reduce 18) on NEQ
59: shift/reduce conflict (shift 50, reduce 18) on LT
59: shift/reduce conflict (shift 51, reduce 18) on LE
59: shift/reduce conflict (shift 52, reduce 18) on GT
59: shift/reduce conflict (shift 53, reduce 18) on GE
59: shift/reduce conflict (shift 54, reduce 18) on AND
59: shift/reduce conflict (shift 55, reduce 18) on OR

因为以上冲突的相关运算符都经过了优先级冲突的处理，所以这些冲突都是无害的。

●error恢复
本文法增加了两个error产生式：
program－>(error)
program－>error;program
为了说明该分析器能够从相应的语法错误中恢复，我们在测试文件“test1.tig”中添加了如下的错误文法：
break;a:=b
由于break位于while或for之外是非法的，上面的文法会发生语法错误。
但是由于增加了产生式“program－>error;program”，所以本分析器能够提示语法错误并从语法错误中恢复，继续分析后面的语法。