一种新型递归函数的求值算法  

Evaluation Algorithms of a New Kind of Recursive Functions

作　　者：陈海明[1] 

机构地区：[1]中国科学院软件研究所计算机科学重点实验室,北京100080

出　　处：《软件学报》2004年第9期1277-1291,共15页Journal of Software

基　　金：国家自然科学基金~~

摘　　要：上下文无关语言上递归函数(recursive functions on context-free languages,简称 CFRF)是为描述计算机上用的非数值算法而提出的一种新型递归函数.该函数的一个重要研究方面是函数的求值算法研究.对此问题的一些研究结果进行了总结.在讨论计算和语法分析的结合方式之后,对主要算法按照算法适用范围从小到大的顺序(同时也是算法研究和提出的顺序)做了较为全面的介绍,着重介绍一种通用的新的高效求值算法,即面向树的求值算法.同时对把 CFRF 扩充为多种类递归函数后的求值方法进行了说明.CFRF 的几个求值算法均已在机器上实现,得到了实践的检验.Recursive functions on context-free languages (CFRF) are a kind of new recursive functions proposed especially for describing non-numerical algorithms used on computers. An important research aspect of this kind of functions is the exploration of evaluation algorithms. The paper summarizes the author's research on this issue. Beginning by a discussion on possible combinations of calculation and parsing, it presents a comprehensive introduction to the major algorithms in an order in which the applicable ranges of the algorithms increase (this is also the order that the algorithms were devised). The introduction emphasizes on a new, efficient, and general evaluation algorithm, i.e. the tree-oriented evaluation algorithm. The paper also explains the evaluation method for the many-sorted recursive functions extended from CFRF. The algorithms of CFRF are realized on computers, and are validated by practice.

关 键 词：上下文无关语言 递归函数 求值算法 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]