基于JAVA实现的Tiger编译器【100012929】

# 基于JAVA实现的Tiger编译器 # 一、项目要求及完成情况 - 正确的词法/语法分析，给出对应的文法文件 - 输出正确的抽象语法树（testcases中50个测试文件，testcase-result中对应的抽象语法树） - 错误处理功能 - 提示错误类型（词法错误、语法错误、语义错误等）、出错位置等（词法错误，语法错误ANTLR默认行为,部分语义错误：变量作用域及基本类型检查） - 错误修复(ANTLR默认行为 single-token insertion and single-token deletion) - 发挥想象力，使编译器尽善尽美（实现了变量作用域检查和基本类型检查） - Project文档 - 使用语法（文法类型，有无改动语法、如何改动等），错误处理说明等（对实现的变量作用变量作用域检查和基本类型检查的错误处理代码进行了介绍） - 对本项目语法的使用工具的体会（ANTLR简述部分） # 二、项目总览 使用ANTLR工具，为Tiger构造一个编译器前端，将输入的Tigger语言转化为抽象语法树，实现了变量作用域检查和简单的Type Checking。 # 三、ANTLR简述 [ANTLR](www.antlr.org)(ANother Tool for language Recognition)，作者Terence Parr(University of San Francisco)。 ANTLR是一个可以接受含有语法描述的语言描述符并且生成程序能够识别这些语言所产生的句子。作为一个翻译程序的 一部分，你可以给你的语法附上简单的操作符和行为并且告诉ANTLR如何构造AST并且如何输出它们。ANTLR知道如何使用Java，C++，C#或者Python来生成它们。 注意到词法错误和语法错误ANTLR有默认的处理行为。 > Here is how ANTLR uses those ideas together in a nutshell: parsers perform single-token insertion and single-token deletion upon mismatched token errors if possible. If not, parsers gobble up tokens until they find a token that could reasonably follow the current rule and then return, continuing as if nothing had happened. >  如上图所示，把源文件转化成AST，需要一个Lexer和Parser。Lexer把源文件读入，分成一个个token。然后Parser读入Lexer产生的token生成AST。在ANTLR提供了Lisenter和Visitor两种方式来遍历抽象语法树。本项目利用这些接口来实现变量声明检查。和基本的类型检查。  # 四、AST的生成 ANTLR是一个比较成熟的工具，[The Definitive ANTLR 4 Reference](http://pragprog.com/book/tpantlr2/the-definitive-antlr-4-reference) 详细介绍了工具的使用说明。为了生成AST，需要完成grammer定义文件Tiger.g4 下面定义的语法，基本与[官方语法文档](https://www.lrde.epita.fr/~akim/ccmp/tiger.html)指定的语法相同。 为了简化之后的Type Checking，把Ojbect相关的new class等语法去掉了。 ```sh java org.antlr.v4.Tool Tiger.g4 ``` 然后会产生TigerLexer.java, TigerParser.java, Tiger.tokens , TiegerLexder.tokens, TigerListener.java, TigerBaseLisetener.java。 其中TigerLexer.java是ANTLR根据g4为我生成的Lexer，TigerParser.java是对应的Parser，TigerListener.java是前面提到的Listener方式的抽象语法树的接口，TigerBaseListener.java是这个接口的一个基本实现。我们的实现通过继承TigerBaseListener来重载中间的放来实现期望的行为。 ```sh java org.antlr.v4.runtime.misc.TestRig Tiger program -tree test.in # 输出文本信息 java org.antlr.v4.runtime.misc.TestRig Tiger program -gui test.in # 生成图形 ``` ## 4.1 TigerLexer.java节选 ```java // Generated from Tiger.g4 by ANTLR 4.2.1 import org.antlr.v4.runtime.Lexer; import org.antlr.v4.runtime.CharStream; import org.antlr.v4.runtime.Token; import org.antlr.v4.runtime.TokenStream; import org.antlr.v4.runtime.*; import org.antlr.v4.runtime.atn.*; import org.antlr.v4.runtime.dfa.DFA; import org.antlr.v4.runtime.misc.*; @SuppressWarnings({"all", "warnings", "unchecked", "unused", "cast"}) public class TigerLexer extends Lexer { protected static final DFA[] _decisionToDFA; protected static final PredictionContextCache _sharedContextCache = new PredictionContextCache(); public static final int T__39=1, T__38=2, T__37=3, T__36=4, T__35=5, T__34=6, T__33=7, T__32=8, T__31=9, T__30=10, T__29=11, T__28=12, T__27=13, T__26=14, T__25=15, T__24=16, T__23=17, T__22=18, T__21=19, T__20=20, T__19=21, T__18=22, T__17=23, T__16=24, T__15=25, T__14=26, T__13=27, T__12=28, T__11=29, T__10=30, T__9=31, T__8=32, T__7=33, T__6=34, T__5=35, T__4=36, T__3=37, T__2=38, T__1=39, T__0=40, INTEGER=41, STRING=42, ID=43, COMMENT=44, LINE_COMMENT=45, WS=46; public static String[] modeNames = { "DEFAULT_MODE" }; ... ``` ## 4.2 TigerParser.java节选 ```java // Generated from Tiger.g4 by ANTLR 4.2.1 import org.antlr.v4.runtime.atn.*; import org.antlr.v4.runtime.dfa.DFA; import org.antlr.v4.runtime.*; import org.antlr.v4.runtime.misc.*; import org.antlr.v4.runtime.tree.*; import java.util.List; import java.util.Iterator; import java.util.ArrayList; @SuppressWarnings({"all", "warnings", "unchecked", "unused", "cast"}) public class TigerParser extends Parser { protected static final DFA[] _decisionToDFA; protected static final PredictionContextCache _sharedContextCache = new PredictionContextCache(); public static final int T__39=1, T__38=2, T__37=3, T__36=4, T__35=5, T__34=6, T__33=7, T__32=8, T__31=9, T__30=10, T__29=11, T__28=12, T__27=13, T__26=14, T__25=15, T__24=16, T__23=17, T__22=18, T__21=19, T__20=20, T__19=21, T__18=22, T__17=23, T__16=24, T__15=25, T__14=26, T__13=27, T__12=28, T__11=29, T__10=30, T__9=31, T__8=32, T__7=33, T__6=34, T__5=35, T__4=36, T__3=37, T__2=38, T__1=39, T__0=40, INTEGER=41, STRING=42, ID=43, COMMENT=44, LINE_COMMENT=45, WS=46; public static final String[] tokenNames = { "<INVALID>", "']'", "'&'", "'in'", "'of'", "','", "'['", "'-'", "'*'", "'while'", "'('", "':'", "'<'", "'<='", "'var'", "'array'", "'nil'", "'to'", "'{'", "'break'", "'let'", "'else'", "'}'", "'do'", "')'", "'function'", "'.'", "'+'", "'for'", "'<>'", "'='", "';'", "'if '", "'>'", "'type'", "':='", "'then'", "'/'", "'>='", "'|'", "'end'", "INTEGER", "STRING", "ID", "COMMENT", "LINE_COMMENT", "WS" }; ... ``` ## 4.3 Tiger.g4语法文件 ``` /** May,28 2014 author: whimsycwd compiler project */ grammar Tiger; program : exp | decs ; exp : 'nil' #Nil | INTEGER #Integer | STRING #String | type_id '[' exp ']' 'of' exp #Array | type_id '{' ( ID '=' exp (',' ID '=' exp )* )? '}' #Record //| 'new' type_id #New | lvalue #LeftValue | ID '(' ( exp (',' exp)*)? ')' #Call | '-' exp #UnaryMinus | exp ('*' | '/') exp #Mul | exp ('+' | '-') exp #Add | exp ('<>' | '=' | '>=' | '<=' | '>' | '<') exp #Cmp | exp ('&' | '|') exp #Logical | '(' exps ')' #ParenExprs | lvalue ':=' exp #Assign | 'if ' exp 'then' exp ('else' exp)? #IfStmt | 'while' exp