Parsing problem for BNFC simple production rules

Question

This is a simplified version of my grammar in BNFC format:

-- programs -------------------------------------
entrypoints Program ;
Prog.           Program ::= [ Def ] ;
terminator      Def "" ;


-- definitions ----------------------------------
DVar.           Def ::= VarDecl ;
DFun.           Def ::= FunDef;

-- functions definitions ------------------------
DFunAll.        FunDef ::= FunType Id "(" [ Arg ] ")" FunBody;
DFunBody.       FunBody ::= "{" RetStmt "}" ;

-- function statements --------------------------
StmtRetVoid.    RetStmt ::= "return" ";" ;

-- variable declarations ------------------------
DVarSimple.     VarDecl ::= Type Id ";" ;
DVarList.       VarDecl ::= Type Id "," [Id] ";" ;

-- arguments ------------------------------------
ArgDecl.        Arg ::= Type Id ;
separator       Arg "," ;

-- types -----------------------------------------
TInt.           Type ::= "int" ;
TFunRetT.       FunType ::= Type ;
TFunRetV.       FunType ::= "void" ;

-- identifiers ------------------------------------
position token  Id (letter (letter | digit | '_')*) ;
separator       Id "," ;

For this grammar happy generates 1 unused rule and 1 shift/reduce conflict warnings. The problem I face here is that I cannot parse a function returning type correctly. It smells like super-easy but I got stuck.

To be more specific, I get parsing error for int foo(int x) {return;} while void foo(int x) {return;} parses successfully. So it seems these three rules do not work together as supposed:

DFunAll.        FunDef ::= FunType Id "(" [ Arg ] ")" FunBody;
TInt.           Type ::= "int" ;
TFunRetT.       FunType ::= Type ;

If I change the FunDef rule to FunDef ::= Type Id "(" [ Arg ] ")" FunBody; parsing goes smoothly but I want to keep Type and FunType distinguished so as not to have void as a regular Type.

rici rici · Accepted Answer · 2019-04-12T02:42:40

I want to keep Type and FunType distinguished so as not to have void as a regular Type.

But you are asking the parser to decide whether int is a Type or a FunType before it has enough information to make the decision. Since it can't tell whether to apply the production FunType ::= Type, it chooses to shift the Id instead (because default resolution of a shift/reduce conflict is to shift). That makes it impossible to use the FunType ::= Type production, which triggers the unused rule warning.

The only simple solution is to give up on FunType altogether, at the cost of some duplication:

DFunAllT.        FunDef ::= Type Id "(" [ Arg ] ")" FunBody;
DFunAllV.        FunDef ::= "void" Id "(" [ Arg ] ")" FunBody;

If the duplication bothers you, you could left factor:

DFunTI.   FunTypeId ::= Type Id;
DFunVI.   FunTypeId ::= "void" Id;
DFunAll.  FunDef ::= FunTypeId "(" [ Arg ] ")" FunBody;

The first one is probably a better fit for your AST though.

Parsing problem for BNFC simple production rules

1 Answers