c - C 的递归下降解析器示例

Question

我正在尝试学习解析表达式。我发现递归下降解析似乎很容易做到这一点。从维基百科，我找到了一个 C 语言的例子。所以，我开始阅读和编辑这段代码以了解它是如何工作的。我根据维基百科页面上的描述编写了缺少的例程，但它无法像我预期的那样从任何表达式中工作。例如:1+2*3+1; 返回

error: statement: syntax error

有人可以解释我错过了什么吗？

当前的C代码:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef enum {ident, number, lparen, rparen, 
          times, // symbol *
          slash, // symbol \ not added yet
          plus, // symbol +
          minus, //symbol -
          eql, //symbol ==
          neq, // !=
          lss, // <
          leq,// <=
          gtr, // >
          geq, // >= 
          callsym, // not added yet 
          beginsym, // not added yet 
          semicolon, // ;
          endsym, 
          ifsym, whilesym, becomes, thensym, dosym, constsym, 
          comma, //:
          varsym, procsym, period, oddsym, 
          not, // !
          eq // =
} Symbol;

Symbol sym;
int peek;
void getsym(void);
void error(const char*);
void expression(void);
void program(void);
void nexttok(void);

#define is_num(c) ((c) >= '0' && (c) <= '9')
#define is_letter(c) ((c) <= 'a' && (c) <= 'z' || (c) >= 'A' && (c) <= 'Z')

int main(void)
{
  program();
  return 0;
}

void nexttok(void)
{
  peek = getchar();
}

void getsym(void)
{
  for(;;) {
    nexttok();
    if(peek == ' ' || peek == '\t') continue;
    else if(peek == EOF) break;
    else break;
  }
  //static char buf[256];
  switch(peek) {
  case '+': sym = plus; return;
  case '-': sym = minus; return;
  case '*': sym = times; return;
  case ';': sym = semicolon; return;
  case ':': sym = comma; return;
  case '=': 
    nexttok();
    if(peek == '=')
      sym = eql;
    else
      sym = eq;
    return;
  case '!': 
    nexttok();
    if(peek == '=')
      sym = neq;
    else
      sym = not;
    return;
  case '<':
    nexttok();
    if(peek == '=')
      sym = leq;
    else
      sym = lss;
    return;
  case '>':
    nexttok();
    if(peek == '=')
      sym = geq;
    else
      sym = gtr;
    return;
  }
  if(is_num(peek)) {
    sym = number;
    return;
  }
}

int accept(Symbol s) {
    if (sym == s) {
        getsym();
        return 1;
    }
    return 0;
}

int expect(Symbol s) {
    if (accept(s))
        return 1;
    error("expect: unexpected symbol");
    return 0;
}

void factor(void) {
    if (accept(ident)) {
        ;
    } else if (accept(number)) {
        ;
    } else if (accept(lparen)) {
        expression();
        expect(rparen);
    } else {
        error("factor: syntax error");
        getsym();
    }
}

void term(void) {
    factor();
    while (sym == times || sym == slash) {
        getsym();
        factor();
    }
}

void expression(void) {
    if (sym == plus || sym == minus)
        getsym();
    term();
    while (sym == plus || sym == minus) {
        getsym();
        term();
    }
}

void condition(void) {
    if (accept(oddsym)) {
        expression();
    } else {
        expression();
        if (sym == eql || sym == neq || sym == lss || sym == leq || sym == gtr || sym == geq) {
            getsym();
            expression();
        } else {
            error("condition: invalid operator");
            getsym();
        }
    }
}

void statement(void) {
    if (accept(ident)) {
        expect(becomes);
        expression();
    } else if (accept(callsym)) {
        expect(ident);
    } else if (accept(beginsym)) {
        do {
            statement();
        } while (accept(semicolon));
        expect(endsym);
    } else if (accept(ifsym)) {
        condition();
        expect(thensym);
        statement();
    } else if (accept(whilesym)) {
        condition();
        expect(dosym);
        statement();
    } else {
        error("statement: syntax error");
        getsym();
    }
}

void block(void) {
    if (accept(constsym)) {
        do {
            expect(ident);
            expect(eql);
            expect(number);
        } while (accept(comma));
        expect(semicolon);
    }
    if (accept(varsym)) {
        do {
            expect(ident);
        } while (accept(comma));
        expect(semicolon);
    }
    while (accept(procsym)) {
        expect(ident);
        expect(semicolon);
        block();
        expect(semicolon);
    }
    statement();
}

void program(void) {
    getsym();
    block();
    expect(period);
}

void error(const char *msg)
{
  fprintf(stderr,"error: %s\n",msg);
  exit(1);
}

Answer 1

statement 从不调用 expression，因此所有表达式都将是语法错误。要解决此问题，您需要更改 statement，以便在 sym 是启动表达式的有效符号时调用 expression。 (accept 是 Not Acceptable ，因为它会消耗符号，而 expression 将看不到它。)