parsing - 创建 shift-reduce / reduce-reduce 免费语法

Question

我正在尝试在 sablecc 中实现一个类似 Java 的简单语言解析器，尽管在实现,和语句时我经常遇到shift-reduce/问题。reduce-reduceifwhileblock

例如，我考虑了以下内容：

stmts= stmt*;

stmt= if_stmt| block_stmt| while_stmt;

block_stmt= { stmts }| ;;

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

例如，这种语法会导致这样的问题，即当你有某种形式的东西时

while (true) ;

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

我一直在到处阅读shift-reduce/reduce-reduce问题的原因，我想我理解它们。但是一件事是要知道是什么导致了它们，而另一件事完全不同的是知道如何构造语法以使我避免它们。我尝试过以非常不同的方式实现语法，但最终还是遇到了问题。

我想，与其只是试图从一个特定的ss/rr问题中运行，还必须有一种范式来遵循这样的范式来避免这类问题？我相信我解决问题的方式一定是完全错误的:(

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

score 2 · Accepted Answer

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

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

1 回答 1