title: Flex/Bison mini C compiler lexical and semantic analysis shift/reduce conflict
body: <p>I want to write a compiler for a mini C language using flex and bison. An example of my language would look like this:</p>
  
  <pre><code>/* This is an example uC program. */
  int fac(int n)
  {
      if (n &lt; 2)
          return n;
      return n * fac(n - 1);
  }
  
  int sum(int n, int a[])
  {
      int i;
      int s;
  
      i = 0;
      s = 0;
      while (i &lt; n) {
          s = s + a[i];
          i = i + 1;
      }
      return s;
  }
  
  int main(void)
  {
      int a[2];
  
      a[0] = fac(5);
      a[1] = 27;
      return 0;
  }
  </code></pre>
  
  <p>Here is my grammer to parse this kind of language:</p>
  
  <pre><code>program         ::= topdec_list
  topdec_list     ::= /empty/ | topdec topdec_list
  topdec          ::= vardec ";"
                    | funtype ident "(" formals ")" funbody
  vardec          ::= scalardec | arraydec
  scalardec       ::= typename ident
  arraydec        ::= typename ident "[" intconst "]"
  typename        ::= "int" | "char"
  funtype         ::= typename | "void"
  funbody         ::= "{" locals stmts "}" | ";"
  formals         ::= "void" | formal_list
  formal_list     ::= formaldec | formaldec "," formal_list
  formaldec       ::= scalardec | typename ident "[" "]"
  locals          ::= /empty/ | vardec ";" locals
  stmts           ::= /empty/ | stmt stmts
  stmt            ::= expr ";"
                    | "return" expr ";" | "return" ";"
                    | "while" condition stmt
                    | "if" condition stmt else_part
                    | "{" stmts "}"
                    | ";"
  else_part       ::= /empty/ | "else" stmt
  condition       ::= "(" expr ")"
  expr            ::= intconst
                    | ident | ident "[" expr "]"
                    | unop expr
                    | expr binop expr
                    | ident "(" actuals ")"
                    | "(" expr ")"
  unop            ::= "-" | "!"
  binop           ::= "+" | "-" | "*" | "/"
                    | "&lt;" | "&gt;" | "&lt;=" | "&gt;=" | "!=" | "=="
                    | "&amp;&amp;"
                    | "="
  actuals         ::= /empty/ | expr_list
  expr_list       ::= expr | expr "," expr_list
  </code></pre>
  
  <p>The flex module works fine and returns the values as desired, but bison keeps giving me strange errors that indicate my grammer is wrong (which is not). Here is my bison file:</p>
  
  <pre><code>%{
  #include &lt;stdio.h&gt;
  #include &lt;stdlib.h&gt;
  
  extern int yylex();
  extern int yyparse();
  FILE* yyin;
  extern int lineNumber;
  
  void yyerror(const char* s);
  %}
  
  %union {
      int intvalue;
  }
  
  %token&lt;intvalue&gt; INTCONST
  %token IDENT
  %token CHARK
  %token ELSEK
  %token IFK
  %token INTK
  %token RETURNK
  %token VOIDK
  %token WHILEK
  %token NOTK
  %token ANDK
  %token COMMAK
  %token DIVIDEK
  %token MULTIPLYK
  %token MINUSK
  %token PLUSK
  %token SEMICOLONK
  %token NEQUALK
  %token EQUALK
  %token ASSIGNMENTK
  %token RECOMPARATORK
  %token LECOMPARATORK
  %token RCOMPARATORK
  %token LCOMPARATORK
  %token RPARANTESESK
  %token LPARANTESESK
  %token RBRACKETK
  %token LBRACKETK
  %token RCURLY
  %token LCURLY
  
  %right ASSIGNMENTK
  %left ANDK
  %left EQUALK NEQUALK
  %left LCOMPARATORK RCOMPARATORK LECOMPARATORK RECOMPARATORK
  %left PLUSK
  %left MULTIPLYK DIVIDEK
  %left MINUSK NOTK
  
  %start program
  
  %%
  
  program: topdec_list
         ;
  topdec_list: /*empty*/
                       | topdec topdec_list
                   ;
  topdec: vardec SEMICOLONK
              | funtype IDENT LPARANTESESK formals RPARANTESESK funbody
        ;
  vardec: scalardec
              | arraydec
        ;
  scalardec: typename IDENT
                   ;
  arraydec: typename IDENT LBRACKETK INTCONST RBRACKETK
                  ;
  typename: INTK
                  | CHARK
                  ;
  funtype: typename
               | VOIDK
         ;
  funbody: LCURLY locals stmts RCURLY
               | SEMICOLONK
         ;
  formals: VOIDK
               | formal_list
         ;
  formal_list: formaldec
                       | formaldec COMMAK formal_list
                   ;
  formaldec: scalardec
           | typename IDENT LBRACKETK RBRACKETK
             ;
  locals: /*empty*/
        | vardec SEMICOLONK locals
          ;
  stmts: /*empty*/
       | stmt stmts
       ;
  stmt: expr SEMICOLONK
      | RETURNK expr SEMICOLONK
          | RETURNK SEMICOLONK
          | WHILEK condition stmt
          | IFK condition stmt else_part
          | LCURLY stmts RCURLY
          | SEMICOLONK
          ;
  else_part: /*empty*/ | ELSEK stmt
                   ;
  condition: LPARANTESESK expr RPARANTESESK
                   ;
  expr: INTCONST
          | IDENT
          | IDENT LBRACKETK expr RBRACKETK
          | unop expr
          | expr binop expr
          | IDENT LPARANTESESK actuals RPARANTESESK
          | LPARANTESESK expr RPARANTESESK
          ;
  unop: MINUSK | NOTK
      ;
  binop: PLUSK
       | MINUSK
           | MULTIPLYK
           | DIVIDEK
           | LCOMPARATORK
           | RCOMPARATORK
       | LECOMPARATORK
           | RECOMPARATORK
           | NEQUALK
           | EQUALK
           | ANDK
           | ASSIGNMENTK
       ;
  actuals: /*empty*/
               | expr_list
               ;
  expr_list: expr
                   | expr COMMAK expr_list
                   ;
  
  %%
  
  int main(int argc, char **argv)
  {
      yyin = fopen("input.c", "r");
      do
      {
          yyparse();
      } while (!feof(yyin));
      fclose(yyin);
      return 0;
  }
  
  void yyerror(const char* error)
  {
      fprintf(stderr, "Parse error in line %d: %s\n", lineNumber, error);
  }
  </code></pre>
  
  <p>for example for this input:</p>
  
  <pre><code>int i;
  i = 0;
  </code></pre>
  
  <p>i get an error that a syntax error happened right after it distinguishes the second <code>i</code> ( i print the tokens in my flex file so i know it has no problem untill it reaches the assignment character ).</p>
  
  <p>Or as another example when passing this line:</p>
  
  <pre><code>int fac(int n);
  </code></pre>
  
  <p>i get the same syntax error ( which exactly is <code>Parse error in line 1: syntax error</code> ) right after the first paranteses, meaning that it sees the second <code>int</code> as a syntax error, which it shouldn't because my grammer looks fine.</p>
  
  <p>Also the warnings produced by bison is as follows (flex and gcc are fine):</p>
  
  <pre><code>semantic_analyzer.y: warning: 26 shift/reduce conflicts [-Wconflicts-sr]
  semantic_analyzer.y:78.10-17: warning: rule useless in parser due to conflicts [-Wother]
   funtype: typename
            ^^^^^^^^
  </code></pre>
  
  <p>Any suggestions or corrections are appreciated :) thanks in advance.</p>