期末周翻到编译原理第六章语法制导翻译那一节看着格外友好——几张表、几行产生式、几个属性等式好像比词法分析里的自动机、语法分析里的项目集规范族轻松不少。真到动手做课后题才发现坑埋得很深综合属性和继承属性到底怎么划界注释分析树画到一半不知道先算哪个节点左递归一消除语义动作就整体错位写进实验代码之后又发现分析栈和属性栈对不上号。语法制导翻译SDT这一章的难点从来不在概念本身而在于属性什么时候能算出值这件事。我把课本例题、课后题和实验里踩过的坑重新捋了一遍按做题时会卡在哪的顺序组织而不是照课本的概念顺序平铺正在啃这一章、准备应付课后题和课程设计的人可以对着看。1. 属性这件事先掰开综合属性与继承属性的真实分界线1.1 信息往哪流决定属性叫什么名字教材上给的定义很干净综合属性由子节点的属性值推出父节点的值继承属性由父节点或兄弟节点的属性值推出本节点的值。定义好背但做题时判断标准经常模糊。我自己的判断办法只有一句话——看这个属性的值是从树的哪个方向流过来的。从下往上汇聚、父节点靠孩子算出来的就是综合属性从上往下或者从左往右传过来、本节点靠长辈或左边的兄弟才能算出来的就是继承属性。拿最经典的声明语句文法举例D - T L T - int T - float L - L , id L - id这里T.type是综合属性它由int或float这些叶子直接算出来方向是自下而上。而L.inh就只能是继承属性因为L想知道这条声明语句声明的到底是什么类型这个信息来自它左边准确说是来自D - T L里的T属于横向传递。同一条产生式里T的属性往上走L的属性从左边接过来两种流向同时存在这就是这一章最容易混淆的地方。再补一个判断题的思路如果把某个属性当成综合属性去写求值等式写完发现等号右边出现了父节点的名字那它一定是继承属性你写错了。反过来如果等式右边出现了子节点的名字那它多半是综合属性。这个自检办法在考场上比背定义快。1.2 注释分析树不是画着玩的它是求值顺序的凭证课后题里有一大类是为下面的输入串构造注释分析树并给出各属性值。很多人包括我第一遍把注释分析树当成语法树旁边抄一遍属性名其实它的真正作用是把属性依赖关系画成一张有向图然后靠拓扑排序确定求值顺序。课本上那个依赖图dependency graph的概念落实到纸面上就是注释分析树加箭头。具体怎么做我总结成三步第一步老老实实画语法分析树叶子是终结符内部节点是非终结符这一步不能省省了后面全乱。第二步在每个节点旁边标出它拥有的属性名只写名字不写值比如L.inh、E.val。第三步按照产生式对应的语义规则从等号右边出现的属性向等号左边的属性画一条有向边边表示必须先算出前者。画完这张图之后如果图里没有环就存在一个拓扑序按这个序从左到右填值即可如果出现了环说明这组属性在单遍扫描里算不出来必须拆成多遍或者改写文法。这一点是很多课后题的隐藏考点——题目给一个看起来人畜无害的 SDD让你判断能否在自底向上分析中一趟算完答案往往是不能因为存在一条从父到子再回到父的环。举个具体的例子输入串int a, b文法用上面的声明语句。语法树是D下挂T(int)和LL下挂L、逗号、id(b)最底下的L挂id(a)。依赖图上T.type指向L.inh顶层那个顶层L.inh又指向它下面那个L.inh形成一条从左到右的链。这条链的方向和语法树的遍历方向一致所以深度优先、先序处理就能一路传下去不需要回溯。这个链的方向和遍历方向一致的直觉就是后面 L 属性定义的来源。1.3 S属性与L属性的判别靠的是往左看这一个动作S 属性定义S-attributed definition指的是只含综合属性的 SDD它的好处是可以在自底向上的分析过程中顺带算完规约一次算一次天然适配 LR 分析器。L 属性定义L-attributed definition放宽了一点允许继承属性存在但限制继承属性只能依赖三样东西父节点自己的继承属性、本节点左边的兄弟节点及其子孙的属性、本节点自己的属性不含通过子节点绕回来的。判别口诀我用了很久把产生式右部从左到右排好看每个符号的继承属性它的依赖来源是不是全在它左边或者它头顶上。只要有一个继承属性往右看了比如A - B C里B的某个继承属性依赖C的属性那它就不是 L 属性。这个限制听起来苛刻实际上几乎所有能自然写出来的语义规则都满足例外通常出现在需要向前看一个符号才能决定类型的场景里比如某些语言的隐式类型推导。为什么这个区分重要因为它直接决定了你的翻译方案能不能塞进现成的分析器框架。S 属性对应一边规约一边算LR 分析器天生支持L 属性对应深度优先一遍走完递归下降或者 LL 分析器能支持。超出这两者的 SDD要么多遍扫描要么改写文法把绕回来的依赖拆掉。考试里让你判断该 SDD 是否为 L 属性考的就是这个位置关系跟属性值本身怎么算没关系。2. 把语义动作塞进产生式位置选错的连锁反应2.1 SDD到SDT的三条对应关系语法制导定义SDD是产生式 语义规则的静态描述语法制导翻译方案SDT是产生式 语义动作的可执行版本动作用花括号包起来嵌在产生式右部。从 SDD 翻成 SDT本质上就是决定每个语义动作放在产生式体的哪个位置。规则只有三条但每条背后的理由值得说清楚。第一条只有综合属性时动作一律放产生式最右端。原因是综合属性的值要等右部所有子符号都算完才能算动作放在末尾正好在所有孩子都处理完、准备规约的时刻执行时机刚刚好。比如E - E1 T { E.val E1.val T.val }这个动作必须在E1和T都规约完之后才执行放末尾是唯一正确的位置。第二条有继承属性且满足 L 属性时动作插在右部符号之间位置由依赖关系决定。要传给某个符号的继承属性动作必须放在那个符号之前要用到某个符号的综合属性动作必须放在那个符号之后。两头都要满足位置就唯一确定了。比如D - T { L.inh T.type } L动作夹在T和L中间因为它要用T的结果又要把结果交给L。第三条不满足 L 属性时无法用单遍 SDT 表达。这种情况要么把语义规则拆成多遍每遍解决一部分依赖要么改写文法把绕回来的属性变成顺着传的。第三条是课后难题的高发区后面第 4 节会专门展开。这里有个容易被忽略的细节动作插入的位置变了属性的可访问范围也跟着变。动作放在T之前就完全看不到T的任何属性放在T之后T的综合属性就能用但T的继承属性此时已经错过了赋值时机。一个符号的继承属性必须在它被展开之前赋值完毕综合属性必须在它被规约之后才能读取这条时间线是所有动作摆放的底层约束。2.2 同一个文法的两种动作摆法输出结果差在哪拿中缀表达式求值这个最熟的例子做对照实验。文法E - E T | T T - T * F | F F - ( E ) | id摆法一纯综合属性动作全在末尾E - E1 T { E.val E1.val T.val } E - T { E.val T.val } T - T1 * F { T.val T1.val * F.val } T - F { T.val F.val } F - ( E ) { F.val E.val } F - id { F.val table[id.lexval] }这套写法里每一行都只有一个动作位置在末尾属性全是综合的所以是标准的 S 属性定义。把它交给 LR 分析器规约时顺手算一下就行不需要额外的数据流分析。摆法二把同样的语义改写成边扫描边输出的后缀式E - E1 T { emit() } E - T T - T1 * F { emit(*) } T - F F - ( E ) F - id { emit(id.lexval) }输入1 2 * 3输出是1 2 3 * 。注意E - T和T - F这两条单位产生式不产生任何输出它们只负责把语法结构接起来。这种写法在课本上叫边分析边翻译好处是不用保存整棵树的属性值坏处是它只能产生输出不能做需要回看前面结果的复杂计算。两种摆法的差异不在语义而在中间结果的保存方式。第一种把E.val挂在树节点上等父节点来取第二种直接把结果打到输出流里靠输出顺序保证正确性。做课后题时先判断题目要的是哪种——给出翻译后的输出序列通常是第二种构造注释分析树通常是第一种不要混着写混着写的卷子经常被判错。2.3 LL与LR对动作位置的容忍度完全不同这一条是我做完实验才真正体会到的。LL 分析自顶向下递归下降对动作位置的容忍度比较高因为分析过程天然是深度优先、从左到右的继承属性用函数参数传、综合属性用返回值传翻译出来的代码跟文法几乎一一对应。你写个parse_E()parse_E的参数就是 E 的继承属性返回值就是 E 的综合属性中间动作就是普通的语句非常直观。LR 分析自底向上就难受多了。它的规约顺序是右部符号全部进栈之后才规约左部所以综合属性很好处理规约时从值栈顶部弹出右部各符号的属性值算完把结果压回去一气呵成。继承属性非常难处理因为继承属性需要在右部符号被规约之前就算好可那时候父节点还没诞生信息根本没地方来。工业上的主流做法包括很多解析器生成工具直接把继承属性这条路堵死——只支持综合属性也就是只支持$$和$1..$n这种引用方式。想在自底向上框架里表达继承语义只能靠改写文法把继承属性变成综合属性或者用把父节点的信息提前压栈这种手工技巧。这条限制在实际项目里影响很大很多看起来自然的语义规则比如声明语句把类型传给变量列表一进 LR 框架就得重写。所以做题时看到一个 SDD先别急着写 SDT先问一句这个 SDD 是 S 属性的吗如果是LR 直接上如果是 L 属性但不是 S 属性LL 能上、LR 要改造两者都不是两边都得改造。这个判断顺序能省掉大量返工。3. 课后题四大题型的拆解套路3.1 中缀表达式转后缀/前缀这类输出型题目这是出现频率最高的一类几乎每本教材都有。题目通常给一个带优先级和括号的表达式文法要求构造 SDT把中缀表达式翻译成后缀表达式。解法套路固定把每个运算符对应的产生式找出来在该产生式的末尾加一个emit(运算符)再把id或num对应的产生式末尾加一个emit(词法值)。上面 2.2 的摆法二就是标准答案。这里要提醒三个容易扣分的点。第一个单位产生式不产生输出。E - T、T - F这类只做向上传递的产生式如果加了输出结果就全乱了。我见过有人在E - T上加了emit()看起来无害实际上破坏了输出序列的长度假设。第二个括号要吃掉不能输出。F - ( E )这条产生式本身不输出任何东西括号在翻译成后缀式之后是不存在的它的作用仅仅是通过语法结构影响结合顺序。第三个前缀式和后缀式的动作位置相反。后缀式把动作放末尾前缀式要把动作放产生式最前面E - E1 T1 { emit() }或者用产生式体开头的动作E - { emit() } E1 T1前提是文法的写法允许。这个细节在考同一文法分别生成前缀和后缀的题里经常挖坑。如果题目进一步要求生成带括号保护的后缀式或者输出中缀表达式的最简形式那就要在属性里保存字符串而不是直接打印这时候属性类型从无变成字符串E.code E1.code T.code 本质还是综合属性只是值变成了串。3.2 声明语句的类型检查与符号表填写第二大类是类型检查和符号表操作题眼通常是给变量声明语句加上类型一致性检查。文法还是前面那个D - T L完整的 SDD 要处理两件事把类型传给列表里的每个变量以及在重复声明时报错。D - T L { L.inh T.type } T - int { T.type int } T - float { T.type float } L - L1 , id { L1.inh L.inh; if lookup(id.lexval) ! null then error(重复声明); insert(id.lexval, L.inh); L.type L.inh } L - id { if lookup(id.lexval) ! null then error(重复声明); insert(id.lexval, L.inh); L.type L.inh }这段规则里L.inh的语义是本声明语句期望的类型它从T一路往右传是典型的继承属性。L.type其实可以省掉因为在纯声明语句里它恒等于L.inh保留它只是为了跟教材写法对齐。真正干活的是insert和lookup这两个动作。做题时最常见的错误是把L.inh写成了综合属性比如写成D - T L { L.type T.type }。这样写语法上没错但它要求L先算出一个type再让D用信息流向反了遇到int a, b, c这种多层嵌套的列表就没法把类型一路传下去。正确的写法是让类型从上往下流在每个L节点展开时就确定好期望类型。还有一个隐含的坑重复声明的检查时机。动作写在L - L1 , id的末尾意味着每遇到一个id就立刻查表插入这样int a, a能在第二个a处报错。如果把插入动作统一挪到D的末尾就得先收集所有 id 再统一插入多一层数据结构的支持。两种写法都对但前者更贴近边分析边翻译的思路也更省内存。3.3 三地址码与四元式的自动生成第三类是三地址码生成比前两类多一个临时变量的概念。核心动作是newtemp()和emit()前者每次调用返回一个全新的临时变量名t1、t2……后者往指令序列里追加一条四元式或三地址语句。S - id E ; { emit(id.lexval, , E.addr) } E - E1 E2 { E.addr newtemp(); emit(E.addr, , E1.addr, , E2.addr) } E - E1 * E2 { E.addr newtemp(); emit(E.addr, , E1.addr, *, E2.addr) } E - - E1 { E.addr newtemp(); emit(E.addr, , uminus, E1.addr) } E - ( E1 ) { E.addr E1.addr } E - id { E.addr id.lexval }输入a b c * d生成的三地址码是t1 c * d t2 b t1 a t2注意E - ( E1 )这条产生式不分配新临时变量直接把内层的地址往上递这是个很实用的优化——括号只影响语法结构不产生计算。同理如果题目要求尽可能少用临时变量还可以在只有一个引用时做地址复用那就超出基础题的范畴了。这里有个结构性的观察值得记下来这套文法带左递归属于 S 属性定义正好能塞进 LR 分析器里一次算完。如果把它改写成消除左递归的形式交给 LL 分析器属性就得从综合变继承麻烦一大堆。很多教材故意在这个例子上用 LR就是在暗示这个匹配关系。做综合题时先看文法形式再看分析器类型最后才决定属性的种类顺序反过来往往白写一遍。3.4 给出SDD判断能否单遍求值第四类题不要求你写规则只要求判断这个 SDD 能不能在自底向上分析中单遍求值或者这个 SDD 是 S 属性还是 L 属性。解法是画依赖图找环但考场上没时间画全图可以用两个快速判据。判据一看有没有继承属性。没有继承属性的一律是 S 属性必定能自底向上单遍求值。有继承属性的继续看判据二。判据二看每个继承属性的来源位置。把产生式右部展开成X1 X2 ... Xn逐个检查Xi的继承属性依赖谁。如果依赖的是X1..Xi-1的属性、或者产生式左部A的属性那是合法的 L 属性如果依赖Xi1..Xn的属性那就越界了不是 L 属性如果依赖Xi自己的子节点属性那更麻烦形成了环。举一个越界的例子A - B C { B.inh C.val }。B在C左边却要用C的值这就是典型的往右看。这种 SDD 在自顶向下分析里没法用因为B展开的时候C还没出现在自底向上分析里也没法用因为B规约的时候C还没进栈。解决办法只有两个要么把产生式改成A - C B调整顺序要么先把C的信息算出来放进一个全局结构里再让B去查——后者在编译器的实际实现里很常见比如符号表先扫一遍。4. 左递归消除之后语义动作该往哪儿挪4.1 报错属性未定义的根因在文法改写这一节讲的是我踩得最久的一个坑。原始文法E - E1 T | T语义动作是E.addr newtemp(); emit(E.addr, , E1.addr, , T.addr)写得好好的。为了做 LL 分析把文法消除左递归E - T E1 E1 - T E1 | ε改完之后一编译报错说E1里的E1.addr未定义——因为原来那个E1是左递归产生的左兄弟现在变成了右递归产生的自己名字虽然一样位置完全变了。左递归消除改变的不只是语法结构它把原来从左兄弟拿信息的路径改成了从父节点拿信息的路径属性的种类必须跟着从综合变成继承。这个变化的本质是原文法里的E1和E是兄弟关系左边那个E1已经算完了它的addr是现成的综合属性新文法里的E1是E的孩子它要算的东西必须由E传下来只能做成继承属性。同一个位置兄弟变父子综合变继承这是所有左递归消除后语义动作错位的通用原因不只是表达式求值这一处。4.2 用继承属性做累加器把左递归的语义搬回来知道根因之后改法就明确了给E1加一个继承属性inh表示左边已经累加出来的地址再给一个综合属性syn表示整个表达式最终的结果地址。翻译方案E - T { E1.inh T.addr; E.addr E1.syn } E1 - T { E2.inh newtemp(); emit(E2.inh, , E1.inh, , T.addr) } E2 { E1.syn E2.syn } E1 - ε { E1.syn E1.inh }三段规则逐个看。第一段E先把T的地址传给E1当作初始累加值等E1递归完把E1.syn收回作为E的结果。第二段E1遇到一个 T先分配一个新临时变量存当前累加值加 T的结果把这个新临时变量当作E2的初始值往下传等E2递归完再把最终结果往上传。第三段E1遇到空产生式说明没有更多项了直接把自己收到的初始值当成最终结果返回。输入b c d跑一遍E把b传给E1E1分配t1算t1 b c把t1传给内层E1内层E1分配t2算t2 t1 d把t2传给最内层最内层E1是 ε返回t2一路往上收E.addr t2。生成的指令序列是t1 b c、t2 t1 d和左递归版本完全一致只是求值顺序从先算完左边再算右边变成了边往下传边算。这个模式在编译原理里叫用继承属性携带累积状态除了算术表达式还可以用来做字符串拼接、链表构造、括号配对计数。凡是从左往右扫、每步都要用到前面结果的场景消除左递归之后都得用这套模板。记住这个模板比死记课本上那几个例子有用得多。4.3 LL预测分析栈里继承属性的传递写法如果坚持用表驱动的 LL 分析器而不是递归下降继承属性就得在分析栈上传递。做法是把分析栈的每个元素从一个符号升级成一个符号加若干个属性槽位展开产生式的时候按照产生式右部的顺序把子符号压栈同时把已知的继承属性值填进对应槽位。以E - T E1为例展开时栈顶的E弹出依次压入E1和T注意顺序因为栈是后进先出要保证T先被处理。此时E1.inh的值还不知道因为T.addr要等T处理完才能算出来。解决办法是在栈上插一个动作符号等T规约完、值算出来之后动作符号再从栈顶取出T.addr填进E1.inh的槽位里。这个动作符号其实是把 SDT 里的中置动作编译成了一个占位非终结符。工业解析器里也有类似机制只是名字不同。手工写分析器的话递归下降其实更省事E()函数里先调用T()拿到地址再把地址作为参数传给E1(addr)一个函数参数就完成了全部工作不需要在栈上折腾槽位。5. 写代码验证时最容易翻车的几个点5.1 分析栈与属性栈不同步的三种表现把 SDT 落到代码里最典型的翻车方式就是语法分析栈和属性值栈不同步。自底向上分析器通常是两个平行栈一个存符号一个存属性值每次移进压一个符号和一个空值每次规约弹出 n 个符号和 n 个值、压入 1 个符号和 1 个值。看着简单实际有三种常见错法。第一种ε 产生式规约时弹 0 个却压了 1 个。E1 - ε这条产生式右部长度为 0规约时应该只压入E1的属性值不弹任何东西。如果代码里统一写了弹出 n 个值n 取 0 没问题但如果在别的地方又手动补了一次压栈值栈就比符号栈多出一个之后所有的$1、$2全部错位一位。第二种属性栈里存了指针规约后原对象被释放。用 C 或 C 写的时候属性值经常是指向 AST 节点的指针规约时销毁子树却忘了把指针置空后续访问就是野指针。用带垃圾回收的语言没这个问题但性能差一些取舍看场景。第三种用解析器生成工具时中置动作改变了$n的编号。这一条坑过很多人。在常见的 Bison 风格工具里写exp : { $$ 0; } exp exp那个{ $$ 0; }会被当成一个匿名非终结符于是$1是它、$2是第一个exp、$3是、$4是第二个exp。如果按$1是左操作数去写取到的就是那个动作的返回值编译器不会报错运行时结果莫名其妙。正确做法是在动作里用$2和$4或者干脆把中置动作改成独立的小产生式。5.2 用四个最小输入做二分定位属性算错的时候直接拿完整程序去调试是不可行的得用最小输入逐层排除。我固定用四个输入做第一轮二分输入考察点出错说明1单叶子、无运算基本规约路径和值传递有问题1 2一次二元运算动作位置或临时变量分配有问题1 2 * 3优先级文法层次或动作归属产生式错了(1 2) * 3括号单位产生式或括号规则有问题这四个输入跑完基本能定位到是哪一层出的错。比如1通过但1 2不对问题肯定在E - E T这条产生式的动作上不用去看括号规则。如果1 2 * 3的结果是(12)*3而不是1(2*3)说明*的动作挂到了错的非终结符上或者T - F这条单位产生式漏了传值。再加一个a b c * d用来测三地址码生成看临时变量的编号顺序对不对。临时变量编号错了说明newtemp()的调用时机和emit()的顺序不一致通常是先 emit 后 newtemp写反了。这个细节在纸面做题时看不出来一跑代码就暴露。5.3 手搓一个百来行的SDT求值器验证思路最后分享一个我自己常用的小办法把文法手写成一个递归下降求值器用函数参数表示继承属性、用返回值表示综合属性跑通之后再回头对照课本的 SDT 写法能验证自己的理解对不对。下面这段是表达式求值的骨架三十行左右能直接跑# 继承属性用函数参数综合属性用返回值 tokens [] pos 0 def peek(): return tokens[pos] if pos len(tokens) else None def eat(t): global pos assert tokens[pos] t, f期望 {t}实际 {tokens[pos]} pos 1 def parse_E(): v parse_T() # E - T while peek() : # E - E T用循环模拟左递归 eat() v v parse_T() # 动作E.val E1.val T.val return v def parse_T(): v parse_F() # T - F while peek() *: # T - T * F eat(*) v v * parse_F() # 动作T.val T1.val * F.val return v def parse_F(): if peek() (: # F - ( E ) eat(() v parse_E() eat()) return v # 括号不产生新值直接传递 else: # F - id t tokens[pos] eat(t) return int(t)这段代码有两个地方值得对照课本看。第一E - E T这条左递归产生式在递归下降里被写成了while循环循环变量v承担的就是 4.2 节里E1.inh的累加器角色只是不用显式声明成继承属性。第二F - ( E )直接返回内层的值不分配任何新东西对应前面说的单位产生式不产生新值逻辑完全一致。跑通这段之后把返回值从整数改成三地址码字符串列表加结果变量名的元组就能顺手验证 3.3 节的临时变量分配对不对把while循环改成显式带参数和返回值的递归就能复现 4.2 节的继承属性模板。同一套文法用三种写法实现对照着看比在纸上画十张注释分析树的理解效率高得多。最后再分享一个小习惯每次做语法制导翻译的题先在草稿纸左上角写下每个符号有哪些属性、每个属性是综合还是继承这张两列的小表再动笔写产生式。这张表花不了两分钟但能挡掉后面百分之八十的返工——尤其是同一个符号在不同产生式里属性种类不一致的情况写规则时最容易搞混先列清楚就一目了然了。