语法分析生成器 JFlex 使用教程
openkk
13年前
这个项目中使用 JFlex 的目的是为我们的计算器创建一个词法分析器。这个词法 <br /> 分析器，或者叫扫描器，将为我们计算器检查输入，而且确认所有的字符归类是有 <br /> 效的。 <br /> 用于 JFlex 的词法分析说明文件可以分成三个部分。每个部分由 %% 分开。 <p>用户代码段 <br /> %% <br /> 参数设置和声明段 <br /> %% <br /> 词法规则段 </p> <p>用户代码段<br /> 这个段中的所有内容将被拷贝到生成的词法类的类声明之前。在这个段中，常见的<br /> 是 package 和 import 语句。我们的词法说明在这个段中引入(import)了两个类<br /> ，sym 和 java_cup.runtime.*，如下所示： <br /> import java_cup.runtime.*; <br /> import sym; </p> <p>在我们的例子中，sym 类(与处理器一起)由CUP产生。 </p> <p>参数设置和声明段<br /> 这个段含有参数，词法状态，和宏定义。设置参数将包含额外的代码，它们将被包<br /> 括在产生的扫描器类。参必须另开新行，以 % 开头。可以包含的参数很多。在随<br /> JFlex 来的手册中可以得到一个可以包含的参数列表。在我们的词法说明中用到<br /> 的参数如下： <br /> %class Lexer <br /> %line <br /> %column <br /> %cup </p> <p>第一个参数，class Lexer，告诉 JFlex 把生成的类命名为Lexer并把代码写到名<br /> 为Lexer.java的文件。参数 Line打开行计数，使你可以用变量yyline存取输入的<br /> 当前行号。参数column有类似的作用，除了它是通过变量yycolumn存取当前列号。<br /> 最后一个参数，cup，把JFlex设置成一个特殊模式，使它与CUP产生的处理器兼容<br /> ，我们使用的就是。 </p> <p>然后，你可以声明扫描器用到的成员变量和函数。可以加入的代码是Java代码，并<br /> 放在 %{ 和 }%之间。它们将被拷贝到生成的词法类源代码中。在我们的词法说明<br /> 中，声明了两个成员函数。这些函数创建java_cup.runtime.Symbol对象。第一个<br /> 仅仅记录当前记号的位置信息。第二个还包含了记号的值。以下是到这个声明的连<br /> 接。 </p> <p>Declarations </p> <p>这个段的最后是宏定义。宏用作正则表达式的缩写。一个宏定义包含一个宏标识符<br /> ，其后为一个=，然后是宏要代表的正则表达式。如下是一个我们的词法说明中用<br /> 到的宏定义的连接。还有一个连接包含了一个列表，列出了创建正则表达式可用的<br /> 东西，及每一项的含义。 </p> <p>Macro Declarations </p> <p>可用于创建正则表达式的列表 </p> <p>词法规则段<br /> 词法分析说明的最后一段包含正则表达式和当扫描器匹配了相关的正则表达式后所<br /> 要执行的动作。扫描器会激活具有最大匹配的表达式。所以如果存在两个正则表达<br /> 式"to"和"too"，扫描器会匹配"too"，因为它是最长的。如果两个正则表达式完全<br /> 相同，具有相同的长度，那么扫描器将匹配最先列在说明中的表达式。假设扫描器<br /> 读进了字符串"to"，它试图在下面所列的正则表达式中寻找一个来匹配所读入的。<br /> 第二个正则表达式是可选的，因为它包含的字符串类是可以匹配字符串"to"的。但<br /> 扫描器会选择列表中的第一个正则表达式，因为它列在最前面。 <br /> "to" <br /> [a-z]* </p> <p>每个正则表达式可以附带动作，这样当扫描器匹配了正则表达式后就可以激活它的<br /> 动作。每个正则表达式的动作就是你可以写的Java代码片段。你想要的动作可以是<br /> 打印出一些东西，或是返回扫描器发现的标识符给处理器。用于打印出扫描器发现<br /> 的标识符并且返回给处理器的示例代码如下所示： </p> <p>"+" { System.out.print("+"); return symbol(sym.PLUS); } <br /> "-" { System.out.print("-"); return symbol(sym.MINUS); } <br /> "*" { System.out.print("*"); return symbol(sym.TIMES); } <br /> "/" { System.out.print("/"); return symbol(sym.DIVIDE); } </p> <p>JFlex 允许程序员定义特殊的词法状态(lexical states)用作开始条件来细化说明<br /> 。YYINITIAL 是一个预定义的词法状态，是词法分析器初始扫描输入的状态。它是<br /> 我们将用的唯一状态。所以，我们所有的正则表达式都将从这个词法状态开始识别<br /> 。然而，可以定义其它这样的状态，本质上说将建立一个状态机的新的分支的开始<br /> 。在下面的例子中，从 YYINITIAL 通过一个变换到达词法状态。在这个状态段定<br /> 义的正则表达式将只能在这个分支中被识别。 </p> <p>{ <br /> \" {string.setLength(0); yybegin(STRING); } <br /> "=" { return symbol(sym.EQ); } <br /> "==" { return symbol(sym.EQEQ);} <br /> "+" {return symbol(sym.PLUS); } </p> <p>{ <br /> \" { yybegin(YYINITIAL); <br /> return symbol(sym.STRINGLITERAL, string.toString());} <br /> [^\n\r"\]+ {string.append(yytext());} <br /> } </p> <p>在如上的代码中，扫描器将从状态 YYINITIAL 开始。当它匹配了正则表达式\"，<br /> 也就是找到了一个双引号，它将把状态转换到 STRING 状态。那么现在能够匹配的<br /> 正则表达式只有这个状态下列出的状态。所以，扫描器将呆在这个状态中直到它匹<br /> 配了另一个双引号 - 在这儿它将再次回到 YYINITIAL 状态。再说一次，在我们的<br /> 计算器中从不使用这样的初始条件，除了最早的YYINITIAL状态。下面是我们使用<br /> 的词法规则的一个连接： </p> <p>到词法规则的连接 </p> <p>------------------------------------------------------------------------</p> <p>到 JFlex 文件 lcalc.flex 的连接。它是我们的计算器的词法说明文件。它里面<br /> 有很多的注释解释为什么。它可以被拷贝，并且本文提供的CUP文件和Main文件都<br /> 可以被拷贝，这样你就可以运行示例项目。它们包括如何准备每个文件和运行计算<br /> 器的指南。做这些需要Jdk，JFlex，和CUP，它们可以从本文中所列的 Web 站点中<br /> 免费下载。 </p> <p>更多的有关JFlex的信息请参考JFlex手册，从本文中所列的 Web 站点免费下载<br /> JFlex时就可以得到。 </p> <p>用 CUP<br /> 在这个项目中CUP的目的是为我们的计算器建立一个句法的分析器。这个句法的分<br /> 析器，或叫处理器，将为我们的计算器检查输入，并且确保句法的正确性。 <br /> 这就是说根据我们的语法说明把输入中的语句安排为一个有效的顺序。 <br /> 一个CUP文件的说明语法分为 4个部分： </p> <p>预先声明 <br /> 终结符和非终结符的说明 <br /> 终结符的优先级和结合性 <br /> 文法 <br /> 预先声明<br /> 这一段提供预先和各种各样的声明来指定如何产生处理器，并提供一部分运行时的<br /> 代码。这个段是可选的，并不需要被包括在一个 CUP 说明文件中。对于我们的计<br /> 算器，我们在这个段中将有三个项。 <br /> 第一项是一个输入声明。我们将输入类 java_cup.runtime.* 。 <br /> import java_cup.runtime.* ; </p> <p>我们加的第二项是处理器代码。这个处理器代码将被直接放在产生的处理器的类定<br /> 义中。它以 parser code {: 开始，以 :} 结束，所有的代码都写在中间。在处理<br /> 器代码中我们将改变两种方法。我们将改变 report_error 和 <br /> report_fatal_error 方法。我们将修改这些方法，使得如果在输入中发生一个语<br /> 法错误或一个致命错误，将打印出一个错误消息，其中包括输入中发生错误的行号<br /> ，列号。这样的在错误消息中的额外信息在定位输入中的错误是非常有用。 </p> <p>到处理器代码的连接 </p> <p>我们在这个段加的最后一项指出处理器该如何从扫描器那里请求下一个标识符，格<br /> 式是 scan with {: ... :}。我们将用这个来告诉处理器去调用 JFlex 创建的扫<br /> 描器。 </p> <p>scan with {: return lexer.yylex(); :}; </p> <p>终结符和非终结符的声明<br /> 这个段包括符号表，及负责命名的声明，并为每个终结符和非终结符提供类型。这<br /> 个段在 CUP 说明中是需要的。终结符声明的语法是：terminal classname name1,<br /> name2, ...; 。Classname 是对象的类型，如 整数(Integer)。如果不写 <br /> classname，终结符将无内容为词法器来传递给处理器。在classname 后面所列的<br /> 终结符的名字是你想要声明为这种类型的，例如下面的： <br /> terminal PLUS, MINUS, TIMES, DIVIDE, SEMI; <br /> terminal Integer NUMBER; </p> <p>注意，这里只有 NUMBER 有一个伴随的 classname。在我们的例子里，它是有值的<br /> 唯一终结符。例如，当词法器识别了一个 PLUS，它把相关的代码传给处理器；但<br /> 是当它识别了一个 NUMBER，它不仅要传NUMBER 相关的代码，还有它的包含在类型<br /> 类中的值(Integer)。 </p> <p>非终结符以同样的方式声明。唯一的区别是声明的开头反映了它是一个非终结符，<br /> 而不是终结符，如下所示： </p> <p>non terminal expr_list, expr_part； <br /> non terminal Integer expr； </p> <p>终结符的优先级和结合性<br /> 这个段指明终结符的优先级和结合性，它是可选的段，不必须包括。这个段在处理<br /> 二义的终结符时会用上。如果不用这个段，你可以调整语法的结构使它没有二义。<br /> 例如，TIMES 应该有比 PLUS 高的优先级。当处理器遇到一个语句比如 5+4*3，它<br /> 不知道这个表达式应该按照 5+(4*3) 计算还是按照(5+4)*3 计算。为了用这个段<br /> 消除这种二义性，你需要如下来声明优先级。最高的优先级从列表的底部开始，向<br /> 上递减。left 表示在那个优先级中终结符的结合性是从左到右。 <br /> precedence left PLUS，MINUS； <br /> precedence left TIMES，DIVIDE； </p> <p>要调整语法的结构消除二义性，你需要如下创建一个结构。这个结构能够消除二义<br /> 性是因为 TIMES 在语法中比PLUS更靠下。这将导致在你向上回溯时 TIMES在PLUS<br /> 前被应用。 </p> <p>语法结构的例子 </p> <p>文法<br /> 在说明的语法中的最后一段，包含处理器的文法。在文法中的每一个产生式有一个<br /> 非终结符在左边，然后是 ::=，其后是零个或多个动作，终结符，非终结符等，再<br /> 后面是一个分号。在等号右边的每一个符号可以标有一个名字，它能用于在处理树<br /> 上包含内容(即数值)。标号名由符号名后面跟一个冒号给出，如下面所示的e1，<br /> e2定义为expr的标号。等号左边的自动赋给标号 RESULT。使用标号RESULT 的一个<br /> 例子将出现在本段的后面。 <br /> expr::=expr:e1 PLUS expr:e2 </p> <p>标号的名字必须在产生式中保持唯一。如果同一个非终结符有几个产生式，它们可<br /> 以在一起声明，用 |隔开。在最后一个产生式的末尾需要一个分号，如下所示： </p> <p><br /> expr::=expr PLUS expr <br /> | expr MINUS expr <br /> ; </p> <p>动作定义也可以写在产生式中。动作就是 Java 代码，当产生式被识别时将被执行<br /> 。动作定义放在一对定界符{:和:}之间。下面是一个使用这些选项的语法片断的例<br /> 子。下面还有连接指到一个名为ycalc.cup 的文件,它包括用于 CUP语法说明，可<br /> 以研究以下它的语法。 </p> <p>expr ::= factor:f PLUS expr:e <br /> {: RESULT = new Integer(f.intvalue() + e.intvalue()); :} <br /> | <br /> factor:f MINUS expr:e <br /> {: RESULT = new Integer(f.intvalue() - e.intvalue()); :} <br /> | <br /> factor:f <br /> {: RESULT = new Integer(f.intvalue()); :} <br /> ; </p> <p>------------------------------------------------------------------------</p> <p>到CUP文件的连接 ycalc.cup。它是我们的计算器的语法说明文件。它里面有很多<br /> 的注释解释为什么。它可以被拷贝，并且本文提供的CUP文件和Main文件都可以被<br /> 拷贝，这样你就可以运行示例项目。它们包括如何准备每个文件和运行计算器的指<br /> 南。做这些需要Jdk，JFlex，和CUP，它们可以从本文中所列的 Web 站点中免费下<br /> 载。 </p> <p>更多的有关JFlex的信息请参考JFlex手册，从本文中所列的 Web 站点免费下载<br /> JFlex时就可以得到。 </p> <p>------------------------------------------------------------------------</p> <p>我们的计算器的主体<br /> 有不止一种方法来写我们项目的主体。有一种是在程序运行时要求用户的输入。另<br /> 外一种是在启动程序时要求提供它一个输入文件的名字。这里所描述的主体是采用<br /> 以上的后一种方法来获得输入。我们所做的第一件事是引入我们将用到的三个类。<br /> 第一个类是为了我们的处理器，第二个是类java_cup.runtime.Symbol ，最后一个<br /> 是类 java.io.* 。然后我们声明类 main。我们将在它里面调用处理器来开始对输<br /> 入文件的语法分析。而处理器在每需要输入文件中的下一个标识符时，它就调用扫<br /> 描器对输入进行词法分析。类 Main 包含两项。它首先把变量 do_debug_parse 设<br /> 置为 false。然后我们定义了方法 main。我们传给 main 一个字符串数组，它包<br /> 含程序启动时从命令行上传来的参数。所以在我们的例子中，字符串数组的第一个<br /> 元素是我们启动程序时输入的文本文件名。然后这个方法就进入一个 try 段，它<br /> 将实际调用处理器。try 段的意思是不管段里试图做什么，如果有任何错误，程序<br /> 将退出这个段。在 try 段中的第一行创建一个新的处理器对象。这个处理器对象<br /> 创建一个新的词法器对象。这个新的词法器对象将使用创建时传给main的字符串作<br /> 为它的输入。try 段的第二行将启动处理器。代码如下所示： <br /> try { <br /> parser p=new parser(new Lexer(new FileReader(argv[0]))); <br /> Object result=p.parse().value; <br /> } </p> <p>在 try 段的后面是 catch 段。catch 段的目的是清除 try 段中的发生的错误。<br /> catch 段将捕获导致我们被踢出try 段的例外，在程序退出之前做必要的清除工作<br /> 。在我们的catch 段中没有做任何事情。在catch 段的后面是方法 finally。这个<br /> 方法关闭所有的东西。我们在这个方法里也不做任何事情。catch 段和 finally <br /> 方法的代码如下所示： </p> <p>catch (Exception e) { <br /> /* do cleanup here -- possibly rethrow e */ <br /> } finally { <br /> /* do close out here */ <br /> } <br /> } </p> <p>这样就结束了方法main和类Main 的内容。现在我们就创建了一个简单的计算器，<br /> 使用 JFlex 作为我们的词法分析器，CUP 作为我们的语法分析器。 </p> <p>------------------------------------------------------------------------</p> <p>到 Java 文件的连接 Main.java。它是我们的计算器的主体。它里面有很多的注释<br /> 解释为什么。它可以被拷贝，并且本文提供的CUP文件和Main文件都可以被拷贝，<br /> 这样你就可以运行示例项目。它们包括如何准备每个文件和运行计算器的指南。做<br /> 这些需要Jdk，JFlex，和CUP，它们可以从本文中所列的 Web 站点中免费下载。 </p> <p><br /> 更多的有关JFlex的信息请参考JFlex手册，从本文中所列的 Web 站点免费下载<br /> JFlex时就可以得到。 </p> <p>------------------------------------------------------------------------</p> <p>编译计算器程序<br /> 为了为运行计算器准备文件，你首先需要在词法说明文件 lcalc.flex 上使用 <br /> JFlex。这将产生文件Lexer.java 。下一步是建立 CUP 文件 ycalc.cup。然后你<br /> 编译 JFlex创建的Lexer.java文件。最后编译 Main.java 文件来结束整个过程。<br /> 做上述事情，你要输入如下的命令行： <br /> >jflex lcalc.flex <br /> >java java_cup.Main < ycalc.cup <br /> >javac Lexer.java <br /> >javac Main.java </p> <p>然后为了运行计算器，你需要输入如下命令行。文件 test.txt 是用于计算器的输<br /> 入文件，可以被扫描和处理。 </p> <p>>java Main test.txt </p> <p>------------------------------------------------------------------------</p> <p>输入/输出的示例<br /> 一个示例输入文件可以是如下所示: <br /> 2+4; <br /> 5*(6-3)+1; <br /> 6/3*5+20; <br /> 4*76/31; </p> <p>如此这般。其对应的输出应是如下： </p> <p>2 + 4 = 6 <br /> 5 * ( 6 - 3 ) + 1 = 16 <br /> 6 / 3 * 5 + 20 = 30 <br /> 4 * 76 / 31 = 9 </p>