# Copyright 2013 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/.

=head1 Name

Marpa::R2::Scanless - Scanless interface

=head1 About this document

This document is intended for readers already familiar with
Marpa::R2's BNF (Stuifzand) interface.
It is an introduction to Marpa's Scanless interface,
dealing with the concepts behind the interface.
The reference documentation for the
scanless interface is in two separate documents,
L<one dealing with scanless grammar objects|Marpa::R2::Scanless::G>
and
L<one dealing with scanless recognizer objects|Marpa::R2::Scanless::R>.

=head1 The two levels of language description

Programmers usually
describe the syntax of a language at two levels.
The same two-level approach can be convenient for implementing
a parser of the language.
But, implementation aside,
a two-level description
seems to be a natural approach to
the design issues that arise in languages
intended for practical use.

The first level is structural.
For example, here is how the Perl docs describe one of
the forms that Perl's C<use> statement takes:

=for Marpa::R2::Display
ignore: 1

    use Module VERSION LIST

=for Marpa::R2::Display::End

and in Perl's source code (C<perly.y>) something similar
drives the parser.

The second level is lexical.
For example,
Perl's L<perlpodspec> page has a number of statements like this:

=for Marpa::R2::Display
ignore: 1

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

=for Marpa::R2::Display::End

The lexical level is character by character.
The structural level is less well-defined,
but in practice it ignores most of the character-by-character issues,
and it almost always avoids dealing with whitespace.

For reasons that will become clear later,
I will sometimes call the lexical level, G0,
and will sometimes call the structural level, G1.
It is important to realize
that the difference between G0 and G1 is one
of level of descripton and
NOT one of precision or exactness.
A structural description of Perl's C<use> statement,
much like the one I showed above,
is in Perl's source code (C<perly.y>),
along with many other, similar,
structural-level descriptions.
These that are used
generate the production parser for Perl so,
clearly, structural level descriptions are every bit
as much a precision instrument as regular expressions.

=head1 A very simple language

In order to focus on very basic issues,
I will use as an example,
an very simple language with a very simple semantics.
The language consists of decimal digits and ASCII spaces.
The semantics will treat it as a series of integers to be added.

Here are three strings in that language

=for Marpa::R2::Display
ignore: 1

     8675311
     867 5311
     8 6 7 5 3 1 1

=for Marpa::R2::Display::End

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

It's sometimes said, in describing languages like the above,
that "whitespace is ignored".
From the purely structural point of view this can be, in one sense, true.
But from the lexical point of view it's clearly quite false.

Combining the two levels of description,
it is very hard to justify an assertion that "whitespace is ignored".
The three strings in the display above
differ only in whitespace.
Clearly the placement
of the whitespace makes a vast difference, and has a major
effect on the structure of string,
which in turn has a determining effect on its semantics.

=head1 Why the structural level?

As we've seen, the structural level ignores essential aspects
of the language.
It is possible to describe a language using a single level of description.
So why have a structural (G1) level of description?
Why not a "unified" instead of a "split" description.

It turns out that, for most languages of practical size,
particularly those that deploy whitespace in a natural
and intuitive way,
a "unified" description rapidly becomes unwriteable,
and even more rapidly becomes unreadable.
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 into account whitespace.
As one example, consider declarations in the C language.

=for Marpa::R2::Display
ignore: 1

    unsigned int a;
    unsigned*b;

=for Marpa::R2::Display::End

In the first of the two lines above the whitespace is necessary.
In the second of the two lines whitespace would be allowed,
but is not necessary.
You cannot simply insist on whitespace between all symbols,
because whitespace is and should be optional between
some symbols and not between others.
Where whitespace is optional, and where it should not be,
depends on which characters are adjacent to each other.
This kind of character-level information is not convenient to represent
at the structural (G1) level.

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

Long before you finish, I expect you will 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.
This was clearly the only practical approach.

=head1 Interweaving the two levels

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

=for Marpa::R2::Display
name: Scanless concept example
partial: 1
normalize-whitespace: 1

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

=for Marpa::R2::Display::End

=head2 A new operator

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

The programmer must decide when to use the "C<~>" operator
and when to use the "C<::=>" operator,
but the choice will usually be easy:
If you want Marpa to "do what I mean" with whitespace, you use the
"C<::=>" operator.
If you want Marpa to do exactly what you say on a character-by-character basis,
then you use the "C<~>" operator.

=head2 Character classes

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

=head2 Discard rules

A new type of rule is introduced:
a "discard" rule.
A discard rule has a C<:discard> pseudo-symbol on its LHS
and one symbol name on its RHS.
It indicates that, when the RHS symbol is recognized,
it should not be passed on as usual to the structural (G1) level.
Instead, the lexical (G0) level will simply "discard" what it has
found.
In the example, whitespace is discarded.

=head1 Lexemes

Tokens at the boundary between G0 and G1 have special
significance.
The top-level undiscarded symbols in G0,
which will be called "G0 lexemes",
go on to become the terminals in G1.
G1's terminals are called "G1 lexemes".
To find the "G0 lexemes",
Marpa looks for symbols which are on
the LHS of a G0 rule, but not on the RHS of any G0 rule.
To find the "G1 lexemes",
Marpa looks for symbols on the RHS of at least one G1 rule,
but not on the LHS of any G1 rule.

G0 and G1 should agree on what is a lexeme and what is not.
If they do not,
the programmer receives a fatal message which describes the
problem and the symbols involved.
So in practice I will usually simply refer to "lexemes".

=head1 Longest tokens match

The G0 grammar looks for tokens on a longest B<tokens> match basis.
Tokens in discard rules are thrown away, and the rest are passed on
to the G1 grammar.
Note that match is longest TOKENS.
There may be more than one longest match, in which case Marpa
uses the full set of longest matches.

=head1 Semantics

The value of a G0 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 G0 point of view.
This means that it makes no sense to specify semantic
actions for G0 rules, and that is not allowed.

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 will
behave in
L<the same way as they do for
ordinary grammars|Marpa::R2::Semantics>.

=head1 Implementation

The scannerless interface uses two co-operating Marpa grammars,
an approach pioneered by Andrew Rodland.
There are separate Marpa grammars for the G0 and G1 levels,
as well as separate parsers.
The details of their interaction are hidden from the user.
Typically, the G0 parser finds tokens and passes them up to the
G1 parser.

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.

=head1 Copyright and License

=for Marpa::R2::Display
ignore: 1

  Copyright 2013 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/.

=for Marpa::R2::Display::End

=cut

# Local Variables:
#   mode: cperl
#   cperl-indent-level: 4
#   fill-column: 100
# End:
# vim: expandtab shiftwidth=4: