parsing - 来自 BNF 的递归下降解析器伪代码

Question

好的，我认为这里会有足够多的 CS 专业学生来检查我的递归下降解析器的伪代码。我从这个 BNF 开发出来的

EXP ::= EXP + TERM | EXP - TERM | TERM
TERM ::= TERM * FACTOR | TERM/FACTOR | FACTOR
FACTOR ::= (EXP) | DIGIT
DIGIT ::= 0|1|2|3

伪代码如下:

procedure exp()
    term()
    if token == ‘+’
        match(‘+’)
        term()
    elseif token == ‘-‘
        match(‘-‘)
        term()
    else
        break    

procedure term()
    factor()
    if token == ‘*’
        match(‘*’)
        factor()
    elseif token == ‘/’
        match(‘/’)
        factor()
    else
        break

procedure factor()
    if token == ‘(‘
        match(‘(‘)
        exp()
        match(‘)’)
    else
        digit()

procedure digit()
    if token == ‘0’
        match(‘0’)
    elseif token == ‘1’
        match(‘1’)
    elseif token == ‘2’
        match(‘2’)
    else
        match(‘3’)

match(t)
    if token == t
        advancetokenpointer
    else
        error

这是正确的吗？我在想我可能需要在每个程序中都有返回，而且我也不确定我的程序是否正确。也许也包括结束程序？无论如何，非常感谢! :-)

Answer 1

你已经成功了一半。特别是，您没有考虑语法的左递归部分，如“EXP::= EXP...”或“TERM::= TERM...”。

无论如何，递归下降不太适合左递归，但幸运的是，您可以在语法中执行标准转换，从而消除这种左递归。例如，以下语法:

A ::= A x B | B

可以这样编码:

procedure A()
  B()
  repeat
    if token == 'x'
      match('x')
      B()
    else
      break

此外，factor 的代码没有正确遵循语法。请注意，在第一个备选方案中，EXP 被递归调用(这是递归下降没有问题的一种递归)，而您调用的是 factor。此外，您正在匹配右括号，就好像它是可选的，但实际上是必需的。 DIGIT 的代码中也存在同样的问题。如果 0、1 或 2 都不匹配，则 3 必须匹配。