控制表

✍ dations ◷ 2024-10-30 15:31:59 #控制流程,数据结构,编译原理

控制表是一个决定控制流程或是主要影响控制流程的表。关于控制表的结构或内容没有硬性的规定，其特点是其可以影响控制流程的能力。这类表格的设计有时称为“表格驱动设计”（不过后者多半是指由外部的表格自动生成代码，而不是在程序中的表格）。以有限状态机为基础的自动机编程有时会用控制表为其实现方式。若控制表有几个不同的层次，其行为就类似UML状态机（英语：UML state machine）。

控制表有时会以关系表（英语：association list）的方式表示，其中会有对应的条件表示式及子程序。控制表可以简化一些类似的程序叙述，而且若是二维的控制表，在阅读及更新上都比一维特性的代码要容易维护，有时控制表甚至可以让非程序员来维护。计算机科学家高德纳在1974年提出的论文《Structured Programming with go to Statements》中就提到“多路分支是一种重要的程序设计技术，但常常被一些数量不足的if指令取代”。

控制表可以是多维的，可以是固定长度或是可变长度（英语：variable length code），而且具有可在不同系统平台之间使用的可携性，系统平台变动时只针对解释器修改软件，不会变动隐含在控制表的结构及其内容中的算法。控制表的结构可能类似一个multimap的关系表，会将数据值（或数据值的结合）映射到一个或多个要进行的函数。

控制表可以是一维表格的形式，这可能也是最简单的控制表。一维表格的控制表将原始数据转换为副程序的偏移值、编号或是指针，转换方式可能是直接以原始数据（英语：raw data）为索引进行查表，或是将原始数据进行简单的数学处理后再作为表格的索引。查表的过程不会用到线性搜索或是二分搜索，可以在常量时间内完成。对于大部分的计算机体系结构而言，上述处理可以利用二或三个机器语言的指令来达成，不需进行比较或是循环处理。此技术一般称为“Trivial hash function”，若特别用在分支表中，则称为双重分派（英语：double dispatch）。若要使用一维表格的控制表，数据的可能范围需要很小，像ASCII或EBCDIC字符都只有255个可能数据，符合此条件，若数据是用ASCII字符表示，且可以确认其中有些数据不可能出现，其对应的控制表会更小。

以下是将ASCII的数据（A,D,M,S）转换为副程序编号（1,2,3,4）的控制表，此控制表为一维数组，可以在常量时间内完成转换。

（下表只列出有使用的部分，中间副程序编号为0的部分省略，下表中的前二栏只作说明用，只有第三栏才是控制表）

在自动机编程及伪会话交易（英语：pseudoconversational transaction）程序中，若相异程序状态的个数不多，可以有效的用控制变量来创建整个程控流程的模型。

上述一维的控制表可以视为将原始数据直接翻译为对应副程序的数值，只是原始数据的种类不多，或者有够快的存储器时，此作法可以快速的进行数据验证及对应副程序数值的转换。

分支表（英语：branch table）是由连续的机器代码branch或jump指令组成的一维数组，其目的是可以进行多路分支（英语：multiway branch），依编号运行对应的指令。有时编译器最优化处理switch指令（英语：switch statement）时，若输入值的范围不大，也可能会用分支表来实现switch指令。

分支表比一连串的If指令要短，但分支脚本仍然会重复出现，而上述的控制表只包括副程序编号，运行上所需时间会分支表要短。

控制表常常也可以视为是真值表或是决策表（英语：decision table）的可执行版本。控制表中常包括了命题及一到多个的对应行动。行动一般会是通用的副程序或是客户创建的副程序，程序扮演类似“解释器”的作用，依命题是否符合运行对应的行动，程序类似一个虚拟机，运行控制表的内容，其抽象化的程度较高。

多维数组的控制表也可以用编程语言中的switch指令来代替，而其条件可以利用逻辑运算的AND和OR指令组合出复杂的条件，条件成立时也可以运行不止一个的副程序。不过各高级语言中的switch指令在语法上可禸能仍然有些差异，而且可能有些语言的switch指令不允许复杂的条件。相较于switch指令，控制表没有编程语言的相依性，在处理上会比较单。

控制表保留了传统程序的本质，去除了编程语言的语法及和平台有关的成分（例如IF/THEN DO.., FOR.., DO WHILE.., SWITCH, GOTO, CALL），将程序浓缩为变量（例如input1）、数值（例如'A','S','M'及'D')及副程序的识别符号（例如'Add','subtract,..'或#1, #2,..）。控制表的结构本身隐含了有关的程序，包括比较是否相等、运行副程序等。

多维的控制表至少会包括一组数值和动作，可能还会有额外的运算符或其他信息，例如输入或输出数据的位置、长度及格式，供控制表相关程序进行数据转换。控制表可能会包括索引或指向要运行副程序的指针或相对位置。

以下举例用的控制表只接受一个输入。

控制表结构中隐含的条件及动作

（这种数据及动作对应的情形类似事件驱动程序设计，但后者的事件本身会有异步的特性）

控制表可以包含的数据种类和使用的编程语言有关，汇编语言没有数据类型的限制，允许的数据最多，其至在动作部分可以包括对应的代码地址。一般控制表会包括各个可能的数值及对应副程序的指针。若有些语言没有指针的概念，则其动作部分可以用一个代码的编号表示，再用switch指令运行对应的副程序。

控制表中可以加入注解或其他文字说明，可以使控制表除了包括其程序逻辑以外，也会提升其可读性。若是在程序开发前就已制作手写的决策表，枚举不同的情形及其动作时，控制表可以用来比对是否符合原始程序规格。控制表中也可以包括一些计数器，提供不同情形的统计信息，可以在程序运行中自动进行最优化，或是之后由人工修改程序，进行最优化。

控制表可以当成程序的静态变量，利用文字档存储，放在数据库中，也可以在程序引导时依参数动态创建。

乍看之下，使用控制表会增加运算负担（英语：Computational overhead），因为需要一个程序来查表及运行对应的副程序。不过将运行的程序及用表格表示的逻辑分开，可以更清楚的让每个程序运行各自的机能。就像是表格的应用程序一様，为了显示其结果，表格软件将复杂的公式变成可以有效用表格显示的方式。

以下的示例是以四则运算为例，为简单起见只接受一个输入，示例的目的只是展示如何用控制表来取代一般程序的指令来调整控制流程。控制表也可以接受多个输入，若利用有层次的链接式控制表，也可以达到结构化程序设计的目的（可能可以使用缩进来突显控制表中的副程序）。

CT1的控制表是一个简单的查找表，第一栏是要测试的数据，若数据等于第一栏的数值，会运行第二栏指定的副程序。实务上这就是一个多路分支的形式来进行，也是一种动态分配（英语：dynamic dispatch）的形式，最后一列是对应数据不符合任一数值时的处理。

CT1

 static const char  CT1 = {  "A",   "S",        "M",        "D" };                          /* permitted input  values */ static const void *CT1p = { &&Add, &&Subtract, &&Multiply, &&Divide, &&Default};           /* labels to goto & default*/ for (int i = 0; i < sizeof(CT1); i++)      /* loop thru ASCII values                                                    */   {if (x == CT1) goto *CT1p; }       /* found --> appropriate label                                               */ goto *CT1p;                           /* not found --> default label                                               */

若控制表改为一个有256个元素的一维数组，直接将数值转换为对应副程序的编号，即利用元素大小为字节的数组进行索引映射（英语：index mapping），可以在常量时间 $O(1)\,$ $O(1)\,$ 内找到对应的副程序，CT1p数组也可以用指向副程序的指针代替标记，就不需用到goto指令，但因为调用副程序需要的系统服务（英语：Housekeeping (computing)）较多，会对程序性能略为影响。

 static const void *CT1p = {&&Default, &&Add, &&Subtract, &&Multiply, &&Divide}; /* the 256 byte table, below, holds values (1,2,3,4), in corresponding ASCII positions (A,S,M,D), all others set to 0x00 */ static const char CT1x={             '\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00',             '\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00',             '\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00',             '\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00',             '\x00','\x01','\x00','\x00','\x04','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x03','\x00','\x00',             '\x00','\x00','\x00','\x02','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00',             '\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00',             '\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00',             '\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00',             '\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00',             '\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00',             '\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00',             '\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00',             '\x00','\x00','\x00','\x00','\x03','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00',             '\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00',             '\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00','\x00'}; /* the following code will execute in constant time, irrespective of the value of the input character (x)                    */ i = CT1x(x);            /* extract the correct subroutine index from table CT1x using its ASCII value as an index initially  */ goto *CT1p;          /* goto (Switch to) the label corresponding to the index (0=default,1= Add,2= Subtract,.) - see CT1p */

以下的例子说明只要编程语言支持依编号分支到各副程序的语法（副程序放在一个启始编号为0的数组中），就可以达到类似上述程序的二维控制表的效果。下例中用数组CT2来决定指针数组CT2P的编号，若编程语言不支持指针数组，也可以用类似SWITCH指令的方式处理，SWITCH指令中可以直接处理输入，或是跳到对应的副程序再处理输入。

CT2

以下的例子不使用实际的代码，只用二个数组来表示，只要是支持依编号分支到数组中（数组是从0开始编号）特定副程序的编程语言皆可适用。可利用数组CT2将输入的数据转换为副程序数组（CP2）的编号，若此编程语言不支持指针，也可以用类似SWITCH指令的作法取代CP2数组的查表，依序将输入值和每一个可能的数据比对，若数据符合，跳到对应的副程序中。

CT2

此例可以在不使用查表法的情形下，很有效率的将ASCII输入数据（A、S、M、D或其他）转换为指针数组的编号，不过为了和上例一致，仍使用数组表示。

也可以配合实际的应用，创造有更多字段的控制表，控制表会比上例复杂，但可以在更多测试输入时有更多测试条件的组合，而不是只比对单一测试条件。以下的控制表有增加一个输入数据（小写的a、s、m、d），若输入满足其中一个数据，该测试条件就成立，也就会进行对应的动作，另外也增加一栏来计算实际运行时各个条件成立过几次。

CT3

上述的控制表更接近程序编程中用到的条件指令，不过实际语言中用到的一些指令已转换为处理控制表的“解释器”程序，控制表只看到各个输入及其对应的副程序编号。结构化程序设计或是“无Goto代码”也可以配合经过适当设计及缩进的控制表结构使用。

在电信领域中决定一通电话特定费率的“电信评级”应用中，“表格驱动评级”（table-driven rating）技术描述将控制表应用在规则可能常常会因为市场外力而进行调整的情形，在许多情形下，决定计费的表格会由非程序设计者花一点时间进行修改及维护，更改需要的时间很短。

若其算法不是事先建在解释器中，而是由程序决定此算法，此技术称为“以规则为基础的评价”（Rule-based Rating），但和表格驱动评级比较，前者的运算负担（英语：Computational overhead）更高。

表格可以看成是一种二维的控制表，其非空白的单元格中有数据，而表格的程序即为解释器。有公式的格子一般前面会前置一个等号，表示这是特殊形态的输入，在处理中可能还会用到其他单元格的数据。表格和上述的“以规则为基础的评价”有很相近的地方，就是控制表的外化，即使是非程序设计者也能进行维护。

和控制表最接近的编程范型是自动机编程或是反射的元编程。不过控制表的解释器及各副程序可以用任何一种或多种编程范型来开发。表格本身可以只是原始数据的集合，不需要编译，在使用时再从外部设备中读取即可，不过表格放在存储器中的效率会比较高。

多维的控制表在概念上类似在虚拟机上运作的字节码，虚拟机是一个跨平台的“解释器”软件，要运行一,一些对应的程序，而要运行的内容是依表格内容所决定。控制表的概念也有些类似通用中间语言，其目的都在创建一个共享的跨平台的“指令集”。

解释器也可以存储各阶段的程序计数器内容或是其他数据，来记录部分或完整程序的流桯，记录的目的可以为了调试的需要、热点（英语：Hot spot (computer science)）侦测、代码覆盖的分析及性能分析，像上述CT3的例子就可以计数各个动作运行过的次数。