Problems with parsing decaf (variable declaration versus constructor)

Question

I am using bison (3.0.4) and lexer to implement the (partial) grammar of Decaf programming language. I am only implementing what is inside the class.

So, my task is simple: store every production rule (as a string) in the tree, and then just print it out.

For example, if you have the following line of code as an input

class Foo { Foo(int arg1) { some2 a; } }

you (must) get the following output

<ClassDecl>         --> class identifier <classBody>
<ClassBody>         --> { <VariableDecl>* <ConstructorDecl>* <MethodDecl>* }
<ConstructorDecl>   --> identifier ( <ParameterList> ) <Block>
<ParameterList>     --> <Parameter> <, Parameter>*
<Parameter>         --> <Type> identifier
<Type>              --> <SimpleType>
<SimpleType>        --> int
<Block>             --> { <LocalVariableDecl>* <Statement>* }
<LocalVariableDecl> --> <Type> identifier ;
<Type>              --> <SimpleType>
<SimpleType>        --> identifier

The first problem (solved) was that it parsed variable declaration instead of constructor declaration, though I have no variable declaration in the scope of a class itself (i.e. I have only inside the constructor's block). This is solved.

Nevertheless, if I give the following class abc { some1 abc; john doe; } it says that syntax error, unexpected SEMICOLON, expecting LP. So, the character at line 19 causes the problem.

Here is .y file (only classBody rule)

class_decl:
  CLASS ID LC class_body RC
  ;


/* FIXME: Gotta add more grammar here */
class_body: var_declmore constructor_declmore method_declmore
  | var_declmore constructor_declmore
  | var_declmore method_declmore
  | constructor_declmore method_declmore
  | method_declmore
  | var_declmore
  | constructor_declmore
  | %empty
  ;


var_declmore: var_decl
  | var_declmore var_decl
  ;


constructor_declmore: constructor_decl
  | constructor_declmore constructor_decl 
  ;

var_decl: type ID SEMICOLON
  | type ID error
  ;

constructor_decl: ID LP parameter_list RP block
  | ID error parameter_list RP block
  ;

Here is the gist to the full .y file.

I got a ton of warnings from that file. Including two shift-reduce conflicts; one reduce-reduce conflict; and a warning about a useless rule. BTW, it is a lot easier to read a grammar if you leave out the actions; see minimal reproducible example — rici
You will get a lot of warnings because rules such as expression, name and new_expression are not used yet. They are used in the statement rule, which has not been implemented yet as I want to figure out the problem with this rule (vardecl and constructor conflict). — oneturkmen
You will find that much easier if you create a minimal reproducible example with only the applicable rules. — rici

rici rici · Accepted Answer · 2017-11-03T17:28:37

The essential problem is that constructor_declmore can be empty, and that both var_decl and constructor_decl can start with ID.

That's a problem because before the parser can recognize a constructor_decl, it needs to reduce an (empty) constructor_declmore. But it obviously cannot do that reduction unless it knows that the var_declmore is finished.

So when it sees an ID it has to decide between one of two actions:

Reduce an empty constructor_declmore, thereby deciding that there are no more var_decls; or
Shift the ID in order to start parsing a new var_decl.

In the absence of precedence declarations (which wouldn't help here), bison/yacc always resolves shift/reduce conflicts in favour of the shift action. So in this case, it assumes that Foo is the ID which starts a var_decl, leading to the error message you note.

The reduce/reduce conflict produced by the grammar should also be looked at. It comes from the method_declmore: method_decl rule, which conflicts with the other possible way of creating a method_declmore by starting with an empty method_declmore and then adding a method_decl.

Problems with parsing decaf (variable declaration versus constructor)

1 Answers