Rsg使用指南
Rsg:
一个基于正规式的扫描器生成器
YYQ
Version 1.1, 2009/8/31
Rsg是一个词法分析器（扫描器）生成工具。它接收一个词法描述文件，处理后生成相应的扫描器源程序，这里描述词法的主要手段就是正规式。
和一些既存的词法生成器相比，如JLex、JFlex，Rsg有相同点也有不同点，Rsg的主要特征有：
- 简单的语法。Rsg借用了高级语言中的一些语法元素，因此描述更加清晰明确。
- 动作分离。和大多数词法生成器一样，JLex等都是把用于动作处理的目标代码（这里是Java）夹杂在输入文件中的，Rsg没有采用这种模式，而是将所有的动作都用一个标识符来代替，具体的动作处理代码则需另外实现（一般是通过扩展子类）。
- 支持词法状态。
- 支持正规式库。Rsg对原来所谓的预定义正规式进行了扩展，形成了容易扩展的正规式库。
- 支持Unicode。实际上，Rsg对Unicode的支持比JLex等强大得多。
下面先通过一个简单的例子来介绍Rsg的使用方法。这是一个能识别标识符、整数、简单的字符串、字符并忽略空白和注释的扫描器。
- 创建输入文件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;
}
- 设置CLASSPATH：
SET CLASSPATH=.;path_to\rsg_bin_X_X.jar;
- 生成扫描器：
java yyq.prod.rsg.RsgC -test RsgQs.rsg
- 编译：
javac *.java
- 准备输入文件RsgQs.in：
"abcdefg" "gfedcba"
abc123 1234567 7654321
/* 注释 */
'a' 'b' 'c' abc
- 运行：
java RsgQsScannerTest RsgQs.in
- 有如下结果，可以对照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个符号。
如第2节例子所示，描述文件基本格式如下：
导入预定义正规式
正规式定义
....
正规式定义
scanner ScannerName {
扫描器规则
词法状态名 {
扫描器规则
...
}
...
}
输入文件大体由两部分组成，前面是正规式的导入或定义，从scanner开始则是由一系列规则组成的扫描器的描述，其中关于词法状态的内容将在3.6节详细讲述。
在Rsg中，标识符由若干个英文字母（U+0041-U+005A，U+0061-U+007A）、下划线（U+002D）、数字（U+0030-U+0039）连接而成，但必须以字母或下划线开头。
此外，下面几个标识符被Rsg用作关键字：
import regexp scanner return skip eoi ini
它们不能再作为标识符来使用。此外，在Rsg中，标识符是大小写敏感的。标识符的使用有时候需要考虑目标语言的语法，以免冲突，命名规则也最好遵从目标语言的命名规则。
有时把正规式单独定义能使代码更加清晰，其语法如下：
regexp 正规式名 = 正规式体 ;
regexp是关键字，正规式名是一个任意的标识符，但不能和别的正规式名重复。
正规式体是正规式定义中最复杂的部分，在说明它之前我们先来介绍Rsg中两种基本的数据类型：字符和字符串。
字符
基本上，Rsg采用和Java相似的语法来描述单个字符，一般字符的表示如下：
'a'、'字'、'符'
以下是用转义序列表示的字符：
\b
|
退格 |
\t
|
制表符 |
\n
|
换行 |
\f
|
换页 |
\r
|
回车 |
\"
|
双引号 |
\"
|
单引号 |
\\
|
斜杠 |
\ddd
|
用8进制表示的\u0000 到 \u00ff之间的字符。 |
\uxxxx[\uxxxx]
|
16进制表示的的Unicode字符，其中中括号部分是可选的。那为什么一个字符有时要用2个转义序列来表示呢？原因是在Rsg内部一个字符实际是指一个Unicode代码点（Code
Point），因此对于基本平面（Basic Multilingual
Plane）以外的字符，就需要用两个16位的字符（即代理字符）来表示了，不过注意，这两个代理字符必须能构成一个合法的代码点，关于代理字符的概念，请参考Unicode规范等相关文档。 |
字符串
字符串实际上就是双引号引起的0个或多个字符，下面都是一些合法的字符串：
""、"abc"、"字符串"、"\u5B57\u7B26\u4E32"
我们现在来介绍正规式的语法，先说一下符号约定，我们一般用大写字母A、B、C等来表示正规式。下表是Rsg中描述正规式的语法及其含义：
| 正规式 |
含义 |
| 字符 |
匹配该字符。 |
| 字符串 |
匹配该字符串。 |
| . |
匹配任意一个字符：U+0000-U+10FFFF。注意，包括换行符（在JLex中.仅匹配换行符以外的任意字符）。 |
| ( ... ) |
括号用于组合多个正规式。 |
| [ ... ] |
用于定义一个字符类。中括号中的元素可以是字符、字符区间、字符串，元素之间用逗号分开。如果在中括号之前有一个~字符，那么将对字符类求反（全集是U+0000
- U+10FFFF）。下面都是一些合法的字符类：
['a']、['a'-'z', 'A'-'Z', '0'-'9']、["aeiou"]、~['\n']
|
| 标识符 |
匹配标识符指定正规式，这个标识符必须是已经被定义的。 |
| A {n, m} |
匹配正规式A最少n次最多m次，A {2, 4}等价于 A A A? A?。 |
| A * |
匹配A零次或任意多次。 |
| A + |
匹配A一次以上。 |
| A ? |
匹配A零次或一次。 |
| % A |
直到正规式。匹配任意串直到遇到一个A（包括A）。 |
| ! A |
匹配除A以外的任何串。 |
| A B |
连接。匹配A后面跟一个B。 |
| A & B |
与。匹配能同时被A和B匹配的串。 |
| A - B |
差。匹配能被A匹配但不能被B匹配的串。 |
| A | B |
并。匹配能被A匹配或被B匹配的串。 |
| A <标识符> |
内部动作。实际上这算不上是正规式运算，仅列在这里，详细后述。 |
各种运算的优先级如下表所示：
| 优先级 |
运算 |
| 高 |
内部动作 |
|
* + ? {} |
| % ! |
| 连接 |
| & |
| - |
| 低 |
| |
另外，&、|、连接运算都是从左向右的。
除了直接定义正规式，我们也可以从正规式库中导入正规式，其导入的方法如下：
import 正规式名1, 正规式名2,... ;
import语句可以有多条，但必须在文件的开始，正规式库中的正规式列表请参考：正规式一览表。
如前所述，扫描器用关键字scanner来定义，后面跟一个标识符指定扫描器的名称。一个扫描器的描述有若干条规则组成，规则又分为几种，下面分别叙述。
普通规则语法如下：
正规式 : [<标识符>] 最终动作 ;
正规式：该规则用于匹配的正规式，可以用前面定义正规式完全相同的方法来书写。
<标识符>
：这部分是可选的，这个标识符代表一个动作，该动作将在规则匹配成功后执行。和一般的扫描器生成器把用于动作处理目标代码直接写在输入文件中不同，Rsg把动作用一个标识符抽象的表示，它的具体实现取决于目标语言（目前只实现了Java），现在做法是，每个动作对应目标语言中的一个函数，这个函数的内容则需另外实现。
最终动作：所谓最终动作，指规则匹配成功后的最终行为，现有两种类型：
-
return：结束本次扫描，并返回一个标识符（一个整形常量名），这个标识符一般能标识扫描到的词法符号的类型。例：
['0' - '9'] + : return INTEGER;
-
skip：忽略所扫描到的内容，重新开始匹配。例：
[' ', '\t', '\r', '\n', '\f'] + : skip; // 忽略空白字符
文件结束规则用于确定输入结束的行为，语法如下：
eoi : [<标识符>] 最终动作 ;
其中eoi是关键字，动作和最终动作跟普通规则意义是一样的。特别提醒的是，在Rsg输出的扫描器中，文件结束被认为是可以匹配无穷次的，一般情况下，不要尝试把eoi规则的最终动作设为skip，那将会导致死循环（此外还有空匹配也可能导致死循环）。
eoi规则是可选的（但最多定义一条），如果没有，那么将使用默认规则：
eoi : return EOI ;
初始化规则语法如下：
ini : <标识符> ;
其中ini是关键字，标识符代表一个动作。ini规则的作用就一个，用于在规则匹配前执行一个动作。默认没有ini规则，而且最多定义一条ini规则。
当有多于一条规则与同一个串匹配时，就出现了二义性，Rsg采用和LEX同样的处理原则：
- 1）能匹配最多字符的规则优先
- 2）如果1）还不能消除冲突，则先给出的规则优先。
在Rsg的输入文件中可以使用两种注释：
- /* text */ 传统注释
- // text 单行注释
除此以外，输入文件中的所有空白字符都将被忽略。
我们可以把扫描器中的若干规则组织到一个组中，并对其命名，则称这样一个规则组为一个词法状态。
有了词法状态我们处理构成更为复杂的文件，先来看一个例子，如果我们要处理一个包含学生成绩的文本文件，这个文件格式是这样的：
01 80
02 90
文件的每一行分别由学号和成绩组成，由于学号和成绩都是数字，如果按前面的方式构造扫描器，将不能正确区分学号和成绩，这时我们可以构造下面的词法文件：
/**
* 词法状态示例。
*/
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();
}
使用词法状态的其他有用信息：
- 系统会预定义一个词法状态DEFAULT，所有没被包含在某个词法状态中的规则都会加入默认词法状态。
- 如果没有使用setLexState改变词法状态，扫描器将一直处于DEFAULT词法状态。
- 扫描器处于某个词法状态时（包括DEFAULT），会对其他词法状态的规则“视而不见”，因此如果想让不同的词法状态都能识别同一条规则，必须把这条规则同时包含在不同的词法状态内。
一般来说，生成的扫描器结构是和目标语言相关的，为了方便，这里还是用接2节的例子来说明，但这里说明的是通用的情况。
由Rsg生成的文件中，有几个是扫描器的实现者需要注意的：
- RsgQsScanner.java 扫描器主类。
- RsgQsTokenTypes.java 定义词法符号类型的常量。
- RsgQsHandler.java 扫描器动作处理接口。
- RsgQsLexStates.java 定义词法状态的常量。
- 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);
在描述文件中包含动作的情况，扫描器的实现者要设计一个实现RsgQsHandler接口的类，并恰当的实现其中的所有接口方法，在构造RsgQsScanner时，也需要一个该类的实例，以便在需要时调用其中的动作方法。在第5节将详细介绍动作和编程接口。
动作用于在匹配过程中做一些语义方面的处理。由于Rsg没有实现词法状态，这限制了Rsg进行复杂的动作处理，作为替代，Rsg实现了两种不同的内部动作，不过其中一种为实验性的。
下面将通过一个具体的例子来展示如何在Rsg中使用动作。我们在第1节的例子上加入一些内部动作，从而在扫描时实现语义处理。
- 创建输入文件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;
}
- 设置CLASSPATH：
SET CLASSPATH=.;path_to\rsg_bin_X_X.jar;
- 生成扫描器代码：
java yyq.prod.rsg.RsgC RsgAct.rsg
- 编写扫描器实现类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();
}
}
- 编写主类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 + "个符号。");
}
}
- 编译：
javac *.java
- 准备输入文件RsgAct.in：
"abcdefg" "gfedcba"
abc123 1234567 7654321
/* 注释 */
'a' 'b' 'c' abc
- 运行：
java RsgActMain RsgAct.in
- 有如下结果：
"abcdefg"
"gfedcba"
abc123
1234567
7654321
'a'
'b'
'c'
abc
文件结束。
用时：47ms，扫描到9个符号。
内部动作分为两种：
- 一种是嵌入到正规式里的，如例中的<beginString>。
- 另一种是规则匹配完成后执行的动作，如例中的<onEoi>。
到目前为止，前者还是实验性的，使用起来有些注意事项：
- 内部动作的优先级是最高的，也就是说它总是和最“紧挨”它的正规式结合。
-
内部动作按“匹配就执行”的原则被执行，这有时很容易导致混乱，如：
A) ( ['0' - '9'] <onDigit> ) *
B) ( ['0' - '9'] ) * <nullOrDigit>
A的情况，动作onDigit将在匹配到一个数字后才执行，而对于B，动作nullOrDigit将在没有匹配到任何数字之前就执行，原因是*匹配空，而按照“匹配就执行”的原则，此时已经匹配了。这只是简单的情况，对于有多处匹配空的情况，内部动作行为将更加难以预料。
- 由于我们采取的是“贪婪”匹配算法，因此可能会出现匹配过了头的情况，而此时内部动作仍将被执行。
鉴于以上原因，在不确定执行流程的情况下不推荐使用第一种内部动作。
为了在内部动作中获得扫描器的状态，可以使用下面这些API
| 名称 |
作用 |
使用限制 |
public String text()
|
返回最近匹配到字符串。这个方法是公开的，也可以由外部调用。 |
可以在第二种内部动作中调用或匹配完了后由外部调用。 |
public int line()
|
返回最近匹配到符号的行。这个方法是公开的，也可以由扫描结束后在外部调用。 |
可以在第二种内部动作中调用或匹配完了后由外部调用。 |
public int column()
|
返回最近匹配到符号的列。这个方法是公开的，也可以由外部调用。 |
可以在第二种内部动作中调用或匹配完了后由外部调用。 |
public int ch()
|
返回最近匹配的字符（CodePoint）。 |
只能在第一种内部动作中调用，在没有任何匹配前调用得到的返回值没有意义。 |
public String rext()
|
返回到当前为止所匹配的字符串。 |
只能在第一种内部动作中调用。 |
public int newMark()
|
创建一个新的标记。并把该标记置为当前输入流的位置。返回标记的id。 |
可以在包括构造方法在内的任何地方调用，但标记会占用资源，需要及时释放。 |
public void cancelMark()
|
取消最后创建的标记。每调用一次只取消一个。 |
|
public void mark(int id)
|
把由id指定的标记置为当前输入流的位置。 |
调用前必须保证标记id是合法的，否则结果无法预料。一般在规则匹配开始前或第一种内部动作中调用。
|
|
public String getMarkedText(int mark1, int mark2)
|
返回标记1和标记2之间的字符串。 |
调用前必须保证标记是合法的，否则结果无法预料。可以在规则匹配中或匹配完了后调用，但下一次规则匹配会使原来的标记无效。 |
public String getMarkedText(int mark)
|
返回指定标记到当前位置的字符串。 |
同上。 |
public void setLexState(int lexId)
|
设置词法状态。 |
|
在Rsg的内部使用Unicode的Code
Point作为其处理字符的基本单位（而不是Java中的基本数据类型char），Rsg生成的扫描器也是如此，因此能处理各种字符编码。为了避免使用过程中出现编码问题，扫描器的实现者必须在以下几个环节使用正确的编码。
首先是Rsg输入文件的编码，这可以通过命令行参数设置，否则将使用默认编码GB18030。其二是Rsg输出的扫描器源文件使用的编码，一般来说这是无关紧要的，但要和编译器保持一致，默认编码为GB18030。三是构造扫描器时使用的编码，实际上扫描器的构造函数接受一个java.io.Reader对象来指定字符流，因此只要在创建Reader对象时使用正确的编码就可以了。
扫描器往往作为分析器的一部分而存在，把字符流分离成词法符号流传给分析器。Rsg没有“内置”地支持某种分析器生成工具，但一般来说用户只要在Rsg生成的扫描器基础上进行适当的“包装”就可以适应不同的分析器。此外Rsg提供一个external参数来指定一个外部词法符号常量接口，这个接口一般由分析器生成工具生成。