可视化语言文法形式化描述综述

可视化是人机交互的主要形式,可视化语言是计算机科学中一个重要研究领域,文法为可视化语言提供了一种有价值的形式化描述方法。本文基于可视化语言的特征,介绍了可视化语言文法形式化描述体系的基本理论,分析了几种典型形式模型,并探讨了当前的主要研究内容和面临的挑战。     

使用递归下降算法分析数学表达式

本文介绍使用编译原理理论中的LL(1)算法中最简单的种形式-递归下降算法来解决数学表达式的解析问题。同时．也介绍手工构造EBNF文法的分析器代码的方法．本文能对开发自己的语法分析器带来帮助。     

基于函数式语义的循环和递归程序结构通用证明技术

各类安全攸关系统的可靠运行离不开软件程序的正确执行.程序的演绎验证技术为程序执行的正确性提供高度保障.程序语言种类繁多,且用途覆盖高可靠性场景的新式语言不断涌现,难以为每种语言设计支撑其程序验证任务的整套逻辑规则,并证明其相对于形式语义的可靠性和完备性.语言无关的程序验证技术提供以程序语言的语义为参数的验证过程及其可靠性结果.对每种程序语言,提供其形式语义后可直接获得面向该语言的程序验证过程.提出一种面向大步操作语义的语言无关演绎验证技术,其核心是对不同语言中循环、递归等可导致无界行为的语法结构进行可靠推理的通用方法.特别地,借助大步操作语义的一种函数式形式化提供表达程序中子结构所执行计算的能力,从而允许借助辅助信息对子结构进行推理.证明所提出验证技术的可靠性和相对完备性,通过命令式、函数式语言中的程序验证实例初步评估了该技术的有效性,并在Coq辅助证明工具中形式化了所有理论结果和验证实例,为基于辅助证明工具实现面向大步语义的语言无关程序验证工具提供了基础.     

一个上下文无关文法的构造定理及其在推断中的应用

递归概念可以在句子中重复派生、循环出现。对这样的句子推断时,若为递归概念的每一个派生部分引进一个递归概念来描述,将推断出多个与之有相似的产生式结构的递归概念,同时也构造出一个新文法。本文先给出新文法的形式化构造方法,证明了新文法与原文法的等价性。在文章的后部,通过实例,介绍该定理在简化复杂文法推断中的应用。     

机器描述形式的代码生成方法

1.前言目前,编译自动化已成为计算机科学的一个重要课题。编译程序自动生成的理想化目标是:输入一种程序语言和一种计算机描述,输出在这种计算机上运行的这种语言的编译程序。然而,由于人们对程序语言和计算机的语义不能给出适当的描述,使得至今尚未产生这样一个软件工具。实现编译自动化的现实方法是:对编译程序的各个部分分别实现自动化。     

一种编译优化测试用例自动生成方法的设计与实现

编译器的质量保证对提高软件产品的质量有着重要作用,对编译优化的测试是其中的核心部分.对编译优化的测试需要大量的测试用例程序.要构造这些测试用例,使用传统手工构造方法面临着效率低的问题,而基于文法的构造方法则针对性不足.从对优化的形式化描述出发来自动构造测试用例能克服这些缺点.本文设计并实现了一种基于形式化描述的编译优化测试用例程序生成方法.该方法基于编译优化的时序逻辑描述构造关键顶点控制流图,逐步转换为控制流图并得到用例程序.针对GCC(版本4.1.1)进行的覆盖率测试实验表明,该方法可以生成具有较高针对性的测试用例,并达到相当的覆盖程度.     

案例教学法在《编译原理》课程中的研究

本文将案例法引入了《编译原理》课程的教学,发挥案例法的优势,以二义文法为主线,探讨了二义文法和递归文法、LL（1）文法、LR（0）文法和SLR（1）文法的关系,找出了一些判定文法有无二义性的充分条件,同时研究了解决二义性的方法,加深了学生对二义文法的理解。     

递归查询算法的研究

本文介绍了ＤｅＤＢ的递归查询算法，提出为减少冗余及回溯计算的基本原理．根据该原理，提出了一种高效的递归查询算法ＧＣＱＡ，它包括２部分，一是预编译算法；另一个是递归编译算法．实验结果表明这种算法是高效的．     

网页树形结构自动生成研究

网页树形结构是网页语言的一种特定描述。根据网页语言这种规整特性,可结合文法理论形式化建模。通过扩展终结符、规则概念,提出非终结符函数、终结符变量函数的构造方法,给出了自动生成特定类型的语言的一种生成模型。最后,给出模型在仪表装配树形中的实例应用。     

形式语言中的几个算法问题

引导学生关注学科前沿,培养学生理论研究兴趣是高校教学的重要任务之一。笔者尝试在编译原理的教学中,引导学生思考关于计算的基本问题:如何描述问题,是否有问题没有算法,等等。文章从编译原理课程中形式语言与自动机部分内容中,引出字符串匹配、自动机等价测试、上下文无关文法等价测试等问题,证明有不可计算的问题,介绍和分析相关算法,引导学生理论研究兴趣,拓展课程学习深度和广度。     

面向对象文法分析

针对编译中的文法分析部分进行了深入探讨，循序渐进地将文法分析面向对象方法实现。从理论根据及示例可以看出：用面向对象方法进行文法分析，可以彻底解决传统文法分析中的左递归、岐义性及回溯问题，且实现起来很方便、灵活，并具有良好的可操作性与可扩展性。     

消除文法无用符号和无用产生式的树型算法

在编译技术的实际应用中，人们总是想定义一种程序语言的文法要尽可能的简单。但是由于技术上的某些原因，造成定义出来的文法虽然逻辑上正确但是不能满足语法分析的要求。所以在进行语法分析之前，首先应该对文法进行预处理，以使进入语法分析的文法能够满足要求。消除文法的无用符号和无用产生式是预处理中的一个重要组成部分。下面介绍一种用构造树和修剪树来实现消除文法的无用符号和无用产生式的方法，我们称之为树型算法。     

抽象数学机模型与程序方法论(下)

四、程序的交换在算法的设计方法中,递归是一种很重要的工具。然而在算法的程序实现中,递归程序的效率低于循环程序。而且有时候,由于设计者所容许采用的语言的限制,根本无法实现递归算法。因此,关于由递归程序变换成循环程序的理论,不但对编译技术,就是对程序方法论,也具有重要意义。     

SLR语法分析器及其语法错误修正

引言 LR分析方法是近二十年来发展很快的一种形式化的语法分析方法。它具有能识别的文法类大,能被自动生成时空效率都较高的分析器及能在最早可能点报错等优点。SLR分析方法是LR分析方法中一种实用的方法。本文结合我们所实现的PASCAL语言的SLR分析器及它的错误修正程序讨论SLR分析器的构造、实现及语法错误修正问题。第一、二节中讨论SLR分析器的构造原理,并结合实践,对分析表实际存储空间的压缩,总控程序的实现和分析器的一些特性等方面进行讨论。第三节中将着重讨论SLR分析器的语法错误修正问题。这里给出了一个错误修正的算     

“编译原理”课程的教学改革实践

作者针对计算机专业“编译原理”课程教学实践中存在的一些问题,提出了在编译原理课程中要引入两个基于λ-演算的小语言,通过对这两个小语言的文法和解释器实现的介绍,使学生了解课程体系结构和课程目标,掌握编程语言重要的基本概念和实现方法,为后续的进一步学习打下基础。     

0-1背包问题的一种新解法

针对目前求解0-1 背包问题算法的优缺点,开发了一种新的非递归算法。从计算0-1 背包问题最优值的递归方程出发,使用形式推导技术及序列抽象数据类型。在开发出循环不变式的同时,归纳得到用抽象程序设计语言Apla描述的非递归算法,并形式化证明了其正确性,在相关工具及部件库的支持下进一步得到C++程序。理论分析和实验结果表明,该算法的时间耗费受背包容量变化的影响很小,是一种有效的方案。     

简单C编译器的实现

文献综述 上实际60年代,众所周知IBM的Backus领导他的小组对FORTRAN语言和其编译器进行了开发工作.由于当时人们对编译理论知之甚少,就导致了开发工作变得异常困难又不方便.Chomsky带着他的团队开始了对自然语言结构的研究,Chomsky 的研究成就是根据文法语言的复杂度来进行语言分类,包含了4个层次:0型文法、1型文法、2型文法和3型文法,每一个都是层层递进的.2型文法是今天程序语言结构的标准方式,分析问题是用于上下无关的文法识别的有效算法.     

适于通信协议形式描述的一种混合模型

通信协议的形式化技术的关键在于形式描述技术(FDT),而形式描述的关键,则在于建立有效的形式化描述模型。目前主要有三类模型:(1)转移模型,它包括有限状态机(FSM);Petri网和形式文法等,(2)程序语言模型,它包括一些典型的过程型语言和说明型语言,如函数式语言和逻辑式语言,(3)混合模型,它由前述两类模型相互结合     

形式化开发非递归Koch曲线算法

形式化方法是构建可信软件的重要途径。Koch曲线是典型的分形图形。基于形式化方法PAR及循环不变式开发策略,开发了Koch曲线非递归算法,并对其进行了形式化的正确性证明。在得到求解Koch曲线算法的循环不变式的同时,直接得到易读、高效且可靠的非递归算法。对使用形式化方法及循环不变式开发策略开发分形程序非递归算法作了较深入的实践和探讨。     

谈谈形式语言与编译课程

针对编译原理课程理论完整性不足、课程定位模糊、与其他课程内容重叠等问题,提出建设形式语言与编译课程,内容涵盖较为完整的III型和II型语言理论、编译原理中编译前端部分的更新内容等,采用理论课和实验课独立设课并于大二下学期同时开出,达到强调编译原理理论性和技术性双目标。