error: start symbol prog does not derive any sentence on bison

Question

So, I'm trying to implement a grammar for a bison compiler and I have some problem when trying to make the file. It gives:

`calcgrammar.y:76.8-11: error: start symbol prog does not derive any sentence
   76 | %start prog
      |        ^~~~
make: *** [Makefile:4: calc] Error 1`

Here's my files:

calcgrammar.y file:

`%{
    #include <stdio.h>
#include <string.h>
#include <math.h>
#define YYDEBUG 1   // Not using --debug

int yywrap();
int yylex();
void yyerror(int *count, const char* str);
double result = 0;
extern FILE * yyin;
%}

%union {
    double value;
}

%token ADD 23
%token SUB 24
%token MUL 25
%token DIV 26
%token LBRAC 27
%token RBRAC 28
%token NEXT 29
%token <value> VAL 30
%token MOD 31
%token IF 32
%token AND 33
%token OR 34
%token VOID 35
%token INT 36
%token DOUBLE 37
%token MAIN 38
%token NOT 39
%token FLOAT 40
%token LBRACE 41
%token RBRACE 42
%token COMMA 44
%token EQUALS 45
%token SEMICOLON 46
%token COMP_EQ 47
%token COMP_NEQ 48
%token COMP_LT 49
%token COMP_LEQ 50
%token COMP_GT 51
%token COMP_GEQ 52
%token CHAR_TYPE 53
%token ELSE 54
%token ELSEIF 55
%token WHILE 56
%token DO 57
%token FOR 58
%token SWITCH 59
%token CASE 60
%token CONST 61
%token CLASS 62
%token PUBLIC 63
%token PRIVATE 64
%token TRY 65
%token CATCH 66
%token BREAK 67
%token BOOL 68
%token STD_COUT 69
%token STD_CIN 70
%token STREAM_INSERTION 71
%token STREAM_EXTRACTION 72
%token RETURN 73
%token STRING 74
%token TRUES 75
%token FALSES 76
%token FLOAT_NUM 77
%token ESCS 78
%token CHAR 79

%type prog
%start prog

%parse-param {int *count}   // passing parameters to yyparse and yyerror. NOT necessary

%%
prog : fun_def INT MAIN LBRAC VOID RBRAC LBRACE block RBRACE ;

fun_def : VOID var_name LBRAC parameters RBRAC LBRACE block RBRACE
        | type var_name LBRAC parameters RBRAC LBRACE block RBRACE
        ;

block : var_def statement expression
        ;

var_def : type var_name
        | type var_name LBRACE expression RBRACE
        | type var_name VAL expression 
        ;

type : INT | VOID | FLOAT | CHAR | BOOL ;

parameters : parameter_list
            | 
            ;

parameter_list : parameter
                | parameter_list COMMA parameter
                ;

parameter : type var_name
            ;

statement : var_name EQUALS expression SEMICOLON
          | STD_COUT STREAM_INSERTION ostream expression SEMICOLON
          | STD_CIN STREAM_EXTRACTION istream var_name SEMICOLON
          | conditional
          | loop
          | RETURN expression
          ;

istream : var_name
        ;

ostream : expression STREAM_INSERTION
        ;


expression : expression operation_2 expression
           | operation_1 expression
           | LBRAC expression RBRAC
           | literal
           | var_name
           ;

operation_2 : comparison
            | logical
            | arithmetic
            ;

operation_1 : SUB
            | NOT
            ;

arithmetic : ADD
           | SUB
           | MUL
           | DIV
           | MOD
           ;

logical : AND
        | OR
        ;

comparison : COMP_EQ
           | COMP_NEQ
           | COMP_LT
           | COMP_LEQ
           | COMP_GT
           | COMP_GEQ
           ;

literal : STRING
        | VAL
        | FLOAT_NUM
        | ESCS
        | CHAR
        | TRUES | FALSES
        ;

var_name : var_name operation_2 EQUALS expression
         | var_name operation_1
         | operation_1 var_name ;

conditional : IF LBRAC expression RBRAC LBRACE block RBRACE
            | IF LBRAC expression RBRAC LBRACE block RBRACE ELSE LBRACE block RBRACE
            | IF LBRAC expression RBRAC LBRACE block RBRACE ELSEIF LBRAC expression RBRAC LBRACE block RBRACE
            | IF LBRAC expression RBRAC LBRACE block RBRACE ELSEIF LBRAC expression RBRAC LBRACE block RBRACE ELSE LBRACE block RBRACE ;

loop : WHILE LBRAC expression RBRAC LBRACE block RBRACE
     | DO LBRACE block RBRACE WHILE LBRAC expression RBRAC
     | FOR LBRAC expression SEMICOLON expression SEMICOLON expression RBRAC LBRACE block RBRACE ;

switch_case : SWITCH LBRAC var_name RBRAC LBRACE block RBRACE
            | SWITCH LBRAC var_name RBRAC LBRACE case RBRACE ;

case: CASE var_name case BREAK SEMICOLON
    | ;

const_var : CONST parameter EQUALS literal SEMICOLON
          | type CONST var_name EQUALS literal SEMICOLON ; 

class : CLASS var_name LBRACE PRIVATE statement PUBLIC statement RBRACE ;

try_catch : TRY LBRACE block RBRACE CATCH LBRAC expression RBRAC LBRACE block RBRACE ;

%%
int yywrap(){
    printf("--\nEnd of File reached. Compile successful.\n--\n");
    return 1;
    }
void yyerror(int *count, const char* str){  // count is extar parameter
    fprintf(stderr,"--\nComiler Error: %s. Fail at Eq. %d.\n", str, *count+1);
}

int main (int argc, char *argv[]){
    yydebug = 0;        // 0 or 1 for --debug
    int counter = 0;
    FILE *fp;
    fp = fopen(argv[1], "r");
    yyin = fp;
    yyparse(&counter);      // extra parameter. NOT necessary
    printf("Equations compiled successfully: %d\n", counter);
    return 1;
}`

calcgrammar.l file:

    `%{
#include "calcgrammar.tab.h"
%}

%%
"+" {return ADD;}
"-" {return SUB;}
"*" {return MUL;}
"/" {return DIV;}
"(" {return LBRAC;}
")" {return RBRAC;}
"{" {return LBRACE;}
"}" {return RBRACE;}
"," {return COMMA;}
"%" {return MOD;}
"std::cout" {return STD_COUT;}
"std::cin" {return STD_CIN;}
"<<" {return STREAM_INSERTION;}
">>" {return STREAM_EXTRACTION;}
";" {return SEMICOLON;}
"main" {return MAIN;}
"if" {return IF;}
"else" {return ELSE;}
"else if" {return ELSEIF;}
"&&" {return AND;}
"||" {return OR;}
"=" {return EQUALS;}
"!" {return NOT;}
"==" {return COMP_EQ;}
"!=" {return COMP_NEQ;}
"<" {return COMP_LT;}
"<=" {return COMP_LEQ;}
">" {return COMP_GT;}
">=" {return COMP_GEQ;}
"int" {return INT;}
"void" {return VOID;}
"float" {return FLOAT;}
"char" {return CHAR_TYPE;}
"bool" {return BOOL;}
"double" {return DOUBLE;}
"while" {return WHILE;}
"do" {return DO;}
"for" {return FOR;}
"switch" {return SWITCH;}
"case" {return CASE;}
"const" {return CONST;}
"class" {return CLASS;}
"public:" {return PUBLIC;}
"private:" {return PRIVATE;}
"try" {return TRY;}
"catch" {return CATCH;}
"break" {return BREAK;}
"return" {return RETURN;}
["].+["] {return STRING;}
"true" {return TRUES;}
"false" {return FALSES}
"\a"|"\b"|"\\"|"\f"|"\v" {return ESCS;}
[0-9]+  {yylval.value=atof(yytext); return VAL;}
[+-]?([0-9]*[.])?[0-9]+ {return FLOAT_NUM;}
[a-zA-Z] {return CHAR;}
[ \t]   {}
\n  {return NEXT;}
.   {printf ("Lexer Error: Bad Token.\n"); return 0;}
%%`

makefile:

`all: clean calc

    calc:
        bison -d  --report=all calcgrammar.y
        flex calcgrammar.l
        gcc lex.yy.c calcgrammar.tab.c -o calc -lm

    clean: 
        rm -f lex.yy.c calcgrammar.tab.* calcgrammar.output calc
    `

I have tried to restart my terminal, inserting every type I made in %type but it still hasn't worked. after running make, the program will be able to identify a program using the command ./calc filename.txt. any help will be huge, thankss.

Answer 1

This error is generated when it is not possible to rewrite the start symbol to a sequence of only literals. In your grammar prog contains block which contains var_def which contains var_name. The issue is that all three branches of var_name contain var_name itself, so this definition is an infinite recursion and can never be resolved to literals.

To bypass this issue you should add another branch to var_name that defines what a simple variable looks like. For example (note that just STRING is of course not accurate for a variable name, but it illustrates the direction of the solution):

var_name : STRING
         | var_name operation_2 EQUALS expression
         | var_name operation_1
         | operation_1 var_name ;

Now you will get many other warnings and conflicts further down the grammar but you don't get the initial error anymore.

Similar questions for further reading: Bison says that start symbol does not derive any sentence, Fatal Error : start symbol START does not derive any sentence, Start symbol START does not derive any sentence %start START.