语法分析器实现

输入词法分析所得 Tokens 数组
输出语法树
术语
- 终止符 Terminal // 形式语言必须完全由终止符组成！
- 非终止符 Non-Terminal
- LL 与 LR
- 递归下降

递归下降的 LL 算法

从语法树顶部的根节点（注意不是首个 Token）开始，向前【匹配非终止符】
每个【匹配非终止符】的过程，都是调用一个函数的过程。若非终止符 X 中又需要匹配该非终止符，此时需再次调用自身以向下匹配该类型，即【递归下降】
当所有的 Token 都被解析后，返回匹配后的原始语法树
隐式构造语法树，适合手写 Parser

递归下降实例

输入 (())
语法
- A → (B)
- B → A
- B → null

设计输入格式

TagOpen - div
Value - xxx
TagClose - div
Tag - TagOpen Value TagClose
Tags - Tag Tag…

实现

词法分析暴露出来的是一个 parse 的函数，输入的是 tokens 数组，然后调用自身关键 NT.html 方法处理整个 tokens 数组，通过 tag、tags 函数的互相调用。在函数互相调用的过程中，一些 match('TagOpen') 开始符、match('TagClose') 终止符的函数回去不断的匹配。最终构造出一棵语法树。

定义 tokens 的 Mock 数据，这个数据在上一节的词法分析中生成。

let t = [
  { type: 'TagOpen', val: '<p>' },
    { type: 'Value', val: 'hello' },
  { type: 'TagClose', val: '</p>' },

  { type: 'TagOpen', val: '<div>' },

    { type: 'TagOpen', val: '<h2>' },
      { type: 'TagOpen', val: '<small>' },
        { type: 'Value', val: 'world' },
      { type: 'TagClose', val: '</small>' },
    { type: 'TagClose', val: '</h2>' },

    { type: 'TagOpen', val: '<span>' },
      { type: 'Value', val: '!' },
    { type: 'TagClose', val: '</span>' },

  { type: 'TagClose', val: '</div>' }
]

参考代码

let tokens = t;
let currIndex = 0;
let lookahead = tokens[currIndex];

function nextToken () {
  return tokens[++currIndex]
}

function match (terminalType) {
  if (lookahead && terminalType === lookahead.type) lookahead = nextToken()
  else throw Error('SyntaxError')
}

function tag(currNode){
  match('TagOpen')
  if (lookahead.type === 'TagOpen') {
    currNode = NT.tags(currNode)
  } else {
    currNode.val = lookahead.val
    match('Value')
  }
  match('TagClose')
  return currNode
}

function tags(currNode){
  while (lookahead) {
    let tagNode = { type: lookahead.val, val: null, children: [] }
    tagNode = NT.tag(tagNode)

    currNode.children.push(tagNode)
    if (lookahead && lookahead.type === 'TagClose') break
  }
  return currNode
}

function parse(){
  let dom = { type: 'html', val: null, children: [] }
  return NT.tags(dom)
}

let dom = parse();

在 tags 中初始化对 currNode 做处理，其实就是初始化的 dom ，一个普通的对象，它的类型是 html ，没有任何的值，也没有 children。

{ type: 'html', val: null, children: [] }

lookahead ，是当前每次语法分析器，下标所处的 token 。如果有 token ，如果有我们调用 token 的匹配规则。初始化 tagNode

let tagNode = { type: lookahead.val, val: null, children: [] }

并且对 tagNode ，进行

输出

dom = {
  type: 'html',
  val: null,
  children: [
    {
      type: '<p>',
      val: 'hello',
      children: []
    },
    {
      type: '<div>',
      val: null,
      children: [
        {
          type: '<h2>',
          val: null,
          children: [
            {
              type: '<small>',
              val: 'world',
              children: []
            }
          ]
        },
        {
          type: '<span>',
          val: '!',
          children: []
        }
      ]
    }
  ]
}

# 语法分析器实现

# 递归下降的 LL 算法

# 递归下降实例

# 设计输入格式

# 实现

语法分析器实现

递归下降的 LL 算法

递归下降实例

设计输入格式

实现