Page 136 - 《软件学报》2025年第8期

于涛 等: 基于下推自动机的同步数据流语言可信编译 3559

表 2 下推自动机

文法产生式 对应的下推自动机
Start → [{0 Q0, ε, PUSH Δ}]
Q0 → [{1 Q_loop, ε, PUSH TypedLv6IdsList }]
Q_loop → [{2 Q_loop, ;, POP ;}, {3 Q_loop, , , POP , }, {4 Q_loop, :, POP :}, {5 End, Δ, POP Δ}, {6
Q_TypedLv6IdsList, ε, POP TypedLv6IdsList}, {9 Q_TypedLv6IdsList1, ;, POP TypedLv6IdsList1}, {12 Q_loop, ε,
POP TypedLv6IdsList1}, {13 Q_TypedLv6Ids, ε, POP TypedLv6Ids}, {18 Q_TypedLv6Ids1, , , POP
TypedLv6IdsList::= TypedLv6Ids1}, {21 Q_loop, ε, POP TypedLv6Ids1}]
TypedLv6Ids {; Q_TypedLv6IdsList → [{7 Q_TypedLv6IdsList1, ε, PUSH TypedLv6IdsList1}]
TypedLv6Ids} Q_TypedLv6IdsList1 -> [{8 Q_loop, ε, PUSH TypedLv6Ids}, {10 Q_TypedLv6IdsList11, ε, PUSH
TypedLv6Ids::= TypedLv6IdsList1}]
Lv6Id {, Lv6Id} : Q_TypedLv6IdsList11 → [{11 Q_loop, ε, PUSH TypedLv6Ids}]
Type
Q_TypedLv6Ids → [{14 Q_TypedLv6Ids1, ε, PUSH Type}]
Q_TypedLv6Ids1 → [{15 Q_TypedLv6Ids2, ε, PUSH :}, {19 Q_TypedLv6Ids11, ε, PUSH TypedLv6Ids1}]
Q_TypedLv6Ids2 → [{16 Q_TypedLv6Ids3, ε, PUSH TypedLv6Ids1}]
Q_TypedLv6Ids3 → [{17 Q_loop, ε, PUSH Lv6Id}]
Q_TypedLv6Ids11 → [{20 Q_loop, ε, PUSH Lv6Id}]

3 核心转换步骤

本节将以提到的 Lustre 语言的主要特性为线索来解释在转换过程中的关键节点是如何处理的.

3.1 同步数据流的并发性
Lustre 的语句并行执行, 与书写顺序无关. 然而, 语句之间的数据依赖关系是客观存在的, 例如 (1) a=1; (2) b=
a; 两条语句需要按 (1)、(2) 的顺序执行. 因此, 需要对 Lustre 源程序按照数据依赖关系进行拓扑排序, 使得生成的
C 语言目标程序能够按照正确的顺序串行执行. 未经拓扑排序的源程序直接编译生成的目标代码在执行时可能产
生错误或未定义的结果.
通过识别程序中语句间的依赖关系: 即一条赋值语句的右值是另一条赋值语句左值的情况, 并根据识别到的
语句间的依赖关系对语句执行拓扑排序, 使得目标程序能够正确串行执行.
拓扑排序算法首先遍历所有的赋值语句, 保存赋值语句的源代码, 左值变量和右值中的变量列表和数量到
assign 结构体中. 在一条赋值语句中, 左值对右值中所有的变量构成依赖关系, 但 pre 和 fby 运算符修饰的变量除
外: pre 和 fby 运算符依赖流上一个周期的值, 在上一个周期就已经计算完毕.
在遍历完程序后, 遍历 assigns 数组, 找到依赖变量数为 0 的赋值语句, 将其取出并保存到结果数组中, 并将该赋
值语句的左值从所有赋值语句的依赖中去除. 以此类推, 直到取出所有的赋值语句. 这就完成了对赋值语句的拓扑排序.

3.2 目标码转换模式
目标码转换模式表示了一段 Lustre 语法单元会被转换为何种 C 语言的代码. 例如, Lustre 的 if 表达式语法单
元“if < Expression1 > then < Expression2 > else < Expression3 >”可能被转换为“Expression1 > ? < Expression2 > :
< Expression3 >”或者“if(< Expression1 >){temp = < Expression2 >} else {temp = < Expression3 >}”; 其中尖括号包裹
的非终结符表示该文法单元在本转换步骤中不转换, 需要后续被递归地转换.
目标码转换模式由人工构建, 首先需要在充分理解 Lustre 语义的基础上找到对应的 C 语言表示; 此后需要通
过大量的测试明确语法单元的具体特性和相互关系, 从而修正 C 目标码模式, 得到最终的目标码转换模式. 下面
将详细说明几个语法单元的目标码转换模式构建的过程.

3.2.1 时态算子
时态算子 pre、→ 和 fby 是 Lustre 中独有的特性, 它们运算结果依赖于过去周期的信息, 因此无法简单地转
换为某些 C 语言的运算符.
时态算子依赖于过去周期信息的特性主要需要在目标语言中实现 3 个功能.
(1) 生成变量保存过去周期的信息;
(2) 调用运算符时读取该变量的值;