Back to search

Rochester Institute of Technology

Table driven prediction for recursive descent LL(k) parsers

Abstract

dc:description.abstract

Programming languages are typically described in BNF or some extension of BNF, and the process of converting these descriptions into parsers is performed by parser generators. Some of the parser generators that convert LL grammars into parsers construct them to use recursive descent that gives them context during execution. The context is provided by the execution stack as the parser descends into the grammar and this is what allows the full expressiveness of LL grammars. Table driven parsers can be generated instead but restrictions are placed on the LL grammars that can be accepted. The benefit of tables is that they facilitate a separation of syntax analysis and semantic code written by a language designer. They are also faster and they simplify language implementation and modification. This paper proposes the possibility of a hybrid system that makes decisions using tables but once decisions are made recursive descent is employed to maintain context. The benefits of each system are maintained, and the drawbacks are mitigated. Also discussed are the modifications made to an existing parser generator, oops (version 2), so that it accepts LL(k) grammars and builds parsers using this system as proof-of-concept.

Degree

thesis:*
Name thesis:degree_name
Computer Science (MS)
Level thesis:degree_level
Thesis
Discipline thesis:degree_discipline
Computer Science (GCCIS)

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Leiserson, William M.
Contributors dc:contributor
  • James Heliotis

Identifiers

dc:identifier.*
Repository record dc:identifier
https://repository.rit.edu/theses/8464

Chain of custody

source
Harvested from
Rochester Institute of Technology
Base URL
repository.rit.edu/do/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Leiserson, William M.. Table driven prediction for recursive descent LL(k) parsers. Thesis thesis, https://repository.rit.edu/theses/8464