Creating shift-reduce / reduce-reduce free grammars
I'm trying to implement a simple Java like language parser in sablecc, although I'm constantly running into shift-reduce
/ reduce-reduce
problems when implementing if
, while
and block
statements.
For instance, I've considered the following:
stmts
= stmt*
;
stmt
= if_stmt
| block_stmt
| while_stmt
;
block_stmt
= { stmts }
| ;
;
while_stmt
= while
(
predicate
)
{
stmts
}
| while
(
predicate
)
;
This grammar, will, for 开发者_如何学编程instance, cause the problem that when you have something of the form
while (true) ;
the parser won't be able to know whether to reduce just ;
(from block_stmt
) or the full while (true);
(from while_stmt
).
I've been reading everywhere the reasons for the shift-reduce
/ reduce-reduce
problems and I think I understand them. But one thing is to know what causes them, and another completely different is knowing how to structure grammars such that I avoid them. I've tried implementing grammars in very different ways and I end up with problems nonetheless.
I guess that instead of just trying to run from a specific ss
/ rr
problem, there must a kind of paradigm to follow such to avoid this kinds of issues? I believe my way of approaching the problem must be totally wrong :(
Any resources around on how to build from scratch a grammar without falling into all these pitfalls? The resources on this matter tend to be either really easy (stating the obvious if then else
problem) or fully flagged grammars, which are kind of impenetrable.
The problem is that your grammar is specified so that eg the semicolon can be interpreted either as the semicolon of while_stmt or that of block_stmt... no sorry not that but somehow the grammar is redundant because { stmt } appears twice on RHS. Normally you would do
stmts ::= stmt | stmts stmt
block_stmt ::= { stmts }
stmt ::= ... | block_stmt | ; // empty
while_stmt ::= while ... stmt
精彩评论