Quick Navigator

Search Site

Unix VPS
A - Starter
B - Basic
C - Preferred
D - Commercial
MPS - Dedicated
Previous VPSs
* Sign Up! *

Contact Us
Online Help
Domain Status
Man Pages

Virtual Servers

Topology Map

Server Agreement
Year 2038

USA Flag



Man Pages

Manual Reference Pages  -  MARPA::PARSE_TERMS (3)

.ds Aq ’


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



This document is intended as a reminder of the standard vocabulary of parsing. I put <B>defining usesB> of terms in boldface, for easy skimming. A reader who feels comfortable with parsing terminology can skip this document entirely. A reader completely new to parsing will find this document too terse and should look elsewhere first.

As an introduction, I recommend Mark Jason Dominus’s excellent chapter on parsing in the Perl context. It’s available on-line. Wikipedia is also an excellent place to start.

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.

    Basic terms

A <B>grammarB> is a set of rules. The <B>rulesB> describe a set of strings of <B>symbolsB>. A string of symbols is often called a <B>symbol stringB>. The rules of a grammar are often called <B>productionsB>.

    Stages of Parsing

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

The term <B>parsingB> is used in a strict and a loose sense. <B>ParsingB> 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 senseB> refers specifically to the phase that finds the structure of the input. When the Marpa documents use the term <B>parsingB> in its strict sense, they will speak explicitly of parsing in the strict sense. Otherwise, <B>parsingB> will mean parsing in the loose sense.

Parsers often use a <B>lexical analyzerB> to convert <B>raw inputB>, usually <B>input textB>, into a series of <B>tokensB>. Each token represents a <B>symbolB> of the grammar and has a <B>valueB>. The series of symbols represented by the series of tokens becomes the <B>symbol string inputB> seen by the recognizer. The <B>symbol string inputB> is also called the <B>input sentenceB>. A lexical analyzer is often called a <B>lexerB> or a <B>scannerB>, and <B>lexical analysisB> is often called <B>lexingB> or <B>scanningB>.


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

    Expression ::= Term Factor

In the production above, Expression, Term and Factor are symbols. A production consists of a <B>left hand sideB> and a <B>right hand sideB>. In a <B>context-free grammarB>, 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, Expression is the left hand side, and Term and Factor are right hand side symbols.

Left hand side and right hand side are often abbreviated as <B>RHSB> and <B>LHSB>. If the RHS of a production has no symbols, the production is called an <B>empty productionB> or an <B>empty ruleB>.

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


A <B>stepB> of a derivation, or <B>derivation stepB>, 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 A, B, C, D, and X are symbols, and

    X ::= B C

is a production, then

    A X D -> A B C D

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

A <B>derivationB> is a sequence of derivation steps. The <B>lengthB> of a derivation is its length in steps. A symbol string <B>directly derivesB> 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 derivationB>.

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

Where the symbol string beginning a derivation consists of a single symbol, we often say that symbol <B>producesB> the symbol string which results from the derivation. We say that the beginning symbol <B>triviallyB>, <B>non-triviallyB>, <B>directlyB> or <B>indirectlyB> 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>matchesB> the symbol string, or that the symbol string <B>matchesB> the symbol.

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 <B>lengthB> of a symbol string is the number of symbols in it. 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>non-emptyB>. 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>non-nullableB>. If a symbol is not nulling, it is <B>non-nullingB>. In any instance where a symbol produces the empty string, it is said to be <B>nulledB>, or to be a <B>null symbolB>.

    Useless Rules

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>. 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 rule which is inaccessible or unproductive is called a <B>uselessB> rule. Marpa can handle grammars with useless rules.

A symbol is <B>reachableB> if it appears in a reachable production. 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 reachable or not accessible, it is <B>unreachableB> or <B>inaccessibleB>. 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.

    Recursion and Cycles

If any symbol in the grammar non-trivially produces a symbol string containing itself, the grammar is said to be <B>recursiveB>. If any symbol non-trivially produces a symbol string with itself on the left, the grammar is said to be <B>left-recursiveB>. If any symbol non-trivially produces a symbol string with itself on the right, the grammar is said to be <B>right-recursiveB>. Marpa can handle all recursive grammars, including grammars which are left-recursive, grammars which are right-recursive, and grammars which contain both left- and right-recursion.

A <B>cycleB> is a non-trivial derivation from any symbol to the string of symbols which contains only itself. Since the result of a cycle is exactly the same as the beginning of a cycle, a cycle is the parsing equivalent of an infinite loop. A grammar which contains no cycles is <B>cycle-freeB>.

A grammar which contains a cycle is called <B>infinitely ambigiousB>, because a grammar with a cycle can repeat that cycle in a derivation an arbitrary number of times. Marpa can handle cycles, and will produce parses even for infinitely ambiguous grammars.


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>.

Terminals are <B>leaf nodesB>. Any node with a symbol being used as a terminal is a <B>terminal nodeB>. In Marpa, symbols on the left hand side of empty productions are also <B>leaf nodesB>. If a node is not a <B>leaf nodeB>, it is an <B>inner nodeB>. A <B>nulled nodeB> 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>ambiguousB>. The standard definition of an ambigious grammar is that, if any parse from a grammar is ambiguous, the grammar is <B>ambiguousB>.

Marpa is unusual in that it allows ambiguous <B>inputB>, so for Marpa this definition needs to be modified. In the Marpa context, a grammar is called ambigious, if for any unambiguous input, some parse from that grammar is ambiguous. Marpa can handle ambiguous grammars, whether ambiguity is defined in the standard way, or used with its Marpa-specific meaning.


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. The rest of this section describes the traditional textbook method of evaluating parse trees. In practice trees can be transformed and evaluated in many ways, but the traditional method is very much in use and in practical applications the traditional method is usually the first considered, if not the one ultimately used.

In the traditional method of evaluating a parse tree, 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 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, bottom-up. The value of a parse is the value of its start symbol.


Copyright 2007-2010 Jeffrey Kegler, all rights reserved. Marpa is free software under the Perl license. For details see the LICENSE file in the Marpa distribution.
Search for    or go to Top of page |  Section 3 |  Main Index

perl v5.20.3 MARPA::PARSE_TERMS (3) 2016-04-03

Powered by GSP Visit the GSP FreeBSD Man Page Interface.
Output converted with manServer 1.07.