Stanford Compiler Week 3 Parsing and Top-Down Parsing

课程主页:

https://www.edx.org/course/compilers

课程视频:

https://www.bilibili.com/video/BV1NE411376V?p=20&t=6

这次回顾第三周的内容,这一周主要解析以及自顶向下的解析。

解析介绍

引子

  • 正则语言
    • 被广泛使用的最弱的形式语言
    • 很多应用

考虑语言:

该语言表示成对左右括号:

正则语言无法表达上述语言,因为正则语言只能统计$\text{cout mod } k$的值。

解析的输入输出

  • 输入:来自词法器的符号序列
  • 输出:程序的解析树

例子

  • COOL语言代码

    1
    if x = y then 1 else 2 fi
  • 解析器输入

    1
    IF ID = ID THEN INT ELSE INT FI
  • 解析器输出

解析器和词法器的比较

阶段 输入 输出
词法器 字符构成的字符串 符号构成的字符串
解析器 符号构成的字符串 解析树

上下文无关语法

  • 并非所有的符号字符串都是程序

  • 解析器必须区分有效和无效的符号字符串

  • 我们需要

    • 描述有效符号字符串的语言
    • 区分有效和无效的符号串的方法
  • 程序设计语言具有递归结构

    1
    2
    3
    if EXPR then EXPR else EXPR fi
    while EXPR loop EXPR pool

  • 上下文无关语法(Context-free grammars,CFG)是这种递归结构的自然表示法

CFG

  • CFG包括:

    • 终止符号集合:$T$

    • 非终止符号集合:$N$

    • 起始符号集合:$S,S\subset N$

    • Productions规则集合:$X\to Y_1\ldots Y_N,X\in N, Y_i \in N\cup T\cup \{\epsilon\}$

      • Productions可以被视为规则:

CFG流程

  1. 从只包含起始符号$S$的字符串开始
  2. 将字符串中任何非终止符$X$替换为某些production $X\to Y_1\ldots Y_n$
  3. 重复(2),直到没有非终止符

例子

例1

回到语言

productions:

$N,T$:

例2

简单算数表达式:

production:

CFG的语言

设$G$为上下文无关语法,起始符号为$S$,则$G$的语言$L(G)$为:

  • 终止符之所以被称为终止符,是因为没有替代规则
  • 终止符一旦产生,就成为永久终止符
  • 终止符应该是语言的符号

注意,这里$\overset \star\rightarrow$是指如下含义:

习题

选择2,3项。

总结

CFG的想法是一个很大的步骤。但是:

  • 语言中的成员身份是“是”或“否”;也需要输入的解析树
  • 必须优雅地处理错误
  • 需要实现CFG
  • 语法的形式很重要
    • 很多语法都产生同一种语言
    • 工具对语法敏感

Derivations

定义

derivation是production序列:

derivation可以画成一棵树。

  • 开始符号是树的根
  • 对于production$X\to Y_1\ldots Y_n$,将子节点$Y_1\ldots Y_n$添加到节点$X$

例子

  • 语法

  • 字符串

    derivation如下:

  • 该示例是一个最左边派生
    • 在每一步中,更换最左的非终止符
  • 有一个等同的概念,最右派生

最右派生例子:

请注意,这里的最右派生和最左派生具有相同的解析树。

解析树

  • 解析树
    • 叶节点是终止符
    • 内部节点是非终止符
  • 叶子的中序遍历是原始输入
  • 解析树显示操作的关联,输入字符串不显示这点

习题

选择最后一项。

总结

  • 我们不只是对$s\in L(G)$感兴趣
    • 我们需要一个$s$的解析树
  • 派生定义了一个解析树
    • 但是一个解析树可能有很多派生
  • 最左派生和最右派生在解析器实现中很重要

歧义

引子

依然考虑如下例子

  • 语法
  • 字符串该字符有两个解析树:

因此产生了歧义性。

  • 如果语法具有多个字符串的解析树,则语法是有歧义的
    • 等价于,对于某个字符串,存在多个最右或最左派生
  • 歧义是不好的
    • 部分程序的含义是定义不明确的

处理方法

  • 有几种方法可以处理歧义

  • 最直接的方法是将语法重写为无歧义的

  • 强制*优先于+

语法重写后的结果如下:

例子

  • 考虑语法

  • 表达式

    有两个解析树:

  • 如果else匹配最近的没有匹配的else

  • 那么此时解析树为

处理方法

  • 无法自动将有歧义的语法转换为没有歧义的语法
  • 小心使用,歧义可以简化语法
    • 有时允许歧义会产生更自然的定义
    • 我们需要消除歧义的机制
  • 不是重写语法
    • 而是使用更自然的(有歧义的)语法
    • 其实包括消除歧义的声明
  • 大多数工具允许优先和关联性声明来消除语法歧义

例子

  • 考虑语法:
  • 歧义:int+int+int有两棵解析树

  • 左关联声明:%left +

    • 在这种情形下,只会取第一种解析树
  • 考虑语法:

    • 字符串int+int*int

  • 两颗树分别对应优先级声明:%left和%left *

习题

应该选前两项。

第一项:$\text{aba}$

第二项:$\text{id+id+id}$

选第一项。

错误处理

  • 编译器的作用是

    • 检测无效程序
    • 翻译合法程序
  • 各种可能的错误(例如,在C中有如下例子:)

  • 错误处理程序应

    • 准确、清晰地报告错误
    • 快速从错误中恢复
    • 不降低有效代码的编译速度

紧急(panic)模式

  • 紧急模式是最简单、最流行的方法

  • 当检测到错误时:

    • 丢弃符号,直到找到具有明确角色的符号
    • 从那里继续
  • 查找同步符号

    • 通常为语句或表达式结束符
  • 考虑一下这个错误的表达式

  • 紧急模式恢复:

    • 跳到下一个整数,然后继续。
  • Bison:使用特殊的终止错误来描述要跳过多少输入

错误productions

  • 错误productions
    • 指定语法中已知的常见错误
  • 例子:
    • 写$5\text{x}$而不是$5\text{*x}$
    • 添加production $\text{E} \rightarrow \ldots \mid \text{E}\text{E}$
  • 缺点
    • 使语法复杂化

错误处理

  • 想法:找到一个正确的“附近”程序
    • 尝试符号插入和删除
    • 彻底搜索
  • 缺点:
    • 难以实现
    • 减慢正确程序的解析速度
    • “附近”不一定是“预定”的程序

总结

  • 过去
    • 缓慢的重新编译周期(甚至每天一次)
    • 在一个周期内找到尽可能多的错误
  • 现在
    • 快速的重新编译周期
    • 用户倾向于每周期更新一个错误
    • 复杂的错误恢复不那么引人注目

抽象语法树(Abstract syntax trees)

  • 解析器跟踪符号序列的派生

  • 但编译器的其余部分需要程序的结构表示

  • 抽象语法树

    • 类似解析树,但忽略一些细节
    • 缩写为AST

例子

  • 考虑语法
  • 以及字符串
  • 词法分析后(符号列表)
  • 在解析过程中,我们构建了一个解析树

  • 该解析树:

  • 跟踪解析器的操作
  • 捕捉嵌套结构
  • 但信息太多

    • 括号
    • 单个后续节点
  • AST也捕获嵌套结构

  • 抽象出具体语法

    • =>更紧凑、更易用
  • 编译器中重要的数据结构

递归下降解析

  • 解析树按如下方式构造

    • 从顶部
    • 从左到右
  • 终止符在符号流中的出现顺序:

例子

  • 考虑语法

  • 符号流是:$\left(\text { int}_{5}\right)$

  • 从顶层非终止符$\text{E}$开始

    • 按顺序尝试$\text{E}$的规则

首先得到如下匹配:

该匹配错误,所以回溯。

该匹配依然错误,再次回溯。

匹配成功。

习题

选第二项。

递归下降算法

  • 依然考虑语法:
  • 让TOKEN作为符号类型

    • 特殊符号INT,OPEN,CLOSE,PLUS,TIMES
  • 让全局next指向下一个输入符号

  • 定义用于检查以下项是否匹配的布尔函数:

    • 一个给定的符号终止符:

      1
      bool term(TOKEN tok) { return *next++ == tok; }
    • $S$的第$n$个production:

      1
      bool Sn() { … }
    • 尝试$S$的所有production:

      1
      bool S() { … }
      • 对于production $\text{E}\to\text{T}$:

        1
        bool E1() { return T(); }
      • 对于production $\text{E}\to\text{T}+\text{E}$:

        1
        bool E2() { return T() && term(PLUS) && E(); }
      • 对于$\text{E}$的所有production(带回溯):

        1
        2
        3
        4
        bool E() {
        TOKEN *save = next;
        return (next = save, E1())
        || (next = save, E2()); }
      • 非终止符$\text{T}$的函数:

        1
        2
        3
        4
        5
        6
        7
        8
        9
        bool T1() { return term(INT); }
        bool T2() { return term(INT) && term(TIMES) && T(); }
        bool T3() { return term(OPEN) && E() && term(CLOSE); }

        bool T() {
        TOKEN *save = next;
        return (next = save, T1())
        || (next = save, T2())
        || (next = save, T3()); }
  • 为了启动解析器

    • 初始化next,将其指向第一个符号
    • 调用E()
  • 易于手工实现

习题

选择第二第四项,第二项错在$\text{&&}$,最后一项错在$\text{T}_1$。

递归下降算法的局限性

例子

依然考虑前一个例子:

假设输入为

函数的调用顺序为

  1. E
  2. E1
  3. T1

T1返回true,函数调用终止,从而解析失败(后续部分无法解析)。

分析

  • 如果非终止符$X$的production成功
    • 无法回溯,从而无法尝试其他production
  • 通用递归下降算法支持全回溯
    • 能够实现任何语法
  • 提出的递归下降算法不通用
    • 但手动执行容易
  • 对于任何非终止最多只有一个production的语法,足以满足要求
  • 可以重写示例语法,以配合所提出的算法使用
    • 通过左分解,未来视频的主题

左递归

  • 考虑production $\mathrm{S} \rightarrow \mathrm{S} \mathrm{a}$

    1
    2
    bool S1() { return S() && term(a); }
    bool S() { return S1(); }
  • 陷入无限循环

  • 左递归语法有一个非终止符$\text{S}$

  • 在这种情况下,递归下降不起作用

    • 陷入无限循环

例子

  • 考虑左递归语法
  • $S$生成所有以一个$\beta$开始,后面跟任意数量$\alpha$的字符串

  • 可以使用右递归重写

  • 一般的
  • 所有从$\text{S}$派生的字符串都以$\beta_1,\ldots,\beta_m$中的一个开始,后面跟几个$\alpha_1,\ldots\alpha_n$

  • 重写为

  • 语法

    也是左递归的,因为

  • 这种左递归也可以消除

  • 一般算法见龙书

习题

选第三项。

总结

  • 递归下降
    • 简单通用的解析策略
    • 必须首先消除左递归
    • 但这可以自动完成
  • 用于生产编译器
    • 例如gcc

本文标题:Stanford Compiler Week 3 Parsing and Top-Down Parsing

文章作者:Doraemonzzz

发布时间:2020年09月12日 - 22:46:00

最后更新:2020年09月21日 - 23:40:58

原始链接:http://doraemonzzz.com/2020/09/12/Stanford Compiler Week 3 Parsing and Top-Down Parsing/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。