Scott G. McPeak

EECS Department, University of California, Berkeley

Technical Report No. UCB/CSD-02-1214

, 2002

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2002/CSD-02-1214.pdf

Elkhound is a parser generator based on the Generalized LR (GLR) parsing algorithm. Because it uses GLR, Elkhound can parse with any context-free grammar, including those that are ambiguous or require unbounded lookahead. Due to a novel improvement to the GLR algorithm, wherein the parser can choose between GLR and ordinary LR on a token-by-token basis, Elkhound parsers are about as fast as LALR(1) parsers on deterministic portions of the input. <p>Unlike existing GLR implementations, Elkhound allows the user to associate arbitrary action code with reductions, and to directly manage subtree sharing and merging. These capabilities make Elkhound adaptable to a wide range of applications and memory management strategies. <p>To demonstrate Elkhound's effectiveness, we used it to build a parser for C++, a language notorious for being difficult to parse. Our C++ parser is small (3500 lines), efficient, maintainable, and elegantly handles even the most troublesome constructs -- by delaying disambiguation until semantic analysis when necessary.

---

BibTeX citation:

@techreport{McPeak:CSD-02-1214,
    Author= {McPeak, Scott G.},
    Title= {Elkhound: A Fast, Practical GLR Parser Generator},
    Year= {2002},
    Month= {Dec},
    Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2002/6187.html},
    Number= {UCB/CSD-02-1214},
    Abstract= {Elkhound is a parser generator based on the Generalized LR (GLR) parsing algorithm. Because it uses GLR, Elkhound can parse with any context-free grammar, including those that are ambiguous or require unbounded lookahead. Due to a novel improvement to the GLR algorithm, wherein the parser can choose between GLR and ordinary LR on a token-by-token basis, Elkhound parsers are about as fast as LALR(1) parsers on deterministic portions of the input. <p>Unlike existing GLR implementations, Elkhound allows the user to associate arbitrary action code with reductions, and to directly manage subtree sharing and merging. These capabilities make Elkhound adaptable to a wide range of applications and memory management strategies. <p>To demonstrate Elkhound's effectiveness, we used it to build a parser for C++, a language notorious for being difficult to parse. Our C++ parser is small (3500 lines), efficient, maintainable, and elegantly handles even the most troublesome constructs -- by delaying disambiguation until semantic analysis when necessary.},
}

EndNote citation:

%0 Report
%A McPeak, Scott G. 
%T Elkhound: A Fast, Practical GLR Parser Generator
%I EECS Department, University of California, Berkeley
%D 2002
%@ UCB/CSD-02-1214
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2002/6187.html
%F McPeak:CSD-02-1214