【CS 143 Compiler 编译原理】Assignment 3:语法分析
这篇文章主要总结 完成 这次 Assignment 所需 知识和思路的总结
代码地址:https://link.zhihu.com/?target=https%3A//github.com/casual-lab/stanford-cool
Bison 语法
cool.y
文法定义文件总体架构
%{
Prologue
%}
Bison declarations
%%
Grammar rules
%%
Epilogue
注释:/* ... */
或 //
(单行注释)
Prologue 和 Epilogue 分别是 原封不动地 复制到输出代码文件地开头和末尾.
Bison declaration
token kind names 终结符名称
Token kind names 就是 终结符 的名称。一个 %token
后可跟随定义 多个 终结符, 用 空格或回车隔开.
%token <tag>? ( id number? string? )+ ( tag ( id number? string? )+ )*
number
段是一个 token 间互不冲突的正整数. string
段是 别名, 在报错等场合使用
%union
声明块
用来声明 语义值 (semantic values) 可能的数据类型. 定义语法和 C 语言 union 相同. 语义也相同: 同时只能取其中一个值. 一个成员赋值, 其他成员会被覆盖。
语义值就是 每个 非终结符 的 Action 段 赋值给 $$
的值。代表了这个非终结符此处的语义值。
%union {
double val;
symrec *tptr;
}
上面表示定义一个 union , 两个可能的 (C 语言) 数据类型是 double
和 symrec *
. 这两个成员名称 会被 %token
, %nterm
和 %type
的 tag
字段使用 用来表示语义值类型。
非终结符 (type)
%type <tag> nonterminal…
<type>
是 在 %union
中定义的类型.
起始符
起始符默认是 Grammar Rules
段第一个 非终结符
也可以在 declaration
段 指定:
%start symbol
Grammar Rules
就是 写 产生式。产生式的左侧必须是 declaration 段声明过的 非终结符。
non_terminal
: rule1-components { action1 C code }
| rule2-components { action2 C code }
如
plus_consts : INT_CONST '+' INT_CONST
{ @$ = @3;
SET_NODELOC(@3);
$$ = plus(int_const($1), int_const($3));
}
通过 action 段,维护当前代码位置,定义连接 AST 新节点,以此生成抽象语法树 AST。
注意,$n
表示(包括终结符、非终结符的)第 n 个 Component 的值。如果是非终结符,则是其规约后赋值到 $$
的值,这里就是子树根节点。@n
表示第 n 个 Component 的代码位置。@$
在这里表示需要维护的当前代码位置。
抽象语法树
在本次 Assignment 中,parser 的输出是一个抽象语法树,是一个复杂数据结构。这一数据结构的 C++ 定义代码同样也是通过软件和少量定义代码生成的。
starter code 中,抽象语法树 是通过 cool-tree.aps
定义并使用 AST package 生成的。我们只需要理解 cool-tree.aps
中的定义,并使用。
类(Phyla)与构造器
Phylum(复数:Phyla)生物学上是指“门”,是比“纲”(class)高的分类。
每个 COOL 语法结构 都生成一个相应的 Cpp class。
cool-tree.aps
每个语法单元都是一个 Phylum ,相当于一个子树根。通过 Constructor 将多个 Phylum (a set of Phyla)聚合到一起 并连接到一个新的 Phylum 。Constructor 表示为一个 函数:
constructor method(name : Symbol;
formals : Formals;
return_type : Symbol;
expr: Expression) : Feature;
AST List
.aps
中的 LIST 数据结构 定义为 多个 Phylum:
phylum Formal;
phylum Formals = LIST[Formal];
LIST 类型有自带的 操作函数 和 方法。函数包括:
Classes nil_Classes();
Classes single_Classes(Class_);
Classes append_Classes(Classes,Classes);
方法 包括:
Class_ nth(int index);
int len();
int first();
Class_ next(int index); // 等同于 phyla->nth(index + 1)
bool more(int index); // phyla->len() - 1 > index
for(int i = l->first(); l->more(i); i = l->next(i))
{ . . . do something with l->nth(i) . . . }
Class 层次结构
分别有两方面层析结构:一是继承关系,二是组合关系。
继承关系,所有 Phyla 和 constructor 都有相应的 class。Phyla 类 直接继承 于 tree_node
,而 Constructor 继承于 适当的 Phyla(a class derived from the appropriate phyla)
所有的 tree_node
都有 函数 dump (用于打印)get_line_number
解决二义性:优先级和结合律
Bison 优先级特性的原理
两方面的 优先级:
- 非终结符 的优先级
- 产生式 的优先级:是由最后一个 非终结符的优先级 决定的
- 也可以用 上下文相关的 优先级 定义
如何起作用?
Bison 使用基于 移入/归约 的算法。每次决定 移入/归约 时,对比可被归约的 栈顶 对应的产生式 和 输入缓存的下一个 token(非终结符)的优先级。
- 非终结符 优先级高,则选择移入,否则归约。
- 优先级相同,则考虑同级间的结合律(left/right associative)
由于非终结符在输出上相当于一个子树,因此 终结符 所谓的结合,就是将两个子树连接到一起。右结合(right-associative)就是优先将右侧的子树连接起来。本质上是右推导(优先展开最右侧非终结符)的逆过程。效果与右推导等价。
任何产生式都有 优先级。但存在 非终结符 没有优先级。如果没有优先级,默认移入。
优先级定义方法
四种声明 都是定义 优先级 的:%left/%right/%precedence/%nonassoc
通过定义的先后次序定义优先级:
/* Precedence declarations go here. */
%left ASSIGN
%left NOT
%nonassoc LE '<' '='
%left '+' '-'
%left '*' '/'
%left ISVOID
%left '~'
%left '@'
%left '.'
如上 ‘.’ 优先级最高,ASSIGN 优先级最低,而 ‘+’ 与 ‘-’ 、‘*’ 与 ‘/’ 优先级分别相同。
但四种声明 在定义优先级的基础上,定义结合律。left / right 分别是同优先级非终结符之间
错误处理
Bison 中的 错误非终结符 error:一个特殊的 终结符。如果 error 入栈,自动触发错误处理程序,调用 yyerror(char *s)
。这一函数可以在 Epilogue 段定义。
举例:
stmts:
%empty
| stmts '\n'
| stmts exp '\n'
| stmts error '\n'
当在 exp 之中发现错误,则弹出并丢弃状态栈顶,直至到达可以接受 error 的状态;再不断丢弃输入缓存直至第一个 ‘\n’
(即恐慌模式 中的 同步语法单元)
其他经验总结
Let 的 二义性
实验文档种特意提到了 let 语句的二义性。具体来说是这样的情形:
let ... in expr + expr
可理解为 let ... in (expr + expr)
也可以理解为 (let ... in expr) + expr
根据 COOL manual 定义应该是前者更对。
已知已经了的定义优先级:
/* Precedence declarations go here. */
%right ASSIGN
%left NOT
%nonassoc LE '<' '='
%left '+' '-'
%left '*' '/'
%left ISVOID
%left '~'
%left '@'
%left '.'
假设此时 当前状态 为 LET ... IN expr · '+' expr
,
- 假设 IN 为最右侧终结符,IN 未定义优先级所以按默认移入,继续拓展 expr;
- 假设 IN 不在最右侧,但最右侧终结符 未定义优先级,同上;
- 假设 最右侧终结符 有优先级,则只有当状态为
LET ... IN expr '+-*/' expr · X
时 才可能存在 移入/归约冲突,才需要考虑优先级 (X 为某终结符)- 当 X 没有 优先级,按默认移入
- 当 X 优先级高,按规则移入
- 当 X 优先级低,状态归约为
LET ... IN expr · X
,X 仍然会移入。
所以问题自然解决。
重复元素与错误处理
下面用来表达 class 中多个 features:
class → c l a s s T Y P E { [ feature ; ] ∗ } \text { class }\to { class {\ } TYPE }\left\{[ \text { feature } ; ]^{*}\right\} class →class TYPE{[ feature ;]∗}
class : CLASS TYPEID '{' nullable_feature_list '}'
{ @$ = @1;SET_NODELOC(@1);
$$ = class_($2,idtable.add_string("Object"),$4,
stringtable.add_string(curr_filename)); }
;
nullable_feature_list
: /* epsilon-产生式 */
{ $$ = nil_Features(); }
| one_feature ';'
{ @$ = @1;SET_NODELOC(@1);$$ = single_Features($1); }
| nullable_feature_list one_feature ';'
{ @$ = @1;SET_NODELOC(@1);$$ = append_Features($1, single_Features($2)); }
| nullable_feature_list error ';'
{ @$ = @1;SET_NODELOC(@1);$$ = $1; }
| error ';'
{ @$ = @1;SET_NODELOC(@1);$$ = nil_Features(); }
;
one_feature
: one_attr {@$ = @1;SET_NODELOC(@1);$$ = $1;}
| one_method {@$ = @1;SET_NODELOC(@1);$$ = $1;}
;
对于可为空的重复元素,一般都会有一个间隔符(如这里的 “,”,或 block expression 的 “;”)
本质上这次 Assignment 是 恐慌式错误处理。
错误处理一般同时考虑两种情况如下:
nullable_feature_list
: nullable_feature_list error ';'
{ ... }
| error ';'
{ ... }
;
因为,当第一个 feature 就出现错误时,不断弹出状态,直至回到 ‘· nullable_feature_list’
的状态,然后 error 入栈。这样是无法进入 nullable_feature_list: nullable_feature_list error ';'
这一分支的。