One-pass, optimal tree parsing — with or without trees

Todd A. Proebsting, Benjamin R. Whaley

Research output: Chapter in Book/Report/Conference proceedingConference contribution

7 Scopus citations


This paper describes the theory behind and implementation of wburg, a code-generator generator that accepts tree grammars as input and produces a code generator that emits an optimal parse of an IR tree in just a single bottom-up pass. Furthermore, wburg eliminates the need for an explicit IR tree altogether. The grammars that wburg-generated parsers can parse are a proper subset of those that two-pass systems can handle. However, analysis indicates that wburg can optimally handle grammars for most instruction sets (e.g., SPARC, MIPS R3000, and x86).

Original languageEnglish (US)
Title of host publicationCompiler Construction - 6th International Conference, CC 1996, Proceedings
EditorsTibor Gyimothy
Number of pages13
ISBN (Print)9783540610533
StatePublished - 1996
Event6th International Conference on Compiler Construction, CC 1996 - Linkoping, Sweden
Duration: Apr 24 1996Apr 26 1996

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other6th International Conference on Compiler Construction, CC 1996

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'One-pass, optimal tree parsing — with or without trees'. Together they form a unique fingerprint.

Cite this