Marpa:...canless(3pm)

🌟 NAME 🌟

Marpa::R2::Scanless — the Scanless interface 💅 (and yeah, the manpage itself is Marpa::R2::Scanless(3pm), user contributed Perl documentation, bestie 🫶)

okay so listen. Scanless. It's so good. Let me tell you everything. Sit down, get a snack 🍓

---

✨ SYNOPSIS ✨

like, here's the vibe, no cap:

use Marpa::R2;

my $grammar = Marpa::R2::Scanless::G->new(
    {   bless_package => 'My_Nodes',
        source        => \(<<'END_OF_SOURCE'),
:default ::= action => [values] bless => ::lhs
lexeme default = action => [ start, length, value ]
    bless => ::name latm => 1

:start ::= Script
Script ::= Expression+ separator => comma
comma ~ [,]
Expression ::=
    Number bless => primary
    | '(' Expression ')' bless => paren assoc => group
   || Expression '**' Expression bless => exponentiate assoc => right
   || Expression '*' Expression bless => multiply
    | Expression '/' Expression bless => divide
   || Expression '+' Expression bless => add
    | Expression '-' Expression bless => subtract

Number ~ [\d]+
:discard ~ whitespace
whitespace ~ [\s]+
# allow comments
:discard ~ <hash comment>
<hash comment> ~ <terminated hash comment> | <unterminated
   final hash comment>
<terminated hash comment> ~ '#' <hash comment body> <vertical space char>
<unterminated final hash comment> ~ '#' <hash comment body>
<hash comment body> ~ <hash comment char>*
<vertical space char> ~ [\x{A}\x{B}\x{C}\x{D}\x{2028}\x{2029}]
<hash comment char> ~ [^\x{A}\x{B}\x{C}\x{D}\x{2028}\x{2029}]
END_OF_SOURCE
    }
);

my $recce = Marpa::R2::Scanless::R->new( { grammar => $grammar } );

my $input = '42*2+7/3, 42*(2+7)/3, 2**7-3, 2**(7-3)';
$recce->read(\$input);
my $value_ref = $recce->value();
die "No parse was found\n" if not defined $value_ref;

# Result will be something like "86.33... 126 125 16"
# depending on the floating point precision
my $result = ${$value_ref}->doit();

package My_Nodes;

sub My_Nodes::primary::doit { return $_[0]->[0]->doit() }
sub My_Nodes::Number::doit  { return $_[0]->[2] }
sub My_Nodes::paren::doit   { my ($self) = @_; $self->[1]->doit() }

sub My_Nodes::add::doit {
    my ($self) = @_;
    $self->[0]->doit() + $self->[2]->doit();
}

sub My_Nodes::subtract::doit {
    my ($self) = @_;
    $self->[0]->doit() - $self->[2]->doit();
}

sub My_Nodes::multiply::doit {
    my ($self) = @_;
    $self->[0]->doit() * $self->[2]->doit();
}

sub My_Nodes::divide::doit {
    my ($self) = @_;
    $self->[0]->doit() / $self->[2]->doit();
}

sub My_Nodes::exponentiate::doit {
    my ($self) = @_;
    $self->[0]->doit()**$self->[2]->doit();
}

sub My_Nodes::Script::doit {
    my ($self) = @_;
    return join q{ }, map { $_->doit() } @{$self};
}

literally a whole calculator in there, we love to see it 👑

---

🎀 ABOUT THIS DOCUMENT 🎀

okay so this document is the intro + the overview of Marpa's Scanless interface (SLIF). Marpa::R2's top-level page has an SLIF tutorial in it. So if you're new to Marpa, or new to its SLIF, you probs wanna start over there first 💖

Then this document picks up where the tutorial left off — we're going deeper, we're being more careful, we're looking at the actual concepts behind the SLIF. And if you want the hardcore reference stuff, that lives in separate documents: one for Scanless grammar objects, one for Scanless recognizer objects, and one for the Scanless DSL ✨

---

🦋 THE TWO LEVELS OF LANGUAGE DESCRIPTION 🦋

So. Programmers usually describe the syntax of a language at two levels. And it turns out the same two-level approach is also super convenient when you're actually implementing a parser for that language. But honestly, implementation aside? A two-level description just seems like the natural way to deal with the design questions that pop up in languages meant for practical, real-world use 🌸

Level one is structural. For example, here's how the Perl docs describe one of the forms that Perl's use statement takes:

use Module VERSION LIST

and over in Perl's source code (perly.y), something similar is what drives the parser.

Level two is lexical. For example, Perl's perlpodspec page has a bunch of statements like this:

[...] you can distinguish URL-links from anything else
by the fact that they match m/\A\w+:[^:\s]\S*\z/.

So like — the lexical level is character by character. And the structural level is less well-defined, but in practice it ignores most of the character-by-character stuff, and it essentially always dodges dealing with whitespace. 🙈

For reasons that'll make sense later, I'm gonna sometimes call the lexical level L0, and sometimes call the structural level G1. (And for historic reasons, L0 is sometimes also called G0. iykyk 💀)

And here's the part that's important: the difference between L0 and G1 is a difference in level of description, and it is NOT a difference in precision or exactness. fr fr. A structural description of Perl's use statement — a lot like the one I just showed you — is sitting right there in Perl's source code (perly.y), alongside many other similar structural-level descriptions. And those get used to generate the production parser for Perl. So like, clearly, structural-level descriptions are every bit as much a precision instrument as regular expressions 💅 periodt

---

🌈 A VERY SIMPLE LANGUAGE 🌈

To keep the focus on the really basic stuff, I'm gonna use a very simple language with a very simple semantics as the example 🧚

The language is made of decimal digits and ASCII spaces. And the semantics treats it as a series of integers that we're adding up.

Here are three strings in that language:

 8675311
 867 5311
 8 6 7 5 3 1 1

According to our semantics, these three strings contain one, two, and seven integers respectively. And the values of the three strings, per our semantics, are the sum of those integers: respectively, 8675311, 6178, and 31. 🔥

Now — people sometimes say, when describing languages like this, that "whitespace is ignored". And from the purely structural point of view, that can be kinda true. But from the lexical point of view? It's clearly, obviously, wildly false. 😭

Because when you combine the two levels of description, it becomes very hard to justify an assertion that "whitespace is ignored". Those three strings up there differ only in whitespace. And clearly the placement of the whitespace makes a vast difference — it has a major effect on the structure of the string, which then has a determining effect on its semantics. So. Yeah. Not ignored. Bestie. 🫶

---

💜 WHY THE STRUCTURAL LEVEL? 💜

So as we just saw, the structural level ignores essential aspects of the language. And it is possible to describe a language using a single level of description. So why even have a structural (G1) level? Why not a "unified" description instead of a "split" one? 🤔

Here's the tea: for most languages of practical size — especially the ones that deploy whitespace in a natural, intuitive way — a "unified" description rapidly becomes unwriteable, and it becomes unreadable even more rapidly.

The reader should be able to convince himself by taking the BNF from his favorite language standard and recasting it so that every rule takes whitespace into account. As one example, consider declarations in the C language:

unsigned int a;
unsigned*b;

In the first of those two lines, the whitespace is necessary. In the second line, whitespace would be allowed but it's not necessary.

And you can't just insist on whitespace between all symbols — because whitespace is, and should be, optional between some symbols and not between others. Where whitespace is optional versus where it shouldn't be depends on which characters are adjacent to each other. And that kind of character-level info is just not convenient to represent at the structural (G1) level. 😮‍💨

So yeah, it is certainly possible to write whitespace-aware BNF for that fragment of the C language. And it's certainly possible to extend it to include more and more of the declaration syntax. But before you've extended the BNF very much, you'll notice it's getting a lot harder to write. And you'll also notice that, as quickly as it's becoming hard to write, it's becoming "write-only" even more quickly — impossible to read. When you make your BNF whitespace-aware, you are more than doubling its size. And you're burying what intuition sees as the structure of the language under a deep pile of special cases. 💀

Long before you finish, I expect you'll realize that the "unified" approach is simply not workable. The authors of the C language relegated lexical issues to their own brief section, and ignored them in most of their language description. And that was clearly the only practical approach. 👑

---

🌸 INTERWEAVING THE TWO LEVELS 🌸

The scanless interface interweaves the "split" and "unified" approaches and — I hope 🥺 — preserves the best features of each. Here's the full syntax of the example whitespace-and-digit language, described using Marpa::R2's scanless interface:

:start ::= <number sequence>
<number sequence> ::= <number>+ action => add_sequence
number ~ digit+
digit ~ [0-9]
:discard ~ whitespace
whitespace ~ [\s]+

✨ A new operator ✨

In this example, three of the scanless interface's extensions to the Stuifzand interface are used. First up: the tilde (~) is used to separate the LHS and RHS of rules at the lexical (L0) level. Meanwhile, rules whose LHS and RHS are separated by the traditional BNF operator (::=) are at the structural (G1) level.

The programmer has to decide when to use the ~ operator and when to use the ::= operator, but honestly that choice will usually be easy: if you want Marpa to "do what I mean" with whitespace, you use the ::= operator. And if you want Marpa to do exactly what you say on a character-by-character basis? Then you use the ~ operator. no cap 🫶

🎀 Character classes 🎀

Perl character classes are now allowed on the RHS of prioritized and quantified rules. The example shows character classes only in L0 rules, but character classes can also be used in G1 rules, bestie. And when a character class is used in a G1 rule, it still must be implemented at the L0 level. Marpa knows this and "does what you mean." 💅

👑 Discard pseudo-rule 👑

A whole new type of rule is introduced here: a "discard" pseudo-rule. A discard pseudo-rule has a :discard pseudo-symbol on its LHS and one symbol name on its RHS.

It means: when the RHS symbol gets recognized, it should not be passed on as usual to the structural (G1) level. Instead, the lexical (L0) level will simply "discard" what it has found. In the example, whitespace is discarded. 🦋

and that's it for part 1, the lore continues in part 2 — don't go anywhere 💖

✨ Lexemes ✨

Okay bestie, this is where the two levels actually touch, and it's giving ✨plot twist✨. Tokens sitting right at the boundary between L0 and G1 are, like, the most important little guys in the whole system 💖

The top-level undiscarded symbols in L0? Those get called "L0 lexemes", and they go on to become the terminals in G1. And G1's terminals? Those are called "G1 lexemes".

So how does Marpa figure out the "L0 lexemes"? She looks for symbols that are on the LHS of a L0 rule, but not on the RHS of any L0 rule. And the "G1 lexemes"? She looks for symbols on the RHS of at least one G1 rule, but not on the LHS of any G1 rule. Slay, systematic queen 👑

L0 and G1 should agree on what counts as a lexeme and what doesn't. If they don't? You, the programmer, receive a fatal message which describes the problem and the symbols involved. So in practice, honestly, I'm just gonna say "lexemes" and we all move on 🫶

---

🦋 Longest acceptable tokens match 🦋

So if you specify latm => 1 as the default — which you almost always should, no cap — the L0 grammar looks for tokens on a longest acceptable tokens match (LATM) basis. Tokens that the structural grammar would reject get thrown away. Tokens in discard pseudo-rules get thrown away too. Everything else gets passed on up to the G1 grammar 💅

Now pay attention here because this is the part people mess up: the match is longest TOKENS, not longest token. Several tokens may have the same length, so several tokens may be "longest". When that happens, Marpa uses the full set of longest tokens in looking for possible parses. Multiple longest tokens, all of them, periodt.

Want more about LATM and its alternative, LTM? There's a detailed description of the latm adverb, go read it 📖

---

💖 Semantics 💖

Here's the tea: the value of a L0 rule is always the string it matches. And the value of a lexeme from the G1 point of view is the same as its value from the L0 point of view. Same value, both perspectives, iconic consistency 💅

Which means — and I need you to hear me — it makes no sense to specify semantic actions for L0 rules. And it is not allowed. Don't try it, bestie, the door is locked 🔒

With the exception of lexeme values, the semantics of the G1 grammar are exactly the same as for ordinary grammars. Actions may be specified for G1 rules, and they'll behave as described in Marpa::R2::Semantics. So go forth and write your actions, you've got this 🌸

---

🌈 Implementation 🌈

The scannerless interface uses two co-operating Marpa grammars — an approach pioneered by Andrew Rodland. Absolute trailblazer behavior, we stan 🎀

There are separate Marpa grammars for the L0 and G1 levels, as well as separate parsers. The details of their interaction are hidden from you, the user. Typically, the L0 parser finds tokens and passes them up to the G1 parser. That's the whole dynamic, cute right?

And here's a genuinely fun fact: the interface described in this document is surprisingly implementation-agnostic. The author developed the basics of this interface while trying an implementation approach that used a single Marpa grammar, before changing to the dual grammar implementation. So the vibe survived a whole architecture glow-up ✨

---

👑 Copyright and License 👑

Copyright 2022 Jeffrey Kegler
This file is part of Marpa::R2.  Marpa::R2 is free software: you can
redistribute it and/or modify it under the terms of the GNU Lesser
General Public License as published by the Free Software Foundation,
either version 3 of the License, or (at your option) any later version.

Marpa::R2 is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
Lesser General Public License for more details.

You should have received a copy of the GNU Lesser
General Public License along with Marpa::R2.  If not, see
http://www.gnu.org/licenses/.

Bestie, real talk: that WITHOUT ANY WARRANTY bit is not a vibe, it's a caveat. No warranty of any kind, fr fr 💀

---

aaaand that's a wrap on Marpa:...canless(3pm), part 2 of 2 💖 this page was served up by perl v5.42.3 on 2026-08-20 🌸 go parse something beautiful, you main character 🫶✨