| 摘要: |
| 上下文无关语言上递归函数(recursive functions on context-free languages,简称CFRF)是为描述计算机上用的非数值算法而提出的一种新型递归函数.该函数的一个重要研究方面是函数的求值算法研究.对此问题的一些研究结果进行了总结.在讨论计算和语法分析的结合方式之后,对主要算法按照算法适用范围从小到大的顺序(同时也是算法研究和提出的顺序)做了较为全面的介绍,着重介绍一种通用的新的高效求值算法,即面向树的求值算法.同时对把CFRF扩充为多种类递归函数后的求值方法进行了说明.CFRF的几个求值算法均已在机器上实现,得到了实践的检验. |
| 关键词: 上下文无关语言 递归函数 求值算法 |
| DOI： |
| 分类号: |
| 基金项目:Supported by the National Natural Science Foundation of China under Grant Nos.60103008, 60273023(国家自然科学基金) |
|
| Evaluation Algorithms of a New Kind of Recursive Functions |
|
CHEN Hai-Ming
|
| Abstract: |
| 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 have been realized on computers, and have been validated by practice. |
| Key words: context-free language recursive function evaluation algorithm |
