这个文法能否被预测递归下降解析器和带回溯的解析器解析

Question

我有以下语法：

IdentifierName ::
    IdentifierStart
    IdentifierName IdentifierPart

其中使用单词 git 应该被解析为以下解析树：

                 IdentifierName
                /              \
        IdentifierName IdentifierPart
       /              \         |
IdentifierName IdentifierPart  't'
       |                |
IdentiiferStart        'i'
       |
      'g'

我想编写一个递归下降算法来做到这一点。现在我有两个选择，要么编写一个带有 backtracking 的递归下降解析器，要么编写一个 predictive 递归下降解析器。它们都是而非 table 驱动解析器。但是，我已经读到，对于带回溯的递归下降，我需要消除左递归。问题中的语法似乎是递归的。

那么我是否需要重构语法或使用预测算法？

Answer 1

是的，语法是左递归的，因此不是 LL。回溯和预测 LL 解析器都不能处理这样的语法。因此，您要么需要更改语法，要么使用其他算法，例如 LR 解析算法。

注意这个文法是正则的，所以其实可以翻译成正则表达式或者直接翻译成有限自动机。

在编写 JavaScript 的真实世界实现时，像这样的词法规则将在词法分析器中处理，只有其他规则将由解析器处理（但是那些指定的左递归同样，因此它们也必须重写才能被 LL 解析器解析。

Answer 2

这往往是词法分析器的工作，而不是解析器的工作。通常，词法分析器在一个循环中一次处理一个字符，使用一个大的 switch 语句（或者等效的 "initial character table" 如果数据驱动。）

// near the end of the big "switch (ch) {" statement ...
default:
    if (!isIdentifierStart(chInit))
        {
        log(Severity.ERROR, ILLEGAL_CHAR, new Object[]{quotedChar(chInit)},
                lInitPos, source.getPosition());
        }
// fall through
case 'A':case 'B':case 'C':case 'D':case 'E':case 'F':case 'G':
case 'H':case 'I':case 'J':case 'K':case 'L':case 'M':case 'N':
case 'O':case 'P':case 'Q':case 'R':case 'S':case 'T':case 'U':
case 'V':case 'W':case 'X':case 'Y':case 'Z':
case 'a':case 'b':case 'c':case 'd':case 'e':case 'f':case 'g':
case 'h':case 'i':case 'j':case 'k':case 'l':case 'm':case 'n':
case 'o':case 'p':case 'q':case 'r':case 's':case 't':case 'u':
case 'v':case 'w':case 'x':case 'y':case 'z':
case '_':
    {
    while (source.hasNext())
        {
        if (!isIdentifierPart(nextChar()))
            {
            source.rewind();
            break;
            }
        }
    String name = source.toString(lInitPos, source.getPosition());
    // ...
    }

如果手动构建，我发现拥有专用的词法分析器（从字符流中生成标记）和解析器（从标记流中生成 AST）比尝试将它们组合到一个解析器中要容易得多.

这个文法能否被预测递归下降解析器和带回溯的解析器解析

Can this grammar be parsed by both predictive recursive descent parser and the parser with backtracking

parsing

recursive-descent

left-recursion

compiler-construction