Traditionally, a lexer and parser are tightly coupled objects; that is, one does not imagine anything sitting between the parser and the lexer, modifying the stream of tokens. However, language recognition and translation can benefit greatly from treating the connection between lexer and parser as a token stream. This idea is analogous to Java I/O streams, where you can pipeline lots of stream objects to produce highly-processed data streams.
ANTLR identifies a stream of Token objects as any object that satisfies the TokenStream interface (prior to 2.6, this interface was called Tokenizer); i.e., any object that implements the following method.
Token nextToken();
Graphically, a normal stream of tokens from a lexer (producer) to a parser (consumer) might look like the following at some point during the parse.
The most common token stream is a lexer, but once you imagine a physical stream between the lexer and parser, you start imagining interesting things that you can do. For example, you can:
The beauty of the token stream concept is that parsers and lexers are not affected--they are merely consumers and producers of streams. Stream objects are filters that produce, process, combine, or separate token streams for use by consumers. Existing lexers and parsers may be combined in new and interesting ways without modification.
This document formalizes the notion of a token stream and describes in detail some very useful stream filters.
A token stream is any object satisfying the following interface.
public interface TokenStream {
public Token nextToken()
throws java.io.IOException;
}
For example, a "no-op" or pass-through filter stream looks like:
import antlr.*;
import java.io.IOException;
class TokenStreamPassThrough
implements TokenStream {
protected TokenStream input;
/** Stream to read tokens from */
public TokenStreamPassThrough(TokenStream in) {
input = in;
}
/** This makes us a stream */
public Token nextToken() throws IOException {
return input.nextToken(); // "short circuit"
}
}
You would use this simple stream by having it pull tokens from the lexer and then have the parser pull tokens from it as in the following main() program.
public static void main(String[] args) {
MyLexer lexer =
new MyLexer(new DataInputStream(System.in));
TokenStreamPassThrough filter =
new TokenStreamPassThrough(lexer);
MyParser parser = new MyParser(filter);
parser.startRule();
} Most of the time, you want the lexer to discard whitespace and comments, however, what if you also want to reuse the lexer in situations where the parser must see the comments? You can design a single lexer to cover many situations by having the lexer emit comments and whitespace along with the normal tokens. Then, when you want to discard whitespace, put a filter between the lexer and the parser to kill whitespace tokens.
ANTLR provides TokenStreamBasicFilter for such situations. You can instruct it to discard any token type or types without having to modify the lexer. Here is an example usage of TokenStreamBasicFilter that filters out comments and whitespace.
public static void main(String[] args) {
MyLexer lexer =
new MyLexer(new DataInputStream(System.in));
TokenStreamPassThrough filter =
new TokenStreamPassThrough(lexer);
filter.discard(MyParser.WS);
filter.discard(MyParser.COMMENT);
MyParser parser = new MyParser(filter);
parser.startRule();
}
Note that it is more efficient to have the lexer immediately discard lexical structures you do not want because you do not have to construct a Token object. On the other hand, filtering the stream leads to more flexible lexers.
Sometimes you want a translator to ignore but not discard portions of the input during the recognition phase. For example, you want to ignore comments vis-a-vis parsing, but you need the comments for translation. The solution is to send the comments to the parser on a hidden token stream--one that the parser is not "listening" to. During recognition, actions can then examine the hidden stream or streams, collecting the comments and so on. Stream-splitting filters are like prisms that split white light into rainbows.
The following diagram illustrates a situation in which a single stream of tokens is split into three.
You would have the parser pull tokens from the topmost stream.
There are many possible capabilities and implementations of a stream splitter. For example, you could have a "Y-splitter" that actually duplicated a stream of tokens like a cable-TV Y-connector. If the filter were thread-safe and buffered, you could have multiple parsers pulling tokens from the filter at the same time.
This section describes a stream filter supplied with ANTLR called TokenStreamHiddenTokenFilter that behaves like a coin sorter, sending pennies to one bin, dimes to another, etc... This filter splits the input stream into two streams, a main stream with the majority of the tokens and a hidden stream that is buffered so that you can ask it questions later about its contents. Because of the implementation, however, you cannot attach a parser to the hidden stream. The filter actually weaves the hidden tokens among the main tokens as you will see below.
Consider the following simple grammar that reads in integer variable declarations.
decls: (decl)+
;
decl : begin:INT ID end:SEMI
;
Now assume input:
int n; // list length /** doc */ int f;
Imagine that whitespace is ignored by the lexer and that you have instructed the filter to split comments onto the hidden stream. Now if the parser is pulling tokens from the main stream, it will see only "INT ID SEMI FLOAT ID SEMI" even though the comments are hanging around on the hidden stream. So the parser effectively ignores the comments, but your actions can query the filter for tokens on the hidden stream.
The first time through rule decl, the begin token reference has no hidden tokens before or after, but
filter.getHiddenAfter(end)
returns a reference to token
// list length
which in turn provides access to
/** doc */
The second time through decl
filter.getHiddenBefore(begin)
refers to the
/** doc */
comment.
The following diagram illustrates how the Token objects are physically weaved together to simulate two different streams.
As the tokens are consumed, the TokenStreamHiddenTokenFilter object hooks the hidden tokens to the main tokens via linked list. There is only one physical TokenStream of tokens emanating from this filter and the interweaved pointers maintain sequence information.
Because of the extra pointers required to link the tokens together, you must use a special token object called CommonHiddenStreamToken (the normal object is called CommonToken). Recall that you can instruct a lexer to build tokens of a particular class with
lexer.setTokenObjectClass("classname");
Technically, this exact filter functionality could be implemented without requiring a special token object, but this filter implementation is extremely efficient and it is easy to tell the lexer what kind of tokens to create. Further, this implementation makes it very easy to automatically have tree nodes built that preserve the hidden stream information.
This filter affects the lazy-consume of ANTLR. After recognizing every main stream token, the TokenStreamHiddenTokenFilter must grab the next Token to see if it is a hidden token. Consequently, the use of this filter is not be very workable for interactive (e.g., command-line) applications.
To use TokenStreamHiddenTokenFilter, all you have to do is:
MyLexer lexer = new MyLexer(some-input-stream); lexer.setTokenObjectClass( "antlr.CommonHiddenStreamToken" );
TokenStreamHiddenTokenFilter filter = new TokenStreamHiddenTokenFilter(lexer);
filter.discard(MyParser.WS); filter.hide(MyParser.SL_COMMENT);
MyParser parser = new