小试牛刀-递归下降算法（2）

欢迎关注公众号《Lua探索之旅》。

词法分析

上一节介绍了EBNF范式，现在开始递归下降算法的第一个环节：词法分析。

简单来说，词法分析就是切词，类似于搜索引擎的中文分词效果，将字符流切分为多个有类型的token。

以下面字符串举例：

10*20/(5+2*5)-10+20

可以分解为数字、加、减、乘、除、左括号、右括号这几种token，对应的c语言枚举就是：

enum TOKEN { 
    NUMBER, ADD, SUB, MUL, DIV, 
    LPAREN, RPAREN, ERROR, };

最后一个枚举ERROR表示语法错误，比如检测到不支持的符号如 '[' 、'%' 等。

定义一个token结构体：

struct token{
  TOKEN type;
  char value[32];
};

type表示类型，value为分词值。

定义取词函数，每次取出一个可用的token：

token next_token();

示例字符串的词法分析的结果就是：

token = 10
token = *
token = 20
token = /
token = (
token = 5
token = +
token = 2
token = *
token = 5
token = )
token = -
token = 10
token = +
token = 20

程序实现

词法分析是个典型的有限状态自动机应用，对输入串逐个字符分析，根据当前state和下一个token进行状态转换。

一般需要画个状态机转换图，这个例子比较简单，直接用语言描述逻辑。

• 若遇到空白字符，直接跳过

• 若遇到'+'，返回ADD

• 若遇到'-'，返回SUB

• 若遇到'*'，返回MUL 

• 若遇到'/'，返回DIV

• 若遇到'('，返回LPAREN 

• 若遇到')'，返回RPAREN

• 若遇到'0'~'9'，贪婪读取下一个字符，直到遇到非'0'~'9'，将分词存入token，返回NUMBER

• 若遇到其他字符，返回ERROR

完整代码如下：

token next_token() {
  token tk;
  tk.type = ERROR;
  char *p = tk.value;

  /*跳过空白字符*/
  while (*next == ' ' || *next == '\n' || *next == '\t')
    next++;

  switch (*next) {
  case '+': tk.type = ADD; break;
  case '-': tk.type = SUB; break;
  case '*': tk.type = MUL; break;
  case '/': tk.type = DIV; break;
  case '(': tk.type = LPAREN; break;
  case ')': tk.type = RPAREN; break;
  default: break;
  }
  if (tk.type != ERROR){
    next++;
    return tk;
  }

  /*数字*/
  if (isdigit(*next)) {
    while (isdigit(*next)) {
      *p = *next;
      next++;
      p++;
    }
    *p = '\0';

    tk.type = NUMBER;
    return tk;
  }
  return tk;
}