开发者

Creating shift-reduce / reduce-reduce free grammars

开发者 https://www.devze.com 2023-02-24 03:03 出处:网络
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.

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
0

精彩评论

暂无评论...
验证码 换一张
取 消

关注公众号