Back to search

Clemson University

PSLR(1): Pseudo-Scannerless Minimal LR(1) for the Deterministic Parsing of Composite Languages

Abstract

dc:description.abstract

Composite languages are composed of multiple sub-languages. Examples include the parser specification languages read by parser generators like Yacc, modern extensible languages with complex layers of domain-specific sub-languages, and even traditional programming languages like C and C++. In this dissertation, we describe PSLR(1), a new scanner-based LR(1) parser generation system that automatically eliminates scanner conflicts typically caused by language composition. The fundamental premise of PSLR(1) is the pseudo-scanner, a scanner that only recognizes tokens accepted by the current parser state. However, use of the pseudo-scanner raises several unique challenges, for which we describe a novel set of solutions. One major challenge is that practical LR(1) parser table generation algorithms merge parser states, sometimes inducing incorrect pseudo-scanner behavior including new conflicts. Our solution is a new extension of IELR(1), an algorithm we have previously described for generating minimal LR(1) parser tables. Other contributions of our work include a robust system for handling the remaining scanner conflicts, a correction for syntax error handling mechanisms that are also corrupted by parser state merging, and a mechanism to enable scoping of syntactic declarations in order to further improve the modularity of sub-language specifications. While the premise of the pseudo-scanner has been described by other researchers independently, we expect our improvements to distinguish PSLR(1) as a significantly more robust scanner-based parser generation system for traditional and modern composite languages.

Degree

thesis:*
Name thesis:degree_name
Doctor of Philosophy (PhD)
Level thesis:degree_level
Dissertation
Discipline thesis:degree_discipline
Computer Science

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Denny, Joel
Contributors dc:contributor
  • Malloy, Brian A
  • Grossman , Harold C
  • Hallstrom , Jason
  • Hedetniemi , Stephen T

Subjects

dc:subject × 7

Identifiers

dc:identifier.*
Repository record dc:identifier
https://open.clemson.edu/all_dissertations/519

Chain of custody

source
Harvested from
Clemson University
Base URL
open.clemson.edu/do/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Denny, Joel. PSLR(1): Pseudo-Scannerless Minimal LR(1) for the Deterministic Parsing of Composite Languages. Dissertation thesis, https://open.clemson.edu/all_dissertations/519