BIB-VERSION:: CS-TR-v2.0
          ID:: STAN//CSL-TR-93-562
       ENTRY:: October 26, 1995
ORGANIZATION:: Stanford University, Computer Systems Laboratory
       TITLE:: An Efficient Top-Down Parsing Algorithm for General
               Context-Free Grammars
        TYPE:: Technical Report
      AUTHOR:: Sankar, Sriram
        DATE:: February 1993
       PAGES:: 26
    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
               processors.
       NOTES:: [Adminitrivia V1/Prg/19951026]
         END:: STAN//CSL-TR-93-562