基于上下文无关语言递归函数的规约语言研究
文献类型：学位论文
| 作者 | 陈海明 |
| 学位类别 | 博士 |
| 答辩日期 | 1999 |
| 授予单位 | 中国科学院软件研究所 |
| 授予地点 | 中国科学院软件研究所 |
| 关键词 | 递归函数 上下文无关语言 形式规约语言 求值 实现 解释器 |
| 学位专业 | 计算机软件 |
| 中文摘要 | 上下文无关语言递归函数（简称CFRF）是专为描述计算机上的非数值算法而提出的，特点是能够非常直接地描述结构对象的加工算法。本文研究基于CFRF的形式规约语言及其实现方法，并用于形式规约的获取和检验工作。为研究语言，首先从实用性出发，对上下文无关语言原始递归函数（简称CFPRF）的定义形式进行扩充。提出了比CFPRF原始定义条件更宽的另一种联立递归式、多重归纳式和部分构造式，并证明它们是CFPRF。进而得到一个函数类CFPRF~＋，它以CFPRF为真子类。我们还讨论了CFPRF~~+与CFRF的关系。提出了形式规约语言LFC（Language for CFRF）。它支持包括CFRF、数上递归函数和字上递归函数在内的多种类递归函数，提供了基于CFPRF的联立递归式和上述定义式的数种函数定义手段，支持的函数类CFPRF~＋。LFC语言也是一个通用的函数式语言，除了具备一般函数式语言所具有的特点（如引用透明性、简洁、良好的数学特性等）外，还因基于CFRF而特别适于描述复杂结构对象的算法。LFC语言把上下文无关语言（简称CFL）作为数据类型，这种类型的表达式是使用通用字连接函数形成的隐式结构的表达式，具有很强的表示能力和灵活性。LFC具有高次、可执行、能证明的特点。由于上下文无关文法可以通过机器学习方法获得，CFRF可以用结构归纳法通过机器辅助构造形成，因此LFC适于形式规约的机器辅助获取。所得到的规约可以进行原型速成，因此得到检验。LFC还与规约库相联系，使规约获取和检验的交互性得到较好的支持。在实现方面，研究了LFC语言的实现方法。根据CFRF的特点，提出了面向树的计算方法，它是一种对于用各种定义方式定义的CFRF都适合的通用实现方法。为此，设计了表达式的一种可以表示出结构的表示形式，以及基于这种表示形式的LFC的中间表示形式。CFL之间的相等、包含和相交关系的不可判定性，结LFC的类型检查带来了困难。我们提出了LFC的一个实用类型系统，给出了相应的算法，从而可以实现表达式形式的转换。在此基础上，设计了LFC函数定义到中间表示表式的翻译和变换方法，包括对函数递归参数和定义形式的分析，参数一致化，模式的表达式表示形式的翻译，部分构造式达到完全构造式的变换，如模式匹配翻译等，我们还讨论了LFC中间表示形式的实现方法，设计了一种利用Scheme解释器的快速实现方法，实现了中间表示形式到Scheme的翻译。本文工作首次把CFL作为函数式语言的数据类型，并研究了表达式表示形式和类型系统等有关问题，它们可为相关研究提供参考。根据以上研究，在机器上实现了LFC的解释器，和实验性运算构造和检验系统FC（Function Constructor），并作为形式规约获取系统SAQ的一个子系统。还进行了实验，检验了本文的研究结果。 |
| 语种 | 中文 |
| 公开日期 | 2011-03-17 |
| 页码 | 89 |
| 源URL | [http://ir.iscas.ac.cn/handle/311060/6002]  |
| 专题 | 软件研究所_中科院软件所_中科院软件所 |
| 推荐引用方式 GB/T 7714 | 陈海明. 基于上下文无关语言递归函数的规约语言研究[D]. 中国科学院软件研究所. 中国科学院软件研究所. 1999. |
入库方式： OAI收割
来源：软件研究所
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。