Rsg:
一個基于正規(guī)式的掃描器生成器

YYQ

Version 1.1, 2009/8/31

內容

• 1. 概述
• 2. 一個簡單的例子
• 3. 描述文件
  • 3.1 標識符和關鍵字
  • 3.2 正規(guī)式定義
  • 3.3 預定義正規(guī)式
  • 3.4 掃描器的描述
    • 3.3.1 普通規(guī)則
    • 3.3.2 文件結束規(guī)則
    • 3.3.3 初始化規(guī)則
    • 3.3.4 優(yōu)先級和二義性
  • 3.5 空白和注釋
  • 3.6 詞法狀態(tài)
• 4. 生成的掃描器
• 5. 動作和編程接口
  • 5.1 使用動作
  • 5.2 API
• 6. 編碼問題
• 7. 和分析器的接口

1. 概述

Rsg是一個詞法分析器（掃描器）生成工具。它接收一個詞法描述文件，處理后生成相應的掃描器源程序，這里描述詞法的主要手段就是正規(guī)式。

和一些既存的詞法生成器相比，如JLex、JFlex，Rsg有相同點也有不同點，Rsg的主要特征有：

• 簡單的語法。Rsg借用了高級語言中的一些語法元素，因此描述更加清晰明確。
• 動作分離。和大多數詞法生成器一樣，JLex等都是把用于動作處理的目標代碼（這里是Java）夾雜在輸入文件中的，Rsg沒有采用這種模式，而是將所有的動作都用一個標識符來代替，具體的動作處理代碼則需另外實現（一般是通過擴展子類）。
• 支持詞法狀態(tài)。
• 支持正規(guī)式庫。Rsg對原來所謂的預定義正規(guī)式進行了擴展，形成了容易擴展的正規(guī)式庫。
• 支持Unicode。實際上，Rsg對Unicode的支持比JLex等強大得多。

2. 一個簡單的例子

下面先通過一個簡單的例子來介紹Rsg的使用方法。這是一個能識別標識符、整數、簡單的字符串、字符并忽略空白和注釋的掃描器。

1. 創(chuàng)建輸入文件RsgQs.rsg：

    

   /**
       * 這是一個簡單的Rsg示例。
       */
       regexp LineTerminator = "\r" | "\n" | "\r\n" ;
       regexp WhiteSpace = LineTerminator | [' ', '\t', '\f'] ;
       regexp Comment = "/*" % "*/" ;
       regexp Letter = ['a'-'z', 'A'-'Z'];
       regexp Digit = ['0'-'9'] ;
       regexp Identifier = Letter (Letter | Digit) * ;
       regexp Integer = Digit + ;
       regexp StringCharacter = ~['\r', '\n', '\"'] ;
       regexp SingleCharacter = ~['\r', '\n', '\''] ;
       scanner RsgQs {
       '"' StringCharacter *  '"' : return STRING; /* 字符串 */
       '\'' SingleCharacter '\'' : return CHARACTER; /* 字符 */
       Identifier : return IDENTIFIER; /* 標識符 */
       Integer : return INTEGER; /* 整數 */
       Comment : skip; /* 注釋 */
       WhiteSpace :skip;
       eoi : return EOI;
       }
       

    

2. 設置CLASSPATH：
   

    

   SET CLASSPATH=.;path_to\rsg_bin_X_X.jar;

    

3. 生成掃描器：
   

    

   java yyq.prod.rsg.RsgC -test RsgQs.rsg

    

4. 編譯：
   

    

   javac *.java

    

5. 準備輸入文件RsgQs.in：

    

   "abcdefg" "gfedcba"
       abc123 1234567 7654321
       /* 注釋 */
       'a' 'b' 'c' abc
       

    

6. 運行：
   

    

   java RsgQsScannerTest RsgQs.in

    

7. 有如下結果，可以對照RsgQsTokenTypes.java來看：
   

    

   1L,1C：0 <"abcdefg">
       1L,11C：0 <"gfedcba">
       2L,1C：2 <abc123>
       2L,8C：3 <1234567>
       2L,16C：3 <7654321>
       4L,1C：1 <'a'>
       4L,5C：1 <'b'>
       4L,9C：1 <'c'>
       4L,13C：2 <abc>
       用時：47ms，掃描到9個符號。
       

    

3. 描述文件

  導入預定義正規(guī)式
正規(guī)式定義
....
正規(guī)式定義
scanner ScannerName {
掃描器規(guī)則
詞法狀態(tài)名 {
掃描器規(guī)則
...
}
...
}

輸入文件大體由兩部分組成，前面是正規(guī)式的導入或定義，從scanner開始則是由一系列規(guī)則組成的掃描器的描述，其中關于詞法狀態(tài)的內容將在3.6節(jié)詳細講述。

3.1 標識符和關鍵字

在Rsg中，標識符由若干個英文字母（U+0041-U+005A，U+0061-U+007A）、下劃線（U+002D）、數字（U+0030-U+0039）連接而成，但必須以字母或下劃線開頭。

此外，下面幾個標識符被Rsg用作關鍵字：

import regexp scanner return skip eoi ini

它們不能再作為標識符來使用。此外，在Rsg中，標識符是大小寫敏感的。標識符的使用有時候需要考慮目標語言的語法，以免沖突，命名規(guī)則也最好遵從目標語言的命名規(guī)則。

3.2 正規(guī)式定義

有時把正規(guī)式單獨定義能使代碼更加清晰，其語法如下：

regexp 正規(guī)式名 = 正規(guī)式體 ;

regexp是關鍵字，正規(guī)式名是一個任意的標識符，但不能和別的正規(guī)式名重復。

正規(guī)式體是正規(guī)式定義中最復雜的部分，在說明它之前我們先來介紹Rsg中兩種基本的數據類型：字符和字符串。

字符

基本上，Rsg采用和Java相似的語法來描述單個字符，一般字符的表示如下：

'a'、'字'、'符'

\b

\t

\n

\f

\r

\"

\"

\\

\ddd

\uxxxx[\uxxxx]

字符串

字符串實際上就是雙引號引起的0個或多個字符，下面都是一些合法的字符串：

""、"abc"、"字符串"、"\u5B57\u7B26\u4E32"

我們現在來介紹正規(guī)式的語法，先說一下符號約定，我們一般用大寫字母A、B、C等來表示正規(guī)式。下表是Rsg中描述正規(guī)式的語法及其含義：

            
['a']、['a'-'z', 'A'-'Z', '0'-'9']、["aeiou"]、~['\n']
            

各種運算的優(yōu)先級如下表所示：

另外，&、|、連接運算都是從左向右的。

3.3 預定義正規(guī)式

除了直接定義正規(guī)式，我們也可以從正規(guī)式庫中導入正規(guī)式，其導入的方法如下：

import 正規(guī)式名1, 正規(guī)式名2,... ;

import語句可以有多條，但必須在文件的開始，正規(guī)式庫中的正規(guī)式列表請參考：正規(guī)式一覽表。

3.4 掃描器的描述

如前所述，掃描器用關鍵字scanner來定義，后面跟一個標識符指定掃描器的名稱。一個掃描器的描述有若干條規(guī)則組成，規(guī)則又分為幾種，下面分別敘述。

3.3.2 普通規(guī)則

普通規(guī)則語法如下：

正規(guī)式 : [<標識符>] 最終動作 ;

正規(guī)式：該規(guī)則用于匹配的正規(guī)式，可以用前面定義正規(guī)式完全相同的方法來書寫。

<標識符> ：這部分是可選的，這個標識符代表一個動作，該動作將在規(guī)則匹配成功后執(zhí)行。和一般的掃描器生成器把用于動作處理目標代碼直接寫在輸入文件中不同，Rsg把動作用一個標識符抽象的表示，它的具體實現取決于目標語言（目前只實現了Java），現在做法是，每個動作對應目標語言中的一個函數，這個函數的內容則需另外實現。

最終動作：所謂最終動作，指規(guī)則匹配成功后的最終行為，現有兩種類型：

• return：結束本次掃描，并返回一個標識符（一個整形常量名），這個標識符一般能標識掃描到的詞法符號的類型。例：

   

      
  ['0' - '9'] + : return INTEGER;
      

   

• skip：忽略所掃描到的內容，重新開始匹配。例：

   

      
  [' ', '\t', '\r', '\n', '\f'] + : skip; // 忽略空白字符
      

   

3.3.2 文件結束規(guī)則

文件結束規(guī)則用于確定輸入結束的行為，語法如下：

eoi : [<標識符>] 最終動作 ;

其中eoi是關鍵字，動作和最終動作跟普通規(guī)則意義是一樣的。特別提醒的是，在Rsg輸出的掃描器中，文件結束被認為是可以匹配無窮次的，一般情況下，不要嘗試把eoi規(guī)則的最終動作設為skip，那將會導致死循環(huán)（此外還有空匹配也可能導致死循環(huán)）。

eoi規(guī)則是可選的（但最多定義一條），如果沒有，那么將使用默認規(guī)則：

eoi : return EOI ;

3.3.3 初始化規(guī)則

初始化規(guī)則語法如下：

ini : <標識符> ;

其中ini是關鍵字，標識符代表一個動作。ini規(guī)則的作用就一個，用于在規(guī)則匹配前執(zhí)行一個動作。默認沒有ini規(guī)則，而且最多定義一條ini規(guī)則。

3.3.4 優(yōu)先級和二義性

當有多于一條規(guī)則與同一個串匹配時，就出現了二義性，Rsg采用和LEX同樣的處理原則：

• 1）能匹配最多字符的規(guī)則優(yōu)先
• 2）如果1）還不能消除沖突，則先給出的規(guī)則優(yōu)先。

3.5 空白和注釋

在Rsg的輸入文件中可以使用兩種注釋：

• /* text */ 傳統(tǒng)注釋
• // text 單行注釋

除此以外，輸入文件中的所有空白字符都將被忽略。

3.6 詞法狀態(tài)

我們可以把掃描器中的若干規(guī)則組織到一個組中，并對其命名，則稱這樣一個規(guī)則組為一個詞法狀態(tài)。

有了詞法狀態(tài)我們處理構成更為復雜的文件，先來看一個例子，如果我們要處理一個包含學生成績的文本文件，這個文件格式是這樣的：

01 80
02 90

文件的每一行分別由學號和成績組成，由于學號和成績都是數字，如果按前面的方式構造掃描器，將不能正確區(qū)分學號和成績，這時我們可以構造下面的詞法文件：

/**
* 詞法狀態(tài)示例。
*/
regexp WhiteSpace = "\r" | "\n" | "\r\n" | [' ', '\t', '\f'] ;
regexp Digit = ['0'-'9'] ;
scanner Grade {
STATE1 {
Digit + : return ID; /* 學號 */
}
STATE2 {
Digit + : return GRADE; /* 成績 */
}
STATE1, STATE2 {
WhiteSpace :skip;
}
eoi : return EOI;
}

然后使用下面的代碼進行處理：

GradeScanner scanner = new GradeScanner ...
scanner.setLexState(GradeLexStates.STATE1);
int type = scanner.scan();
while (type != GradeTokenTypes.EOI) {
switch(type) {
case GradeTokenTypes.ID :
System.out.println("學號：" + scanner.text() );
scanner.setLexState(GradeLexStates.STATE2);
break;
case GradeTokenTypes.GRADE :
System.out.println("成績：" + scanner.text() );
scanner.setLexState(GradeLexStates.STATE1);
break;
}
type = scanner.scan();
}

使用詞法狀態(tài)的其他有用信息：

• 系統(tǒng)會預定義一個詞法狀態(tài)DEFAULT，所有沒被包含在某個詞法狀態(tài)中的規(guī)則都會加入默認詞法狀態(tài)。
• 如果沒有使用setLexState改變詞法狀態(tài)，掃描器將一直處于DEFAULT詞法狀態(tài)。
• 掃描器處于某個詞法狀態(tài)時（包括DEFAULT），會對其他詞法狀態(tài)的規(guī)則“視而不見”，因此如果想讓不同的詞法狀態(tài)都能識別同一條規(guī)則，必須把這條規(guī)則同時包含在不同的詞法狀態(tài)內。

4 生成的掃描器

一般來說，生成的掃描器結構是和目標語言相關的，為了方便，這里還是用接2節(jié)的例子來說明，但這里說明的是通用的情況。

由Rsg生成的文件中，有幾個是掃描器的實現者需要注意的：

• RsgQsScanner.java 掃描器主類。
• RsgQsTokenTypes.java 定義詞法符號類型的常量。
• RsgQsHandler.java 掃描器動作處理接口。
• RsgQsLexStates.java 定義詞法狀態(tài)的常量。
• NoMatchException.java 異常。

RsgQsScanner類的構造方法需要一個java.io.Reader型的參數，用于給定輸入的字符流。

每次掃描由方法scan完成，它完成匹配并最終返回詞法符號的類型。

public int scan() throws IOException, yyq.prod.rsg.rt.ScanException;

RsgQsHandler類是一個包含所有的動作方法的接口。對于描述文件中的每一個動作XXX，在RsgQsHandler類中將包含一個同名的方法：

public void XXX(RsgQsScanner scanner);

5 動作和編程接口

動作用于在匹配過程中做一些語義方面的處理。由于Rsg沒有實現詞法狀態(tài)，這限制了Rsg進行復雜的動作處理，作為替代，Rsg實現了兩種不同的內部動作，不過其中一種為實驗性的。

5.1 使用動作

下面將通過一個具體的例子來展示如何在Rsg中使用動作。我們在第1節(jié)的例子上加入一些內部動作，從而在掃描時實現語義處理。

1. 創(chuàng)建輸入文件RsgAct.rsg：

    

   /**
       * 展示在Rsg中使用動作的示例。
       */
       regexp LineTerminator = "\r" | "\n" | "\r\n" ;
       regexp WhiteSpace = LineTerminator | [' ', '\t', '\f'] ;
       regexp Comment = "/*" % "*/" ;
       regexp Letter = ['a'-'z', 'A'-'Z'];
       regexp Digit = ['0'-'9'] ;
       regexp Identifier = Letter (Letter | Digit) * ;
       regexp Integer = Digit <firstDigit> ( Digit <otherDigit> ) + ;
       regexp StringCharacter = ~['\r', '\n', '\"'] ;
       regexp SingleCharacter = ~['\r', '\n', '\''] ;
       scanner RsgAct {
       '"' <beginString> ( StringCharacter <strChar> )*  '"' : return STRING; /* 字符串 */
       '\'' SingleCharacter <singleChar> '\'' : return CHARACTER; /* 字符 */
       Identifier : return IDENTIFIER;  /* 標識符 */
       Integer : return INTEGER; /* 整數 */
       Comment : skip; /* 注釋 */
       WhiteSpace :skip;
       eoi : <onEoi> return EOI;
       }
       

    

2. 設置CLASSPATH：
   

    

   SET CLASSPATH=.;path_to\rsg_bin_X_X.jar;

    

3. 生成掃描器代碼：
   

    

   java yyq.prod.rsg.RsgC RsgAct.rsg

    

4. 編寫掃描器實現類RsgActHandlerImpl.java：

    

   import java.io.*;
       /**
       *
       * 掃描器的實現類。
       *
       */
       public class RsgActHandlerImpl implements RsgActHandler {
       private StringBuilder string;
       private int integer;
       private int character;
       public void firstDigit(RsgActScanner scanner) {
       int ch = scanner.ch();
       integer = ch - '0';
       }
       public void otherDigit(RsgActScanner scanner) {
       int ch = scanner.ch();
       integer *= 10;
       integer += (ch - '0');
       }
       public void beginString(RsgActScanner scanner) {
       string = new StringBuilder();
       }
       public void strChar(RsgActScanner scanner) {
       int ch = scanner.ch();
       string.appendCodePoint(ch);
       }
       public void singleChar(RsgActScanner scanner) {
       character = scanner.ch();
       }
       public void onEoi(RsgActScanner scanner) {
       System.out.println("文件結束。");
       }
       public int getCharacter() {
       return character;
       }
       public int getInteger() {
       return integer;
       }
       public String getString() {
       return string.toString();
       }
       }
       

    

5. 編寫主類RsgActMain.java：

    

   import java.io.*;
       import java.nio.charset.*;
       import yyq.prod.rsg.rt.*;
       /**
       * Main類。
       */
       public class RsgActMain {
       public static void main(String[] argv) throws IOException, yyq.prod.rsg.rt.NoMatchException {
       if(argv.length < 1) {
       System.out.println("使用方法：java RsgActMain file");
       System.exit(1);
       }
       long t1 = System.currentTimeMillis();
       RsgActHandlerImpl handler = new RsgActHandlerImpl ();
       RsgActScanner scanner = new RsgActScanner (
       new InputStreamReader(
       new FileInputStream(argv[0]),
       Charset.forName("GB18030")), handler);
       int count = 0;
       int type = scanner.scan();
       while (type != RsgActTokenTypes.EOI) {
       switch(type) {
       case RsgActTokenTypes.STRING :
       System.out.println("\"" + handler.getString() + "\"");
       break;
       case RsgActTokenTypes.CHARACTER :
       System.out.print("'");
       System.out.print(Character.toChars(handler.getCharacter()));
       System.out.println("'");
       break;
       case RsgActTokenTypes.INTEGER :
       System.out.println(handler.getInteger());
       break;
       case RsgActTokenTypes.IDENTIFIER :
       System.out.println(scanner.text());
       break;
       default :
       System.out.println("非法類型");
       break;
       }
       count++;
       type = scanner.scan();
       }
       long t2 = System.currentTimeMillis();
       System.out.println("用時：" + (t2 - t1) + "ms，掃描到" + count + "個符號。");
       }
       }
       

    

6. 編譯：
   

    

   javac *.java

    

7. 準備輸入文件RsgAct.in：

    

   "abcdefg" "gfedcba"
       abc123 1234567 7654321
       /* 注釋 */
       'a' 'b' 'c' abc
       

    

8. 運行：
   

    

   java RsgActMain RsgAct.in

    

9. 有如下結果：
   

    

   "abcdefg"
       "gfedcba"
       abc123
       1234567
       7654321
       'a'
       'b'
       'c'
       abc
       文件結束。
       用時：47ms，掃描到9個符號。
       

    

內部動作分為兩種：

1. 一種是嵌入到正規(guī)式里的，如例中的<beginString>。
2. 另一種是規(guī)則匹配完成后執(zhí)行的動作，如例中的<onEoi>。

到目前為止，前者還是實驗性的，使用起來有些注意事項：

• 內部動作的優(yōu)先級是最高的，也就是說它總是和最“緊挨”它的正規(guī)式結合。

• 內部動作按“匹配就執(zhí)行”的原則被執(zhí)行，這有時很容易導致混亂，如：

  A) ( ['0' - '9'] <onDigit> ) *

  B) ( ['0' - '9'] ) * <nullOrDigit>

  A的情況，動作onDigit將在匹配到一個數字后才執(zhí)行，而對于B，動作nullOrDigit將在沒有匹配到任何數字之前就執(zhí)行，原因是*匹配空，而按照“匹配就執(zhí)行”的原則，此時已經匹配了。這只是簡單的情況，對于有多處匹配空的情況，內部動作行為將更加難以預料。

• 由于我們采取的是“貪婪”匹配算法，因此可能會出現匹配過了頭的情況，而此時內部動作仍將被執(zhí)行。

鑒于以上原因，在不確定執(zhí)行流程的情況下不推薦使用第一種內部動作。

5.2 API

為了在內部動作中獲得掃描器的狀態(tài)，可以使用下面這些API

public String text()

public int line()

public int column()

public int ch()

public String rext()

public int newMark()

public void cancelMark()

public void mark(int id)

public String getMarkedText(int mark1, int mark2)

public String getMarkedText(int mark)

public void setLexState(int lexId)

6 編碼問題

在Rsg的內部使用Unicode的Code Point作為其處理字符的基本單位（而不是Java中的基本數據類型char），Rsg生成的掃描器也是如此，因此能處理各種字符編碼。為了避免使用過程中出現編碼問題，掃描器的實現者必須在以下幾個環(huán)節(jié)使用正確的編碼。

首先是Rsg輸入文件的編碼，這可以通過命令行參數設置，否則將使用默認編碼GB18030。其二是Rsg輸出的掃描器源文件使用的編碼，一般來說這是無關緊要的，但要和編譯器保持一致，默認編碼為GB18030。三是構造掃描器時使用的編碼，實際上掃描器的構造函數接受一個java.io.Reader對象來指定字符流，因此只要在創(chuàng)建Reader對象時使用正確的編碼就可以了。

7 和分析器的接口

掃描器往往作為分析器的一部分而存在，把字符流分離成詞法符號流傳給分析器。Rsg沒有“內置”地支持某種分析器生成工具，但一般來說用戶只要在Rsg生成的掃描器基礎上進行適當的“包裝”就可以適應不同的分析器。此外Rsg提供一個external參數來指定一個外部詞法符號常量接口，這個接口一般由分析器生成工具生成。