内容范围: 程式编译器. 内容程度: 高级, 进阶. 内容抽象: 看似不同的高阶结构, 却有着相同的底层指令. 内容精度: 观念模式. 【前言】 本篇是我个人研究编译器设计的一点中途心得. 希望有志与此的同好, 能一起 分享. 本文内容不是编译器的教学手册, 因此不会描述所有必要的基础, 只着重在我 想表达的重点上. 所以如果看不懂的人, 请参考其它编译器书籍或等候未来我发表 相关文章. 【概要】 程式语言中所具有的种种不同的结构化指令, 看似在表面上有所不同, 但是其 底层的机械码却是相同的. 都可以使用GOTO指令塑造出来. 例如: BASIC: IF/ ELSE/ END IF FOR/ EXIT FOR/ NEXT DO/ EXIT DO/ LOOP SUB/ EXIT SUB/ END SUB ... (A) 语言指令 底层GOTO结构 功能说明 -------- ------------ -------- IF 计算逻辑式 if not TRUE goto .else_001 逻辑为假, 跳至ELSE段. ... ... 一般运算叙述. 逻辑为真, 继续执行. ... ... goto .if_001.endif IF段结束跳至出口. ELSE label .else_001 ELSE段进入点注标. ... ... 一般运算叙述. END IF label .if_001.endif IF出口注标. (B) 语言指令 底层GOTO结构 功能说明 -------- ------------ -------- FOR I=y to z初始化 I=y 变数初始化. label .for_001 入口注标. 判断逻辑式: I <= z if not TRUE goto .next_001 逻辑为假, 跳至出口注标. ... 一般运算叙述. 逻辑为真, 继续执行. ... EXIT FOR goto .next_001 运算叙述, 跳至出口运算. ... 一般运算叙述. ... add I = I + step 累加器. 累加变数指定间距. goto .for_001 跳至入口注标. NEXT label .next_001 next出口注标. 【正文】 __缘由__ 在我研究机械码执行的过程里, 我很惊讶的发现: 一般常见的结构化叙述竟然 可以只使用简单的goto指令来建置完成. 实际上因为我也只有goto可以用... goto指令在程式语言的演进中被视为「搅乱」程式逻辑的「元凶」. 因为程式 设计师在胡乱的goto之後, 根本不知道原来的流程是怎样跑的, 以致於除错追踪变 得很困难. 然而如果你只是程式设计界的後辈. 只学会前人惨痛的「结果」. 那你抛弃 goto的後果就会造成你写不出语言编译器! 因为你不懂得goto的基本意义. __机械执行__ 在「机械执行」的世界里, 其实只有「位址转移」这种基本的功能. 也就是 goto! 一段机械码连续执行下来, 遇到goto, 就转移到指定的机械段继续执行. 如果 没有, 就继续执行下去... 在机器的眼光中看不见人类所谓的高阶结构--也就是像IF/END IF 这种「结构 化指令」. __机械执行的单纯性__ 很多人习惯高阶程式设计之後, 并不了解所谓的「机械化」会到什麽程度. 因 为高阶语言是专为贴近人类思考所开发出来的. 机械化的定义是这样: 原理 解说 1. 执行命令的明确性. 也就是一个指令有一个固定的动作. 2. 执行顺序的可预期性. 指令和指令间相互衔接的转移. 3. 没有任何执行是「未知的」. 「机械运转」的基本法则. 也由於这样的定义, 才使得由「物质」来实现「机械运算」成为可能. 其中, goto指令就是基本的第二法条. 指令间的转移. 另外, 隐含的指令转移 就是下一个指令位址. 附带说明. 「机械化执行」中, 不能有任何执行是「未知」的. 任何「无法决 定」的运算, 也必须被明确「定义」出来, 叫做「意外」. 而执行「意外」的 机械码就是「直接当机」 (锁住後续的其它执行, 避免灾害扩大.) __机械码的世界__ 如果你仔细设计一个虚拟机器, 用来执行你自己自定的机械码, 那它看起来会 像这样: 「左转, 右转, 向前走 5 秒, 後退走 3 秒.」 这个机器只有4 个指令, 左转, 右转、前进、後退. 并且每个指令都有条件参数. 转向时, 包括角度. 前进後退时, 包括时间. 你把机械码定义出来以後, 可以控制电脑鼠走迷宫, 或是工厂的无人化自动搬 运车等. 由於每个指令都是可以实现的. 所以「机械」执行变得可能. __电脑的机械码__ 现在大家所知道的电脑, 其实也是运用这种基本的思想造出来的. 只是底层的 硬体运作是电流与类比转换器. 电流能不能流经指定的通路 (开关) , 决定了其结果如何. 如果通路的另一端 连上了另一个电磁开关的话. 当电流经过开开关关等数亿个电路阀门, 如果有一个通路正好通向外界的灯泡 或许你就会看到指令执行「亮」起来. 这个灯泡其实就是一种「类比转换器」. 将电流转换成「光」的能源形式. 而 不再是「看不见」的东西. 电脑就是这样由复杂的电流开关加上机械动作的类比转换器所构成的. 不过, 由於人类为了方便自己了解与简单描述起见, 才会用文字来定义「每个 动作」. 这就造成所谓的二进制码, 与更高阶的组合语言码了. 很多人并不知道, 其实你偶而由二进制码编辑器看见的一堆乱码 (或数字). 已经是经过高阶化的东西. 它是以16进位的数字码型式来表示电流各点的开关状态. 如果你还不能想像的话, 想想盲人用的点字书就会晓得. 点字书上的点, 可以视为 「开」的状态. 无点即「关」. 但是数字码却是以号码来表示功能. __回归正传的goto__ 我之所以简单介绍前面的机械执行与机械码, 是要告诉你. 我了解goto并不是 肤浅的. 我是真的明白所谓的「机械控制」是什麽, 才会决定goto其实是机械执行 的根本基础. goto的用不用, 在早期引起了很大的纷争! 设计师的习惯, 功能的实现, 与系 统开发管理上的益处等. 这里我需要你明白, 在「这」之下, 没有goto, 你无法完成工作. 在「这」之 上. 滥用goto, 只会使你头痛, 如果头痛的不是接你工作的那个人的话. __在goto之前__ 我在早期研究编译器功能时, 首先做的就是「直线」运算. 也就是没有分支转 移的运算. 最简单的机械指令设计就是这样: 指令编号: 1 机械码: '1' 功能: 暂存器加一. (count) 指令长度: 1 参数: 无. (後面没有了! 不要怀疑! 只有一个指令!) 虚拟机器像这样: (在电脑中用软体程式来模拟机器) '==BASIC 码== '--机器启动初始化-- Counter = 0 '暂存器归零. CodeSize = Len(codeStr$) '取得机械码的程式长度. pinSize = 1 '预设机械指令只有1 个字元长. if CodeSize > 0 then pi = 1 else pi = 0 '没有机械码时不运转. '--运转行程-- Do While pi '==机械运算核心== Select case Val(mid$(codeStr$,pi,1)) Case 1 'Count Counter = Counter + 1 '暂存器加1. pinSize = 1 '机械指令长度: 1 Case Else pi = 0: pinSize = 0 '无定义的机械码, 当机. (脱离机器) end Select '==机械核心结束== pi = pi + pinSize '切换执行到下一个机械码位址. if pi > CodeSize then pi = 0 '决定是否继续执行: 超出机械码范围. if pi < 1 then pi = 0 '决定是否继续执行: 不合理的范围. Loop '--运转结束-- 程式看起来像这样: 1 1 1 (连续执行「加一」3 次) 或是 1 1 1 1 1 (连续执行「加一」5 次) 程式影像似这样: codeStr$="111" 或 codeStr$="11111" 把codeStr$ 喂给前面的虚拟机器「吃」, 你就会得到暂存器是3 或5 的结果. 由於机器没有输出指令. 你必须自己在执行後加上「记忆体倾印」的功能. 例如: Print Counter __goto: 功能的分支执行__ 前面的机器是非常简单的. 只有一个指令! 并且只能「加一」. 但是「千里之 行始於足下」. 所有复杂功能都是後来加上的. 你可以想像再添加所有可能指令到 机器核心上..像买菜、洗碗、拖地等.... 这里我要加上功能分支指令goto. 指令编号: 2 机械码: '2' 功能: 流程转移. 绝对位移. (goto) 指令长度: 3 参数: 位址. 两码. 一个程式看起来像这样: codeStr$ = "11208111" 指令分解成: "1, 1, 2:08, 1, 1, 1" 有6 个指令. 其中goto在第三个. goto的参数有两码. 00到99. 可位移99个位元组. 算是小跳跃. 机器核心加上此段: Case 2 'Goto pi = Val(mid$(codeStr$, pi+1, 2)) '新的执行点. pinSize = 0 '机械指令长度: 归零. 因为pi已是新值. 程式执行起来像这样: 影像: 1, 1, 2:08, 1, 1, 1 -> -> | > ->..........| 继续..跳..........到这里继续 其中, 後面的两个 '1' 指令被跳过去了! 在2:08之後. goto 直接执行指令转移到绝对位址8 上面. 所以 codeStr$ "11208111" 第8 个位址为 '1' 即: "1120811*"星号所在的指令. 最後, 执行的结果倾印暂存器会是3, 因为只加了3 次. 在"**20811*" 有星号 的指令1 被执行. 从这里你就知道分支执行是多简单的事! 机器只是改变执行指标到新的位址. 其它都不必动. 真实的电脑原理完全一样! 只是看起来电子电路, 电流控制会复杂很多. __goto: 跳跃的可能形式__ 一般应用上goto会有短跳跃与长跳跃两种形式. 还有相对跳跃与绝对跳跃等模 式. 短跳跃除了指令较短之外, 其内部机械运转要动到的相关部位也较小. 你可以 想像成: 走到厨房..及走到学校去..两种跳跃形式. 当然「走到厨房」 (短跳跃) 成本比长跳跃 (到学校去) 低得多! 绝对跳跃是基本指令. 相对跳跃可以由绝对跳跃模拟出来. 差别在多一个可变 的基底暂存器. 相对跳跃所做的, 除了指令後的参数值--相对位移量之外, 机器还会自动加上 现在的状态: 基底暂存器值. 说明一下, 这个「基底暂存器」是你自己的机器弄出 来的. 它可以是另一个变数, 像前面的机器Counter 变数类似. 例如JumpBase等. 绝对跳跃的运算法如下: pi = 参数值. 直接指明绝对位址, 正值. 相对跳跃: pi = 参数值 + 基底暂存器. 相对於基底暂存器的前後位址. 可能正负. 从这里你也可以知道. 要塑造goto有多简单! 而且实际由机器实现 (有电流或 物质运转) 也是很基本的事. __goto的goto: 「进化」__ 这个双关语标题其实就是本篇重点了: 「结构化指令的底层塑造」 当你简单的在机器实现goto功能之後. 你就可能实现所有的「高阶」结构化指 令. 像IF/END IF, FOR/NEXT 等. 回过头去看前面的「概要」. 我不需要重复篇幅将内容打两次. 你应该可以看 得懂我在写什麽. 到目前为止, 我的虚拟机器只差条件判断式 (if) 而已! 如果你注意到的话. 你可能发现 label 这个定义字要怎麽「执行」. label 不是执行指令! 不会在机器核心运算! 它是写程式的助忆码. 其真正的 结果应该是它所在的位址: 一个「数值」而已! 并且不会产生机械码.(自己的机械 码) label 是由编译器来识别的. 当程式编译完成後, 你在机械码中是看不到这些 字样 (功能) 的. 程式通常都是由人来写. 所以程式原文的语法会很高阶. 这也是程式语言为何 要发展到接近人类思考与习惯的原因. 由於机械码的位址很难用人工计算! 所以直接由编译器来代算会比较简单! 前面的例子, 我们手写的机械码 "11208111".由於是非常简化的功能, 所以跳 跃位址一眼就看得出来. 由: |...>* 指令2:08, 转移到後面* 的位址. 然而复杂的大程式, 都是由编译器来记住跳跃注标的位址, 反复计算才计算出 来的! 这包括要计算前面指令的大小, 跳跃时考虑短跳跃或长跳跃. 往前跳或往後 跳等. __goto如何造出结构化__ 我用IF/END IF当例子. 解释goto如何能架构出「结构化语法」 ------------------------------------------------------- IF 计算逻辑式 if not TRUE goto .else_001 逻辑为假, 跳至ELSE段. ... ... 运算叙述. 逻辑为真, 继续执行. ... ... 一般运算叙述. goto .if_001.endif IF段结束跳至出口. ELSE label .else_001 ELSE段进入点注标. ... ... 一般运算叙述. END IF label .if_001.endif IF出口注标. ------------------------------------------------------- 由於我手上的指令只有goto可以用.(在机械运算的底层) 因此我必须想办法将高阶语法用goto塑造出来! 经过基本原理的思考之後我发现: 所谓的「结构化执行」也不过就是「区段」 的执行罢了! 用这眼光看其它的语法, Do/Loop, For/Next. 没有不是区段执行的. 连副程式或副程序都是! 在早期高阶语法的设计要点中, 很明确的任务是要解决执行流程不易追踪的问 题. 而流程追踪不是在机器执行阶段才要查, 而是必须要在原始码书面阶段就要能 够检查才行! goto造成的指标乱跳, 使得人的脑筋也乱跳. 所以一个循序、有固定出入口的 高阶语法变成容易了解的解决方案. 结构化语法总是由上往下执行, 因功能需求, 有可能回复回到开头再往返循环. 并且, 出口总是固定, 不是在语法结束, 就是後来加的中途出口叙述. 然而中 途出口叙述在机械码转换之中也总是从语法结束後离开的. 这和正常离开并没有两 样. 我在理解语法的基本原理之後, 配合goto的能力. 我就将「结构化语法」使用 goto指令造出来了. 首先: 'IF' (开头的指令) 是一个逻辑运算式. 这里的机械码转换和表面语意 是相反的! 很奇怪! 'IF'说明的是 '成立' 才做. 但是机械流程用goto来想後, 却是 '不成立' 要 跳离! 跳离到 'ELSE' 段落去做! 原因在goto只做'跳'的动作,'IF' 却是留在原地, 所以要反过来 '不成立' 才可以跳. 另外, 你可以发现, 结构的几个地方有 label标记. 即 else 区段开头, 及 END IF结构结尾的部份. 这是很容易理解的. 因为 'IF' 的构造, 不是二选一, 可 能跳到第二段做, 就是单选 (IF/END IF), 条件不成立直接结束 (跳至结尾). 如果 'IF' 段成立. 则ELSE段不能执行, 所以在 'IF' 区段编译时, 会在段尾 加入goto结尾的指令, 以便离开. 然而ELSE段已经是临近结束, 执行完就会自然离 开, 所以ELSE段没有最後的goto. __goto的挑战: 巢状结构化__ 或许有人会问! 现行的程式语法中有巢状表示法, 也就是IF中有IF等. 那goto 又要如何设计? 语法范例: ------------------------------------------------------- IF 计算逻辑式 if not TRUE goto .else_001 逻辑为假, 跳至ELSE段. ... ... 运算叙述. 逻辑为真, 继续执行. '--巢状内层--------------------- IF 计算逻辑式 if not TRUE goto .else_002 ... ... goto .if_002.endif ELSE label .else_002 ... ... END IF label .if_002.endif '------------------------------- ... ... goto .if_001.endif IF段结束跳至出口. ELSE label .else_001 ELSE段进入点注标. ... ... 一般运算叙述. END IF label .if_001.endif IF出口注标. ------------------------------------------------------- 眼尖的程式设计师一看到最前面的范例出现 "if_001.." 的注标就会自己懂了! 注标之所以有编号, 正是为了巢状结构用的. 这样编译器才不会找错人, 跳到 不该执行的段落去! 最後, 说明一下. "goto .if_xxx.endif", "label .if_xxx.endif" 都是编译 器自己假造出来的. 在中间语法分析阶段, 编译器可以自己加入必要的系统码. 因 此goto/ label 都是编译器添加的, 方便自己编译出正确的语法来使用. 或者, 你可以说, 这样的「底层GOTO结构」正是代表成品机械码最直接的表示 法. 因为它已经「明示」了原来「结构化语法」所没有的东西. __goto的最後说明: 副程序__ 前面的范例并没有列出所有的「结构化语法」转换的形式. 这些都可以由您自 己来做. 原则一样. 但是值得一提的是副程序的转换法. 很简单, 可是却可能在一开始就被忽略. (C) 语言指令 底层GOTO结构 功能说明 -------- ------------ -------- goto .SUBEND_0001 避免前面的叙述「不经同意」执行 SUB label .SUB_0001 副程序的进入点. END SUB label .SUBEND_0001 副程序的出口. 一开始的 goto 很重要! 因为副程序是区段保护的! 没有正确呼叫不能任意进 入副程序中. 这个「陷阱」让我一开始就掉进去! 直到虚拟机器执行到不该执行的码时我才 发现! 原因在原始码指令都是连续的. 连副程序定义在里面也只是「一个指令段落」 而已! 由於设计师有可能在原始码中任意地方加上副程序. 因此有机会出现副程序段 与主流程段交替出现的写法.(这是使用一般文字编辑器写程式所可能出现的结果.) 然而根据副程序的「意义」. 表明它是「独立」的程式区段. 所以其存在「和 前後的程式码顺序无关」. 一开始我只注意到副程序要有进入点, 否则不会执行. 却忘掉要加「流程保护 」码. 即最开头的goto指令. 结果初次的编译结果就是被副程序定义之前的程式码 「无意中闯入」! 因为副程序就写在它的後面而已! 【结语】 本篇主要阐明. goto是编译器转换成机械执行码的最基本功能. 也是建置「结 构化指令」的最终实现指令. 实际上没有电脑是直接提供「结构化指令」的机械码 的. 高阶形式都有低阶的化约. 另外, 本篇也简单的描述了「机械化执行」的一些原则. 这大概可以加强你对 goto能力的印象. 最後. 要实现完整的编译功能其实还有很长的路要走. 虽然本篇提出了一个简 单的虚拟机器来说明goto实作的方式. 但是高阶语法的解译, 位址运算, 及符号表 等等, 本篇没有另加说明. 因此你可以知道, 本篇的重点只在这个概念: 「结构化指令的底层其实只是goto而已」! Tommy 99/12/08 後注: 现代流行的事件驱动模型. 虽然改变了循序执行的表象. 但是底层执行, 甚至事件 函式中的执行段等等, 无一不是以「结构化指令」作基础的. 所以不要以为有了「 事件驱动」就不要懂「结构化执行」, 任何高阶抽象的背後都会有基础的功能来支 持的. -- ※ Origin: 枫桥驿站<bbs.cs.nthu.edu.tw> ◆ From: tommy @ 125-232-135-111.dynamic.hinet.net