The Generalized LR (GLR) parsing algorithm is attractive for use in parsing programming languages because it is asymptotically efficient for typical grammars, and can parse with any context-free grammar, including ambiguous grammars. However, adoption of GLR has been slowed by high constant-factor overheads and the lack of a general, user-defined action interface.\parIn this paper we present algorithmic and implementation enhancements to GLR to solve these problems. First, we present a hybrid algorithm that chooses between GLR and ordinary LR on a token-by-token basis, thus achieving competitive performance for determinstic input fragments. Second, we describe a design for an action interface and a new worklist algorithm that can guarantee bottom-up execution of actions for acyclic grammars. These ideas are implemented in the Elkhound GLR parser generator.\parTo demonstrate the effectiveness of these techniques, we describe our experience using Elkhound to write a parser for C++, a language notorious for being difficult to parse. Our C++ parser is small (3500 lines), efficient and maintainable, employing a range of disambiguation strategies.
Keywords for this software
References in zbMATH (referenced in 7 articles , 1 standard article )
Showing results 1 to 7 of 7.
- Munkby, Gustav; Schupp, Sibylle: Automating exception-safety classification (2011)
- Brabrand, Claus; Giegerich, Robert; Møller, Anders: Analyzing ambiguity of context-free grammars (2010)
- Rinderknecht, Christian; Volanschi, Nic: Theory and practice of unparsed patterns for metacompilation (2010)
- Schmitz, Sylvain: An experimental ambiguity detection tool (2010)
- Scott, Elizabeth; Johnstone, Adrian: Recognition is not parsing - SPPF-style parsing from cubic recognisers (2010)
- Scott, Elizabeth; Johnstone, Adrian; Economopoulos, Rob: BRNGLR: a cubic Tomita-style GLR parsing algorithm (2007)
- McPeak, Scott; Necula, George C.: Elkhound: A fast, practical GLR parser generator (2004)