NDLI: A new grammatical transformation into LL(k) form (Extended Abstract)

Please wait, while we are loading the content...

Degrees of translatability and canonical forms in program schemas: Part I

Semantics and axiomatics of a simple recursive language.

The decidability of equivalence for deterministic finite-turn pushdown automata

Storage requirements for deterministic / polynomial time recognizable languages

Complete problems for deterministic polynomial time

Some simplified NP-complete problems

Computational parallels between the regular and context-free languages

Complexity measures for regular expressions

The power of negative thinking in multiplying Boolean matrices

Determining graph properties from matrix representations

Computational complexity of probabilistic Turing machines

Polynomial and abstract subrecursive classes

Comparison of polynomial-time reducibilities

A characterization of the power of vector machines

On the lengths of proofs in the propositional calculus (Preliminary Version)

On the complexity of the theories of weak direct products (Preliminary Report)

Structure of complexity in the weak monadic second-order theories of the natural numbers

Linear time algorithm for isomorphism of planar graphs (Preliminary Report)

Testing graph connectivity

Efficient stable sorting with minimal extra space

An efficient algorithm for computing optimal disk merge patterns. (Extended Abstract)

Limitations of synchronization primitives with conditional branching and global variables

Construction with parallel derivatives of the closure of a parallel program schema

Parallel scheduling of programs in a restricted model of computation

Some restrictions on W-grammars

A new grammatical transformation into LL(k) form (Extended Abstract)

Observations on nondeterministic multidimensional iterative arrays

Intersections of linear context-free languages and reversal-bounded multipushdown machines (Extended Abstract)

Managing storage for extendible arrays (Extended Abstract)

A partial solution to the reachability-problem for vector-addition systems

On some generalizations of binary search

Computational complexity and numerical stability

New algorithms and lower bounds for the parallel evaluation of certain rational expressions

Combining dimensionality and rate of growth arguments for establishing lower bounds on the number of multiplications

On the number of additions to compute specific polynomials (Preliminary Version)

A new grammatical transformation into LL(k) form (Extended Abstract)

Content Provider	ACM Digital Library
Author	Hammer, Michael
Abstract	For some time, it has been recognized that left-to-right deterministic top-down parsing has a number of features to recommend it. The logic of such a parser is easily expressed as a one-state pushdown machine, and very flexible translations can readily be performed in conjunction with top-down processing. The major difficulty with this style of parsing is that there are relatively few grammars which satisfy the rather restrictive requirements to admit of top-down parsing (the LL(k) grammars), in comparsion with grammars that can be parsed deterministically bottom-up (the LR(k) grammars). There has been some research along the lines of trying to apply transformations to non-LL(k) grammars in order to convert them into equivalent LL(k) form [1,2,3]; the most successful approach has been that of Rosenkrantz and Lewis [4]. They define class of grammars, the LC(k) grammars, which can be parsed in a mixed hybrid of top-down bottom-up techniques; this class strictly includes the LL(k) grammars, as well as many interesting but non-LL(k) grammars. They then provide a deterministic algorithm for converting any LC(k) grammar into an equivalent LL(k) grammar. This work is a generalization of, and in the same spirit as, the Lewis and Rosenkrantz program. We investigate a new hybrid parsing method, basically bottom-up in character, but which contains a minimal infusion of top-down ideas. We consider the class of grammars which can be parsed by this method, and observe that it strictly includes the class of LC(k) grammars. Then we exhibit an algorithm for deriving from any such grammar an equivalent LL(k) grammar; this derived grammar is also as “useful” as the original one in directing compilation activities, for it can support translations equivalent to those supportable by the original grammar.
Starting Page	266
Ending Page	275
Page Count	10
File Format	PDF
DOI	10.1145/800119.803904
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	1974-04-30
Publisher Place	New York
Access Restriction	Subscribed
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in