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

3558 软件学报 2025 年第 36 卷第 8 期

本文的研究对象是 Lustre 语言的 V6 版本, 参考资料主要为 Lustre V6 官网公开的官方文档和文法文档. 其中
文法文档给出了 Lustre V6 完整的上下文无关文法, 文法形式如图 4 所示. 为了能够使用该文法, 首先需要对它进
行标准化, 主要工作有 3 点: 消除化简 EBNF 范式、消除文法左递归、格式化符号.

图 4 Lustre V6 语法规则

扩展巴科斯-瑙尔范式 (extended Backus-Naur form, EBNF) 是一种主要用于描述上下文无关语法的元语法符
号表示法. 相较于常见的产生式表示方法, EBNF 范式定义了许多助记符. 助记符能简化产生式, 便于书写、阅读
和理解, 但是在识别算法中支持助记符会极大增加开发的难度和工作量. 考虑到扩展性, 其他语言的上下文无关文
法表示并不一定采用 EBNF 范式表达, 即使同为 EBNF 范式, 表达方式也可能略有不同 (Lustre V6 官方文档中的
定义方式就和 ISO/IEC 14977 中定义的 EBNF 范式不同). 权衡之下, 本文选择手动将 EBNF 范式中的助记符化简,
得到没有助记符的上下文无关文法版本. 并且为了防止在之后下推自动机识别的过程中产生无限循环, 需要消除
左递归. 最后, 为了便于识别程序区分产生式中的终结符和非终结符, 将终结符书写为小写字母开头的字符串, 将
非终结符书写为大写字母开头的字符串, 如表 1 所示.

表 1 标准化前后的文法产生式

Lustre 产生式 标准化后的Lustre 产生式
TypedLv6IdsList → TypedLv6Ids TypedLv6IdsList1
TypedLv6IdsList::= TypedLv6IdsList1 → ; TypedLv6Ids TypedLv6IdsList1
TypedLv6Ids {; TypedLv6Ids}
→ $
TypedLv6Ids → Lv6Id TypedLv6Ids1 : Type
TypedLv6Ids::= TypedLv6Ids1 → , Lv6Id TypedLv6Ids1
Lv6Id {, Lv6Id} : Type
→ $

文法标准化后, 可以输入到下推自动机生成模块自动生成下推自动机. 上文提到, 上下文无关文法和下推自动
机的表达能力是等价的, 每个上下文无关文法都对应一个下推自动机. 进一步的, 由于上下文无关文法的并仍然是
上下文无关文法, 所以下推自动机的并仍然是下推自动机. 所以, 由下推自动机生成模块生成的下推自动机可以识
别 Lustre V6 程序, 并且由多个上下文无关文法生成的下推自动机也可以合并为一个下推自动机. 因此, 既可以将
整个语言的上下文无关文法一次性转化成下推自动机, 也可以分别转换文法单元再合并为一个下推自动机. 生成
的下推自动机如表 2 所示, 其中箭头“→”左侧表示当前状态, 箭头“→”右侧由可能到达的状态列表组成, 列表中的
每个元素为一个三元组{Q, a, PUSH/POP e}, 代表在读入字符 a 时, 到达 Q 状态, 并在栈中压入 (PUSH) 或弹出
(POP) 元素 e.