2理论计算机科学电子笔记65 No.3（2002）网址：http://www.elsevier.nl/locate/entcs/volume65.html7页动作语义和ASF+SDF- 系统演示-Peter D.苔藓1，2丹麦奥胡斯大学计算机科学系摘要模块化和工具支持是程序设计语言形式化描述的重要特性。不受限制的上下文无关文法与动作语义的结合允许具有非常好的模块性的完整语言描述此外，通过在ASF+SDF中指定描述，ASF+SDF元环境可以用于提供适当的工具支持。1介绍正如Heering和Klint [3]所指出的，人们非常希望能够给出编程语言的完整形式化描述，并将其用于生成各种工具，如解析器，静态分析器，解释器和编译器。对于实际应用，语言描述具有良好的模块性是很重要的关于语法，在（扩展的）BNF中制定的正则表达式和语法通常被认为适合于描述上下文无关的语法，并且被解析器生成器很好地支持。然而，它们中的大多数都将严格语法限制为LALR或LL，这严重破坏了模块化;一个值得注意的例外是SGLR解析器生成[6]，它允许使用任意上下文无关语法。在语义描述方面，关于使用哪种形式主义的协议较少。许多人主张使用属性语法来实现静态语义，事实上Eli系统支持从具有良好模块性的属性语法生成静态分析器。其他静态语义的形式主义一般都有一些关于模块化的缺点。对于动态语义，支持模块化规范的主要框架有一元语义、模块SOS、ASM和本文的主题--动作语义。1 电子邮件地址：pdmosses@brics.dk2金砖国家：计算机科学基础研究，丹麦国家研究基金会2002年由Els e vierScienceB. V. 操作访问根据C CB Y-NC-N D许可证进行。苔藓3ASF+SDF Meta-Environment [1]提供了工具支持来实现各种语言，包括规范语言。使用元环境的早期版本，van Deursen和作者实现了ASD工具[8]，为编写和检查动作语义描述的格式良好性以及解析程序并从中生成动作提供了工具支持。ASF+SDF的后续增强使直接在ASF+SDF中制定动作语义描述更具吸引力，ASD工具现在已经变得多余。在简要回顾了动作语义的主要概念后，简要介绍了如何用ASF+SDF语言编写动作语义描述，解释了动作语义描述的模块结构，并指出了该方法的一些优点假设读者熟悉ASF+SDF形式主义[7]。2动作语义学动作语义框架[5]是指称语义和操作语义的混合：归纳定义的语义函数将编程语言构造映射到称为动作的语义实体，而用于表达动作的动作符号的语义本身是操作定义的动作表示法包括一些标准的数据表（数字、字符、列表等），并且可以添加更多的数据库动作表示法的关键特征是，相同的表示法用于组合动作（例如，顺序地），而不管这些动作可能有多复杂。 这确保了良好的模块化：定义特定构造的语义的语义方程被指定，而与所述语言中包括的其它构造无关。动作记谱法的原始版本是在1980年代末和1990年代初开发的3模块动作语义描述的模块化结构最初与定义语义学相同：描述被分为三个主要模块：规范化（抽象）语法、语义实体和语义功能。抽象的语法和语义函数通常根据所描述语言的结构类型被细分为独立的（相互依赖的）模块：表达式、语句、声明等。语义实体也根据数据的种类被细分为模块：值、变量、数组、记录等。然而，尽管这种模块化结构相当自然，并且有助于在单个动作语义描述中导航，但是很少有机会重用整个语义功能模块，因为两种不同的语言具有完全相同的任何类型的结构是不寻常的-除非其中一种只是另一种的扩展。苔藓4为了允许直接重用，Doh和作者在LDTA'01 [2]上提出了其主要思想来自Montages框架[4]，是让每个单独的编程结构的描述成为一个单独的模块。这样一个模块指定了构造的语法和语义，以及必须对所涉及的语义实体做出的任何假设相同的语义实体可能需要与多个构造相关联，因此它们仍然在单独的模块中指定，并在需要时导入。一个特定的编程语言的描述现在基本上只是一个特定模块的组合，并且用于通用构造（如算术表达式和条件语句）的模块可以在许多不同的语言描述中重用而无需更改。直接重用单个结构的语义描述的一个剩余障碍是，通常用于动作语义学中抽象语法的符号强烈暗示了相应的具体语法。一个描述Pascal语言中条件语句的模块会使用[[“if”E“then”S1“else”S2]]作为抽象语法;原则上它可以在C语言的描述中重用，但看起来会很奇怪。可以使用重命名将抽象语法表示法从Pascal风格转换为C风格，但这在很大程度上可能是乏味的。为了便于重用，似乎最好使用抽象语法的中性符号，反映熟悉的语义概念和术语，而不是某些特定具体语法的词汇符号。构造的具体语法的规范及其到抽象语法的映射与给出构造的语义的模块分离，使得后者可以直接在具有相应构造的所有语言的描述中重用，而不管它们的具体语法。4插图研讨会上的系统演示展示了如何在ASF+SDF中制定具有出色模块性的完整语言它还展示了如何使用元环境来检查动作语义描述的格式良好性，以及如何解析所描述语言中的程序并将其映射到动作。3演示中显示的大多数模块都用于JOOS（Java的子语言它们中的许多可以在不改变其他编程语言描述的情况下重用本节的其余部分解释了各种模块的作用，并给出了一些摘录来说明ASF+SDF的使用。完整的模块本身可在http：//www.brics.dk/cnpdm/LDTA-02/上查阅。这些模块大致按照可重用性从高到低的顺序来考虑，3动作解释器和动作编译器将被纳入未来版本的系统，允许程序根据它们的语义运行。苔藓5使用定义通常用于动作语义描述中的动作符号的固定模块，并使用为各个构造指定具体语法和动作语义的特定组合的特设模块来结束，这些模块直接用于整个编程语言的完整描述4.1内核操作表示法动作表示法的核心由一组固定的基本动作和动作组合子组成，以及一些标准的数据类型，如整数和字符串。它在ASF+SDF中的规范被划分为与以下动作特征相关的符号的模块：控制和数据流，绑定范围，对存储的影响，以及执行单独动作的并发代理之间的交互动作的基本组成结构由SDF规则指定，例如：Action -> Action {left}因此，特定的动作组合子可以指定如下：“and”->中缀一个基本操作可能涉及任意数据：“提供”数据->操作sortData本质上是action表示法的一个参数，通过将其他排序作为子排序嵌入其中来实例化（而不是通过重命名）。内核动作表示法模块在所有语言描述中被重用，而不会改变（直接或间接）使用它们中指定的动作原语和组合。4.2进一步的行动记录将内核操作表示法扩展到完整标准操作表示法的模块的组织方式与内核操作表示法模块本身的组织方式相同。每个标准动作组合子由SDF规则声明，例如：“而且”->中缀并由ASF方程定义为缩写，可用于将标准动作表示法扩展为内核动作表示法：4[0]A1此外A2 =（A1和A2）然后给出覆盖_上面，A1和A2是sortAction的变量，符号指定标准操作表示法扩展的模块与内核模块一样广泛地重用。用户还可以声明他们自己的动作组成的非标准缩写，以与上面所示相同的方式[4]定义方程实际上是在一个单独的模块中指定的，因此如果需要，可以很容易地禁止它们。苔藓6并且那些变得广泛使用的符号随后可以被并入标准动作符号的未来版本中。4.3内核数据需要与动作的特定特征相关的各种数据，例如，表示存储单元的数据的排序单元与对存储的影响（分配、更新等）有关。其他内核数据排序包括常见的实体，如整数和字符串。数据操作的表示法与操作组合符的样式相同：数据DataOpInfix数据->数据{left}“+”|“-”|“*”->DataOpInfix4.4进一步的数据新的数据类型通过声明它们的构造函数和选择器来指定。例如，子排序ObjectofData的构造器和选择器是这样声明的：对象|类|绑定|identity -> DataOpPrefix对应于以下SDF 2声明的未排序版本：object（class：Class，bindings：Bindings，identity：Identity）-> Object {cons}数据操作组合的缩写可以用与操作缩写相同的方式声明和定义。4.5抽象语法一个抽象语法模块要么声明一个新的排序（和一些变量）：排序Stm变量“S”[0-9]* -> Stm或者一个新的抽象语法结构：conditional（Cond，Stm，Stm）-> Stm {cons}构造器符号，如' conditional '，是故意选择的，以避免任何引用的词汇符号，如' if '，这可能是用于表达条件在一个特定的语言（打破了以前的风格中使用的在抽象语法中采用中性符号应该允许它直接重用于外观完全不同的语言，例如Pascal和C。4.6抽象语义用于抽象语法排序或构造的动作语义的模块导入相应的抽象语法模块，以及提供所需的任何语义实体的模块。在语法排序的情况下，它还声明苔藓7用于排序语义函数，确定用于表示它的语义实体的排序-通常是动作：5执行Stm -> Action对于抽象语法构造，抽象语义为其指定一个特定的语义，例如：[0] 执行序列（S1，S2）=执行S1，然后执行S2对于上面的语句排序，没有替代语义;但是对于表达式求值，例如，相同构造的替代模块将指定子表达式的顺序和交错求值。4.7具体语言结构为了获得具体语言结构的动作语义，我们声明了一个操作sort语句变量“S”[0-9]* ->语句上下文无关语法abs语句-> Stm并通过为每个具体构造给出一个方程来定义它（归纳）-可能每个构造都有一个单独的模块，以便于重用：上下文无关语法“if”“（“Expression”）”Statement“else”Statement -> Statementequations[1]abs if（E）S1 else S2 =条件式（cond（abs E），abs S1，abs S2）注意，映射abs不必保留分支的顺序，因此可以将let声明和where声明映射到同一个抽象局部声明构造。4.8具体语言最后，一个完整的语言模块导入所有提供所需具体构造的模块-可能添加优先级声明，并修复各种标准类型数据之间的关系：JOOS模块import JOOS/Statements JOOS/Statements/IfElse.5潜在改进声明新数据操作（作为对象）-> DataOpPrefix，例如）是缺乏有关域的信息，[5]语义函数的值域是一种数据，用于一种具有直接数学解释的结构。苔藓8操作的范围排序，以及关于哪些是构造函数或选择器。需要此信息以允许对操作中的数据操作进行类型检查;目前，必须以特殊的附加表示法提供此信息，并沿模块导入层次结构显式传递。使用Meta级操作来允许在SDF模块中照常声明数据操作并提取所需信息将是有吸引力的。考虑到编写和阅读许多小模块的方便性，ASF+ SDF在将声明收集到模块中时需要各种关键字，例如导出和上下文无关语法这将是可取的，以开发一个变种的ASF+SDF，避免这种然而，即使没有这样的增强，ASF+SDF似乎已经很好地支持了动作语义的规范。确认在元环境中实现动作语义是与Jørgen Iversen合作的。特别感谢CWI的Markvan den Brand、Jurgen Vinju和他们的同事提供了很多有用的建议和合作。引用[1] ASF+SDF元环境。主页：http://www.cwi.nl/projects/MetaEnv/meta/。[2] K.- G.杜和P. D.苔藓通过组合动作语义模块来组合编程语言。In M. van denBrand和D. Parigot，编者，《理论计算机科学电子笔记》，第44卷。ElsevierScience Publishers，2001.[3] J. Heering和P. Klint。程序设计语言的语义：面向工具的方法。ACM SIGPLAN通知，3月。两千[4] P. Kutter和A.皮耶兰托尼奥Montages：现实编程语言的规范。JUCS，3（5）：416[5] P. D.苔藓动作语义学。主页：http://www.brics.dk/Projects/AS/.[6] M. G. J. van den Brand、J. Scheerder、J. J. Vinju和E.维瑟无扫描广义LR解析器的消歧过滤器。In R. N. Horspool，编辑，《建筑工程》（CCSpringer-Verlag，2002.[7] A. van Deursen，J. Heering，and P. Klint，editors. 语言原型，第5卷，AMAST系列计算机。世界科学，1996年。[8] A. van Deursen和P. D.苔藓ASD：动作语义描述工具。在AMAST'96中，Proc.5th Intl.Conf. 《代数方法论和软件技术》，慕尼黑，LNCS第1101卷，第579-582页。Springer-Verlag，1996.
