创建shift-reduce / reduce-reduce自由语法

Question

我试图在sablecc中实现一个简单的Java式语言解析器，尽管我在实现if, while和block语句时不断遇到shift-reduce/reduce-reduce问题。

例如，我考虑过以下内容:

stmts = stmt*;

stmt = if_stmt | block_stmt | while_stmt;

block_stmt = { stmts } | ;;

while_stmt = while ( predicate ) { stmts } | while ( predicate ) ;

这个语法，例如，会导致这样的问题:当你有一些形式为

的东西时

while (true) ;

解析器将无法知道是只减少;(从block_stmt)还是减少完整的while (true);(从while_stmt)。

我一直在阅读shift-reduce/reduce-reduce问题的原因，我想我理解他们。但是要知道是什么导致了错误，另一个完全不同的是要知道如何组织语法以避免错误。我尝试过用不同的方式实现语法，但还是遇到了问题。

我想，而不是仅仅试图从一个特定的ss/rr问题运行，必须有一种范式来遵循这样的避免这类问题?我想我处理这个问题的方法肯定是完全错误的。

有没有关于如何从头开始构建语法而不陷入所有这些陷阱的资源?关于这个问题的资源要么非常简单(说明明显的if then else问题)，要么完全标记语法，这有点难以理解。

Answer 1

问题是您的语法被指定，以便例如分号可以被解释为while_stmt或block_stmt的分号…不，抱歉，不是那个，但是语法是多余的，因为{stmt}在RHS上出现了两次。通常你会写

 stmts ::= stmt | stmts stmt
 block_stmt ::= { stmts }
 stmt ::= ... | block_stmt | ;     // empty
 while_stmt ::= while ... stmt