LBLR(k)优化中的错误检测

LBLR(k)给出了一个非常有效的优化算法。它通过状态归并的方法使LR(k)的状态数大大的减少,并使利用文法产生式进行归约之后的转向状态唯一。这样,在LR(k)的分析算法中,状态符不再需要进栈,节省了空间和时间的开销。本文在[2],[3]之后主要讨论了LBLR(k)优化中的错误检测问题,使LBLR(k)优化仍能保持LR(k)的有效的查错功能。     

广义上下文无关文法和它的语法分析

本文介绍了广义上下文无关文法,这种文法允许正则表达式出现在产生式的右部。然后,我们定义了相应的LR(κ)文法。紧接着我们给出了一种分析算法,它是由正规的LR型分析算法扩充而得的。在这个方法中我们强调节省状态,并在此条件下使分析算法尽可能地简单。     

多功能LR语法分析器构造系统XYZ/PG的理论与实现

:本文详细地讨论了正则LR(K)分析表(canonical LR(K)parsing table)与优化LR(K)分析表之间的转换关系,并在这一讨论的基础上提出了构造优化和加速LR(K)语法分析器的一个新算法。同时,文中给出了算法的正确性证明。作为多功能LR语法分析器构造系统——XYZ/PG的主体,本文算法已用PASCAL语言在NORD-500型计算机及DAUL 68000微型计算机上实现。与目前堪称最优的Pager算法相比本文算法通常可得到体积更小的LR(K)语法分析器。     

BCLR(k)文法及其分析算法

LR(k)是很重要的一类文法,但是用正规方法构成的分析算法,需要过多的状态和很大的存储空间,因此它不适合于实际应用。后来虽然提出了SLR(k)和LALR(k)文法,但是它们都只是LR(k)文法较小的子集。本文给出了状态图和状态链的概念,并且定义了BCLR(k)文法。它是LR(k)文法较大的子集,并且包含了作为它的真子集的LALR(k)和SLR(k)文法。可是它所需的状态数却与SLR(k)文法一样多。在本文的最后,我们对算法作了某些改动,使之能分析一般的LR(k)文法。     

LR(1)语法分析程序的自动生成系统

本文描述一个自动构造LR(1)文法的语法分析程序生成器PG系统(ParserGenerator)及其初步实现。该系统采用分解合并状态方法构造的LR(1)语法分析程序具有规范LR(1)语法分析程序的功能,而产生的分析表空间远远小于规范LR(1)分析表的空间,等于或稍大于LALR(1)分析表的空间。该系统可作为语言开发工具系统的子系统,以产生具有LR(1)文法语言的语法分析程序,也可扩充成独立的系统用于其它目的。     

LBLR(k)优化及其算法

本文给出LBLR(k)优化中的状态区分的新定义,从而消除了进行LBLR(k)优化时所做的限制条件,使该优化方法不仅对LALR(k)文法与SLR(k)文法适用,而且对LR(k)文法亦可进行LBLR(k)优化。最后本文给出实现LBLR(k)优化的算法。     

LR(1)文法和LBLR(1)文法语法分析表的自动生成

一、前言 LR(K)文法所产生的语言类是恰能被确定的下推自动机所接受的语言类。它不但具有文法类大的优点,而且分析速度快,查错功能强。LBLR(K)文法是LR(K)文法的子类,它在编译时占用的空间小,分析速度较快,而且在空间上有和LR(K)文法一样强的查错能力。但是,对一般文法来说,其LR(1)语法分析动作表f和走向表g、LBLR(1)语法分析动作表f_B以及走向表gR的构造是十分繁冗复杂,使用手工计算不仅要花费大量的人力和时间,而且其正确性往往得不到保证,因此,这些语法分析表的自动生成就显得十分必要。我们在美国CROMEMCO公     

LR(K)语法分析器的优化及加速

本文提出了构造优化和加速LR(K)语法分析器的一个新算法。它作为多功能LR语法分析器自动构造系统——XYZ/PG的主体,已用PASCAL语言在NORD-500型计算机上实现。与目前堪称最优的Pager算法相比较,本文算法通常可得到体积更小的LR(K)语法分析器。     

基于Z规格的LR(k)形式化分析及验证

在编译器的构造中,常由于语义的二义性等问题导致不正确的目标程序.为解决此问题,提出了一种新型的语法及语义正确性验证方案,即建立LR (k)文法和Z规格说明的联系,以此构造LR (k)文法的形式化描述及其形式化验证.实验结果表明,该方案能有效描述并检测LR (k)文法分析器中的语法错误及语义二义性,有助于提高分析器的有效性.     

LBLR(K)文法与文法分划

本文介绍一种二级文法,它是我们构造的一个语法分解自动生成系统XYZ/PG的理论基础。我们认为,由顶向下的递归子程序方法分块太细,而由底向上的语法分解程序由一整块构成又失之分块太粗,二者均不便于阅读和修改。在第二节、,我们将介绍一种方法,将一文法自然地分划成一组用由顶向下的方式联结起来的子文法,这样组成格型结构即为这二级文法的外部语法,而每一子文法则是一由底向上的LR型文法,我们称这种文法为LBLR(K)文法,它即构成这二级文法的内部语法。将由顶向下与由底向上两种方法以这样的方式结合起来,可以大大提高语法分解程序的可阅读性和可修改性。 在第三节中我们详细地讨论了LBLR(K)。这文法是由文[1]中介绍的BLR(K)加以改进而成。对于LBLR(K),文[1]所讨论的状态合并的优化方法仍然完全可以应用,但是文[1]所加的所谓由底向上条件这样一种限制性条件则取消了。已经证明,代替这个条件,在状态合并后可能产生的表面上的“冲突”,可以用检查栈内在最左一个合并状态后面的一个符号的方法来予以避免。因此,从SLR(K)或LALR(K)出发,进行状态合并所得到的文法与原来的文法大小是一致的。     

一个自动构造增量式LR（1）句法分析器的有效方法

本文提出了自动构造增量式LR(1)句法分析器的一个有效方法.用该方法构造得到的分析器不仅允许对原语句作多处修改,而且还允许奠基的LR(1)文法含有右边为空的产生式。为了分析一个经过修改的语句,它们所需的空间和时间分别与该语句的长度和所作修改的总和形成线性比.为了进行实验,本方法已在Motorola-68010机上获得实现。     

一种用FPL表示LR(K)分解程序的方法

LR(K)文法是当前最受注意的形式文法之一。其优点是:(1)受限制小,(2)查错功能强,(3)翻译速度快,(4)便于机械生成。其不足之处是:状态过多,颇占存储;其表示方法亦有不足之处,例如,插入语义子程序不便,亦不便于阅读。FPL(即 Floyd-Evans产生式,我们称为归约式)是一种被认为适于表示语法分解算法的形式语言,其优点是便于插入语义子程序,亦便于阅读。但不足之处是,较难于生成紧凑的 FPL 程序。本文中将介绍一种从LR(K)的位式集表机械生成 FPL 程序并予以优化的方法。我们认     

一个实用的语法分析器自动生成系统

一、前言LR分析算法是knuth 1965年首先提出的.LR分析器能自动生成,运行效率高,查错功能强,识别语法类大,可用于大多数由上下文无关文法描述的程序语言.然而,由于一般的LR分析器状态数量极多,需要大量的存储空间,很不实用.为此,人们做了许多努力.以后演变出的SLR、LALR文法都是对LR文法加以某种限制,所识别的文法类是LR文法的一个子集,因此可以比较有效地实现.     

SLL(k)文法及其分析算法的构造

本文继[4]对 Strong LL(k)文法(即 SLL(k)文法)作了较深入的探讨。文中首先给出了SLL(k)文法的充分必要条件,并详细地论述了该条件的可计算性;然后给出 SLL(k)文法分析算法的 Floyd-evans产生式语言(即 PL)表示及其构造算法。 本文所使用的记号在[4]中可以找到,并且本文所说的文法都是指压缩过的上下文无关文法。     

一种LR(1)-LALR(1)分析表的自动生成标法

本文实际上给出了LR(1)与LALR(1)的两种分析表的自动生成标法。后者是在前者的基础上产生的,故称这种LALR(1)分析表为LR(1)-LALR(1)分析表。 由于这种自动生成算法依赖于LR(1)分析表,故需要较多的计算机存储空间和运算时间,但该算法的显著特点是非常简明、容易实现,而且LR(1)-LALR(1)分析表本身并不大。一般像ALGOL60文法的LR(1)-LALR(1)分析表不超过400个状态和2000个位式,它已经可以达到实用的要求。 由该算法生成的LR(1)-LALR(1)分析表已经在近两年多来成功地应用在两个编译系统上。实践证明这种方法能达到大量地节省劳力、提高工作质量的要求。并为新的编译系统的开展提供强有力的工具。参考文献8种。     

程序设计语言的GLR优化分析

阐述了在程序设计语言语法分析器的构造中采用通用LR(generalized LR,简称GLR)分析算法的动机.提出了一个多层次的优化策略,加快了GLR分析器的分析速度.为基本的GLR算法增加了必要的运行时控制机制,以实现语法分析时调用文法规则附带的语义动作,化解输入串的二义性,同时避免GLR分析器可能存在的语义动作延迟问题.优化后的算法已在一个可视化语法分析器自动生成环境VPGE中实现.实验结果表明,在分析确定性的编程语言时,自动生成的GLR分析器的分析速度与自由软件基金会的Bison生成的LALR(1)分析器的分析速度有可比性.     

有限后看区分与LBLR(k)文法

本文给出了适用LBLR(k)方法分析的文法——LBLR(k)文法的充分必要条件以及其语法分析程序所需要的状态表(即分析动作表和走向表)的构造算法,讨论了LBLR(k)文法与其它某些文法之间的关系。     

FIRST和FOLLOW集合的并行算法设计

描述了多处理机环境中FIRST和FOLLOW集合求解的一种并行处理方法，并讨论了FIRST和FOLLOW集合的并行算法设计思想和它的实现策略，在构造文法G的LL(1)分析表以及判定文法G是否LL(1)文法时，求解FIRST和FOLLOW集合是很重要的内容，由于文法中终结符和非终结符个数很多，考虑FIRST和FOLLOW集合的并行处理方法，对并行编译处理和提高效率有其理论和现实意义。     

采用预测策略的Earley算法

在自然语言处理中,句法分析主要有基于统计的方法和基于规则的方法。Earley算法是一种基于规则的方法,可以分析任意上下文无关文法(CFG),而不需要对文法进行修改。详细分析了Earley算法的特点。在通常的Earley算法中增加了多种预测机制,这些预测机制借鉴了LL,LR以及SLR等确定性分析算法的一些思想,并对这几种不同的预测机制及其组合在相同条件下进行了中文句法分析实验。结果显示,引入这些预测机制通常可以减少产生项目的数量,从而节省存储空间,减少运行时间。     

关于正则文法及有限自动机的一点注记

本文讨论了正则语言的特征标c以及它的生成正则文法的变量个数n和其接受有限自动机的状态个数S(NM)之间的关系。得到了不等式n≥[log_2c-1],S(NM)≥[log_2c-1]。并且证明了,对任意整数 c>2,常存在这样的正则语言,此语言具特征标c,并恰能被一个含变量个数为[(log_2c)-1]的正则文法生成。