形式语言理论

形式语言理论对于计算机程序语言和编译程序的研究有着重要意义.本文综述了N.Chom-sky等人在这方面所做的工作,通俗地介绍形式语言理论中四种类型的文法(有限状态文法、上下文无关文法、上下文有关文法和0型文法)以及与之相应的四种自动机(有限自动机、后进先出自动机、线性有界自动机和图灵机).可供计算机软件和数理语言学工作者参考.     

译校者的话

《形式语言及其与自动机的关系》一书可看成数字电子计算机编译程序理论和语言理论之著作,着重讲形式语言与自动机的关系。 作者首先对什么是过程和算法作了一般定义。然后阐明了语言的两个生成系统,一个是文法,另一个是识别器,即常说的自动机。两者都是有穷表示,但说明的语言却都可以是无穷的。     

AGDL——一个属性文法定义语言

AGDL是一个属性文法定义语言,用来进行编译程序自动生成的说明。AGDL具有抽象数据类型的定义的施用型(Applicative language)语言,因此属性文法规则简明易读,是用来发展编译程序生成的重要工具语言。     

文法推断研究的历史和现状

文法推断属于形式语言的归纳学习问题,它研究如何从语言的有限信息出发,通过归纳推断得到语言的语法定义.文章综述文法推断研究的历史和现状.首先阐述文法推断的理论模型,接着罗列上下文无关文法类及其非平凡子类、隐马尔可夫模型以及随机上下文无关文法的推断方法,最后简介文法推断的应用,并展望其发展趋势.     

编译程序的范式结构及用属性文法进行编译程序设计(下)

4.用属性文法进行编译程序设计近些年属性文法得到广泛的发展与应用.用属性文法进行编译程序设计可以是工具的辅助设计,也可以是人工进行设计.我们在这里主要介绍程序员如何根据属性文法的定义进行编译程序设计,并假定读者对属性文法的基本概念已经清楚.4.1属性文法的分类及判定问题     

一个测试程序自动生成器的设计与实现

本文介绍了一个用于编译程序测试的程序自动生成器,该生成器以编译程序对象语言的前后文无关文法作为输入,根据该语言的具体特点,对语言的数据对象采用了一种表结构的描述方式,并通过对表的操作,有效的解决了语言的前后文相关问题,该生成器不但可按语言文法的描述自动生成覆盖该语言各种语法现象的程序,而且还可按用户要求生成具有某种语法现象的程序,另外,该生成器在生成策略、生成算法及推导机制等方面也有自己显著的特色。     

基于范畴论的形式语言模型建模方法研究

形式语言模型转换的语义一致性与其形式系统完备性分析是当前形式语言理论尚未有效解决的难题。针对形式语言模型的应用需求与研究现状,建立形式文法模型及其形式语言模型,应用范畴论方法构建具有普适意义的形式文法模型范畴与形式语言模型范畴。在形式语言族模型的形式化理论框架内,用与特定形式语言无关的范畴论方法研究形式语言模型转换的语义一致性。初步分析形式系统的完备性,通过与形式语言理论主要研究方法的比对论证了范畴论方法的优势,为形式语言模型的范畴论方法研究提供一个便利、高效的形式化理论框架。     

属性文法的研究与应用

本文详细讨论了有关属性文法的基本概念,属性文法的两种分类方法,两种分类之间的关系及属性文法的判定问题。本文还讨论了如何用属性文法定义编译程序的遍体制说明及与指称语义的关系。最后讨论了属性文法在编译程序中的应用与属性计算器的程序处理。     

自动生成前端编译程序的一种方法

本文构造的ＸＹＺ／ＮＧＡＥ系统是建立在属性文法基础上的前端编译程序自动生成系统。本文在概念了属性文法及其描述语言之后，简要地介绍该系统的体结构以及为减少空间开销而采用的优化措施。     

一个自动编译系统ACS

本文介绍一个自动编译系统ACS。对某上下文无关文法语言,写出其词法描述、语法描述、语义描述和目标机描述。ACS系统可以自动生成此语言在目标机上的编译程序。ACS系统由六个子模块组成:词法自动生成器、语法自动生成器、语义自动生成器、中间语言转换程序、优化程序和代码自动生成器。本文将分别讨论这六个子模块的原理和功能,还将给出用ACS系统生成的一个编译程序实例—Mini_Ada编译程序。     

LR分析法在词法分析器自动构造中的应用

提出了一种新的自动构造编译程序词法分析器的方法,LR分析法通常用于语法分析,但只要适当修改LR分析总控程序,就可将LR分析法用于词法分析器的自动构造。该方法的优点不仅在于将词法分析器自动构造方法与语法分析器自动构造方法统一,简化了编译程序的设计和构造,而且该方法自动化程序较高,只要确定描述单词的文法和词形编码表,便可自动生成任何程序设计语言编译程序的词法分析器。     

写在前面

《编译程序技术》根据编者对近几年来阅读国外文献的笔记的理解,几经修改而成。它主要介绍了已在Gries的著作中提到的那些文法的分析算法。在他的著作里,有些内容过于简单,国内文献又不甚多。为了使我国读者掌握几种文法的分析算法,特在《编译程序技术》里对此作了必要的补充,不时地加上我们的看法,充实了一些例子。此外,我们还引进了弱优先文法概念,并     

编译程序自动测试中的知识表示

软件测试是软件工程的重要研究课题之一。本文把人工智能(AI),知识工程和属性文法多种知识和技术应用于软件测试,主要对编译程序测试中的知识分类和知识表示问题进行讨论,它是开发知识型编译程序测试环境的基本出发点。     

编译程序的范式结构及用属性文法进行编译程序设计(上)

本文将介绍编译程序自动生成的方法,该方法在NCI(华北计算技术研究所)用来发展编译程序自动生成系统(CSG).本文还详细地讨论属性文法以及如何使用属性文法进行编译程序设计.     

一种特殊的上下文无关文法及其语法分析

SAQ系统是一个进行软件规约获取、检验和复用的实验系统，其中以上下文无关文法表示的概念是规约的一部分.SAQ要求将概念的词法和句法定义结合在一个上下文无关文法中.如果用常规的上下文无关文法描述诸如程序设计语言和自然语言等一些复杂概念的语法，则需要把诸如空格和回车等没有实质意义的分隔符包含到语法中去(这种描述方法称为朴素表示法),使得语法描述很累赘.为此，作者设计了一种特殊的上下文无关文法,它把通常上下文无关文法定义中的非终极符集合和终极符集合进行细化.用这种文法可以相对简洁地描述程序语言和自然语言等复杂概     

自动机与形式语言理论简介

形式语言理论是计算机科学的一个重要分支,这一领域是在1956年前后形成的。那时,Noam Chomsky 在他的自然语言的研究中给出了文法的数学模型,并且采用对产生式加限制的办法将文法分成了四类。尽管这四类文法还不能够很好地描述自然语言,但却令人满意地描述了程序设计语言。     

BSX:一个在微型机上实现的编译程序生成系统

本文介绍了一个基于属性文法的编译程序生成系统BSX。该系统能接受较大的前后义无关属性文法类。并且由于采用了ALL(1)语法分析方法和局部多遍从左到右属性计算法,使得产生出的编译程序结构简单、高效,适合于在微型机上运行。     

属性文法的概念和定理

1.引言属性文法的概念是 Knuth 于1968年提出来的。我们知道,通常的编译程序,当要分析某一字符串时,首先辨认出语法结构,然后调用一语义程序。也就是说,语法分析和语义分析是分两步各自独立地进行的。下     

一种新的编译程序测试用例自动生成策略及其实现

自动生成测试用例是测试编译程序的途径之一,目前一般均使用Purdom提出的产生式选择策略来自动生成测试用例,本文提出了描述前后文无关文法的一种图表示方法,这种图称为文法的DG图。基于DG图,我们给出了一种优于Purdom策略的新的编译程序测试用例自动生成策略,并讨论了这种策略的实现原理。