Generation of efficient LALR parsers for regular right part grammars

Summary A method for building small fast LALR parsers for regular right part grammars is given. No grammar transformation is required. No extra state of the LALR parser for the recognition of strings generated by a right part is required. At some reduce states the parser may refer to lookback states (states in which the parser may be restarted after the reduction). An optimizing algorithm to reduce these references is also given.     

Constructing LR parsers for regular right part grammars

Summary Regular right part (RRP) grammars differ from context free (CF) grammars by virtue of the fact that the production right parts are nondeterministic finite automatons (FAs). LR(k) parsers for RRP grammars are linear time parsers which can determine the right end of each handle by considering at most k terminal symbols to its right and the left end (after the right end has been found) by considering at most one parse stack state to its left. This paper is concerned with the construction of a class of LR(k) parsers for RRP grammars which makes use of FAs for determining both the right and left ends of the handle.This work has been supported by a Carleton University grant and National Research Council of Canada grant no. A3585     

LALR(1, 1) parser generation for regular right part grammars

Summary Commonly used extensions to BNF can be modelled by the formalism of regular right part grammars. A method for building LR parsers for such grammars is given, which works by first constructing an LR(0) automaton and then augmenting it with readback machines constructed to recognize the reverse of the state sequences leading to a reduction. The state sequences which will be accepted by such readback machines are also the sequences which link reductions to their lookback states (states in which the parser may be re-started after the reduction), which are needed in order to compute LALR(1) lookahead sets using the algorithm devised recently by DeRemer and Pennello.An algorithm is presented which computes these lookback states using the structure of the LR(0) automaton, and it is shown how this can easily be extended to build readback machines at the same time.     

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.     

A note on regular kolam array grammars generating right triangles

A group structure is identified among the Regular Kolam Array Grammars that generate the families of Kirsch's right triangles with labelled vertices and their reflections about the leg and/or base of the triangles.     

Incremental generation of parsers

An LR-based parser generator for arbitrary context-free grammars that generates parsers by need and handles modifications to its input grammar by updating the parser it has generated so far is described. The need for these techniques is discussed in the context of interactive language definition environments. All required algorithms are presented. Measurements are given comparing their performance with that of conventional techniques     

SLR(1) and LALR(1) parsing for unrestricted grammars

Summary Simple LR(1) and lookahead LR(1) phrase structure grammars are defined and corresponding deterministic two-pushdown automata which parse all sentences are given. These grammars include a wide variety of grammars for non context-free languages. A given phrase structure grammar is one of these types if the parse table for the associated automaton has no multiple entries. A technique for construction of this parse table is given which in the lookahead case involves elimination of inverses in a grammar for lookahead strings for LR(0) items and computation of first sets for strings of symbols in the given 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.     

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 new heuristic for inferring regular grammars

Modifications to a grammatical inference scheme by Feldman et al. are presented. A comparison of the relative performance of the original and modified schemes is made using the complexity measures of Feldman and Wharton. The case where a complex model is used to generate the sample set is then analyzed. A set of 104 samples was found that trained the program to infer the grammar that corresponded to the original model. The results of a study of the performance of this algorithm when there is a large number of samples is then presented. The major conclusion of this study is that the modified scheme has a superior performance on small sample sets but is highly unsuitable for large ones.     

Yet another storage technique for lr parsing tables

A submatrix storage scheme for sparse matrices is presented which has been found useful for storing LR parsing tables. It is not the most compact representation but it is easy to use and of order (1) in speed of access. The method is compared with the two most popular methods of storing LR parsing tables which use ‘linear lists’ and ‘row displacement’. Results of using the submatrix method to store the parsing tables for the Pascal language are included.     

On the generative power of regular pattern grammars

Acta Informatica - It is shown that for every recursively enumerable language L $$ \subseteq $$ ∑* there exists a selective substitution grammar with a regular selector over a binary alphabet...     

Yet another proof of the cascade decomposition theorem for finite automata

We give here a short proof that each finite automaton can be built as a cascade of permutation automata and identity-reset automata.This paper was presented at the Conference on the Algebraic Theory of Machines, Languages and Semigroups, 29 August–8 September 1966, at Asilomar, California, organized by the Krohn-Rhodes Research Institute.     

Yet another application of a binomial recurrence order statistics

We investigate the moments of the maximum of a set of i.i.d geometric random variables. Computationally, the exact formula for the moments (which does not seem to be available in the literature) is inhibited by the presence of an alternating sum. A recursive expression for the moments is shown to be superior. However, the recursion can be both computationally intensive as well as subject to large round-off error when the set of random variables is large, due to the presence of factorial terms. To get around this difficulty we develop accurate asymptotic expressions for the moments and verify our results numerically.     

Reversible logic grammars for natural language parsing and generation

The use of a single grammar in natural language parsing and generation is most desirable for a variety of reasons, including efficiency, perspicuity, integrity, robustness, and a certain amount of elegance. These characteristics have been noted before by several researchers, but it was only recently that more serious attention started to be paid to the problem of creating a bidirectional system for natural language processing. In this paper we discuss a somewhat more radical version of the problem: given a parser for a language, can we reverse it so that it becomes an efficient generator for the same language? Furthermore, since both the parser and the generator are based upon the same grammar, are there any normalization conditions upon the form of the grammar that must be met in order to assure the maximum efficiency of the reversed program? Can other grammars be transformed into the normal form? We describe the results of an experiment with PROLOG-based logic grammar which has been derived from a substantial-coverage string grammar for English. We present an alogorithm for automated inversion of a unification parser into an efficient unification generator, using the collections of minimal sets of essential arguments for predicates. We discuss the scope of the present version of the algorithm and then point out several possible avenues for extension. We also outline a preliminary solution to the question of grammar's “normal form” and suggest a handful of normalizing transformations that can be used to enhance the efficiency of the generator. This research interacts closely with a Japanese-English machine translation project at New York University, for which the first implementation of the inversion algorithm has been prepared.     

Automatic generation of MPEG test streams from high-level grammars

This paper describes a technique to generate complex, moving picture experts group (MPEG) data streams containing packets which range through a selected set of variants, as allowed by the grammar of the packet stream. The Prolog logic programming language has been used, whose declarative power allows data generation almost directly from the grammar, i.e. without the need for explicitly programming a grammar traversal mechanism as would be the case with an imperative language. A reasonably declarative style of grammar and variation definition is achieved, and at the same time, a reasonably efficient generation process. The basic idea is to use a declarative fragment of Prolog for the grammar, but to use imperative features of Prolog for matters like packet enumeration and packet payload generation. Generation of test data from grammars is not new, nor is the use of Prolog programs for generation of test data, but as far as we know, the combination of both has not reported on in the literature, nor its application to MPEG demultiplexers/decoders.     

Yet another application of the Monte Carlo method for modeling in the field of biomedicine

By means of Monte Carlo simulations performed in the C programming language, an example of scientific programming for the generation of pseudorandom numbers relevant to both teaching and research in the field of biomedicine is presented. The relatively simple algorithm proposed makes possible the statistical analysis of sequences of random numbers. The following three generators of pseudorandom numbers were used: the rand function contained in the stdlib.h library of the C programming language, Marsaglia's generator, and a chaotic function. The statistical properties of the sequences generated were compared, identical parameter values being adopted for this purpose. The properties of two estimators in finite samples of the pseudorandom numbers were also evaluated and, under suitable conditions, both the maximum-likelihood and method of moments proved to be good estimators. The findings demonstrated that the proposed algorithm appears to be suitable for the analysis of data from random experiments, indicating that it has a large variety of possible applications in the clinical practice.