=head1 NAME

Parse::Marpa::Doc::Parse_Terms - Standard Parsing Terms used in the Marpa Documents

=head1 DESCRIPTION

This document is intended
as a reminder of
the standard vocabulary of parsing.
I put B<defining uses> of terms in boldface, for easy skimming.
A reader who feels comfortable with parsing terminology,
can skip this document entirely.

All the definitions here are consistent with
at least some of the textbook definitions,
and are in that sense standard.
But no effort is made to
cover the full range of standard meaning,
or even to give the most common meaning.
The focus is on the meaning of the terms as used in the Marpa documentation.

If you've never looked into parsing before,
you'll probably find this document too terse.
As an introduction, I reccommend
L<Mark Jason Dominus's
excellent chapter on parsing in the Perl context|Parse::Marpa::Doc::Bibliography/"Dominus 2005">.
It's available on-line.
L<Wikipedia|Parse::Marpa::Doc::Bibliography/"Wikipedia"> is also an excellent place to start.

=head2 Basic terms

A B<grammar> is a set of rules.
The B<rules> describe a set of strings of B<symbols>.
A string of symbols is often called a B<symbol string>.
The rules of a grammar are often called B<productions>.

=head2 Stages of Parsing

A B<recognizer> is a program that determines whether its B<input>
is one of the symbol strings in the set described by the rules of a grammar.
A B<parser> is a program which finds the structure of the input
according to the rules of a grammar.

The term B<parsing> is used in a strict and a loose sense.
B<Parsing> in the loose sense means all the phases of finding a grammar's structure,
including a separate recognition phase if the parser has one.  (Marpa does.)
If a parser has phases,
B<parsing in the strict sense> refers specifically to the phase that finds the structure of the input.
When the Marpa documents use the term B<parsing> in its strict sense, they will
speak explicitly of "parsing in the strict sense".
Otherwise, B<parsing> will mean parsing in the loose sense.

Parsers often use a
B<lexical analyzer> to convert B<raw input>,
usually B<input text>,
into a series of B<tokens>.
Each token represents a B<symbol> of the grammar and has a B<value>.
The series of symbols represented by the series of tokens
becomes the B<symbol string input>
seen by the recognizer.
The B<symbol string input> is also called the B<input sentence>.
A lexical analyzer is often called a B<lexer> or a B<scanner>,
and B<lexical analysis> is often called B<lexing> or B<scanning>.

=head2 Productions

A standard way of describing rules is Backus-Naur Form, or B<BNF>.
In one common way of writing BNF, a production looks like this.

=begin Marpa::Test::Display:

## skip display

=end Marpa::Test::Display:

    Expression ::= Term Factor

The equivalent in Marpa's MDL language looks like this:

=begin Marpa::Test::Display:

## skip display

=end Marpa::Test::Display:

    Expression: Term, Factor.

In the production above, C<Expression>, C<Term> and C<Factor> are symbols.
A production consists of a B<left hand side> and a B<right hand side>.
In a B<context-free grammar>,
like those Marpa parses,
the left hand side of a production 
is always a symbol string of length 1.
The right hand side of a production is a symbol string of zero or more symbols.
In the example, C<Expression> is the left hand side, and 
C<Term> and C<Factor> are right hand side symbols.

Left hand side and right hand side are often abbreviated as B<rhs> and B<lhs>.
If the rhs of a production has no symbols,
the production is called an B<empty production>
or an B<empty rule>.

Any symbol which is allowed to occur
in the symbol string input is called a B<terminal> symbol.
If the symbols in a symbol string are all terminals,
that symbol string is also called a B<sentence>.

=head2 Derivations

A B<step> of a derivation, or B<derivation step>, is made by taking a symbol string
and any production in the grammar whose lhs occurs in that symbol string,
and replacing any occurrence of the lhs symbol in the symbol string with the
rhs of the production.  For example, if C<A>, C<B>, C<C>, C<D>, and C<X> are symbols,
and

=begin Marpa::Test::Display:

## skip 2 displays

=end Marpa::Test::Display:

    X: B, C.

is a production, then

    A X D -> A B C D

is a derivation step, with "C<A X D>" as its beginning and "C<A B C D>" as its end or result.
We say that the symbol string "C<A X D>"
B<derives> the symbol string
"C<A B C D>".

A B<derivation> is a sequence of derivation steps.
The B<length> of a derivation is its length in steps.  A symbol string B<directly
derives> another if and only if there is a derivation of length 1 from the first symbol
string to the second string.  Every symbol string is said to derive itself in a derivation
of length 0.  Such a zero length derivation is a B<trivial derivation>.

If a derivation is not trivial or direct, that is, if it has more than one step,
then it is an B<indirect> derivation.  A derivation which is not trivial, that is,
one which has one or more steps, is a B<non-trivial> derivation.

Where the symbol string beginning a derivation consists of a single symbol,
we often say that symbol B<produces> the symbol string which results from the derivation.
We say that the beginning symbol
B<trivially>, B<non-trivially>, B<directly> or B<indirectly>
produces
the symbol string if the length of the derivation is respectively,
0, greater than 0, 1, or greater than 1,
just as we do when we say a symbol string derives another symbol string.
When a symbol produces or derives a symbol string,
we also say that the symbol B<matches> the symbol string,
or that the symbol string B<matches> the symbol.

In any parse, one symbol is distinguished as the B<start symbol>.
The parse of an input is B<successful>
if and only if the start symbol produces the input sentence
according to the grammar.

=head2 Nulling

The B<length> of a symbol string is the number of symbols in it.
The zero length symbol string is called the B<empty string>.
The empty string can be considered to be a sentence, in which
case it is the B<empty sentence>.
A string of one or more symbols is B<non-empty>.
A derivation which produces the empty string is a B<null derivation>.
A derivation from the start symbol which produces the empty string
is a B<null parse>.

If in a particular grammar, a symbol has a null derivation,
it is a B<nullable symbol>.
If, in a particular grammar,
the only sentence produced by a symbol is the empty sentence,
it is a B<nulling symbol>.
All nulling symbols are nullable symbols.

If a symbol is not nullable, it is B<non-nullable>.
If a symbol is not nulling, it is B<non-nulling>.
In any instance where a symbol produces the empty string,
it is said to be B<nulled>,
or to be a B<null symbol>.

=head2 Other Special Cases

If any derivation from the start symbol uses a rule,
that rule is called B<reachable> or B<accessible>.
A rule that is not accessible
is called B<unreachable> or B<inaccessible>.
If any derivation which results in a sentence uses a rule,
that rule is said to be B<productive>.
A rule that is not productive is called B<unproductive>.
A simple case of an unproductive rule is one whose rhs contains a symbol which is not
a terminal and not on the lhs of any other rule.
A B<useless> rule is one which is inaccessible or unproductive.

A symbol is B<reachable> if it appears in a reachable production.
A symbol is B<productive> if it appears on the lhs of a productive rule,
or if it is a nullable symbol.
If a symbol is not reachable or not accessible,
it is B<unreachable> or B<inaccessible>.
If a symbol is not productive,
it is B<unproductive>.

If any symbol in the grammar non-trivially produces a symbol string containing itself,
the grammar is said to be B<recursive>.
If any symbol non-trivially produces a symbol string with itself on the left,
the grammar is said to be B<left-recursive>.
If any symbol non-trivially produces a symbol string with itself on the right,
the grammar is said to be B<right-recursive>.

A non-trivial derivation from any symbol to the symbol string of length
one containing the original symbol is a cycle.
Put less formally, any non-trivial derivation, which starts from a symbol
and ends with a symbol string containing nothing but the same symbol, 
completely unchanged, is a cycle.
A grammar which contains no cycles is B<cycle-free>.
A B<proper context-free grammar> in one which is
cycle-free and has no useless rules or empty productions.

=head2 Structure

The structure of a parse can be represented by as a series of derivation steps from
the start symbol to the input.
Another way to represent structure is as a B<parse tree>.
Every symbol used in the parse is
represented by a B<node> of the parse tree.
Wherever a production is used in the parse,
its lhs is represented by a B<parent node>
and the rhs symbols are represented by B<child nodes>.
The start symbol is the B<root> of the tree.
Terminals and symbols on the
left hand side of empty productions are B<leaf nodes>.
If a node is not a B<leaf node>, it is an B<inner node>.
A B<nulled node> is one that represents a nulled symbol.

If, for a given grammar and a given input,
more than one derivation tree is possible,
we say that parse is B<ambiguous>.
If any parse from a grammar is ambiguous,
the grammar is B<ambiguous>.

The node at the root of the tree is the B<start node>.
Any node with a symbol being used as a terminal is a B<terminal node>.
The B<depth> of a node is its distance from the root.
The root node is at depth 0.
If a parent node is at depth C<n>,
its children are at depth C<n+1>.
As with depths in bodies of water, the concepts of B<higher> and B<lower>
have the sense opposite to that of the numerical values.
The node at depth 0 is higher than any other node.
Parent nodes are higher than their children.

=head2 Semantics

In real life, the structure of a parse is usually a means to an end.
Grammars usually have a B<semantics> associated with them,
and what the user actually wants is the B<value> of the parse
according to the semantics.
The tree representation is especially useful when evaluating a parse.

Every node which represents a terminal symbol
has a value associated with it on input.
Non-null inner nodes 
take their semantics from the production whose lhs they represent.
Nulled nodes are often deal with in special ways.
Their handling in Marpa is described L<elsewhere|Parse::Marpa/"Null Symbol Values">.

The semantics for a production
describe how to calculate the value of the node which represents the lhs
(the parent node)
from the values of zero or more of the nodes which represent the rhs symbols
(child nodes).
Values are computed recursively, bottom-up.
The value of a parse is the value of its start symbol.

=head1 SUPPORT

See the L<support section|Parse::Marpa/SUPPORT> in the main module.

=head1 AUTHOR

Jeffrey Kegler

=head1 LICENSE AND COPYRIGHT

Copyright 2007 - 2008 Jeffrey Kegler

This program is free software; you can redistribute
it and/or modify it under the same terms as Perl 5.10.0.

=cut