摘要
上下文无关语言上递归函数(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.
出处
《软件学报》
EI
CSCD
北大核心
2004年第9期1277-1291,共15页
Journal of Software
基金
国家自然科学基金~~
关键词
上下文无关语言
递归函数
求值算法
Algorithms
Computers
Context free grammars
Context free languages
Evaluation
Trees (mathematics)