how set up different typing depending of declaration in flex/yacc

user_17598488 0
Viewed 51

i'm writting a flex/yacc code in order to recognize a language. In this language, functions can be declarate with type int, void or void* but arguments and variables can only have type int or void*.

for exemple :

int foo(); is ok

void foo(); is ok

void *foo(); is ok

int i; is ok

void *i; is ok

void i; is NOT ok

in my .y file i only succeeded to recognize type int and void* so it's ok for arguments and variables but for functions void is missing

my .y file :

%{

#include <stdio.h>
#include <stdlib.h>
int yylex();
void yyerror(const char *s);

%}

%token IDENTIFIER CONSTANT 
%token LE_OP GE_OP EQ_OP NE_OP
%token EXTERN
%token INT VOID
%token IF RETURN GOTO

%start program
%%

primary_expression
        : IDENTIFIER
        | CONSTANT
        ;

postfix_expression
        : primary_expression
        | postfix_expression '(' ')'
        | postfix_expression '(' argument_expression_list ')'
        ;

argument_expression_list
        : primary_expression
        | argument_expression_list ',' primary_expression
        ;

unary_expression
        : postfix_expression
        | unary_operator primary_expression
        ;

unary_operator
        : '&'
        | '*'
        | '-'
        ;

multiplicative_expression
        : unary_expression
        | primary_expression '*' primary_expression
        | primary_expression '/' primary_expression
        ;

additive_expression
        : multiplicative_expression
        | primary_expression '+' primary_expression
        | primary_expression '-' primary_expression
        ;

relational_expression
        : additive_expression
        | primary_expression '<' primary_expression
        | primary_expression '>' primary_expression
        | primary_expression LE_OP primary_expression
        | primary_expression GE_OP primary_expression
        ;

equality_expression
        : relational_expression
        | primary_expression EQ_OP primary_expression
        | primary_expression NE_OP primary_expression
        ;

expression
        : equality_expression
        | unary_operator primary_expression '=' primary_expression
        | primary_expression '=' additive_expression
        ;

declaration
        : declaration_specifiers direct_declarator ';'
        ;

declaration_specifiers
        : EXTERN type_specifier
        | type_specifier
        ;

type_specifier
        : VOID '*'
        | INT
        ;

direct_declarator
        : IDENTIFIER
        | direct_declarator '(' parameter_list ')'
        | direct_declarator '(' ')'
        ;

parameter_list
        : parameter_declaration
        | parameter_list ',' parameter_declaration
        ;

parameter_declaration
        : declaration_specifiers direct_declarator
        ;

statement
        : compound_statement
        | labeled_statement
        | expression_statement
        | selection_statement
        | jump_statement 
        ;

compound_statement
        : '{' '}'
        | '{' statement_list '}'
        | '{' declaration_list '}'
        | '{' declaration_list statement_list '}'
        ;

declaration_list
        : declaration
        | declaration_list declaration
        ;

statement_list
        : statement
        | statement_list statement
        ;

labeled_statement
        : IDENTIFIER ':' statement
        ;

expression_statement
        : ';'
        | expression ';'
        ;

selection_statement
        : IF '(' equality_expression ')' GOTO IDENTIFIER ';'
        ;
jump_statement
        : RETURN ';'
        | RETURN expression ';'
        | GOTO IDENTIFIER ';'
        ;

program
        : external_declaration
        | program external_declaration
        ;

external_declaration
        : function_definition
        | declaration
        ;

function_definition
        : declaration_specifiers direct_declarator compound_statement
        ;

%%

void yyerror(const char *s ) {
        fprintf( stderr, "%s\n", s );
        printf("\n");
        exit(1);
}

int main() {
        printf("\n");
        yyparse();
        printf("\n");
        return 0;
}

I tried to write 2 different rules, one for declaration of functions and one for declaration of arguments/variables but i got reduce/reduce conflicts

yacc flex-lexer compiler-construction parsing
1 Answers

There's no good way around that conflict, assuming you want something like C syntax. The parser cannot tell whether void is a valid type until it sees the ( which starts the parameter list, but any reasonable grammar will want to have resolved the type specifier before parsing the identifier being declared.

There are various bad ways to modify the grammar which will sort of work until you try to implement more features. But they won't work well, because the resulting workarounds are very difficult to read, and even harder to modify.

In a way, this shouldn't be a surprise. "A function can be void but not a variable" is a statement about the semantics of a declaration, not the syntax. For the C parser, void v; is no different from declaring v to have an incomplete type, which is pretty clearly a semantic question.

And, if you really emulate C, you'd have to deal with things like:

void f(int x), v;

where the function declaration is fine, but the variable declaration is not.

If you think about it as semantics, then it is reasonable that it be checked post-parse, along with type-agreement and other semantic validation. And that's the usual approach.

user_15662210
Related