Report Number: CSL-TR-93-562
Institution: Stanford University, Computer Systems Laboratory
Title: An Efficient Top-Down Parsing Algorithm for General
Author: Sankar, Sriram
Date: February 1993
Abstract: This report describes a new algorithm for top-down parsing of
general context-free grammars. The algorithm does not require
any changes to be made to the grammar, and can parse with
respect to any grammar non-terminal as the start symbol. It
is possible to generate all possible parse trees of the input
string in the presence of ambiguous grammars. The algorithm
reduces to recursive descent parsing on LL grammars.
This algorithm is ideal for use in software development
environments which include tools such as syntax-directed
editors and incremental parsers, where the language syntax is
an integral part of the user-interface. General context-free
grammars can describe the language syntax more intuitively
than, for example, LALR(1) grammars. This algorithm is also
applicable to batch-oriented language processors, especially
during the development of new languages, where frequent
changes are made to the language syntax and new prototype
parsers need to be developed quickly.
A prototype implementation of a parser generator that
generates parsers based on this algorithm has been built.
Parsing speeds of around 1000 lines per second have been
achieved on a Sun SparcStation 2.
This demonstrated performance is more than adequate for
syntax-directed editors and incremental parsers, and in most
cases, is perfectly acceptable for batch-oriented language