Generalised LR parsing algorithms

• 1. Introduction
  • 1.1 Motivation
  • 1.2 Contributions
  • 1.3 Outline of thesis
• 2. Recognition and parsing
  • 2.1 Languages and grammars
  • 2.2 Context-free grammars
    • 2.2.1 Generating sentences
    • 2.2.2 Backus Naur form
    • 2.2.3 Recognition and parsing
    • 2.2.4 Parse trees
  • 2.3 Parsing context-free grammars
    • Top-down parsing
    • 2.3.2 Bottom-up parsing
    • 2.3.3 Parsing with searching
    • 2.3.4 Ambiguous grammars
  • 2.4 Parsing deterministic context-free grammars
    • 2.4.1 Constructing a handle finding automaton
    • 2.4.2 Parsing with a DFA
    • 2.4.3 LR parsing
    • 2.4.2 Parsing with lookahead
  • 2.5 Summary
• 3. The development of generalised parsing
  • 3.1 Overview
  • 3.2 Unger’s method
    • The CYK algorithm
  • 3.4 Summary
• 4. Generalised LR parsing
  • 4.1 Using the LR algorithm to parse all context-free grammars
  • 4.2 Tomita’s Generalised LR parsing algorithm
    • 4.2.1 Graph structured stacks
    • 4.2.2 Example - constructing a GSS
  • 4.2.3 Tomita’s Algorithm 1
    • 4.2.4 Parsing with \(\epsilon\)-rules
    • 4.2.5 Tomita’s Algorithm 2
  • 4.3 Farshi’s extension of Algorithm 1
    • Farshi’s recogniser
    • 4.3.1 Example - a hidden-left recursive grammar
    • 4.3.2 Example - a hidden-right recursive grammar
  • 4.4 Constructing derivations
    • 4.4.1 Shared packed parse forests
    • 4.4.2 Tomita’s Algorithm 4
    • 4.4.3 Rekers’ SPPF construction
    • Rekers’ parser with improved sharing in the SPPF
  • 4.5 Summary
• 5. Right Nulled Generalised LR parsing
  • 5.1 Tomita’s Algorithm 1e
    • 5.1.1 Example - a hidden-left recursive grammar
    • 5.1.2 Paths in the GSS
    • Example - an incorrect parse
  • 5.2 Right Nulled parse tables
  • 5.3 Reducing non-determinism
  • 5.4 The RNGLR recognition algorithm
    • RNGLR recogniser
  • 5.5 The RNGLR parsing algorithm
    • RNGLR parser
  • 5.6 Resolvability
  • 5.7 Summary
• 6.Binary Right Nulled Generalised LR parsing
  • 6.1 The worst case complexity of GLR recognisers
    • Example - Recognition in \(O(n^{4})\) time
  • 6.2 Achieving cubic time complexity by factoring the grammar
  • 6.3 Achieving cubic time complexity by modifying the parse table
  • 6.4 The BRNGLR recognition algorithm
    • BRNGLR recogniser
  • 6.5 Performing ‘on-the-fly’ reduction path factorisation
    • BRNGLR ‘on-the-fly’ recogniser
  • 6.6 GLR parsing in at most cubic time
    • BRNGLR parser
    • Example - parsing in \(O(n^{3})\) time
  • 6.7 Packing of bookkeeping SPPF nodes
    • Example - how to pack bookkeeping SPPF nodes
  • 6.8 Summary
• 7.Reduction Incorporated Generalised LR parsing
  • 7.1 The role of the stack in bottom-up parsers
  • 7.2 Constructing the Intermediate Reduction Incorporated Automata
    • IRIA construction algorithm
  • 7.3 Reducing non-determinism in the IRIA
  • 7.4 Regular recognition
    • 7.4.1 Recursion call automata
    • 7.4.2 Parse table representation of RCA
  • 7.5 Generalised regular recognition
    • Example - right and hidden-left recursion
    • Example - further issues surrounding hidden-left recursion
    • Example - ensuring all pop actions are done
    • RIGLR recogniser
  • 7.6 Reducing the non-determinism in the RCA
    • Reducing the number of processes in each \(U_{i}\)
  • 7.8 Generalised regular parsing
    • 7.8.1 Constructing derivation trees
    • 7.8.2 Constructing an SPPF
    • RIGLR parser
  • 7.9 Summary
• 8 Other approaches to generalised parsing
  • 8.1 Mark-Jan Nederhof and Janos J. Sarbo
  • 8.2 James R. Kipps
    • Kipps’ \(O(n^{3})\) recognition algorithm
  • 8.3 Jay Earley
    • Earley’s algorithm
  • 8.4 Bernard Lang
  • 8.5 Klaas Sikkel
• 9. Some generalised parser generators
  • 9.1 ANTLR
  • 9.2 PRECCx
  • 9.3 JavaCC
  • 9.4 BtYacc
  • 9.5 Bison
  • 9.6 Elkhound: a GLR parser generator
  • 9.7 Asf+Sdf Meta-Environment
• 10. Experimental investigation
  • 10.1 Overview of chapter
  • 10.2 The Grammar Tool Box and Parser Animation Tool
  • 10.3 The grammars
  • 10.4 The input strings
  • 10.5 Parse table sizes
  • 10.6 The performance of the RNGLR algorithm compared to the Tomita and Farshi algorithms
    • A non-cubic example
    • 10.6.2 Using different LR tables
  • 10.6.3 The performance of Farshi’s algorithms
  • 10.7 The performance of the BRNGLR algorithm
    • 10.7.1 GSS construction
    • 10.7.2 SPPF construction
  • 10.8 The performance of Earley algorithm
  • 10.9 The performance of the RIGLR algorithm
    • 10.9.1 The size of RIA and RCA
    • 10.9.2 Asymptotic behaviour
• 11. Concluding remarks
  • 11.1 Conclusions
  • 11.2 Future work
    • Resolution of ambiguities
    • Investigating the effect of the additional GSS nodes created by the BRNGLR algorithm
    • Using the RIGLR algorithm to improve the performance of scannerless parsers
    • Error reporting in GLR parsers

Indices and tables

• Search Page