Abstract/Details

PSLR(1): Pseudo-scannerless minimal LR(1) for the deterministic parsing of composite languages


2010 2010

Other formats: Order a copy

Abstract (summary)

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 pseudoscanner 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.

Indexing (details)


Subject
Computer science
Classification
0984: Computer science
Identifier / keyword
Applied sciences; Bison; Extensible languages; Grammarware; IELR(1); Scanner-based parsers; Scannerless parsers
Title
PSLR(1): Pseudo-scannerless minimal LR(1) for the deterministic parsing of composite languages
Author
Denny, Joel E.
Number of pages
122
Publication year
2010
Degree date
2010
School code
0050
Source
DAI-B 71/05, Dissertation Abstracts International
Place of publication
Ann Arbor
Country of publication
United States
ISBN
9781109746488
Advisor
Malloy, Brian A.
Committee member
Grossman, Harold C.; Hallstrom, Jason; Hedetniemi, Stephen T.
University/institution
Clemson University
Department
Computer Science
University location
United States -- South Carolina
Degree
Ph.D.
Source type
Dissertations & Theses
Language
English
Document type
Dissertation/Thesis
Dissertation/thesis number
3402515
ProQuest document ID
305191666
Copyright
Database copyright ProQuest LLC; ProQuest does not claim copyright in the individual underlying works.
Document URL
http://search.proquest.com/docview/305191666
Access the complete full text

You can get the full text of this document if it is part of your institution's ProQuest subscription.

Try one of the following:

  • Connect to ProQuest through your library network and search for the document from there.
  • Request the document from your library.
  • Go to the ProQuest login page and enter a ProQuest or My Research username / password.