

o  We say that a first symbol string <B>directly derivesB> a second symbol string if and only if there is a derivation of length 1 from the first symbol string to the second symbol string. 
o  Every symbol string is said to derive itself in a derivation of length 0. A zero length derivation is a <B>trivial derivationB>. 
o  A nontrivial derivation of a symbol string from itself is called a <B>cycleB>. Grammars which contain cycles are traditionally considered useless, but Marpa will parse with such grammars. 
o  If a derivation is not trivial or direct, that is, if it has more than one step, then it is an <B>indirectB> derivation. 
o  A derivation which is not trivial (that is, a derivation which has one or more steps) is a <B>nontrivialB> derivation. 
Wherever symbol or string X derives Y, we may also say X <B>producesB> Y. Derivations are often described as symbol matches. Wherever symbol or string X derives Y, we may also say that Y <B>matchesB> X or that X <B>matchesB> Y. It is particularly common to say that X matches Y when X or Y is a sentence.
In any parse, one symbol is distinguished as the <B>start symbolB>. The parse of an input is <B>successfulB> if and only if the start symbol produces the input sentence according to the grammar. The set of all input sentences that a grammar and a start symbol will successfully parse is their <B>languageB>. Traditionally, the start symbol is part of a grammar’s definition. The <B>languageB> of a grammar is the language of the grammar and its default start symbol.
The zero length symbol string is called the <B>empty stringB>. The empty string can be considered to be a sentence, in which case it is the <B>empty sentenceB>. A string of one or more symbols is <B>nonemptyB>. A derivation which produces the empty string is a <B>null derivationB>. A derivation from the start symbol which produces the empty string is a <B>null parseB>.If in a particular grammar, a symbol has a null derivation, it is a <B>nullable symbolB>. If, in a particular grammar, the only sentence produced by a symbol is the empty sentence, it is a <B>nulling symbolB>. All nulling symbols are nullable symbols.
If a symbol is not nullable, it is <B>nonnullableB>. If a symbol is not nulling, it is <B>nonnullingB>. In any instance where a symbol produces the empty string, it is said to be <B>nulledB>, or to be a <B>null symbolB>.
If any derivation from the start symbol uses a rule, that rule is called <B>reachableB> or <B>accessibleB>. A rule that is not accessible is called <B>unreachableB> or <B>inaccessibleB>. If any derivation which results in a sentence uses a rule, that rule is said to be <B>productiveB>. A rule that is not productive is called <B>unproductiveB>. For example, a rule is unproductive unless every symbol on its RHS either is a terminal or is the LHS of some other rule. A rule which is inaccessible or unproductive is called a <B>uselessB> rule. Marpa can handle grammars with useless rules.A symbol is <B>reachableB> or <B>accessibleB> if it appears in a reachable production. If a symbol is not reachable, it is <B>unreachableB> or <B>inaccessibleB>. A symbol is <B>productiveB> if it appears on the LHS of a productive rule, or if it is a nullable symbol. If a symbol is not productive, it is <B>unproductiveB>. A symbol which is inaccessible or unproductive is called a <B>uselessB> symbol. Marpa can handle grammars with useless symbols.
If any symbol in the grammar nontrivially produces a symbol string containing itself, the grammar is said to be <B>recursiveB>. If any symbol nontrivially produces a symbol string with itself on the left, the grammar is said to be <B>leftrecursiveB>. If any symbol nontrivially produces a symbol string with itself on the right, the grammar is said to be <B>rightrecursiveB>. Marpa can handle all recursive grammars, including grammars which are leftrecursive, grammars which are rightrecursive, and grammars which contain both left and rightrecursion.A <B>cycleB> is a nontrivial derivation of a string of symbols from itself. If it is not possible for any derivation using a grammar to contain a cycle, then that grammar is said to be <B>cyclefreeB>. Traditionally, a grammar is considered useless if it is not cyclefree.
The traditional deprecation of cycles is wellfounded. A cycle is the parsing equivalent of an infinite loop. Once a cycle appears, it can be repeated over and over again. Even a very short input sentence can have an infinite number of parses when the grammar is not cyclefree.
For that reason, a grammar which contains a cycle is also called <B>infinitely ambiguousB>. Marpa can parse with grammars which are not cyclefree, and will even parse inputs that cause cycles. When a parse is infinitely ambiguous, Marpa limits cycles to a single loop, so that only a finite number of parses is returned.
The structure of a parse can be represented as a series of derivation steps from the start symbol to the input. Another way to represent structure is as a <B>parse treeB>. Every symbol used in the parse is represented by a <B>nodeB> of the parse tree. Wherever a production is used in the parse, its LHS is represented by a <B>parent nodeB> and the RHS symbols are represented by <B>child nodesB>. The start symbol is the <B>rootB> of the tree. The node at the root of the tree is called the <B>start nodeB>.Traditionally, grammars divide all symbols sharply into terminals and nonterminals. A terminal symbol must ALWAYS be used as a terminal. A nonterminal symbol can NEVER be used as a terminal.
Marpa’s use of terminals is nontraditional, and its terminology is different accordingly. As in the traditional approach, Marpa’s nonterminals can never be used as terminals. But Marpa terminals can be used anywhere, even in places where the traditional approach requires a a nonterminal symbol. In particular, a Marpa terminal can be the LHS of a rule.
Traditionally, and in Marpa as well, every node is either a <B>inner nodeB> or a <B>leaf nodeB>. In Marpa, <B>leaf nodesB> are of two kinds:
o Nodes for nulled symbols. A node for a nulled symbol is called a <B>nulled nodeB>. o Nodes for symbols being used as terminals.
Marpa allows ambiguous grammars. Traditionally we say that a parse is <B>ambiguousB> if, for a given grammar and a given input, more than one derivation tree is possible. However, Marpa allows ambiguous input tokens, which the traditional definition does not take into account. If Marpa used the traditional definition, all grammars would be ambiguous except those grammars which allowed only the null parse. Another complication is that in Marpa the start symbol of a grammar is not fixed.It is easiest if the Marpa definition and the traditional definition were extensionally equivalent  that is, if Marpa’s set of ambiguous grammars was exactly the same as the set of traditionally ambiguous grammars. This can be accomplished by using a slightly altered definition. In the Marpa context, a grammar with an associated start symbol is <B>ambiguousB> if and only if, for some UNAMBIGUOUS stream of input tokens, that grammar with that start symbol produces more than one parse tree. A Marpa grammar is <B>ambiguousB> if that Marpa grammar with its default start symbol is ambiguous.
In real life, the structure of a parse is usually a means to an end. Grammars usually have a <B>semanticsB> associated with them, and what the user actually wants is the <B>valueB> of the parse according to the semantics.The tree representation is especially useful when evaluating a parse. In the traditional method of evaluating a parse tree, every node which represents a terminal symbol has a value associated with it on input. Nonnull inner nodes take their semantics from the production whose LHS they represent. Nulled nodes are dealt with as special cases.
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, bottomup. The value of a parse is the value of its start symbol.
Copyright 2012 Jeffrey Kegler This file is part of Marpa::XS. Marpa::XS 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::XS 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::XS. If not, see http://www.gnu.org/licenses/.
perl v5.20.3  MARPA::XS::VOCABULARY (3)  20160405 
Visit the GSP FreeBSD Man Page Interface.
Output converted with manServer 1.07.