computer science

Scannerless parsing

Scannerless parsing is a computer science topic covered in the lgStudy science library. This page brings together a partial reference excerpt, illustrations, worked examples, real-world applications and a short study plan, so you can understand Scannerless parsing rather than just read about it. In short: In computer science, scannerless parsing (also called lexerless parsing) performs tokenization (breaking a stream of characters into words) and parsing (arranging the words into phrases) in a single step, rather than breaking it up into a pipeline of a lexer followed by a parser, executing concurrently. A language grammar is scannerless if it uses a single formalism to express both the lexical (word level) and phras…

Key takeaways

Scannerless parsing belongs to computer science; place it in that map before memorising details.
Learn the definition first, then one example that makes the definition concrete.
Connect Scannerless parsing to a quantity you can measure, compute or draw — that is where exam questions come from.
Reproduce the core statement of Scannerless parsing from memory before moving on to harder problems.

Reference excerpt

In computer science, scannerless parsing (also called lexerless parsing) performs tokenization (breaking a stream of characters into words) and parsing (arranging the words into phrases) in a single step, rather than breaking it up into a pipeline of a lexer followed by a parser, executing concurrently. A language grammar is scannerless if it uses a single formalism to express both the lexical (word level) and phrase level structure of the language. Dividing processing into a lexer followed by a parser is more modular; scannerless parsing is primarily used when a clear lexer–parser distinction is unneeded or unwanted. Examples of when this is appropriate include TeX, most wiki grammars, makefiles, simple application-specific scripting languages, and Raku.

Advantages Only one metalanguage is needed Non-regular lexical structure is handled easily "Token classification" is unneeded which removes the need for design accommodations such as "the lexer hack" and language reserved words (such as "while" in C) Grammars can be compositional (can be merged without human intervention) [a]

Disadvantages 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. The resulting parser tends to be significantly less efficient than a lexer-parser pipeline with regard to both time and memory.

Implementations SGLR is a parser for the modular Syntax Definition Formalism (SDF), and is part of the ASF+SDF Meta-Environment and the Stratego/XT program transformation system. JSGLR, a pure Java implementation of SGLR, also based on SDF. TXL supports character-level parsing. dparser generates ANSI C code for scannerless GLR parsers. Spirit allows for both scannerless and scanner-based parsing. SBP is a scannerless parser for Boolean grammars (a superset of context-free grammars), written in Java. Laja is a two-phase scannerless parser generator with support for mapping the grammar rules into objects, written in Java. The Raku grammars feature of the general purpose programming language Raku. PyParsing is a scannerless parser written in pure Python. META II Has built in token parsers functions. TREE-META Like META II also is scannerless having builtin lexer functions. CWIC 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.

Notes a This is because parsing at the character level makes the language recognized by the parser a single context-free language defined on characters, as opposed to a context-free language of sequences of strings in regular languages. Some lexerless parsers handle the entire class of context-free languages, which is closed under composition.

References

Further reading Visser, E. (August 1997). Scannerless Generalized-LR Parsing. The Netherlands: University of Amsterdam. CiteSeerX 10.1.1.37.7828. {{cite book}}: Cite uses deprecated parameter |citeseerx= (help)

Worked examples

Example 1 — a first encounter with Scannerless parsing

Start with the simplest possible case. Write down what Scannerless parsing claims or describes in one sentence, then invent the smallest concrete situation in which that sentence is true. In computer science, the smallest case is usually a single object, a single equation or a single measurement. Check that every symbol or term in your sentence has a meaning in that case.

Example 2 — changing one variable

Take the situation from Example 1 and change exactly one quantity: double it, halve it, or set it to zero. Predict what should happen to Scannerless parsing before you calculate. Comparing your prediction with the result is the fastest way to find out whether you understand the idea or only the words.

Example 3 — an exam-style question

Typical questions about Scannerless parsing ask you to (a) state it precisely, (b) apply it to given data, and (c) explain a limitation. Practise writing all three answers in under five minutes; the third part is what separates a full-mark answer from an average one.

Applications of Scannerless parsing

In research: Scannerless parsing appears in computer science research whenever the underlying quantities have to be modelled precisely. Papers usually cite it as a starting assumption and then explore where it breaks down.
In technology and industry: Engineering practice reuses Scannerless parsing in design rules, simulations and safety margins. Knowing the idea lets you read a specification sheet and understand why the numbers look the way they do.
In the classroom: Scannerless parsing is common in secondary-school and first-year university syllabi. It links to neighbouring topics Parsing algorithms, so understanding it makes those chapters shorter.
In everyday life: Look for Scannerless parsing outside the textbook — in sport, cooking, traffic, electronics or the sky above you. An example you found yourself is remembered far longer than one you were given.

Ask Teacher Smith questions about this articleOpens your AI tutor with a question about “Scannerless parsing” →

Affiliate

Preply — study more efficiently by working with a personal tutor. 50% off.

How to study Scannerless parsing in 20 minutes

Read the reference excerpt below once, without taking notes.
Close the page and write down what Scannerless parsing means in your own words.
Compare your version with the excerpt and mark what you missed.
Work through the three examples above with pen and paper.
Explain Scannerless parsing out loud to somebody else — or to Teacher Smith in the lgStudy chat.

Frequently asked questions

What is Scannerless parsing in simple terms?

Why does Scannerless parsing matter?

Because it connects several computer science ideas at once: it gives you a definition you can apply, a quantity you can calculate, and a way to check whether a result is plausible.

How should I study Scannerless parsing?

Read the excerpt, restate it from memory, then work through the examples and applications listed on this page. The five-step study plan above takes about twenty minutes.

What does this page cover?

It gives you a compact reference excerpt plus original lgStudy explanations, examples, applications and study material on Scannerless parsing.