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 "printlist.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	<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 record_ceclaration*/

%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		QUALIFIER

%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 token of 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		'(' '[' 
%left           '.'      /*add the '.' as left first*/

%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;
	print_list(global_declarations);

	/* 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 the record_declaration to the declaration options*/
;


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
    {
	List *var_list;
	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;
	var_list = $<list>$;
	print_list(var_list);
    }
;


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);
    }
;
    
record_declaration           /*creat a new record declaration*/
:
    RECORD
    {
	new_scope();
    }
    IDENTIFIER
    IS
    var_declarations
    END
{
	Declaration *decl = new_record_declaration($<token>3,$<list>5);
	$<list>$ = new_list();
	list_append($<list>$, decl);
	leave_scope();
	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
    {
	
	Declaration *scopeDecl;
	scopeDecl = lookup(global_scope,$<token>1->name);
#ifdef DEBUG
	printf("token->name = %s\n",$<token>1->name);
#endif
		if (scopeDecl == NULL)
		{	
			error($<token>1,"%s is an unknown type, can be an undefined type or recursive declaration\n",$<token>1->name);
		}
		else if (scopeDecl->subtype != record_decl) /* was record_type */
		{
			error($<token>1,"%s is an unknown type\n",$<token>1->name);
		}
		else
		{
			$<type>$=new_record_type(scopeDecl);
		}
	
	/* zoek de text van de identifier op in de globalscope
		(lookupt)
		dan heb je als het goed is een record Declaration
		daarin zit een Type, die het resultaat van deze rule moet zijn */
    }
;


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
    '.'
    IDENTIFIER
    {
	$<expr>$ = new_expression(expr_dot, $<token>2, $<expr>1, new_expression(expr_ident,$<token>3,NULL,NULL));
    }
|
    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      /* 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);
}