递归下降算法

递归下降算法(Recursive Descent Parsing) 左边是一个非终结符(Non-terminal),右边是它的产生式(Production Rule)。在语法解析的过程中,左边会被右边的替代。如果替代之后还有非终结符,那么继续这个替代过程,直到最后全部都是终结符(Terminal),也就是Token。只有终结符才可以成为AST的叶子节点,这个过程,也叫做推导(Derivation)的过程。上级文法嵌套下级文法,上级的算法调用下级的算法,表现在生成AST中,上级算法生成上级节点,下级算法生成下级节点。这就是下降的含义。

理解

以四则运算解析器为例,运算语法规则为:

additive: minus | minus + additive
minus: multiple | multiple - minus
multiple: divide | divide * multiple
divide: number | number / divide
primary: number | (additive)

四则运算递归下降算法如下

function additive(tokenReader) {
  let child1 = minus(tokenReader);
  let node = child1;
  let token = tokenReader.peek();
  if (child1 != null && token != null) {
    if (token.type === tokenTypes.Plus) {
      token = tokenReader.read();
      let child2 = additive(tokenReader);
      if (child2 != null) {
        node = new ASTNode(nodeTypes.Additive);
        node.appendChild(child1);
        node.appendChild(child2);
      }
    }
  }
  return node;
}
function minus(tokenReader) {
  let child1 = multiply(tokenReader);
  let node = child1;
  let token = tokenReader.peek();
  if (child1 != null && token != null) {
    if (token.type === tokenTypes.Minus) {
      token = tokenReader.read();
      let child2 = minus(tokenReader);
      if (child2 != null) {
        node = new ASTNode(nodeTypes.Minus);
        node.appendChild(child1);
        node.appendChild(child2);
      }
    }
  }
  return node;
}
function multiply(tokenReader) {
  let child1 = divide(tokenReader);
  let node = child1;
  let token = tokenReader.peek();
  if (child1 != null && token != null) {
    if (token.type === tokenTypes.Multiply) {
      token = tokenReader.read();
      let child2 = multiply(tokenReader);
      if (child2 != null) {
        node = new ASTNode(nodeTypes.Multiplicative);
        node.appendChild(child1);
        node.appendChild(child2);
      }
    }
  }
  return node;
}
function divide(tokenReader) {
  let child1 = primary(tokenReader);
  let node = child1;
  let token = tokenReader.peek();
  if (child1 != null && token != null) {
    if (token.type === tokenTypes.Divide) {
      token = tokenReader.read();
      let child2 = divide(tokenReader);
      if (child2 != null) {
        node = new ASTNode(nodeTypes.Divide);
        node.appendChild(child1);
        node.appendChild(child2);
      }
    }
  }
  return node;
}
function primary(tokenReader) {
  let node = number(tokenReader);
  if (!node) {
    let token = tokenReader.peek();
    if (token != null && token.type === tokenTypes.LeftPara) {
      tokenReader.read();
      node = additive(tokenReader);
      tokenReader.read();
    }
  }
  return node;
}
function number(tokenReader) {
  let node = null;
  let token = tokenReader.peek();
  if (token != null && token.type === tokenTypes.Number) {
    token = tokenReader.read();
    node = new ASTNode(nodeTypes.Numeric, token.value);
  }
  return node;
}

通过下降递归算法生成了AST

理解​

理解