Summary:
- 上下文无关文法(CFG)
- 推导和语法树
- 语法制导翻译
- 翻译模式
- Yacc 编程
- 自顶向下预测分析
- 设计实现预测分析器
- 简单词法分析
- 代码生成
语法定义
上下文无关文法(CFG):描述源程序的语法结构
CFG 的四个部分:
- 终结符 terminal:不可被取代、不可拆分的基本符号(e.g. if, else)
- 非终结符 nonterminal(e.g. expr, stmt)
- 产生式 production 左部只有一个非终结符,右部是非终结符
- 唯一一个特定的非终结符:开始符号 start symbol
定义几个概念:
- Σ:有穷字母表,其中元素(符号)构成符号串
- 空字 ε:不含任何符号的序列
- Σ*:符号串全体,包括空字
- φ:空集{},注意区分空集和空字
- 符号串子集的(笛卡尔)积,注意顺序
- n 次积和 0 次积
- 闭包 closure \(V*\) 和正则闭包 \(V^+\)
- 终结符集合 \(V_T\),非终结符集合 \(V_N\),产生式集合 \(P\),开始符号 \(S\)
符号约定:
- expr, digit
- 终结符:数字、运算符、黑体
- 非终结符:斜体
- |= 或,候选式
推导
推导 derivation:从 start symbol 开始,用 production 右部替换左部,反复替换得到最终的单词串
语法分析树 parse tree:从根节点开始,每个节点应用 production 产生子节点
- 叶节点从左到右构成树的输出 yield
- 定义无歧义语法消除 ambiguity(同一个单词有多棵语法树)
- 运算符结合律:左结合 +,-,*,/;右结合 ^,=
- 运算符优先级
- 结合优先级的表达式文法:expr, term, factor
语法制导翻译
确定每个语法结构如何翻译后,把翻译方法转换为语义规则/语义动作,附着在 production 上。
或:一边解析 parse 字符串一边干别的事 (构造语法树/直接生成中间代码/类型检查…),语法分析起支配作用
e.g.表达式 E 的后缀形式 Postfix (E)生成:
when E = E1 op E2:
Postfix(E) = Postfix(E1 op E2) = Postfix(E1) Postfix(E2) op
语法制导定义
syntax-directed definitions (SDD):对 CFG 的推广
- 每个文法符号关联一组属性
- 每个 production 关联一组语义规则 semantic rule,这些规则用来计算该 production 中各个符号的属性值
e.g.后缀表达式的语法制导定义
文法符号的属性:
- 综合属性 synthesized attribute:节点综合属性由其子节点/自身属性决定,bottom-up 计算(后序遍历、深度优先)
- 继承属性 inherited attribute:节点属性由其父节点/自身/sibling 节点属性决定(终结符没有继承属性)
语法制导翻译的基本过程:
- 输入单词串,生成语法分析树
- 节点 n 标记为 \(X\),其属性为 \(a\),写作 \(X.a\)
- 利用 \(X\) production 的语义规则计算节点 n 的 \(X.a\) 的值
- 注释语法分析树 annotated parse tree
语法制导翻译模式
syntax-directed translation scheme (SDT):在 production 中嵌入语义动作,计算文法符号的属性值
语义动作在 production 中的位置就是在语法树中的位置,也就是动作执行的顺序
考虑属性的依赖关系,确定嵌入位置。
rest -> + term {print('+')} rest
带语义动作的语法分析树:一边进行语法分析,一边从左至右执行语义动作
或:后序遍历语法树,遍历到语义动作节点执行相应代码 (属性计算/结果输出/…)
Yacc 程序
yacc/bison 程序结构(*. y,分三部分,%%分隔)
/*P1: declarations 定义段*/
%{
/*
定义段一般分两种:
1. C语言编写的,包括头文件include、宏定义、全局变量定义、函数声明等
2. 声明文法的终结符和非终结符
常用的 Bison 标记声明有:%token %union %start %type %left %right %nonassoc 等。
- %token TOKEN1 TOKEN2 定义使用了哪些终结符
- %left % right %nonassoc 同上,表明了结合性,先定义的优先级低
*/
%}
%%
/*P2: grammar rules 规则段(rule & action)*/
A: a1 {语义动作1}
|a2 {语义动作2}
|...
|an {语义动作n}
|b //没有{...}时就使用缺省的语义动作
; //production 结束标记
// 语义动作一般在产生式右部分析完,归约动作进行前执行
// 动作中$1指右边第一个标记的值,$2表示右边第二个标记的值,依次类推;$$表示归约后的值(左边的值)
%%
/*P3: supporting C routines 用户辅助程序段(C函数)*/
// 为C代码,会被原样复制到C文件中,一般自定义一些函数
e.g.简单表达式计算
语法分析
自顶向下 top-down:从 start symbol 开始,不断进行推导,直到推导所得的符号串与输入串相同为止。
预备概念:LL (1) 文法是什么?
第一个 L:left to right,从左向右扫描输入的 token 序列;
第二个 L:leftmost derivation,分析时从文法最左边开始进行推导;
(1):只需要向右看一个符号就可以决定推导方向。
LL (1)是如何解析 token 序列的?
- 用 parsing queue 的第一个元素和 input 的第一个 token 匹配;
- 如果第一个元素是非终结符(可以继续迭代),就找到对应的 production 并替换,回到步骤 1,若找不到这样的 production,报错;
- 如果第一个元素是终结符(无法继续迭代),则和 input 的第一个 token 匹配,二者都消去,回到步骤 1,若匹配不上,报错;
- parsing queue 和 input 都为空时,匹配成功,结束。
预备工作:消除文法的二义性,消除左递归,提取左公共因子,计算 FIRST 集合和 FOLLOW 集合,判断文法是否为 LL (1)型文法;如果是,就可以用下面 LL (1)型文法的两个具体实现进行分析。
一些额外问题:
- 如何消除左递归?
改写文法
A -> Aa|b 改写为
A -> bR; R -> aR|ε
- 如何判断文法是否是 LL (1)型?
递归下降分析
- 对节点选择一个 production,利用右部构造子节点;继续选择下一个没有扩展的子节点,迭代
- 扫描,与当前输入单词逐个比较,不匹配就回溯
预测分析 predictive parsing
递归下降的问题:回溯花费的时间过多,可能会组合爆炸
-> 如何在每步都确定唯一可能的候选式?
根据下一个输入单词(超前单词)选择
- production 选择
- 对所有 production 构造 FIRST 集,和当前第一个 token 比对,有匹配就可以替换;
- 如果有冲突(FIRST 交集),则预测分析不适用;
- 若当前非终结符可以被替换为空(即存在 S->ε),且替换后 parsing queue 的下一个终结符(构造 FOLLOW 集)可以和当前第一个 token 匹配,就可以替换。
- production 的使用
- 对非终结符,调用对应的递归函数;
- 对终结符,和当前第一个 token 比较,若匹配就继续读,否则报错。
问题:如何构造 FIRST 集和 FOLLOW 集?
A->a, A->b, FIRST (a) 和 FIRST (b) 不能有交集
参考资料:你知道LL(1)吗
结合翻译模式:将语义动作复制到预测分析器里
位置:语义动作位于语法符号 X 之后,就将其紧接在处理 X 的代码之后;如果位于 production 开始,就复制到函数最前面
词法分析
语法分析是主体,词法分析器作为前者的调用接口,调用一次返回一个 token
平凡算法:根据下一字符判断进入哪个 token 的识别
- 去除空白和注释
- 常量
- 标识符、关键字识别
- <id, 符号表项指针>
- 关键字 keyword、保留字 reserved
- 运算符,每个独自作为一类单词
符号表
字典保存单词的实例和索引 token
insert(s,t) 单词t的实例s(字符串)插入符号表,返回t
t 可以是 id 或关键字(if,else)
lookup(s) 查找字符串s对应的表中索引
一种实现方式:指针指向符号串存储的位置(紧凑存储)
带符号表功能的词法分析器:先查询 lexbuf 是否已经在符号表里,没有再插入
代码生成
语法符号的属性 - 汇编代码
上层语法结构的代码 - 下层语法结构的代码,再拼接一些汇编指令
expr -> expr1 + term {
expr.addr = newtemp;
expr.code = expr1.code || term.code ||
"MOV EAX, expr1.addr
MOV EBX, term.addr
ADD EAX, EBX
MOV expr.addr, EAX"
}
stmt -> id := expr 赋值
{stmt.code = expr.code ||
"MOV EAX, expr.addr
MOV id.addr, EAX"}
stmt -> if(expr) stmt1 { 控制流
out = newlabel;
stmt.code = expr.code || 'jz' out || stmt1.code || out
}
stmt -> while(expr) stmt1 {
test = newlabel; out = newlabel;
stmt.code := test || expr.code || 'jz' out ||
stmt1.code || 'jmp' test || out
}
翻译模式:
stmt -> if
expr {out:=newlabel; print('jz', out);}
then
stmt1 {print(out);}
stmt -> while {test:=newlabel, print(test)}
expr {out:=newlabel; print('jz', out);}
then
stmt1 {print('jmp', test); print(out);}