grammar.y

一个编译器修改的例子

%{
#include "declaration.h"
#include "error.h"
#include "lex.h"
#include "list.h"
#include "expression.h"
#include "scope.h"
#include "statement.h"
#include "token.h"
#include "type.h"

#include <ctype.h>
#include <stdlib.h>

extern void yyerror();
extern int  yylex();

%}

%union
{
    struct declaration	*decl;
    struct expression	*expr;
    struct list		*list;
    struct scope	*scope;
    struct statement	*stat;
    struct type		*type;
    struct token	*token;
}

%type	<decl>	function_header
%type	<decl>	name_and_argument_list
%type	<decl>	procedure_header
%type	<decl>	subprogram_header
%type	<decl>	identifier1 /*add : temp declaration for record declaration */

%type	<expr>	expression
%type	<expr>	opt_by_expression

%type	<list>	actual_parameters
%type	<list>	declaration
%type	<list>	declarations
%type	<list>	formal_parameter
%type	<list>	formal_parameters
%type	<list>	formal_parameter_list
%type	<list>	identifier_list
%type	<list>	opt_actual_parameters
%type	<list>	opt_statements
%type	<list>	subprogram_declaration
%type	<list>	var_declaration
%type	<list>	var_declaration_list
%type	<list>	var_declarations
%type	<list>	record_declaration /*add : adding a new syntax for record type */

%type	<stat>	assignment_statement
%type	<stat>	compound_statement
%type	<stat>	delete_statement
%type	<stat>	expression_statement
%type	<stat>	for_statement
%type	<stat>	if_statement
%type	<stat>	repeat_statement
%type	<stat>	return_statement
%type	<stat>	statement
%type	<stat>	while_statement


%type	<type>	type
%type	<type>	array_type

%token		ASSIGNMENT

%token		ARRAY
%token		_BEGIN /* underscore prevents conflict with flex BEGIN macro */
%token		BOOL
%token		BY
%token		CHAR
%token		DELETE
%token		DO
%token		ELSE
%token		END
%token	<token>	FALSE
%token		FOR
%token		FUNCTION
%token		IF
%token		INT
%token		IS
%token	<token>	NEW
%token	<token>	__NULL      /* NULL and _NULL are already occupied by C libs */
%token		OF
%token		PROCEDURE
%token		REAL
%token		REPEAT
%token	<token>	RETURN
%token		STRING
%token		THEN
%token		TO
%token	<token>	TRUE
%token		UNTIL
%token		VAR
%token		WHILE
%token          RECORD   /*add : declare a new token RECORD */

%token	<token>	CHAR_CONSTANT
%token	<token>	IDENTIFIER
%token	<token>	INTEGER_CONSTANT
%token	<token>	REAL_CONSTANT
%token	<token>	STRING_CONSTANT
%token	<token>	'[' 

%left	<token>	OR
%left	<token>	AND
%left	<token>	'=' NOT_EQUAL
%nonassoc<token>'<' SMALLER_EQUAL '>' GREATER_EQUAL
%left	<token>	'+' '-'
%left	<token>	'*' '/'
%right	<token>	NOT SIZE UNARY_MINUS UNARY_PLUS
%left		'(' '[' '.'  /* add : The precedence level of '.' is the same as '[' and '(' */

%start		program

%expect 1	/* Expect 1 shift-reduce conflict for the dangling else */

%%


program
:
    {
        /* Initialise the global scope before doing anything else. */
	global_scope = new_scope();
    }
    declarations
    {
        /* The AST is just a list of declarations, stored in
	 * global_declarations. The actual list is created a few rules down,
	 * in name_and_argument_list.
	 */
	global_declarations = $<list>2;

	/* Finally, leave the global scope when all is done.
	 */
	leave_scope();
    }
;


declarations
:
    declaration
|
    declarations
    declaration
    {
	$<list>$ = $<list>1;
	list_merge($<list>$, $<list>2);
    }
;


declaration
:
    subprogram_declaration
|
    var_declarations
|
    record_declaration   /*add*/
;

/*add : syntax of record declaration */
record_declaration
:
   RECORD
   identifier1
   IS
   var_declaration_list
   END
   {
     leave_scope();
     RECORD_DECL($<decl>2).formal_var= $<list>4;
     $<list>$= new_list();
     list_append($<list>$,$<decl>2);
   }
;
identifier1
:
   IDENTIFIER
   {
    $<decl>$=new_record_declaration($<token>1);
    if(lookup_in_this_scope(current_scope,$<token>1->name)==0) /*check if record has been declared*/
       declare($<token>1->name, $<decl>$);
    else
       error($<token>1,"%s has been declared", $<token>1->name);
    RECORD_DECL($<decl>$).formal_var_scope = new_scope(); /* add : create new_scope() for members of record */
   }
;
subprogram_declaration
:
    subprogram_header
    ';'
    {
	leave_scope();	/* scope introduced by arguments in
			 * name_and_argument_list (through subprogram_header)
			 */
	$<list>$ = new_list();
	list_append($<list>$, $<decl>1);
    }
|
    subprogram_header
    IS
    statement
    {
	leave_scope();	/* scope introduced by arguments in
			 * name_and_argument_list (through subprogram_header)
			 */
	SUBPROG_DECL($<decl>1).body = $<stat>3;
	SUBPROG_DECL($<decl>1).has_been_defined = true;
	$<list>$ = new_list();
	list_append($<list>$, $<decl>1);
    }
;


subprogram_header
:
    function_header
|
    procedure_header
;


function_header
:
    FUNCTION
    name_and_argument_list
    ':'
    type
    {
	$<decl>$			   = $<decl>2;
	SUBPROG_DECL($<decl>$).return_type = $<type>4;
    }
;


procedure_header
:
    PROCEDURE
    name_and_argument_list
    {
	$<decl>$ = $<decl>2;
	SUBPROG_DECL($<decl>$).return_type = new_simple_type(void_type);
    }
;


name_and_argument_list
:
    IDENTIFIER
    {
	$<decl>$ = new_subprogram_declaration($<token>1);

	if ((SUBPROG_DECL($<decl>$).redeclaration = lookup_in_this_scope(
		current_scope, $<token>1->name)) == 0)
	    declare($<token>1->name, $<decl>$);

	SUBPROG_DECL($<decl>$).formal_args_scope = new_scope();
    }
    formal_parameters
    {
	$<decl>$			   = $<decl>2;
	SUBPROG_DECL($<decl>$).formal_args = $<list>3;
	SUBPROG_DECL($<decl>$).type	   = new_subprog_type($<decl>$);
    }
;


formal_parameters
:
    '('
    ')'
    {
	$<list>$ = new_list();
    }
|
    '('
    formal_parameter_list
    ')'
    {
	$<list>$ = $<list>2;
    }
;


formal_parameter_list
:
    formal_parameter
|
    formal_parameter_list
    ';'
    formal_parameter
    {
	$<list>$ = $<list>1;
	list_merge($<list>$, $<list>3);
    }
;


formal_parameter
:
    var_declaration
|
    VAR
    var_declaration
    {
	Declaration *first_var_decl = list_index($<list>2, 0);

	VAR_DECL(first_var_decl).type->call_by_ref = true; /* ??????*/
	$<list>$ = $<list>2;
    }
;


var_declarations
:
    VAR
    var_declaration_list
    {
	$<list>$ = $<list>2;
    }
;


var_declaration_list
:
    var_declaration
    ';'
|
    var_declaration_list
    var_declaration
    ';'
    {
	$<list>$ = $<list>1;
	list_merge($<list>$, $<list>2);
    }
;


var_declaration
:
    identifier_list
    ':'
    type
    {
	unsigned i;

	for (i = 0; i < list_size($<list>1); i ++)
	    VAR_DECL((Declaration *) list_index($<list>1, i)).type = $<type>3;

	inc_ref_count($<type>3, i - 1);
	$<list>$ = $<list>1;
    }
;


identifier_list
:
    IDENTIFIER
    {
	Declaration *decl = new_var_declaration($<token>1);

	$<list>$ = new_list();
	list_append($<list>$, decl);
	declare($<token>1->name, decl);
    }
|
    identifier_list
    ','
    IDENTIFIER
    {
	Declaration *decl = new_var_declaration($<token>3);

	$<list>$ = $<list>1;
	list_append($<list>$, decl);
	declare($<token>3->name, decl);
    }
;


type
:
    BOOL
    {
	$<type>$ = new_simple_type(bool_type);
    }
|
    CHAR
    {
	$<type>$ = new_simple_type(char_type);
    }
|
    INT
    {
	$<type>$ = new_simple_type(int_type);
    }
|
    REAL
    {
	$<type>$ = new_simple_type(real_type);
    }
|
    STRING
    {
	$<type>$ = new_array_type(new_simple_type(char_type));
    }
|
    array_type
|
    IDENTIFIER /* add : new type of a record declaration and check if this record has been declared */
    {
      if(lookup_in_this_scope(global_scope,$<token>1->name)==0)
        {
         error($<token>1, "%s hasn't been declared ",$<token>1->name);
        }
      else
         $<type>$= new_record_type(lookup_in_this_scope(global_scope,$<token>1->name));
    } 
;


array_type
:
    ARRAY
    OF
    type
    {
	$<type>$ = new_array_type($<type>3);
    }
;


statement
:
    assignment_statement
|
    compound_statement
|
    delete_statement
|
    expression_statement
|
    for_statement
|
    if_statement
|
    repeat_statement
|
    return_statement
|
    while_statement
;


assignment_statement
:
    expression
    ASSIGNMENT
    expression
    ';'
    {
	$<stat>$ = new_assignment_statement($<expr>1, $<expr>3);
    }
;


compound_statement
:
    {
	$<scope>$ = new_scope();
    }
    var_declarations
    _BEGIN
    opt_statements
    END
    {
	$<stat>$ = new_compound_statement($<list>2, $<list>4, $<scope>1);
	leave_scope();
    }
|
    _BEGIN
    opt_statements
    END
    {
	$<stat>$ = new_compound_statement(new_list(), $<list>2, 0);
    }
;


opt_statements
:
    /* EPSILON */
    {
	$<list>$ = new_list();
    }
|
    opt_statements
    statement
    {
	$<list>$ = $<list>1;
	list_append($<list>$, $<stat>2);
    }
;


delete_statement
:
    DELETE
    expression
    ';'
    {
	$<stat>$ = new_delete_statement($<expr>2);
    }
;


expression_statement
:
    expression
    ';'
    {
	$<stat>$ = new_expression_statement($<expr>1);
    }
;


for_statement
:
    FOR
    expression
    ASSIGNMENT
    expression
    TO
    expression
    opt_by_expression
    DO
    statement
    {
	$<stat>$ = new_for_statement($<expr>2, $<expr>4, $<expr>6, $<expr>7,
				     $<stat>9);
    }
;


opt_by_expression
:
    /* EPSILON */
    {
	$<expr>$ = 0;
    }
|
    BY
    expression
    {
	$<expr>$ = $<expr>2;
    }
;


if_statement
:
    IF
    expression
    THEN
    statement
    {
	$<stat>$ = new_if_statement($<expr>2, $<stat>4, 0);
    }
|
    IF
    expression
    THEN
    statement
    ELSE
    statement
    {
	$<stat>$ = new_if_statement($<expr>2, $<stat>4, $<stat>6);
    }
;
    

repeat_statement
:
    REPEAT
    statement
    UNTIL
    expression
    ';'
    {
	$<stat>$ = new_repeat_statement($<stat>2, $<expr>4);
    }
;


return_statement
:
    RETURN
    ';'
    {
	$<stat>$ = new_return_statement(0, $<token>1);
    }
|
    RETURN
    expression
    ';'
    {
	$<stat>$ = new_return_statement($<expr>2, $<token>1);
    }
;


while_statement
:
    WHILE
    expression
    DO
    statement
    {
	$<stat>$ = new_while_statement($<expr>2, $<stat>4);
    }
;


expression
:
    NOT
    expression
    {
	$<expr>$ = new_expression(expr_not, $<token>1, $<expr>2, 0);
    }
|
    SIZE
    OF
    expression
    {
	$<expr>$ = new_expression(expr_size, $<token>1, $<expr>3, 0);
    }
    %prec SIZE
|
    '-'
    expression
    {
	$<expr>$ = new_expression(expr_unary_min, $<token>1, $<expr>2, 0);
    }
    %prec UNARY_MINUS
|
    '+'
    expression
    {
	$<expr>$ = new_expression(expr_unary_plus, $<token>1, $<expr>2, 0);
    }
    %prec UNARY_PLUS
|
    expression
    OR
    expression
    {
	$<expr>$ = new_expression(expr_or, $<token>2, $<expr>1, $<expr>3);
    }
|
    expression
    AND
    expression
    {
	$<expr>$ = new_expression(expr_and, $<token>2, $<expr>1, $<expr>3);
    }
|
    expression
    '='
    expression
    {
	$<expr>$ = new_expression(expr_eq, $<token>2, $<expr>1, $<expr>3);
    }
|
    expression
    NOT_EQUAL
    expression
    {
	$<expr>$ = new_expression(expr_ne, $<token>2, $<expr>1, $<expr>3);
    }
|
    expression
    '<'
    expression
    {
	$<expr>$ = new_expression(expr_st, $<token>2, $<expr>1, $<expr>3);
    }
|
    expression
    SMALLER_EQUAL
    expression
    {
	$<expr>$ = new_expression(expr_se, $<token>2, $<expr>1, $<expr>3);
    }
|
    expression
    '>'
    expression
    {
	$<expr>$ = new_expression(expr_gt, $<token>2, $<expr>1, $<expr>3);
    }
|
    expression
    GREATER_EQUAL
    expression
    {
	$<expr>$ = new_expression(expr_ge, $<token>2, $<expr>1, $<expr>3);
    }
|
    expression
    '+'
    expression
    {
	$<expr>$ = new_expression(expr_plus, $<token>2, $<expr>1, $<expr>3);
    }
|
    expression
    '-'
    expression
    {
	$<expr>$ = new_expression(expr_min, $<token>2, $<expr>1, $<expr>3);
    }
|
    expression
    '*'
    expression
    {
	$<expr>$ = new_expression(expr_mul, $<token>2, $<expr>1, $<expr>3);
    }
|
    expression
    '/'
    expression
    {
	$<expr>$ = new_expression(expr_div, $<token>2, $<expr>1, $<expr>3);
    }
|
    expression
    '['
    expression
    ']'
    {
	$<expr>$ = new_expression(expr_index, $<token>2, $<expr>1, $<expr>3);
    }
|
    '('
    expression
    ')'
    {
	$<expr>$ = $<expr>2;
    }
|
    expression
    '('
    {
	$<token>$ = new_token();
    }
    opt_actual_parameters
    ')'
    {
	$<expr>$ = new_expression(expr_func_call, $<token>3, $<expr>1, 0);
	EXPR_FUNC_CALL($<expr>$).actual_args = $<list>4;
    }
|
    IDENTIFIER
    {
	$<expr>$ = new_expression(expr_ident, $<token>1, 0, 0);
	EXPR_IDENT($<expr>$).scope	   = current_scope;
    }
|
    TRUE
    {
	$<expr>$ = new_expression(expr_bool_const, $<token>1, 0, 0);
    }
|
    FALSE
    {
	$<expr>$ = new_expression(expr_bool_const, $<token>1, 0, 0);
    }
|
    CHAR_CONSTANT
    {
	$<expr>$ = new_expression(expr_char_const, $<token>1, 0, 0);
    }
|
    INTEGER_CONSTANT
    {
	$<expr>$ = new_expression(expr_int_const, $<token>1, 0, 0);
    }
|
    REAL_CONSTANT
    {
	$<expr>$ = new_expression(expr_real_const, $<token>1, 0, 0);
    }
|
    STRING_CONSTANT
    {
	$<expr>$ = new_expression(expr_string_const, $<token>1, 0, 0);
    }
|
    __NULL
    {
	$<expr>$ = new_expression(expr_null, $<token>1, 0, 0);
    }
|
    NEW
    ARRAY
    '['
    expression
    ']'
    OF
    type
    {
	$<expr>$       = new_expression(expr_new, $<token>1, $<expr>4, 0);
	$<expr>$->type = new_array_type($<type>7);
	delete_token($<token>3);
    }
|
    expression'.'IDENTIFIER /* add : syntax for an expression of record */
    {
     $<expr>$=new_expression(expr_record,$<token>3,$<expr>1,0);
    }
;


opt_actual_parameters
:
    /* EPSILON */
    {
	$<list>$ = new_list();
    }
|
    actual_parameters
;


actual_parameters
:
    expression
    {
	$<list>$ = new_list();
	list_append($<list>$, $<expr>1);
    }
|
    actual_parameters
    ','
    expression
    {
	$<list>$ = $<list>1;
	list_append($<list>$, $<expr>3);
    }
;


%%

void yyerror(const char *message)
{
    if (isprint(*yytext))
	error(0, "%s near %s", message, yytext);
    else
	error(0, "%s", message);
}