GLR parser

<h2 id="algorithm">Algorithm</h2>
<p>Briefly, the GLR algorithm works in a manner similar to the <a href="/facts/LR_parser/bpMod8K0">LR parser</a> algorithm, except that, given a particular grammar, a GLR parser will process all possible interpretations of a given input in a <a href="/facts/Breadth-first_search/2kulDXCx">breadth-first search</a>. On the front-end, a GLR <a href="/facts/Parser_generator/Ud51JPrv">parser generator</a> converts an input grammar into parser tables, in a manner similar to an LR generator. However, where LR parse tables allow for only one <a href="/facts/State_transition/eK0E4j8R">state transition</a> (given a state and an input token), GLR parse tables allow for multiple transitions. In effect, GLR allows for shift/reduce and reduce/reduce conflicts.
</p><p>When a conflicting transition is encountered, the parse stack is forked into two or more parallel parse stacks, where the state corresponding to each possible transition is at the top. Then, the next input token is read and used to determine the next transition(s) for each of the "top" states – and further forking can occur. If any given top state and input token do not result in at least one transition, then that "path" through the parse tables is invalid and can be discarded.
</p><p>A crucial optimization known as a <a href="/facts/Graph-structured_stack/lF74CGza">graph-structured stack</a> allows sharing of common prefixes and suffixes of these stacks, which constrains the overall <a href="/facts/Mathematical_optimization/oRn8Iv5I">search space</a> and memory usage required to parse input text. The complex structures that arise from this improvement make the search graph a <a href="/facts/Directed_acyclic_graph/k6zq1os9">directed acyclic graph</a> (with additional restrictions on the "depths" of various nodes), rather than a tree.
</p>
<h2 id="advantages">Advantages</h2>
<p>Recognition using the GLR algorithm has the same worst-case time complexity as the <a href="/facts/CYK_algorithm/W2J1SJ9z">CYK algorithm</a> and <a href="/facts/Earley_algorithm/b8XkRfW2">Earley algorithm</a>: <i>O</i>(<i>n</i>3). However, GLR carries two additional advantages:
</p>
<ul><li>The time required to run the algorithm is proportional to the degree of nondeterminism in the grammar: on deterministic grammars the GLR algorithm runs in <i>O</i>(<i>n</i>) time (this is not true of the Earley and CYK algorithms, but the original Earley algorithms can be modified to ensure it)</li>
<li>The GLR algorithm is "<a href="/facts/Online_algorithm/64TsU7Yz">online</a>" – that is, it consumes the input tokens in a specific order and performs as much work as possible after consuming each token (also true for Earley).</li></ul>
<p>In practice, the grammars of most programming languages are deterministic or "nearly deterministic", meaning that any nondeterminism is usually resolved within a small (though possibly unbounded) number of tokens. Compared to other algorithms capable of handling the full class of context-free grammars (such as <a href="/facts/Earley_parser/b8XkRfW2">Earley parser</a> or <a href="/facts/CYK_algorithm/W2J1SJ9z">CYK algorithm</a>), the GLR algorithm gives better performance on these "nearly deterministic" grammars, because only a single stack will be active during the majority of the parsing process.
</p><p>GLR can be combined with the <a href="/facts/LALR/4ey0KkTU">LALR</a>(1) algorithm, in a hybrid parser, allowing still higher performance.<a class="footnote-ref" id="fnref:5" href="#fn:5"><sup>5</sup></a>
</p>
<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Comparison_of_parser_generators/ECnFQrmV">Comparison of parser generators</a></li>
<li><a href="/facts/DMS_Software_Reengineering_Toolkit/G3Xeppn0">DMS Software Reengineering Toolkit</a></li>
<li><a href="/facts/GNU_Bison/tTrt7Vrw">GNU Bison</a>, a parser generator that can create LALR and GLR parsers</li>
<li><a href="/facts/Packrat_parser/8XdfJ7D0">Packrat parser</a>, another parser that can parse ambiguous and nondeterministic languages</li></ul>

<h2 id="further-reading">Further reading</h2>
<ul><li>Grune, Dick; Jacobs, Ceriel J.H. (2008). <i>Parsing Techniques</i>. Springer Science+Business Media. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-0-387-20248-8.</li>
<li>Tomita, Masaru (1984). "LR parsers for natural languages". <i>COLING</i>. 10th International Conference on Computational Linguistics. pp. 354–357.</li>
<li>Tomita, Masaru (1985). "An efficient context-free parsing algorithm for natural languages". <i>IJCAI</i>. International Joint Conference on Artificial Intelligence. pp. 756–764.</li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1"><p>Masaru Tomita (6 December 2012). Generalized LR Parsing. Springer Science & Business Media. ISBN 978-1-4615-4034-2. <a href="978-1-4615-4034-2" target="_blank">978-1-4615-4034-2</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li>
<li id="fn:2"><p>Lang, Bernard (1974). "Deterministic techniques for efficient non-deterministic parsers". In Loeckx, J. (ed.). Automata, Languages and Programming. Lecture Notes in Computer Science. Vol. 14. Saarbrücken: Springer. pp. 255–269. doi:10.1007/3-540-06841-4_65. ISBN 978-3-540-06841-9. ISSN 0302-9743. <a href="978-3-540-06841-9" target="_blank">978-3-540-06841-9</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li>
<li id="fn:3"><p>Masaru Tomita. Efficient parsing for natural language. Kluwer Academic Publishers, Boston, 1986. <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li>
<li id="fn:4"><p>Lang, Bernard (December 1971). "Parallel non-deterministic bottom-up parsing". ACM SIGPLAN Notices. Proceedings of the international symposium on Extensible languages. 6 (12): 56–57. doi:10.1145/942582.807982. <a href="https://www.researchgate.net/publication/255677839" target="_blank">https://www.researchgate.net/publication/255677839</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li>
<li id="fn:5"><p>"Elkhound, Elsa and Cqual++: Open-Source Static Analysis for C++". YouTube. 22 August 2012. Archived from the original on 2021-12-21. <a href="https://www.youtube.com/watch?v=uncfFsbUF68" target="_blank">https://www.youtube.com/watch?v=uncfFsbUF68</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></p></li>
</ol>

GLR parser open-in-new

GLR parser