decaf-doc
  • Introduction
  • pa1a
    • 实验内容
    • lalr1使用指导
      • 编写lexer
      • impl块的可选属性
      • 产生式和语法动作
      • 解决冲突
      • 一个完整的例子
    • 抽象语法树
    • 框架中部分实现的解释
    • 文件结构
  • pa1b
    • 实验内容
    • lalr1使用指导
    • 错误恢复
    • 文件结构
  • pa2
    • 实验内容
    • 语义分析
    • 符号表
    • 语句的返回类型
    • visitor模式
    • 框架中部分实现的解释
  • pa3
    • 实验内容
    • 中间代码
    • 中间代码中的类型信息
    • 运行时存储布局
    • 面向对象机制
    • tacvm介绍
  • pa4
    • 实验内容
    • 基本块
    • 数据流分析概述
    • 数据流优化概述
    • 公共表达式提取
    • 复写传播
    • 常量传播
    • 死代码消除
  • pa5
    • 实验内容
    • 图着色基本原理
    • 改进干涉图节点
    • 着色算法
    • 预着色节点
    • 干涉图节点合并
    • 调用约定
Powered by GitBook
On this page

Was this helpful?

  1. pa1b

lalr1使用指导

Previous实验内容Next错误恢复

Last updated 5 years ago

Was this helpful?

本次pa会用到lalr1的ll(1)文法部分,大多数概念与之前是相同的,这里只介绍不一样的部分。可参考一下。

当用作ll(1)文法的parser generator时,lalr1没有提供利用优先级和结合性来解决冲突的机制,所以运算符的优先级和结合性在这里都没有意义了,大家需要手动地用产生式的组合来描述"优先级和结合性"这种性质。类似于左递归和左公因子之类的问题也需要手动解决。对于冲突的产生式,lalr1会汇报冲突警告,并且使用出现在最前面的产生式。

decaf语言由于允许if语句的else分支为空,所以不是严格的ll(1)语言。在解析非终结符MaybeElse时遇到终结符Else时,有两个产生式,即MaybeElse -> Else Stmt和MaybeElse ->,都可以被选择,lalr1会汇报一个警告并且选择前者。这里实现的逻辑是"最近悬挂if匹配",常见的编程语言中也都是这个逻辑。

ll(1)的lexer部分与之前基本一样,不过在#[lex(TomlOfLexer)]中的priority字段写一个空数组即可,反正写了也用不到。

生成的代码包含了lalr(1)版本中的东西,即"两个enum,即TokenKind和StackItem,两个struct,即Token和Lexer,并为你希望成为parser的struct提供一个parse函数"。此外还有:

  1. u32常数NT_NUM,表示非终结符的数目

  2. 包在lazy_static!中的元素为HashSat<u32>的数组FOLLOW,用非终结符编号作下标访问,得到它的follow集合

  3. 包在lazy_static!中的元素为HashMap<u32, (u32, Vec<u32>)>的数组TABLE,用非终结符编号作下标访问,得到它的预测分析表。预测分析表是一个终结符到(产生式编号, 产生式右端项内容)的映射,其中产生式右端项内容,即Vec<u32>,就是每个右端项的编号

  4. 为你希望成为parser的struct添加了一个fn act(&mut self, prod: u32, value_stk: Vec<StackItem<'p>>) -> StackItem<'p>函数,其中prod即产生式编号,value_stk是每个右端项对应的解析结果,返回值为以value_stk为参数执行prod对应的语法动作后的结果

相比于lalr(1)版本中的StackItem,这里的StackItem增加了一个variant:StackItem::_Fail,表示解析失败的文法符号。如果value_stk中有任何一个StackItem::_Fail,则act函数的返回值就会是StackItem::_Fail。

利用#[verbose(OutputPath)]可以查看每个文法符号和产生式的编号,文法符号编号保证所有非终结符的编号都在0..NT_NUM范围内,所有终结符都在NT_NUM..范围内。如pa1a的文档中所描述的一样,如果设置了这个属性,那么生成出来的代码中会包含show_token和show_prod这两个函数,分别接受文法符号的编号和产生式的编号,返回表示对应的文法符号的名字和产生式内容的字符串。在pa1a中这个功能其实没有什么用处,但在pa1b中你也许可以利用它来调试。

parse函数会转发调用一个未提供实现的_parse函数,_parse需要利用上面提供的这些东西来实现一个支持一定程度的错误恢复的parser。

一个解析四则运算表达式的基于ll(1)文法的parser小例子