本章翻譯人 CowNew開源團隊 周曉
記號流
長久以來, 詞法分析器和語法分析器是緊緊耦合在一起的; 也就是說, 你不可以在他們中間做任何事情,也不能修改記號流。但是，用記號流來處理詞法分析器和語法分析器之間的連接的話，會給代碼識別和翻譯帶來極大的幫助。這個想法類似于Java的輸入輸出流，利用輸入輸出流你可以用管道的方式處理多個深加工的數(shù)據(jù)流。
ANTLR識別任何滿足TokenStream接口的記號流對象(2.6以前的版本, 這個接口叫做Tokenizer);也就是說記號流對象要實現(xiàn)以下的方法。
Token nextToken();
如圖, 在分析過程中的某一時刻，從詞法分析器(生產(chǎn)者)到語法分析器(消費者)的一般記號流會像是下面的樣子。
最普通的記號流是一個詞法分析器，但是想象一下，在詞法分析器和語法分析器中間有一個流的實體，都能做哪些有趣的事情呢。比如說，你可以：
- 過濾掉不想要的記號
- 插入一些輔助的記號，幫助語法分析過程識別一些復雜的結構
- 把一個流分成多個流，把某些感興趣的記號送到不同的流中
- 把多個記號流合并成一個流，從而“模擬”PCCTS,lex等詞法分析工具的狀態(tài)。
記號流概念的優(yōu)雅在于它對詞法分析器和語法分析器沒有影響--它們只不過是流的生產(chǎn)者和消費者。流對象是消費者用來生產(chǎn)，處理，合并或者分離記號流的過濾器?？梢允挂延械脑~法分析器和語法分析器在不修改的情況下合并成一種新的工具。
這份文檔正式提出了記號流的概念，詳細描述了一些非常有用的流過濾器。
一個記號流是任何滿足下面接口的對象。
public interface TokenStream {
public Token nextToken()
throws java.io.IOException;
}
例如, 一個"沒有操作"或者說僅僅是讓記號通過這里的過濾器是這樣工作的：
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"
}
}
在下面的main()程序中，你使用這個簡單的流對象從詞法分析器中獲得記號，然后語法分析器從流對象中獲得記號。
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();
}
多數(shù)情況下，你希望詞法分析器忽略掉空白符和注釋，然而，你還希望在語法分析器必須使用注釋的情況下重用詞法分析器。這時，你只要為需要注釋和空白符連同普通記號的情況設計一個詞法分析器。然后，當你想忽略空白符的時候，只要在詞法分析器和語法分析器中間加入一個過濾器，過濾掉空白符。
針對這種情況,ANTLR提供了TokenStreamBasicFilter。你可以在不修改詞法分析器的情況下讓它過過濾掉任何類型的記號。下面TokenStreamBasicFilter的用法的例子中過濾掉了注釋和空白符。
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();
}
可以看到，它比修改詞法分析器的詞法結構要來的有效，你也會這么做的吧，因為這樣你不用去構建一個記號對象。另一方面，采用這種過濾流的方法使詞法分析器的設計更加靈活。
有時，在識別階段，你想讓翻譯器忽略但不是丟棄輸入的部分記號。比如說，你想在語法分析時忽略注釋，但在翻譯時又需要注釋。解決辦法是將注釋發(fā)送到一個隱藏的記號流中，所謂隱藏，就是語法分析器沒有對它進行監(jiān)聽。在識別期間，通過動作來檢查這些隱藏的流，收集注釋等等。流分離過濾器有點像棱鏡把白光分離成彩虹。
下面的圖中示出了把一個記號流分成三個的情況。
讓語法分析器從最上面的流中獲得記號。
用流分離器可以實現(xiàn)很多功能。比如，"Y-分離器"像有線電視Y連接器一樣，復制符號流。如果過濾器是線程安全的而且有緩沖器緩沖，過濾器就可以同時為多個語法分析器提供記號。
這一節(jié)描述了ANTLR提供的一個叫做TokenStreamHiddenTokenFilter的流過濾器,它工作的時候有點像給一堆硬幣分類,把一分一分的放到一個箱子里,把一角一角的放到另一個箱子里,等等。這個過濾器把輸入流分離成兩個流，一個包含主要記號，另一個被緩沖以便以后可以訪問。因為這種實現(xiàn)方式，無論怎么做，你都無法讓語法分析器直接訪問隱藏流。下面你將會看到，過濾器實際上把隱藏記號交織在主記號中。
考慮以下的簡單文法,該文法用來聲明整型變量.
decls: (decl)+
;
decl : begin:INT ID end:SEMI
;
比如說有以下輸入:
int n; // list length
/** doc */
int f;
假定詞法分析器忽略空白符,你用過濾器把注釋分離到一個隱藏流。那么現(xiàn)在如果語法分析器從主記號流中獲得記號，它只會看到"INT ID SEMI FLOAT ID SEMI",注釋在隱藏流中。實現(xiàn)了語法分析器可以忽略注釋，而你的語義動作可以從過濾器中查詢隱藏流中的記號。
第一次識別出文法規(guī)則decl,begin記號前后沒有對隱藏記號的引用,但
filter.getHiddenAfter(end)
返回一個對下面記號的引用
// list length
接下來就會訪問到
/** doc */
第二次識別出decl
filter.getHiddenBefore(begin)
指向
/** doc */
的引用
下圖示出記號對象是如何組織記號來模擬兩個不同的流。
因為記號是假定的，TokenStreamHiddenTokenFilter對象通過鏈表來連接隱藏記號和主記號。過濾器只提供了一個物理上的記號流，通過交織指針維護和管理記號次序。
因為這個額外的指針需要把記號連接到一起，你必須要用一個叫CommonHiddenStreamToken的特殊記號對象(普通記號對象叫做CommonToken)。前面曾說過，你可以用以下的方法去指定詞法分析器為特定的類制造記號。
lexer.setTokenObjectClass("classname");
技術上，如果不請求特殊記號對象，也可以實現(xiàn)同樣功能的過濾器，但這樣實現(xiàn)非常有效率而且它很容易告訴詞法分析器去生成什么種類的記號。進一步說，這樣實現(xiàn)使得它很容易去自動完成包含隱藏流信息的樹結點的創(chuàng)建。
這個過濾器影響ANTLR的懶惰消費。在識別每一個主記號之后， TokenStreamHiddenTokenFilter必須獲取下一個記號看它是不是一個隱藏記號。因此，這個過濾器在交互程序(比如命令行)下工作的不是很好。
要使用TokenStreamHiddenTokenFilter，僅僅要做的是：
- 創(chuàng)建詞法分析器，讓它創(chuàng)建鏈接隱藏記號的記號對象。
MyLexer lexer = new MyLexer(some-input-stream);
lexer.setTokenObjectClass(
"antlr.CommonHiddenStreamToken"
);
- 創(chuàng)建一個TokenStreamHiddenTokenFilter對象,該對象從上面的詞法分析器中獲得記號。
TokenStreamHiddenTokenFilter filter =
new TokenStreamHiddenTokenFilter(lexer);
- 設置TokenStreamHiddenTokenFilter要隱藏哪些記號，要丟棄哪些記號。例如,
filter.discard(MyParser.WS);
filter.hide(MyParser.SL_COMMENT);
- 創(chuàng)建一個語法分析器，從TokenStreamHiddenTokenFilter而不是從詞法分析器中獲得記號。
MyParser parser = new MyParser(filter);
try {
parser.startRule(); // parse as usual
}
catch (Exception e) {
System.err.println(e.getMessage());
}
查看ANTLR指南，在preserving whitespace處有一個完整的例子。
最后，在翻譯階段，如果需要這些隱藏的流記號，在遍歷樹的時候,則可以按正常的方式使用。怎么做才能在不打亂樹文法的情況下把隱藏流的信息送給翻譯器呢？很簡單： 用AST結點儲存這些隱藏流記號。ANTLR定義了CommonASTWithHiddenTokens來自動連接隱藏流記號到樹結點; 聯(lián)合一個樹結點，適用于樹結點的方法在這里也適用于訪問這些隱藏記號。你只需要告訴語法分析器去創(chuàng)建這種類型的結點而不是默認的CommonAST類型的結點。
parser.setASTNodeClass("antlr.CommonASTWithHiddenTokens");
樹結點作為記號對象的功能被創(chuàng)建。當ASTFactory創(chuàng)建樹結點的時候，樹結點的initialize()方法被調用。從記號創(chuàng)建的樹結點包含隱藏記號，不管在前還是在后，都有著同樣的對隱藏記號的引用。你不需要用這個結點定義，但它工作在很多翻譯任務中：
package antlr;
/** CommonAST在初始化時把從記號中獲得
* 的隱藏記號的信息復制，用來創(chuàng)建結點
*/
public class CommonASTWithHiddenTokens
extends CommonAST {
// 指向隱藏記號
protected Token hiddenBefore, hiddenAfter;
public CommonHiddenStreamToken getHiddenAfter() {
return hiddenAfter;
}
public CommonHiddenStreamToken getHiddenBefore() {
return hiddenBefore;
}
public void initialize(Token tok) {
CommonHiddenStreamToken t =
(CommonHiddenStreamToken)tok;
super.initialize(t);
hiddenBefore = t.getHiddenBefore();
hiddenAfter = t.getHiddenAfter();
}
}
注意到這個結點定義假設你用了CommonHiddenStreamToken對象。如果你沒有讓詞法分析器創(chuàng)建CommonHiddenStreamToken對象，就會出現(xiàn)運行時類下行異常。
利用對主流記號的引用分隔輸入流，保存隱藏流記號時，GC允許在記號流上工作。在上面的整數(shù)聲明的例子中，當沒有更多的對第一個SEMI記號以及第二個INT記號的引用時，comment記號將會作為垃圾回收的候選人。如果所有的記號是連在一起的，一個單獨的對任意記號的引用會阻止任何記號被回收。這在ANTLR實現(xiàn)不是問題。
翻譯時,過濾器在保存空白符和注釋方面做得很好，但在處理輸出和輸入相差很遠的情況下，用過濾器不是一個最好的辦法。例如，有3個注釋散布在一個輸入聲明語句中，你想在翻譯階段合并到輸出聲明語句的頭部。比起察看注釋周圍的每一個分析的記號，更好的辦法是有一個真正實際上分開的流來保存注釋以及一個方法去聯(lián)系分析好的記號的組和注釋流記號的組。你或許想支持像"給我在注釋流上從開始分析到結束分析時最初出現(xiàn)的的所有記號."
這個過濾器實現(xiàn)了同JavaCC中special記號及其相似的功能。Sriram Sankar (JavaCC之父) 關于特殊記號有一個非常好的想法，在1997的Dr. T's Traveling Parsing Revival and Beer Tasting Festival，出席者認同了泛化記號流的概念?，F(xiàn)在JavaCC特殊記號功能僅僅是另一個ANTLR流過濾器，好處是你不用去為指定哪些記號是特殊的而修改詞法分析器。
現(xiàn)在，考慮一下相反的問題，你想合并多個流而不是把一個流分成多個。當你的輸入包含根本上不同的片段，比如說Java和JavaDoc注釋，你會發(fā)現(xiàn)僅用一個詞法分析器去識別所有的輸入片段是很難的。這主要是因為合并各種部分的記號定義會造成二義性詞法語言或者識別出一些錯誤的記號。例如，"final"在某些部分里是一個關鍵字，但在另一個部分里它可能會是一個標示符。同樣，"@author"是一個合法的javadoc注釋里的標記，但在Java代碼中，它是不合法的。
大部分人為了解決這個問題，為詞法分析器設定了很多狀態(tài)，在不同的部分里切換到不同的狀態(tài)來工作(例如，在"讀取Java模式"和"讀取JavaDoc模式"中間切換)。詞法分析器開始是以Java模式工作的，然后在遇到"/**"后切換到JavaDoc模式; "*/"強制切換回Java模式。
讓一個詞法分析器在多個狀態(tài)下工作可以解決上述的問題，但有一個更好的解決問題的辦法，讓多個詞法分析器協(xié)同工作，生成一個記號流。為什么說這種辦法更好呢？因為分開的詞法分析器更利于重用(不是剪貼粘貼，而僅僅是告訴流的多元管理器去切換不同的詞法分析器，就得到了一個新的詞法分析器)。例如，JavaDoc詞法分析器可以在解決任何有JavaDoc注釋的語言問題時得到重用。
ANTLR預設了一個記號流叫做TokenStreamSelector，可以用它在多個詞法分析器間進行切換。不同詞法分析器中定義的動作控制這個選擇器切換輸入流?？紤]下面的Java代碼片段。
/** Test.
* @author Terence
*/
int n;
給出2個詞法分析器，JavaLexer和JavaDocLexer，2個詞法分析器的動作序列可能看起來是下面的樣子：
JavaLexer: 匹配JAVADOC_OPEN, 切換到JavaDocLexer
JavaDocLexer: 匹配AUTHOR
JavaDocLexer: 匹配ID
JavaDocLexer: 匹配JAVADOC_CLOSE, 切換回JavaLexer
JavaLexer: 匹配INT
JavaLexer: 匹配ID
JavaLexer: 匹配SEMI
在Java詞法分析器的文法中，你需要定義一個規(guī)則去切換到JavaDoc詞法分析器(把需要切換的詞法分析器記錄在棧中):
JAVADOC_OPEN
: "/**" {selector.push("doclexer");}
;
同樣地，在JavaDoc詞法分析器中定義一個規(guī)則切換回去：
JAVADOC_CLOSE
: "*/" {selector.pop();}
;
選擇器中有一個棧，所以JavaDoc詞法分析器不用知道誰調用了它。
入圖，選擇器和并2個詞法分析器流，為下游的語法分析器提供單獨的一個記號流。
選擇器可以為你維護流列表，所以你可以通過名字或者實際對象的引用來切換到另一個輸入流。
public class TokenStreamSelector implements TokenStream {
public TokenStreamSelector() {...}
public void addInputStream(TokenStream stream,
String key) {...}
public void pop() {...}
public void push(TokenStream stream) {...}
public void push(String sname) {...}
/** Set the stream without pushing old stream */
public void select(TokenStream stream) {...}
public void select(String sname)
throws IllegalArgumentException {...}
}
用選擇器很簡單:
TokenStreamSelector selector =
new TokenStreamSelector();
- 為流命名(不是一定要命名--在切換的時候你可以用流對象的引用來避免使用哈希表查找)。
selector.addInputStream(mainLexer, "main");
selector.addInputStream(doclexer, "doclexer");
- 選擇哪一個詞法分析器先從字符流中讀數(shù)據(jù)。
// start with main java lexer
selector.select("main");
JavaParser parser = new JavaParser(selector);
在介紹語法分析器如何使用選擇器之前，注意一下這2個詞法分析器都要從同一個輸入流中讀取字符。以前的ANTLR2.6.0版本，每一個詞法分析器都有它自己的記錄行號的變量，輸入字符流變量等等。為了共享同樣的輸入狀態(tài)，ANTLR2.6.0代理詞法分析器來處理字符輸入到對象中，LexerSharedInputState可以被n個詞法分析器共享(單線程)。為了讓多個詞法分析器共享狀態(tài)，你創(chuàng)建第一個詞法分析器，獲得它的輸入狀態(tài)對象，然后在構建其它詞法分析器并且需要共享輸入狀態(tài)的時候使用它:
// 創(chuàng)建Java詞法分析器
JavaLexer mainLexer = new JavaLexer(input);
// 創(chuàng)建javadoc詞法分析器; 使用
// java詞法分析器的共享輸入狀態(tài)
JavaDocLexer doclexer =
new JavaDocLexer(mainLexer.getInputState());
就像一個詞法分析器在從不同的輸入片段中生產(chǎn)一個單獨的流會遇到很多麻煩，一個單獨的語法分析器在處理多記號流的時候也會遇到一些麻煩。又是同樣的問題，一個記號在一個詞法分析器中可能是一個關鍵字，在另一個詞法分析器中可能會是一個標示符。把語法分析器分解成子分析器，為每一個輸入片段單獨處理它們的單詞表，這樣做同時也利于語法分析器的重用。
下面的語法分析器文法用主詞法記號的詞表(用importVocab指定)，在遇到JAVADOC_OPEN的時候，它創(chuàng)建并且調用一個JavaDoc分析器去處理接下來在注釋中的記號流。
class JavaParser extends Parser;
options {
importVocab=Java;
}
input
: ( (javadoc)? INT ID SEMI )+
;
javadoc
: JAVADOC_OPEN
{
// 創(chuàng)建一個分析器去處理javadoc注釋
JavaDocParser jdocparser =
new JavaDocParser(getInputState());
jdocparser.content(); // 用jdocparser繼續(xù)分析
}
JAVADOC_CLOSE
;
你會發(fā)現(xiàn)從2.6.0版本起，ANTLR語法分析器也共享記號輸入流狀態(tài)。當創(chuàng)建"子分析器"時, JavaParser告訴它從同一輸入狀態(tài)對象中獲取記號。
JavaDoc分析器匹配一串標簽:
class JavaDocParser extends Parser;
options {
importVocab=JavaDoc;
}
content
: ( PARAM // includes ID as part of PARAM
| EXCEPTION
| AUTHOR
)*
;
當子分析器規(guī)則content結束后，控制權自然地返回給它的調用方,也就是Java分析器中的javadoc。
如果語法分析器需要去查看JavaDOc注釋起始位置后的2個記號，那會發(fā)生什么呢？換句話說，以主分析器來看，JAVADOC_OPEN之后的記號是什么呢? 自然是記號 JAVADOC_CLOSE！ 主分析器把任何JavaDoc注釋都看作是一個實體,不管這個注釋有多復雜; 它不用去了解注釋記號流內(nèi)部情況,它也不需要這么做--子分析器會去處理這件事情。
在子分析器中，content規(guī)則后是什么記號呢？是"End of file"記號。子分析器的分析過程不能確定你的代碼中將會調用怎樣的方法。但這不是一個問題，因為一般情況會有一個單獨的記號標示子分析過程的結束。即使因為某種原因EOF被載入到分析過程，EOF也不會出現(xiàn)在記號流中。
多詞法分析器狀態(tài)也經(jīng)常被用來處理那些非常復雜的單個記號，比如說嵌入轉義字符的字符串，輸入"\t"應該被識別為一個字符串。針對這種情況，典型的做法是在第一個引號之后，切換詞法分析器到"字符串狀態(tài)"然后在識別完字符串之后切換回"普通狀態(tài)"。
所以把這種代碼依靠模式做事情的方式叫做"模態(tài)"編程，這通常是一個比較差的方式。在這種復雜記號的情況下，最好是用多個規(guī)則直接指定復雜的記號。這里有一個什么時候該用多記號流和什么時候不該用的黃金規(guī)則:
復雜的單個記號應該通過調用另一個(protected)詞法規(guī)則來匹配，對一段輸入片段來說應該用多個詞法分析器處理此輸入流并提供給分析器。
例如，詞法分析器字符串的定義應該僅僅是調用另一個規(guī)則來處理轉義字符的情況:
STRING_LITERAL
: '"' (ESC|~('"'|'\\'))* '"'
;
protected // 不是一個記號; 僅僅被另一個規(guī)則調用
ESC
: '\\'
( 'n'
| 'r'
| 't'
| 'b'
| 'f'
| '"'
| '\''
| '\\'
| ('u')+
HEX_DIGIT HEX_DIGIT HEX_DIGIT HEX_DIGIT
...
)
;
在很多情況下，你希望在原代碼基礎上修改或者增加一段程序或數(shù)據(jù)文件。ANTLR 2.7.3 介紹了一個(只有Java/C#版本)非常簡單但非常強大的類
TokenStream處理以下問題：
- 輸出語言和輸入語言相似
- 語言元素的相對次序不改變
參見antlr網(wǎng)站上的
Syntax Directed TokenStream Rewriting。
ANTLR 2.6版本為使用記號流提供了基本結構，一旦我們有經(jīng)驗使用它們，今后的版本將會更加強大。
現(xiàn)在的"隱藏記號"流過濾器解決"忽略但保存空白符"的問題解決的很好，但它在很多情況下不能很好的處理注釋。例如，在真正的翻譯過程中，你想在各種單獨的樹結點上收集注釋(像DECL或者METHOD)而不是把它們分布在樹的各個地方。你迫切需要一個流分離器緩沖注釋到一個隔離的流中，這時你就可以說"給我在識別這個規(guī)則上所用掉的所有注釋"或者 "給我這2個記號之間的所有注釋." 這幾乎是你在注釋翻譯時所需要的所有功能。
記號流會帶來很多便利。大部分人不經(jīng)常思考關于記號流的事，使得很難去想象可以在其他一些什么地方可以變的更好。讓思想更奔放一些。怎樣處理嵌入語言的輸入片段，就像你所能看到的Java中嵌入SQL(每一個輸入的部分被分開并通過不同的流)。怎么樣分析含有和不含有調試信息的Java .class文件？如果你有一個可以分析不含調試信息的.class文件分析器，你想用這個來分析含有調試信息的.class文件，不要去管這個分析器，為你的詞法分析器新增關于調試信息的結構。然后用一個過濾器分離調試信息記號到另一個流，這樣，對兩種類型的.class文件，原來的分析器都可以正常工作了。
稍后，我想加一個"視圖"，這是真正的另一個查看過濾器的方法。想象一下從一個詞法分析器(根視圖)中發(fā)射出一個未加工的記號流。對它，我可以非常輕松的構建一棵視圖樹。例如，給出一個嵌有SQL的Java程序，你可能想為分析或翻譯在輸入流上建立視圖，會是下面的樣子：
你可以把SQL流或者去掉注釋的Java流交給你的語法分析器處理，分析器中的動作也可以去訪問注釋流。
將來，我還會增加分析器的另一個功能，去生成記號流(或文本)作為輸出，就像建立了樹一樣。用這樣方式，多傳遞分析變得十分自然和簡單，因為語法分析器也變成了流的生產(chǎn)者。一個語法分析器的輸出可以是另一個語法分析器的輸入。
Version: $Id: //depot/code/org.antlr/release/antlr-2.7.6/doc/streams.html#1 $