On the relationship between the LL(k) and LR(k) grammars

In the literature various proofs of the inclusion of the class of LL(k) grammars into the class of LR(k) grammars can be found. Some of these proofs are not correct, others are informal, semi-formal or contain flaws. Some of them are correct but the proof is less straightforward than demonstrated here.     

LR(k)任意文法位置的断点调试方法

LR(k)文法能描述所有确定型上下文无关语言,广泛应用于各类分析器生成器中.传统的LR(k)文法断点调试方法仅支持在产生式右部末尾设置断点(后文简称尾部断点),不支持在产生式右部中间位置设置断点(后文简称中间断点),这给分析器的开发和调试带来了不便.文中提出了一种新颖的LR(k)文法断点调试方法,不但支持传统的尾部断点,还支持中间断点.该方法可显著增加可利用的断点数量,可以跟踪到更细粒度的文法成分,从而帮助用户更好地进行文法调试,降低分析器的开发难度.     

A scheme for LR(k) parsing with error recovery part II: error recovery

The paper is the second in a series of three papers devoted to a detailed study of LR(k) parsing with error recovery and correction. Error recovery in LR(k) parsing of a context-free grammar is formalized by extending an LR(k) parser of the grammar such that it accepts all strings over the terminal vocabulary. The parse produced by this extension for a terminal string is a right parse if the string is in the language. In the case of a string not in the language the parse produced by the extension contains so-called error productions which represent the error recovery actions performed by the extension. The treatment is based on the formalization of LR(k) parsing presented in the first paper in the series and it covers practically all error recovery methods designed for LR(k) parsing.     

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

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

Incremental generation of LR parsers

Implementation of a new compiler usually requires making frequent adjustments to grammar definitions. An incremental technique for updating the parser tables after a monor change to the grammer could potentially save much computational effort. More importantly, debugging a grammar is made easier if the grammar is re-checked for correctness after each small change to the grammar. The basic design philosophy of an incremental parser generator, and incremental algorithms for LR(0), SLR(1) and LALR(1) parser generation are discussed in this paper. Some of these algorithms have been incorporated into an implementation of an incremental LALR(1) parser generator.     

A scheme for lr(k) parsing with error recovery part iii: error correction

The paper is the third in a series of three papers devoted to a detailed study of LR(k) parsing with error recovery and correction. A new class of syntax errors is introduced, called (k)-local parser defined errors, which suit better than the conventional minimum distance errors for characterization of error detection and recovery in LR(k) parsing. The question whether a given string has n k-local parser defined errors for some integer n is shown to be decidable. Using the formalization of LR(k) parsing and error recovery presented in the first and the second paper in the series it is shown that the canonical LR(k) parser of an LR(k) grammar always has an error recovering extension which is able to produce a correction for any terminal string containing only (k)-local parser defined errors.     

An alternative approach to the improvement of LR(k) parsers

Summary The methods of improving LR(k) parsers proposed by DeRemer and Korenjak are shown to be based on a single concept — that of modifying the contextual information on which parsing decisions are made. This concept is then used to derive a straightforward algorithm for eliminating unit productions from an LR parser.     

Elimination of single productions and merging nonterminal symbols of LR(1) grammars

Aho and Ullman give an algorithm in [1] for eliminating reductions of the form A → B, where A and B are nonterminals, from a set of LR(k) parsing tables, thus increasing the speed of the parser and reducing its size. We present a modification of their algorithm and show that after reductions by A → B have been eliminated, the symbols A and B can be equated and the associated columns of the parsing table merged, further reducing the size of the parser. The new set of tables parses according to an “abridged” grammar with fewer nonterminal symbols than the original. Finally, we give an algorithm which for certain LR(1) grammars constructs a set of LR(1) tables with no reductions by single productions, directly from the grammar.     

A note on a proposed LALR parser for extended context-free grammars

The lemma in “An improved LALR(k) parser generation for regular right part grammars” [Inform. Process. Lett. 47 (1993) 123-129] to test the applicability of the method is shown to be false by means of a counter-example grammar.     

Parallel construction of SLR (1) and LALR (1) parsers

The generation of an LR parser consists of constructing a parse table, with one row per state (in a push-down automaton), and one column per terminal symbol. Traditionally, this is carried out row by row, with the computation of one row depending (potentially) on all the others. We present a technique for carrying out the lookahead computation of SLR (1) and LALR (1) parsers in a completely parallel fashion. Our technique performs the computation by column, rather than by row. We show that the computation is totally independent for each column, making it ideal for parallelization. The speedup factor of the technique is min (N, T), whereN is the number of processors andT is the number of terminal symbols in the user's grammar.     

一种新的删除HB(k)树的结点的算法

Foster的删除HB(k)树的结点的算法的主要思想是先删除结点再自下而上处理某些子树,涉及自下而上的后退。提出一种新的删除HB(k)树的结点的算法,其主要思想是先自上而下处理某些子树再删除结点,不涉及自下而上的后退。举例说明新算法的执行过程。证明新算法是正确的。与Foster的删除HB(k)树的结点的算法相比,新算法不涉及辅助栈的使用。设n是HB(k)树的结点的个数。新算法的时间复杂性是O(log2n),与Foster的删除HB(k)树的结点的算法的相同。实验结果表明新算法的平均执行时间比Foster的删除HB(k)树的结点的算法短。新算法的空间复杂性是O(1),比Foster的删除HB(k)树的结点的算法低。     

A General Approach to L(h, k)-Label Interconnection Networks

Given two non-negative integers h and k,an L(h,k)-labeling of a graph G=(V,E) is a function from the set V to a set of colors,such that adjacent nodes take colors at distance at least h,and nodes at distance 2 take colors at distance at least k.The aim of the L(h,k)-labeling problem is to minimize the greatest used color.Since the decisional version of this problem is NP-complete,it is important to investigate particular classes of graphs for which the problem can be efficiently solved.It is well known that the most common interconnection topologies,such as Butterfly-like,Bene(?),CCC,Trivalent Cayley networks,are all characterized by a similar structure:they have nodes organized as a matrix and connections are divided into layers.So we naturally introduce a new class of graphs,called (1×n)-multistage graphs,containing the most common interconnection topologies,on which we study the L(h,k)-labeling.A general algorithm for L(h,k)-labeling these graphs is presented,and from this method an efficient L(2,1)-labeling for Butterfly and CCC networks is derived.Finally we describe a possible generalization of our approach.     

并行GCR(k)算法在多尺度预报模式中的应用

针对多尺度预报模式离散得到的非对称稀疏线性方程组的求解,通过利用GCR(k)算法的固有性质,消除GCR(k)算法的内积计算数据相关性,给出了一种改进的GCR(R)(IGCR(k))算法.同GCR(k)算法对比,IGCR(k)算法与GCR(k)算法有相同的收敛性,在基于MPI的分布式存储并行机群上进行并行计算时,同步开销次数减少为GCR(k)算法的一半.数值计算结果与理论分析表明改进的GCR(k)算法的性能要优于GCR(k)算法.     

编译原理中的LR类分析方法的教学研究

编译原理课程的教学不仅要介绍编译的基本原理和技术,还要培养学生的学习兴趣、专业思维和科学研究的方法及能力,文章以LR类分析方法为例,以还原知识的发现过程为主线,重现解决问题的思路与方法,以期培养学生的专业学习兴趣和科研能力。     

Matching preclusion for the (n,k)-bubble-sort graphs

The matching preclusion number of a graph is the minimum number of edges whose deletion results in a graph that has neither perfect matchings nor almost-perfect matchings. In this paper, we find this number for the (n, k)-bubble-sort graphs and classify all the optimal solutions.     

A language independent error recovery method for LL(1) parsers

An efficient and systematic LL(1) error recovery method is presented that has been implemented for an LL(1) parser generator. Error messages which provide good diagnostic information are generated automatically. Error correction is done by discarding some input symbols and popping up some symbols from the parsing-stack in order to restore the parser to a valid configuration. Thus, symbol deletions and insertions are simulated. The choice between different possible corrections is made by comparing the cost of the inserted (popped) symbols with the reliability value of the recovery symbol (the first input symbol that is not discarded). Our concept of reliability is based on the observation that input symbols differ from each other in their ability to serve as recovery points. A high reliability value of a symbol asserts that it was probably not placed in the input by accident. So it is reasonable not to discard that symbol but to resume parsing. This is done even if a string with high insert-cost has to be inserted before that symbol in order to fit it to the part of the program that has already been analysed. The error recovery routine is invoked only when an error is detected. Thus, there is no additional time required for parsing correct programs. Error-correcting parsers for different languages, including Pascal, have been generated. Some experimental results are summarized.     

A programmer-friendly LL(1) parser generator

LL(1) grammars have the conceptual and practical advantage that they allow the compiler writer to view the grammar as a program; this allows a more natural positioning of semantic actions and a simple attribute mechanism. Resulting parsers can be constructed that achieve fully automatic error-recovery, which allows the compiler writer to ignore totally the issue of syntax errors. Measurement shows that such parsers can be reasonably efficient.     

(n,k)-冒泡排序网络的子网络可靠性

并行计算机系统互连网络的拓扑性质对系统功能的实现起着重要的作用.为了精确度量基于(n,k)-冒泡排序网络构建的并行计算机系统的子网络容错能力,建立了(n,k)-冒泡排序网络中(n-m,k-m)-冒泡排序子网络与特定字符串之间的一一对应关系,研究了点故障模型下(n,k)-冒泡排序网络中(n-m,k-m)-冒泡排序子网络的...     

A sufficient condition for a graph to be an (a,b, k)-critical graph

Let G be a graph, and let a, b, k be integers with 0≤a≤b, k≥0. An [a, b]-factor of graph G is defined as a spanning subgraph F of G such that a≤d _F (x)≤b for each x∈V(G). Then a graph G is called an (a, b, k)-critical graph if after deleting any k vertices of G the remaining graph of G has an [a, b]-factor. In this article, a sufficient condition is given, which is a neighborhood condition for a graph G to be an (a, b, k)-critical graph.