[Other] 递归下降解析器(模式)

很多人工编写的解析器,会采用 “递归下降” 的解析方法,例如 typescriptswcbabel-parser 等等。

这可能是 “递归下降” 方法所编写的代码,更利于调整,结构上更加清晰。
虽然这种方法无法处理 左递归文法
但大多数场景我们都可以采用 左递归消除 的办法,对文法进行改写。

本文用几个例子,简单总结一下 “递归下降解析器” 的常用写法。

一、list 解析器

1. 字符串、文法 和 语法树

递归下降解析器是一种自上而下的解析器,由一组相互递归的程序(或等价的非递归程序)构建而成,其中每个程序都实现了文法中的一个非终结符。
—— 递归下降解析器

这样说可能比较抽象,我们先写一个简单的 list 解析器,来说明情况。
完整的代码如下:github: thzt/tiny-parser#list

它可以用来解析如下字符串:

(ab cd 
  (ee ff gg)
)

文法如下:

list       = '(' elements ')'
elements   = element | element elements
element    = identifier | list

identifier = [a-z]+
whitespace = ' ' | '\n'

它是指,list 由 括号包围的 elements 构成,而 elements 则是由 一个或多个 element 组成。
最后,element 或者是 一个标识符 identifier,或者是一个 list(又回到了 list,表明结构上是递归的)。

比如,上文提到的字符串,

(ab cd 
  (ee ff gg)
)

ab cd ee ff gg 都是 identifier(ee ff gg) 是一个 list
(ab cd (ee ff gg)) 也是一个 list

解析的过程,其实是根据文法,将字符串整理成数据结构的过程。
整理后的数据结构(语法树)如下,


题外话:
我们看到 字符串 在结构上是递归的,所以很自然的我们会想到,用递归的程序来解决问题。这个其实是跟 上下文无关语言的 泵引理 有关,它指出了 上下文无关语言 在结构上的自相似性。上下文无关语言中的字符串只要足够长,它的某一部分总能 “坍缩” 到相同的非终结符上去(即语法树的树高不会无限增加)。

2. TypeScript & namespace

为了方便编写,我们使用了 TypeScript,且用到了不太常见的 namespace 特性,
所以这里多解释一下,

namespace Parser {
  // ...
}

namespace 会编译成一个立即执行的函数(一个闭包),
namespace 导出(export) 的函数,就是闭包向外透出的值。
编译产物 可参考这里 github: thzt/tiny-parser#list out/index.js

var Parser;
(function (Parser) {  // namespace 的编译结果
    // ...
    function parse(code) {  }
    Parser.parse = parse;  // 导出的 parse 方法
    // ...
})(Parser || (Parser = {}));

3. 解析器的结构

解析器 主要有 4 个部分组成:

  • (1)解析器的初始化:源码、初始位置、结束位置
  • (2)递归解析的入口:开始调用一组互相递归的函数,从 parseList 开始
  • (3)一些互相递归的函数:parseList/parseElements/parseElement
  • (4)词法分析器:用来返回 token(单词)

可参考如下代码:github: thzt/tiny-parser#list src/parser.ts

namespace Parser {
  let sourceText: string;
  let pos: number;
  let end: number;
  let token;

  export function parse(code) {
    // 1. 解析器的初始化
    sourceText = code;
    pos = 0;
    end = sourceText.length;

    // 2. 递归解析的入口
    nextToken();
    assert(SyntaxKind.LeftBracket);
    const body = parseList();
    nextToken();
    assert(SyntaxKind.EndOfFile);

    return body;
  }

  // 3. 一些互相递归的函数:parseList/parseElements/parseElement
  function parseList() {  }
  function parseElements() {  }
  function parseElement() {  }

  // 4. 词法分析器
  function nextToken() {  }
}

这里值得一提的是,互相递归的那些函数,其实是跟 文法中的 产生式 一一对应的。

list       = '(' elements ')'                   -> parseList
elements   = element | element elements         -> parseElements
element    = identifier | list                  -> parseElement

所以只要我们写出 文法,这些互相递归的函数也就有了。
这也是很多 递归下降的 “解析器生成器” 常用的代码生成办法,例如 peg.js

4. 词法分析器(nextToken)

以上代码中的词法分析器,就是一个函数 nextToken,其实非常的容易编写。
github: thzt/tiny-parser#list src/parser.ts#nextToken
总共也就 30 多行代码,

function nextToken() {
  while (true) {
    if (pos >= end) {
      return token = createNode(SyntaxKind.EndOfFile, pos, pos, null);
    }

    let ch = sourceText.charAt(pos);
    switch (ch) {
      case '(':
        return token = createNode(SyntaxKind.LeftBracket, pos++, pos, '(');

      case ')':
        return token = createNode(SyntaxKind.RightBracket, pos++, pos, ')');

      case ' ':
      case '\n':
        pos++;
        continue;

      default:
        if (isIdentifierStart(ch)) {
          return token = scanIdentifier();
        }

        return token = createNode(SyntaxKind.RightBracket, pos++, pos, ch);
    }
  }
}

它会逐个字符进行判断,将不同类型的 “单词” 切分开,例如,

(ab cd 
  (ee ff gg)
)

会被切分成:(abcd(eeffgg)) 这样一系列 token。
效果是:ab 被合并成了一个,空格和换行符被忽略了。

5. 互相递归的函数

上文我们提到了互相递归的函数:parseList/parseElements/parseElement,
是跟文法中的 产生式 一一对应的,

list       = '(' elements ')'                   -> parseList
elements   = element | element elements         -> parseElements
element    = identifier | list                  -> parseElement

其实,不止是函数名,函数内部的编写方式,也可以根据产生式来生成(有套路)。
我们分别来看一下。

  // list       = '(' elements ')'
  function parseList() {  // 进来时当前 token 是 '('
    const elements = parseElements();  // 这里解析 `elements`
    const rb = nextToken();  // 这里的 token 为 `)`

    // 以上解析完了 `(` elements ')',返回。我们的 ast 中只保存了 elements
    return elements;
  }
  // elements   = element | element elements
  function parseElements() {
    const elements = [];  // 由一个或多个 element 组成,所以用个数组来存

    while (true) {
      nextToken();
      if (isElementsTeminate()) {  // 向前看一个字符,判断后面还是不是 element
        break;
      }

      const element = parseElement();  // 解析 element
      elements.push(element);
    }

    return elements;  // 将 elements 数组返回
  }
  // element    = identifier | list
  function parseElement() {
    if (token.kind === SyntaxKind.LeftBracket) {  // 分支判断
      return parseList();  // 如果是 list 就是递归调用 parseList
    }

    console.assert(token.kind === SyntaxKind.Identifier);  // 否则就把标识符返回
    return token;
  }

parseList 会调用 parseElementsparseElements 会调用 parseElement
最后 parseElement 又有可能递归调用 parseList
这就是一组互相递归的函数了。

二、html 解析器

解析完了最简单的 list 之后,我们来看一个较为复杂的例子,

<div id="tiny" class="parser">
  <span>
    abc
  </span>
</div>

文法如下:

html       = '<' identifier props '>' html '</' identifier '>' | identifier
props      = '' | identifier '=' '"' identifier '"'

identifier = [a-z]+
whitespace = ' ' | '\n'

解析器仍然是由 4 部分组成:

  • (1)解析器的初始化
  • (2)递归解析的入口
  • (3)一些互相递归的函数
  • (4)词法分析器
    所不同的是,互相递归的函数变了,变成了 parseHtml/parseProps
namespace Parser {
  let sourceText: string;
  let pos: number;
  let end: number;
  let token;

  export function parse(code) {
    // 1. 解析器的初始化
    sourceText = code;
    pos = 0;
    end = sourceText.length;

    // 2. 递归解析的入口
    nextToken();  // <
    assert(SyntaxKind.LeftBracket);
    const html = parseHtml();

    nextToken();  // eof
    assert(SyntaxKind.EndOfFile);

    return html;
  }

  // 3. 一些互相递归的函数:parseList/parseElements/parseElement
  function parseHtml() {  }
  function parseProps() {  }

  // 4. 词法分析器
  function nextToken() { }
}

完整的代码:github: thzt/tiny-parser#html

三、四则运算 解析器

文法:

Expr -> Term | Term + Expr
Term -> Factor | Factor * Term
Factor -> NUMBER | ( Expr )

字符串:

((1 + 2) * 3 + 4) * (5 + 6)

语法树:


完整的代码:github: thzt/tiny-parser#arithmetic

参考

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 203,772评论 6 477
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 85,458评论 2 381
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 150,610评论 0 337
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 54,640评论 1 276
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 63,657评论 5 365
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 48,590评论 1 281
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 37,962评论 3 395
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 36,631评论 0 258
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 40,870评论 1 297
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,611评论 2 321
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,704评论 1 329
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,386评论 4 319
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 38,969评论 3 307
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,944评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,179评论 1 260
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 44,742评论 2 349
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,440评论 2 342

推荐阅读更多精彩内容