java - 为我愚蠢:解析是什么？

Question

昨天我问了语法，今天在Java中，我正在学习如何使用我完成的词法分析器中的标记来实现解析语法的算法。

对于这个问题，我需要一个人来检查我的理解。

让我们假设给定Scheme语法：

exp -> ( rest
     | #f
     | #t
     | ' exp
     | integer_constant
     | string_constant
     | identifier

rest -> )
     | exp+ [ . exp ] )

以下伪代码正确吗？我研究了递归下降解析器，并且需要通过创建解析树的节点来为解释器创建解析树。

 Node parseExp() {
      check to see if the token is left parenthesis
           if true, return a node for Cons (which is a non-terminating node in Scheme 
           parse tree) and call parseRest()
      else check to see if the token is #f
           if true, return a node for Boolean with stored value #f
      else check to see if the token is #t
           if true, return a node for Boolean with stored value #t
      else check to see if the token is quote
           if true, return a node for Quote and recursively call parseExp()
      else check to see if the token is integer_constant
           if true, return a node for Integer with stored value int
      else check to see if the token is string_constant
           if true, return a node for String with stored string value
      else check to see if the token is identifier
           if true, return a node for identifier with stored string value
      else
           print error message saying a Syntax error occured
           return null
 }

 Node parseRest() {
      check to see if the token is right parenthesis
           if true, return a node for Nil (which is a terminating () node in scheme 
           parse tree)
      else  // I am having difficulty trying to put this into an algorithm here
           call parseExp() for the first expression
           while (token does not equal right parenthesis) {
                getNextToken()
                if (token equals right parenthesis)
                     return a node for right parenthesis
                else if (token equals dot)
                     return a node for dot
                     getNextToken()
                     if (token equals right parenthesis)
                          print error message saying a Syntax error occurred
                          return null
                     else
                        call parseExp()
                else
                     parseExp() 
           }    
 }

如果我对此有错误的想法，请纠正我。据说parseRest（）需要先行标记才能做出决定，可以解释一下，并且可能是伪代码示例吗？

谢谢！

Answer 1

您走在正确的道路上，但存在一些问题：

check to see if the token is left parenthesis
     if true, return a node for Cons (which is a non-terminating node in Scheme 
     parse tree) and call parseRest()

这有点模棱两可，因为您没有提到您打算对 parseRest()的结果执行什么操作，但是我假设您想将其存储在Cons节点中。这样做的问题是Cons节点应该有两个子节点（如果列表是列表的开头，列表的尾部则是一个子节点-如果不清楚，则可能必须查看Scheme语言的规则），但parseRest仅给您一个节点，因此不起作用。因此，让我们退后一步，想一想 (时想要什么：

(是对的开始（即点对或非空列表），或者是空列表 ()。在第一种情况下，我们想要一个Cons节点，但是在第二种情况下，我们想要一个Nil节点，因为空列表不是cons单元。因此，我们有两种可能性，在查看了列表的其余部分之前，我们不知道该选择哪一种。因此，不应在此处做出决定，而应在parseRest函数内部做出决定。因此，我们将代码更改为：

check to see if the token is left parenthesis
     if true, return the result of parseRest()

现在让我们看一下parseRest：

在这里，您有时会返回点和括号的节点，但是这些根本不应该是AST中的节点-它们是令牌。另一个问题是，当您递归调用parseRest时，您仍然不清楚要对结果做什么。可能会以为您想返回结果，但是while循环将毫无意义，因为每次您都在第一次迭代中返回它。实际上，即使在非递归情况下，这也是一个问题：例如，您返回一个点节点，然后继续解析其后的表达式。但是在返回之后函数将退出，因此返回之后的所有内容都将被忽略。所以这行不通。

在讨论如何使其工作之前，首先让我们更清晰地了解所生成的AST的外观：


对于“（）”，我们需要一个Nil节点。可以在您当前的代码中正常工作。
对于“（x）”，我们需要 Cons(Ident("x"), Nil)。
对于“（x。y）”，我们要 Cons(Ident("x"), Ident("y"))。
对于“（x y）”，我们需要 Cons(Ident("x"), Cons (Ident("y"), Nil))。
对于“（x y。z）”，我们要 Cons(Ident("x"), Cons (Ident("y"), Ident("z")))。


我希望现在的模式很清楚（否则，您可能要查看Scheme语言）。那么我们如何获得这种AST？

好吧，如果看到 )，我们将返回 Nil。同样，这已经在您的代码中起作用了。否则，我们将解析一个表达式（如果此处没有有效的表达式，则会出现错误）。那之后会发生什么呢？好吧，如果我们找到一个表达式，则该表达式是Cons单元的第一个元素。所以我们要返回 Cons(theExpression, ...)。但是 ...部分有什么内容？好吧，这取决于下一个令牌是否为点。如果是点，则我们有一个点表达式，因此点后需要一个表达式，我们想返回 Cons(theExpressionBeforeTheDot, theExpressionAfterTheDot)。如果没有圆点，则表示我们在列表中，其后是尾巴。所以我们要返回 Cons(theExpression, parseRest())。


据说parseRest（）需要先行标记才能做出决定，可以解释一下，并且可能是伪代码示例吗？


前瞻性意味着您必须查看下一个令牌，而无需实际将其从流中删除。就伪代码而言，这意味着您想知道在调用 nextToken()时将返回哪个令牌，而无需实际更改对 nextToken()的下一次调用将返回的内容。因此，您将拥有另一个内置函数，例如 peekNext()，它可以返回下一个令牌，而无需实际推进令牌流中的迭代器。

在parseRest中需要此标记的原因是点：当您检查下一个标记是否为点并且事实证明它不是一个点时，则您不希望该标记实际消失。也就是说，您将调用parseExpression，然后parseExpression将调用nextToken，对吗？当发生这种情况时，您希望它返回当前表达式之后的令牌-您不想跳过该令牌，因为您必须检查它是否是一个点。因此，在检查点时，您需要调用 peekToken而不是 nextToken（不过，当它是点时，仍需要删除令牌）。