LALR(1) Conflict Resolution

After class a question was raised regarding how the parser can recognize a field declaration versus a method declaration because they both start out with a type declaration and an identifier.

I think I understand the confusion. You should remember that an LALR(1) parser has one lookahead symbol to decide which *state* it should transition into, but a state can include more than one of the original productions.

So during a parse:

class Program {
int f . (

The parser should be in a state that "includes" both method declaration (if there are no field decls) and field declaration and upon seeing the "(" will move into a state for a method declaration.

The trick is to delay the decision as to which rule should be
matched as long as possible. If you have the following rules:

program -> CLASS id LBRACE field_decl method_decl RBRACE;

field_decl -> type id ... | ;

method_decl -> type id LPAREN ... | ;

You will get a conflict upon seeing a type.

The parser will have to decide upon seeing a type whether it is a
field_decl or a method_decl. But it cannot tell yet and you did not give it the option of delaying the decision until later and continuting in a state that includes both.

You do not want to limit the decisions that the parser must make early in the parse. You need the early states to contain each option (i.e., whether there is a field_decl or not).

How can you re-write the grammar above to be conflict-free?

I hope this helps. Let me know if there are still any problems. I can write more on this subject.