c++ - 在c中生成解析树

Question

下面的代码应该生成输入表达式的解析树，但问题是输出 E,T,F,S (代码中使用的函数)。我希望它是这样的:

a+b*c => E*c => E+b*c => a+b*c

     #include <stdio.h>
     #include <stdlib.h>
     #include <ctype.h>
     char next;
     void E(void);void T(void);
     void S(void);void F(void);
     void error(int);void scan(void);
     void enter(char);
     void leave(char);
     void spaces(int);
     int level = 0;



    //The main should always be very simple
    //First scan the string
    //second check for end of string reached , if yes success and if not error.

    //P ---> E '#'
    int main(void){
       printf("Input:");
       scan();  E();
       if (next != '#') error(1);
       else printf("***** Successful parse *****\n");
    }

    //E ---> T {('+'|'-') T}
    void E(void){
       enter('E');
       T();
       while (next == '+' || next == '-') {
          scan();
          T();
       }
       leave('E');
    }


    //T ---> S {('*'|'/') S}
    void T(void)
    {
       enter('T');  S();
       while (next == '*' || next == '/') {
          scan(); S();
       }
       leave('T');
    }

    //S ---> F '^' S | F
    void S(void)
    {
       enter('S'); F();
       if (next == '^') {
          scan();  S();
       }
       leave('S');
    }

    //F ---> char | '(' E ')'
    void F(void)
    {
       enter('F');
       if (isalpha(next)) 
       { 
           scan();
       }
       else if (next == '(') {
          scan(); E();
          if (next == ')')
              scan();
          else
              error(2);
       }
       else { 
          error(3);
       }
       leave('F');
    }
    //Scan the entire input
    void scan(void){
       while (isspace(next = getchar()));
    }

    void error(int n)
    {
       printf("\n*** ERROR: %i\n", n);
       exit(1);
    }

    void enter(char name)
    {
       spaces(level++);
       printf("+-%c\n", name);
    }

    void leave(char name)
    {
      spaces(--level);
      printf("+-%c\n", name);

    }
    //TO display the parse tree
    void spaces(int local_level)
    {
       while (local_level-- > 0)
       printf("| ");
    }

Answer 1

看起来像一个递归下降解析器。首先，手工计算出语法。你所期待的并不是你的语法所说的。从您的评论中可以看出，

E ---> T {('+'|'-') T}   expression
T ---> S {('*'|'/') S}   term
S ---> F '^' S | F       subexpression?
F ---> char | '(' E ')'  factor

E 和 T 的定义将 * 置于比 + 更高的优先级，因此您不可能得到 E*c。如果你想要这样，你必须将语法切换为

E ---> T {('*'|'/') T}   expression
T ---> S {('+'|'-') S}   term

如果您只想输出包含表达式的其余部分，

1. 获取整行内容
2. 更改您的扫描仪或词法分析器以从该扫描行获取下一个字符。将此标记为扫描点。
3. 更改您的 Enter 例程以打印助记符以及扫描点的行。