C 中的递归下降解析器 - 回溯时出错

Question

使用示例输入“(a)”为给定语法实现递归下降解析器。
这个程序的输出是检查用户读取的输入是否解析成功。至于程序的流程应该如何处理这个特定的输入...

main() 调用起始符号 E() -> T() -> T1() [计算结果为 false ] 因此追溯到其父函数 T() 现在调用 T2() （计算结果也为false），因此 T() -> T3() -> E() -> E1() -> T() -> T1()（计算结果为 true）。

最终 E() 也应该为真，函数 T3() 的语句 return termial('(') && E() && termial(')'); 中的最后一个条件 termial(')') 应该用 ')' 执行token 的值。然而，事实证明 token == '(' 仍然存在，因此程序的输出结果为

Parsed Unsuccessfully

不太确定为什么 token 不等于 ')'

 //Grammar :
 //E -> T | T + E
 //T -> a | a * T | (E)
 //
 //Input :
 //(a)

#include <stdio.h>

char *next;

int E();
int E1();
int E2();
int T();
int T1();
int T2();
int T3();

int termial(char token){
    return (*next++ == token);
}

int E1(){
    return T();
}

int E2(){
    return T() && termial('+') && E();
}

int E(){
    char *temp = next;
    return (next = temp, E1()) || (next = temp, E2());
}

int T1(){
    return termial('a');
}

int T2(){
    return termial('a') && termial('*') && T();
}

int T3(){
    return termial('(') && E() && termial(')');
}

int T(){
    char *temp = next;
    return (next = temp, T1()) || (next = temp, T2()), (next = temp, T3());
}


int main(int argc, const char * argv[]) {
    char str[10];
    int result;
    printf("INPUT a string to be parsed : ");
    scanf("%s", str);
    next = &str[0];
    result = E();
    result == 1 ? printf("Parsed Successfully") : printf("Parsed Unsuccessfully");
    printf("\n");
    return 0;
}

Answer 1

在T()中：

int T(){
  char *temp = next;
  return (next = temp, T1()) || (next = temp, T2()), (next = temp, T3());
}

(next = temp, T3()) 总是被调用（在它之前的逗号处没有短路），并且 return false 在大多数情况下在你的案例中，当 T1() 或 T2() 成功并且应该成功结束函数时会导致各种失败。

将该行更改为：

return (next = temp, T1()) || (next = temp, T2()) || (next = temp, T3());

C 中的递归下降解析器 - 回溯时出错

Recursive Descent Parser In C - Error while backtracking

c

parsing

recursive-descent

backtrace