编译原理实习JavaCC-副本.ppt

JavaCC基础,编译原理实习,西北农林科技大学本科实习材料,学 期：2014年春季 时 间：2019年6月6日星期四,信息工程学院软件工程系 主讲：赵建邦,JavaCC基础,1 JavaCC概述 JavaCC源文件（.jjt）的结构 2 JavaCC所生成的类 3 词法规则注意事项 4 语法规则注意事项 5 添加语义规则 6 四元式示例(switch-case和函数调用),1 JavaCC概述,JavaCC是一个词法分析器和语法分析器的生成器,return语句,int,main,1 JavaCC概述,JavaCC 本身并不是一个词法分析器或是语法分析器，而是一个分析程序生成器。它可以根据输入的语言规范输出一个词法和语法分析器。 输入： (满足JavaCC格式: .jjt文件) 输出： ( .java 文件),1 JavaCC概述,生成好的词法、语法分析器带有一个main( )方法，可以接收键盘输入的句子（默认）或者写在文件里的句子。 新建一个jjt文件的步骤： 1.建立java项目 2.建立一个语法分析包（例如：parser） 3.“新建”-“其它”-“JavaCC Template File” 4.创建一个“.jjt”文件,包名,jjt 文件名,1.1 jjt文件的结构,/*第一部分*/ 语法分析器的属性设置 /*第二部分*/ 语法分析器的类声明 /*第三部分*/ 词法规则声明 /*第四部分*/ 语法规则实现,8,1.2 声明一个词法分析器,SKIP : “ “ SKIP : “n“ | “r“ | “rn“ TOKEN : TOKEN : TOKEN : | “.“ | “.“ | “.“ TOKEN : ,在词法声明部分，以#开头的token只是在词法分析时使用，不能作为语法分析的输入，也就是说，它相对词法分析是局部的,举例,9,1.2 声明一个词法分析器,Javacc中的语法表示吸收了UNIX中正规文法的一些记号 l ： 其中的内容是可选的 +：前面的内容出现一次或多次 *: 前面的内容出现0次或多次 ?： 前面的内容出现0次或一次 |： 前面或后面 ()：改变运算的优先级，把其中的内容作为一个整体,1.2 声明一个词法分析器,jjt文件自动生成的对标识符的定义：,1.2 声明一个词法分析器,自定义词法规则：,手动添加关键字规则， 确保关键字先于标识符定义,如果被分析的源程序中有不符合语言规范的地方，词法和语法分析器会将错误输出在Eclipse控制台。,运行程序,2 JavaCC所生成的类,jj文件和jjt文件都可以被JavaCC编译，生成词法和语法分析器。,.jj文件的语法声明部分,AAA是将要生成的语法分析器类名， 可以由用户设定。,2 JavaCC所生成的类,jj文件和jjt文件都可以被JavaCC编译，生成词法和语法分析器。,AAA是将要生成的语法分析器类名， 可以由用户设定。,.jjt文件的语法声明部分,2 JavaCC所生成的类,Token.java & AAATokenMgrError:单词 & 词法错误,2 JavaCC所生成的类,Token.java & AAATokenMgrError:单词 & 词法错误,2 JavaCC所生成的类,SimpleCharStream.java:词法分析器的输入流,可以接受InputStream类型和Reader 类型的输入流。,2 JavaCC所生成的类,AAAConstants.java:接口，单词常量,.jjt文件的单词声明（部分）,2 JavaCC所生成的类,AAAConstants.java:接口，单词常量,.jjt文件的单词声明（部分）,tokenImage5,2 JavaCC所生成的类,AAATokenManager.java:词法分析器,2 JavaCC所生成的类,AAATokenManager.java:词法分析器 重要的成员变量和方法： /*词法分析器所使用的输入流*/ static protected SimpleCharStream input_stream; /*词法分析器的构造方法*/ public AAATokenManager(SimpleCharStream stream) /*浏览下一个单词*/ public static Token getNextToken(),实习要求1：可以通过上面几个类和对应的方法得到 MiniC程序的单词序列。,2 JavaCC所生成的类,AAA.java & ParseException:语法分析器 & 语法异常类,2 JavaCC所生成的类,AAA.java & ParseException:语法分析器 & 语法异常类 AAA.java的方法来自于： /*第一部分*/ 写在AAA类声明部分的方法 /*第二部分*/ 写在AAA语法结构部分的方法 /*第三部分*/ JavaCC添加的方法(部分)： AAA (InputStream) AAA (Reader) AAA (AAATokenManager) Token getNextToken() Token jj_consume_token(int),.jjt文件的方法声明（部分）,2 JavaCC所生成的类(jjt),Node.java & SimpleNode.java:语法树节点的接口和实现,/*AAA的start()会返回 语法树根节点的引用*/ SimpleNode n = AAA.Start(); /* SimpleNode的dump()可以输出语法树*/ n.dump(“);,实习要求2：可以修改dump( )方法将语法树输出到文本。,TOKEN: | “.“ | “.“ TOKEN:,在词法声明部分，以#开头的token只是在词法分析时使用，不能作为语法分析的输入，也就是说，它相对词法分析是局部的,3 词法规则注意事项（举例）,JavaCC中的语法表示吸收了UNIX中正规文法的一些记号： l ： 其中的内容是可选的 + ：前面的内容出现一次或多次 * : 前面的内容出现0次或多次 ? ：前面的内容出现0次或一次 | ： 前面或后面 ()： 改变运算的优先级，把其中的内容作为一个整体,TOKEN: /* KEY */ | | ,3 词法规则注意事项（举例）,TOKEN: /* IDENTIFIERS */ ( |)* | | ,具有包含关系的词法定义，必须防止失效情况： KEY的声明必须在IDENTIFIER的声明之前,4 语法规则注意事项,语法部分决定了编译器的功能是否强大。 文法中的每个非终结符对应一个函数，函数调用表示非终结符之间的组成关系。 JavaCC默认生成的“AAA.jjt”文件是一个简单的表达式分析器。 能够表达带括号的五则（+、-、*、/、%）混合运算； 优先级： （） *、/、% +、- 例如：“a+b*3;”、“a*(b-d % 5);”是合法的句子。,SimpleNode Start() : Expression() “;“ return jjtThis; ,4 语法规则注意事项,Start Expression ;,void UnaryExpression() : “(“ Expression() “)“ | Identifier() | Integer() ,Unary ( Expression ) | id | integer,4 语法规则注意事项,“AAA.jjt”的文法决定了该语法分析器无法识别如下语句： “a+ -b;”、“a+;”、“-a + +5;”等。 修改文法： 可以识别“a+ -b;”、“-a - -5;”等。 但仍然不能识别自增自减运算。,void UnaryExpression() : “(“ Expression() “)“ | (“-“ | “+“ )? ( Identifier() | Integer() ) ,Type + | - | Unary ( Expression ) | Type ( id| integer),4 语法规则注意事项,在语法分析阶段需要注意的主要问题是： 明确编译器的主要功能。 根据C语言的语法和实习要求提取MiniC的文法。 程序 （函数）+ 函数 类型 函数名 （参数列表） 函数体 表达式 常量 整型常量 | 字符常量 | 标识符 | 整型常量,此处的简易文法仅作参考！ 部分产生式需要修改才能使用。,4 语法规则注意事项,在语法分析阶段，可能会遇到冲突：(代码左侧有黄色小三角),/*原因： 二义性或者文法非LL(1) */ if E if E S e S,if E if E S e S,if E if E S e S,4 语法规则注意事项,个别冲突可以借助LOOKAHEAD(K)关键字解决,/*语法分析器执行完if-S之 后先找“else”，找到则 匹配最近的if，否则执行 后面的语句 */ if E if E S e S,if E if E S e S,if E if E S e S,5 添加语义规则,JavaCC采用自顶向下语法分析，可以在文法的任意位置添加语义子程序。 只需要在需要添加语义子程序的地方使用花括号即可添加。,void MultiplicativeExpression() : / 乘除表达式 UnaryExpression() ( ( “*“ / op是Token对象 | “/“ ) UnaryExpression() )* ,注意：在1处添加的语义子程序往往用来实例化变量，这些变量在语法分析过程中被使用；,只有语法结构的方法,语义子程序写在花括号里面,String MultiplicativeExpression() : / 乘除表达式，注意返回值类型 String first; String middle; String newTemp; Token op; first = UnaryExpression() / first是返回的字符串 newTemp = first; ( ( op = “*“ / op是Token对象 | op = “/“ | op = “%“ ) middle = UnaryExpression() / middle是返回的字符串 newTemp = variableNameGenerator.genVariableName(); QTInfo qt = new QTInfo(op.image, first, middle, newTemp); qtTable.addQTInfo(qt); )* return newTemp; /返回临时变量字符串 “T1”，“T2” ,对于之前的方法添加了语义子程序。,6 四元式示例,JavaCC能够根据jjt文件得到语法分析所用的类，但是为了编写一个合格的编译器，开发者需要额外添加一些类，以完成四元式的翻译、符号表的存储、差错处理等。 建议将jjt的类放置到一个包内，开发者新建的类放到另一个包内。,parser包,GUI包,用户类包,6 四元式示例（switch-case）,void main() switch(ts) case 0: a =23; break; case 1: switch(lts) case a: a1 = 6; break; default: a2 = 9; case 3: d = 34; default: e = 34; ,1: (case, ts, 0, 3 ) 2: (J, _, _, 5 ) 3: (=, 23, _, a ) 4: (Jbr, _, _, 16 ) 5: (case, ts, 1, 7 ) 6: (J, _, _, 12 ) 7: (case, lts, a, 9 ) 8: (J, _, _, 11 ) 9: (=, 6, _, a1 ) 10: (Jbr, _, _, 12 ) 11: (=, 9, _, a2 ) 12: (case, ts, 3, 14 ) 13: (J, _, _, 15 ) 14: (=, 34, _, d ) 15: (=, 34, _, e ),6 四元式示例（函数调用）,void f(double d) double x = 3.0; return; int f(int d) d = d*d; return d; double f(int x, double b) return b; void main() double c,b,d5; int x,y,z3; c = f(x,b) + z1+; ,1: (=, 3.0, _, x )