Scannerless parsing

<h2 id="advantages">Advantages</h2>
<ul><li>Only one <a href="/facts/Metalanguage/peNXFNUV">metalanguage</a> is needed</li>
<li>Non-regular lexical structure is handled easily</li>
<li>"Token classification" is unneeded which removes the need for design accommodations such as "<a href="/facts/The_lexer_hack/BlqdnN15">the lexer hack</a>" and language <a href="/facts/Reserved_word/pHDlUUgY">reserved words</a> (such as "while" in <a href="/facts/C_(programming_language)/Ky2No763">C</a>)</li>
<li>Grammars can be compositional (can be merged without human intervention) [a]</li></ul>
<h2 id="disadvantages">Disadvantages</h2>
<ul><li>Since the lexical scanning and syntactic parsing are combined, the resulting parser tends to be more complicated and thus harder to understand and debug. The same will hold for the associated grammar, if a grammar is used to generate the parser.</li>
<li>The resulting parser tends to be significantly less efficient than a lexer-parser pipeline with regard to both time and memory.<a class="footnote-ref" id="fnref:1" href="#fn:1"><sup>1</sup></a></li></ul>
<h2 id="implementations">Implementations</h2>
<ul><li>SGLR is a parser for the modular <a href="/facts/Syntax_Definition_Formalism/j5VpTd4W">Syntax Definition Formalism</a> (SDF), and is part of the ASF+SDF Meta-Environment and the Stratego/XT program transformation system.</li>
<li>JSGLR, a pure Java implementation of SGLR, also based on SDF.</li>
<li><a href="/facts/TXL_(programming_language)/Nohn8cGt">TXL</a> supports character-level parsing.</li>
<li>dparser generates ANSI C code for scannerless <a href="/facts/GLR_parser/Pn3I1AYt">GLR parsers</a>.</li>
<li><a href="/facts/Spirit_Parser_Framework/cDuudXYM">Spirit</a> allows for both scannerless and scanner-based parsing.</li>
<li><a href="/facts/Scannerless_Boolean_Parser/WI25EpgV">SBP</a> is a scannerless parser for <a href="/facts/Boolean_grammar/q2IP1ocH">Boolean grammars</a> (a superset of context-free grammars), written in Java.</li>
<li>Laja is a two-phase scannerless parser generator with support for mapping the grammar rules into objects, written in Java.</li>
<li>The <a href="/facts/Raku_rules/fHPb7SXl">Raku grammars</a> feature of the general purpose programming language <a href="/facts/Raku_(programming_language)/9eYW7vRJ">Raku</a>.</li>
<li>PyParsing is a scannerless parser written in pure Python.</li>
<li><a href="/facts/META_II/eA8GbqrX">META II</a> Has built in token parsers functions.</li>
<li><a href="/facts/TREE-META/KHSWJaQ3">TREE-META</a> Like META II also is scannerless having builtin lexer functions.</li>
<li><a href="/facts/Metacompiler/Ud51JPrv">CWIC</a> compiler for writing and implementing compilers. Has token rules as part of its language. Rules in CWIC were compiled into Boolean functions returning success or failure.</li></ul>
<h2 id="notes">Notes</h2>
<ul><li>a  This is because parsing at the character level makes the language recognized by the parser a single <a href="/facts/Context-free_language/sHDxB5So">context-free language</a> defined on characters, as opposed to a context-free language of sequences of strings in <a href="/facts/Regular_language/ahxw67T1">regular languages</a>. Some lexerless parsers handle the entire class of context-free languages, which is closed under composition.</li></ul>

<h2 id="further-reading">Further reading</h2>
<ul><li><a href="/facts/Eelco_Visser/V6klxEKA">Visser, E.</a> (August 1997). <i>Scannerless Generalized-LR Parsing</i>. The Netherlands: University of Amsterdam. <a href="/facts/CiteSeerX_(identifier)/SceDmd3c">CiteSeerX</a> <a href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.37.7828">10.1.1.37.7828</a>.</li></ul>

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

<ol>
<li id="fn:1"><p>Economopoulos, Giorgios; Klint, Paul; Vinju, Jurgen (2009). "Faster Scannerless GLR Parsing" (PDF). Compiler Construction. Lecture Notes in Computer Science. Vol. 5501. pp. 126–141. doi:10.1007/978-3-642-00722-4_10. ISBN 978-3-642-00721-7. <a href="978-3-642-00721-7" target="_blank">978-3-642-00721-7</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li>
</ol>

Scannerless parsing open-in-new

Scannerless parsing