Terence Parr
This glossary defines some of the more important terms used in the
ANTLR documentation. I have tried to be very informal and provide
references to other pages that are useful. For another great source
of information about formal computer languages, see Wikipedia.
A language is ambiguous if the same sentence or phrase can be
interpreted in more than a single way. For example, the following
sentence by Groucho Marx is easily interpreted in two ways: "I once
shot an elephant in my pajamas. How he got in my pajamas I'll never
know!" In the computer world, a typical language ambiguity is the
if-then-else ambiguity where the else-clause may be attached to either
the most recent if-then or an older one. Reference manuals for
computer languages resolve this ambiguity by stating that else-clauses
always match up with the most recent if-then.
A grammar is ambiguous if the same input sequence can be derived in
multiple ways. Ambiguous languages always yield ambiguous grammars
unless you can find a way to encode semantics (actions or predicates
etc...) that resolve the ambiguity. Most language tools like ANTLR
resolve the if-then-else ambiguity by simply choosing to match
greedily (i.e., as soon as possible). This matches the else with the
most recent if-then. See nondeterministic.
ANother Tool for Language Recognition, a
predicated-LL(k) parser generator that handles lexers, parsers, and
tree parsers. ANTLR has been available since 1990 and led to a
resurgence of recursive-descent parsing after decades dominated by LR
and other DFA-based strategies.
Abstract Syntax Tree. ASTs are used as internal
representations of an input stream, normally constructed during a
parsing phase. Because AST are two-dimensional trees they
can encode the structure (as determined by the parser) of the input as
well as the input symbols.
A homogeneous AST is in one in which the physical objects are all of
the same type; e.g., CommonAST in ANTLR. A heterogeneous
tree may have multiple types such as PlusNode,
MultNode etc...
An AST is not a parse tree, which encodes the sequence of rules
used to match input symbols. See What's the
difference between a parse tree and an abstract syntax tree (AST)? Why
doesn't ANTLR generate trees with nodes for grammar rules like JJTree
does?.
An AST for input 3+4 might be represented as
+
/ \
3 4
or more typically (ala ANTLR) in child-sibling form:
+
|
3--4
Operators are usually subtree roots and operands are usually leaves.
Bit sets are an extremely efficient representation for dense integer
sets. You can easily encode sets of strings also by mapping unique
strings to unique integers. ANTLR uses bitsets for lookahead
prediction in parsers and lexers. Simple bit set implementations do
not work so well for sparse sets, particularly when the maximum
integer stored in the set is large.
ANTLR's bit set represents membership with a bit for each possible
integer value. For a maximum value of n, a bit set needs
n/64 long words or n/8 bytes. For ASCII bit sets with a
maximum value of 127, you only need 16 bytes or 2 long words. UNICODE
has a max value of \uFFFF or 65535, requiring 8k bytes, and these sets
are typically sparse. Fortunately most lexers only need a few of
these space inefficient (but speedy) bitsets and so it's not really a
problem.
A particularly efficient data structure for representing trees. See AST.
A grammar where recognition of a particular construct does not depend
on whether it is in a particular syntactic context. A context-free
grammar has a set of rules like
stat : IF expr THEN stat
| ...
;
where there is no restriction on when the IF alternative may
be applied--if you are in rule stat, you may apply the
alternative.
A grammar where recognition of a particular construct may depend on a
syntactic context. You never see these grammars in practice because
they are impractical (Note, an Earley parser is O(n^3) worst-case for
context-free grammars). A context-free rule looks like:
Α → γ
but a context-sensitive rule may have context on the left-side:
αΑβ → αγβ
meaning that rule Α may only be applied (converted to γ)
in between α and β.
In an ANTLR sense, you can recognize context-sensitive constructs with
a semantic predicate. The action evaluates to true or false
indicating the validity of applying the alternative.
See Context-sensitive gramar.
Deterministic Finite Automata. A state machine
used typically to formally describe lexical analyzers. lex
builds a DFA to recognize tokens whereas ANTLR builds a recursive
descent lexer similar to what you would build by hand. See Finite
state machine and ANTLR's lexer documentation.
The set of symbols that may be matched on the left-edge of a rule.
For example, the FIRST(decl) is set {ID, INT} for the following:
decl : ID ID SEMICOLON
| INT ID SEMICOLON
;
The situation gets more complicated when you have optional
constructs. The FIRST(a) below is {A,B,C}
a : (A)? B
| C
;
because the A is optional and the B may be seen on the left-edge.
Naturally k>1 lookahead symbols makes this even more complicated.
FIRST_k must track sets of k-sequences not just individual symbols.
The set of input symbols that may follow any reference to the
specified rule. For example, FOLLOW(decl) is {RPAREN, SEMICOLON):
methodHead : ID LPAREN decl RPAREN ;
var : decl SEMICOLON ;
decl : TYPENAME ID ;
because RPAREN and SEMICOLON both follow references to rule decl.
FIRST and FOLLOW computations are used to analyze grammars and
generate parsing decisions.
This grammar analysis all gets very complicated when k>1.
A finite means of formally describing the structure of a possibly
infinite language. Parser generators build parsers that recognize
sentences in the language described by a grammar. Most parser
generators allow you to add actions to be executed during the parse.
Semantic predicates describe the semantic context in which a rule or
alternative applies. The predicate is hoisted into a prediction
expression. Hoisting typically refers to pulling a predicate out of
its enclosing rule and into the prediction expression of another
rule. For example,
decl : typename ID SEMICOLON
| ID ID SEMICOLON
;
typename : {isType(LT(1))}? ID
;
The predicate is not needed in typename as there is no decision,
however, rule decl needs it to distinguish between its two
alternatives. The first alternative would look like:
if ( LA(1)==ID && isType(LT(1)) ) {
typename();
match(ID);
match(SEMICOLON);
}
PCCTS 1.33 did, but ANTLR currently does not hoist predicates into
other rules.
The ability of ANTLR to define a new grammar as it differs from an
existing grammar. See the ANTLR documentation.
The nth lookahead character, token type, or AST node type depending
on the grammar type (lexer, parser, or tree parser respectively).
A common sequence of symbols on the left-edge of a set of alternatives
such as:
a : A B X
| A B Y
;
The left-prefix is A B, which you can remove by left-factoring:
a : A B (X|Y)
;
Left-factoring is done to reduce lookahead requirements.
Generally a literal refers to a fixed string such as begin
that you wish to match. When you reference a literal in an ANTLR
grammar via "begin", ANTLR assigns it a token type like any
other token. If you have defined a lexer, ANTLR provides information
about the literal (type and text) to the lexer so it may detect
occurrences of the literal.
An approximation to full lookahead (that can be applied to both LL and LR
parsers) for k>1 that reduces the complexity of storing and testing
lookahead from O(n^k) to O(nk); exponential to linear reduction. When
linear approximate lookahead is insufficient (results in a
nondeterministic parser), you can use the approximate lookahead to
attenuate the cost of building the full decision.
Here is a simple example illustrating the difference between full
and approximate lookahead:
a : (A B | C D)
| A D
;
This rule is LL(2) but not linear approximate LL(2). The real
FIRST_2(a) is {AB,CD} for alternative 1 and {AD} for alternative 2.
No intersection, so no problem. Linear approximate lookahead
collapses all symbols at depth i yielding k sets instead of a possibly
n^k k-sequences. The approximation (compressed) sets are
{AB,AD,CD,CB} and {AD}. Note the introduction of the spurious
k-sequences AD and CB. Unfortunately, this compression introduces a
conflict upon AD between the alternatives. PCCTS did full LL(k) and
ANTLR does linear approximate only as I found that linear approximate
lookahead works for the vast majority of parsing decisions and is
extremely fast. I find one or two problem spots in a large grammar
usually with ANTLR, which forces me to reorganize my grammar in a
slightly unnatural manner. Unfortunately, your brain does full LL(k)
and ANTLR does a slightly weaker linear approximate lookahead--a
source of many (invalid) bug reports ;)
This compression was the subject of my doctoral
dissertation (PDF 477k) at Purdue.
Formally, LL(k) represents a class of parsers and grammars that parse
symbols from left-to-right (beginning to end of input stream) using a
leftmost derivation and using k symbols of lookahead. A leftmost
derivation is one in which derivations (parses) proceed by attempting
to replace rule references from left-to-right within a production.
Given the following rule
stat : IF expr THEN stat
| ...
;
an LL parser would match the IF then attempt to parse expr rather than
a rightmost derivation, which would attempt to parse stat first.
LL(k) is synonymous with a "top-down" parser because the
parser begins at the start symbol and works its way down the
derivation/parse tree (tree here means the stack of method activations
for recursive descent or symbol stack for a table-driven parser). A
recursive-descent parser is particular implementation of an LL parser
that uses functions or method calls to implement the parser rather
than a table.
ANTLR generates predicate-LL(k) parsers that support syntactic and
sematic predicates allowing you to specify many context-free and
context-sensitive grammars (with a bit of work).
In a parser, this is the nth lookahead Token object.
A possibly infinite set of valid sentences. The
vocabulary symbols may be characters, tokens, and tree nodes in an
ANTLR context.
A recognizer that breaks up a stream of characters into
vocabulary symbols for a parser. The parser pulls vocabulary symbols
from the lexer via a queue.
When parsing a stream of input symbols, a parser has matched (and no
longer needs to consider) a portion of the stream to the left of its
read pointer. The next k symbols to the right of the read pointer are
considered the fixed lookahead. This information is used to direct
the parser to the next state. In an LL(k) parser this means to
predict which path to take from the current state using the next k
symbols of lookahead.
ANTLR supports syntactic predicates, a manually-specified form of
backtracking that effectively gives you infinite lookahead. For
example, consider the following rule that distinguishes between sets
(comma-separated lists of words) and parallel assignments (one list
assigned to another):
stat: ( list "=" )=> list "=" list
| list
;
If a list followed by an assignment operator is found on the input
stream, the first production is predicted. If not, the second
alternative production is attempted.
A lexer method automatically generated by ANTLR that figures out which
of the lexer rules to apply. For example, if you have two rules ID
and INT in your lexer, ANTLR will generate a lexer with methods for ID
and INT as well as a nextToken method that figures out which rule
method to attempt given k input characters.
Nondeterministic Finite Automata. See Finite
state machine.
A parser is nondeterministic if there is at least one decision point
where the parser cannot resolve which path to take. Nondeterminisms
arise because of parsing strategy weaknesses.
Note that a parser may have multiple decision points that are
nondeterministic.
A recognizer that applies a grammatical structure to a stream
of vocabulary symbols called tokens.
A semantic predicate is a boolean expression used to alter the parse
based upon semantic information. This information is usually a
function of the constructs/input that have already been matched, but
can even be a flag that turns on and off subsets of the language (as
you might do for a grammar handling both K&R and ANSI C). One of the
most common semantic predicates uses a symbol table to help
distinguish between syntactically, but semantically different
productions. In FORTRAN, array references and function calls look the
same, but may be distinguished by checking what the type of the
identifier is.
expr : {isVar(LT(1))}? ID LPAREN args RPAREN // array ref
| {isFunction(LT(1))}? ID LPAREN args RPAREN // func call
;
A selective form of backtracking used to recognize language constructs
that cannot be distinguished without seeing all or most of the
construct. For example, in C++ some declarations look exactly like
expressions. You have to check to see if it is a declaration. If it
parses like a declaration, assume it is a declaration--reparse it with
"feeling" (execute your actions). If not, it must be an expression or
an error:
stat : (declaration) => declaration
| expression
;
An alternative in a grammar rule.
A protected lexer rule does not represent a complete token--it is a
helper rule referenced by another lexer rule. This overloading of the
access-visibility Java term occurs because if the rule is not visible,
it cannot be "seen" by the parser (yes, this nomeclature sucks).
See LL(k).
A regular language is one that can be described by a regular grammar
or regular expression or accepted by a DFA-based lexer such as those
generated by lex. Regular languages are normally used to
describe tokens.
In practice you can pick out a regular grammar by noticing that
references to other rules are not allowed accept at the end of a
production. The following grammar is regular because reference to
B occurs at the right-edge of rule A.
A : ('a')+ B ;
B : 'b' ;
Another way to look at it is, "what can I recognize without a stack
(such as a method return address stack)?".
Regular grammars cannot describe context-free languages, hence, LL or
LR based grammars are used to describe programming languages. ANTLR
is not restricted to regular languages for tokens because it generates
recursive-descent lexers. This makes it handy to recognize HTML tags
and so on all in the lexer.
A rule describes a partial sentence in a language such as a statement
or expression in a programming language. Rules may have one or more
alternative productions.
See Lexer.
See What
do "syntax" and "semantics" mean and how are they different?.
Essentially a rule that has been expanded inline. Subrules are
enclosed in parenthesis and may have suffixes like star, plus, and
question mark that indicate zero-or-more, one-or-more, or optional.
The following rule has 3 subrules:
a : (A|B)+ (C)* (D)?
;
See What
do "syntax" and "semantics" mean and how are they different?.
A vocabulary symbol for a language. This term typically refers to the
vocabulary symbols of a parser. A token may represent a constant
symbol such as a keyword like begin or a "class" of input
symbols like ID or INTEGER_LITERAL.
See Token
Streams in the ANTLR documentation.
See AST and What's the
difference between a parse tree and an abstract syntax tree (AST)? Why
doesn't ANTLR generate trees with nodes for grammar rules like JJTree
does?.
A recognizer that applies a grammatical structure to a
two-dimensional input tree. Grammatical rules are like an "executable
comment" that describe the tree structure. These parsers are useful
during translation to (i) annotate trees with, for example, symbol
table information, (2) perform tree rewrites, and (3) generate output.
The set of symbols used to construct sentences in a language. These
symbols are usually called tokens or token types. For lexers, the
vocabulary is a set of characters.
See ANTLR.