Fatal Error: does not derive any sentence

Question

When I run parser.y on the following file I get the following errors:

myanalyzer.y: warning: 14 nonterminals useless in grammar
myanalyzer.y: warning: 36 rules useless in grammar
myanalyzer.y:7.8-18: fatal error: start symbol main_struct does not derive any sentence

I cannot understand what is wrong with the code:

    %{
    #include <stdio.h>
    #include <string.h>
    extern int line_num;
    extern char *yytext;
%}
%start main_struct

%left PLUS

%token PUBLIC   1
...         
%token CONSTANT_CHAR    45

%%
main_struct:variables_declaration
        class_declaration
        functions_declaration
        ;  

constant:   INT
        |BOOLEAN
        |CHAR
        |STRING
        |FLOAT
        |DOUBLE 
        ;

locality:   PUBLIC
        | PRIVATE
        ;

identifier1:    IDENTIFIER
        | identifier1 COMMA IDENTIFIER
        ;

class_body: /*empty*/
        |  locality variables_declaration locality functions_declaration identifier1
        |  locality variables_declaration identifier1
        |  locality functions_declaration identifier1
        |  identifier1
        ;


variables_declaration:  /*empty*/ 
            |  variables_declaration constant identifier1 SEMICOLON
                |  variables_declaration constant identifier1 COMMA
                ;

class_declaration:  /*empty*/ 
            | class_declaration CLASS identifier1 BEGIN class_body END
            ;

functions_declaration:  functions_declaration constant identifier1 LEFT_PARENTHESIS vars_in_func RIGHT_PARENTHESIS BEGIN function_body END
            | functions_declaration VOID identifier1 LEFT_PARENTHESIS vars_in_func RIGHT_PARENTHESIS BEGIN function_body END
            ;

vars_in_func:       /*empty*/ 
            | constant identifier1
            | vars_in_func COMMA constant identifier1
            ;

function_body:      /*empty*/ 
            | variables_declaration identifier1
            | identifier1
            ; 
%%

int main ()
{     
  if ( yyparse() == 0 && error==0){
     printf("Accepted\n");
   }
  else{
     printf("Rejected\n");
   }
}

I am now working first time with Bison so the code might not be good but I want to compile it so I can begin testing. But how can I fix this error?

Notice: I can simple do that:

main_struct:variables_declaration
            | class_declaration
            | functions_declaration
            ;

But this will be wrong because I want my program to have all 3 declarations.

Answer 1

functions_declaration has no non-recursive production, unlike variables_declaration and class_declaration which both have empty productions. Without a non-recursive production, it is impossible to derive a sentence from a non-terminal, since the derivation can never terminate.

Since no sentence can match functions_declaration, main_struct also cannot be matched, and that in turn renders all nonterminals useless.

There are two common patterns for writing repeating non-terminals, which correspond to the regular expression operators * (0 or more) and + (1 or more):

optional_repeating_element: /* EMPTY */
                          | optional_repeating_element element
                          ;

repeating_element         : element
                          | repeating_element element
                          ;

Note that these only differ in the base case. In both cases, you need to separately define a production for a single element. So in your case, you could use:

functions_declaration: function
                     | functions_declaration function
                     ;

function: constant identifier1 LEFT_PARENTHESIS vars_in_func RIGHT_PARENTHESIS
          BEGIN function_body END
        | VOID identifier1 LEFT_PARENTHESIS vars_in_func RIGHT_PARENTHESIS
          BEGIN function_body END
        ;

---

Three notes:

1) Don't manually number your tokens. Bison will do it for you, and the result is much more maintainable. Also, it is usually a lot more readable to use single-quoted characters for terminals which are single characters; these terminals don't need to be declared, and you can use a simple default flex rule to handle all of them (. {return *(unsigned char*)yytext;}.) So it is all around simpler, both to write and to read.

2) Your definition of vars_in_func will accept some sentences you probably don't want to accept. What you have is:

vars_in_func:       /*empty*/ 
            | constant identifier1
            | vars_in_func COMMA constant identifier1
            ;

Since vars_in_func can be empty (first production), the third production allows vars_in_func to start with a COMMA, so the following would be valid:

(, int foo)

To do this correctly, you need to separate the empty parameter-list case from the recursion.

3) Your use of identifier1 (which is quite a confusing name for a list of identifiers) is going to cause you problems. You allow function declarations to declare a list of names, but that is not distinguishable with finite lookahead from a variable declaration which declares a list of names. Consider the two sentences:

int variable1, variable2, variable3;

int function1, function2, function3() BEGIN END

When the parser finds the first ,, it cannot know whether what follows is a list of integer variables, or a list of functions with the same parameters and body. I'm guessing that you didn't really intend the second case to be possible, which means you shouldn't use identifier1 in functions_declaration (or class_declaration). Even in your parameter list non-terminal (vars_in_func), you have something odd, though parseable; vars_in_func is a comma-separated list of a type followed by a comma-separated list of names, so the following is legal:

void function(int a, b, int c, d)

Perhaps you intended that, but I'm not convinced.