基于ANTLR实现的Tiger编译器前端

Sunshine

发布日期: 2021-01-05 12:58:16 浏览量: 112
评分:
star star star star star star star star star star_border
*转载请注明来自write-bug.com

一、项目要求及完成情况

  • 正确的词法/语法分析,给出对应的文法文件2分 √ (Tiger.g4)

    • 输出正确的抽象语法树5分 √ (testcases中50个测试文件,testcase-result中对应的抽象语法树)
  • 错误处理功能

    • 提示错误类型(词法错误、语法错误、语义错误等)、出错位置等 5分 √ (词法错误,语法错误ANTLR默认行为,部分语义错误:变量作用域及基本类型检查
    • 错误修复 3分 √ (ANTLR默认行为 single-token insertion and single-token deletion)
  • 发挥想象力,使编译器尽善尽美 5分 √ (实现了变量作用域检查和基本类型检查)

  • Project文档

    • 使用语法(文法类型,有无改动语法、如何改动等),错误处理说明等 5分 √ (对实现的变量作用变量作用域检查和基本类型检查的错误处理代码进行了介绍
    • 对本项目语法的使用工具的体会 5分 √ (ANTLR简述部分)

二、项目总览

使用ANTLR工具,为Tiger构造一个编译器前端,将输入的Tigger语言转化为抽象语法树,实现了变量作用域检查和简单的Type Checking。

三、ANTLR简述

ANTLR(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 详细介绍了工具的使用说明。为了生成AST,需要完成grammer定义文件Tiger.g4 下面定义的语法,基本与官方语法文档指定的语法相同。 为了简化之后的Type Checking,把Ojbect相关的new class等语法去掉了。

  1. 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来重载中间的放来实现期望的行为。

  1. java org.antlr.v4.runtime.misc.TestRig Tiger program -tree test.in # 输出文本信息
  2. java org.antlr.v4.runtime.misc.TestRig Tiger program -gui test.in # 生成图形

4.1 TigerLexer.java节选

  1. 1 // Generated from Tiger.g4 by ANTLR 4.2.1
  2. 2 import org.antlr.v4.runtime.Lexer;
  3. 3 import org.antlr.v4.runtime.CharStream;
  4. 4 import org.antlr.v4.runtime.Token;
  5. 5 import org.antlr.v4.runtime.TokenStream;
  6. 6 import org.antlr.v4.runtime.*;
  7. 7 import org.antlr.v4.runtime.atn.*;
  8. 8 import org.antlr.v4.runtime.dfa.DFA;
  9. 9 import org.antlr.v4.runtime.misc.*;
  10. 10
  11. 11 @SuppressWarnings({"all", "warnings", "unchecked", "unused", "cast"})
  12. 12 public class TigerLexer extends Lexer {
  13. 13 protected static final DFA[] _decisionToDFA;
  14. 14 protected static final PredictionContextCache _sharedContextCache =
  15. 15 new PredictionContextCache();
  16. 16 public static final int
  17. 17 T__39=1, T__38=2, T__37=3, T__36=4, T__35=5, T__34=6, T__33=7, T__32=8,
  18. 18 T__31=9, T__30=10, T__29=11, T__28=12, T__27=13, T__26=14, T__25=15, T__24=16,
  19. 19 T__23=17, T__22=18, T__21=19, T__20=20, T__19=21, T__18=22, T__17=23,
  20. 20 T__16=24, T__15=25, T__14=26, T__13=27, T__12=28, T__11=29, T__10=30,
  21. 21 T__9=31, T__8=32, T__7=33, T__6=34, T__5=35, T__4=36, T__3=37, T__2=38,
  22. 22 T__1=39, T__0=40, INTEGER=41, STRING=42, ID=43, COMMENT=44, LINE_COMMENT=45,
  23. 23 WS=46;
  24. 24 public static String[] modeNames = {
  25. 25 "DEFAULT_MODE"
  26. 26 };
  27. etc ...

4.2 TigerParser.java节选

  1. 1 // Generated from Tiger.g4 by ANTLR 4.2.1
  2. 2 import org.antlr.v4.runtime.atn.*;
  3. 3 import org.antlr.v4.runtime.dfa.DFA;
  4. 4 import org.antlr.v4.runtime.*;
  5. 5 import org.antlr.v4.runtime.misc.*;
  6. 6 import org.antlr.v4.runtime.tree.*;
  7. 7 import java.util.List;
  8. 8 import java.util.Iterator;
  9. 9 import java.util.ArrayList;
  10. 10
  11. 11 @SuppressWarnings({"all", "warnings", "unchecked", "unused", "cast"})
  12. 12 public class TigerParser extends Parser {
  13. 13 protected static final DFA[] _decisionToDFA;
  14. 14 protected static final PredictionContextCache _sharedContextCache =
  15. 15 new PredictionContextCache();
  16. 16 public static final int
  17. 17 T__39=1, T__38=2, T__37=3, T__36=4, T__35=5, T__34=6, T__33=7, T__32=8,
  18. 18 T__31=9, T__30=10, T__29=11, T__28=12, T__27=13, T__26=14, T__25=15, T__24=16,
  19. 19 T__23=17, T__22=18, T__21=19, T__20=20, T__19=21, T__18=22, T__17=23,
  20. 20 T__16=24, T__15=25, T__14=26, T__13=27, T__12=28, T__11=29, T__10=30,
  21. 21 T__9=31, T__8=32, T__7=33, T__6=34, T__5=35, T__4=36, T__3=37, T__2=38,
  22. 22 T__1=39, T__0=40, INTEGER=41, STRING=42, ID=43, COMMENT=44, LINE_COMMENT=45,
  23. 23 WS=46;
  24. 24 public static final String[] tokenNames = {
  25. 25 "<INVALID>", "']'", "'&'", "'in'", "'of'", "','", "'['", "'-'", "'*'",
  26. 26 "'while'", "'('", "':'", "'<'", "'<='", "'var'", "'array'", "'nil'", "'to'",
  27. 27 "'{'", "'break'", "'let'", "'else'", "'}'", "'do'", "')'", "'function'",
  28. 28 "'.'", "'+'", "'for'", "'<>'", "'='", "';'", "'if '", "'>'", "'type'",
  29. 29 "':='", "'then'", "'/'", "'>='", "'|'", "'end'", "INTEGER", "STRING",
  30. 30 "ID", "COMMENT", "LINE_COMMENT", "WS"
  31. 31 };
  32. etc ...

4.3 Tiger.g4语法文件

  1. /**
  2. May,28 2014
  3. author: whimsycwd
  4. compiler project
  5. */
  6. grammar Tiger;
  7. program : exp
  8. | decs
  9. ;
  10. exp : 'nil' #Nil
  11. | INTEGER #Integer
  12. | STRING #String
  13. | type_id '[' exp ']' 'of' exp #Array
  14. | type_id '{' ( ID '=' exp (',' ID '=' exp )* )? '}' #Record
  15. //| 'new' type_id #New
  16. | lvalue #LeftValue
  17. | ID '(' ( exp (',' exp)*)? ')' #Call
  18. | '-' exp #UnaryMinus
  19. | exp ('*' | '/') exp #Mul
  20. | exp ('+' | '-') exp #Add
  21. | exp ('<>' | '=' | '>=' | '<=' | '>' | '<') exp #Cmp
  22. | exp ('&' | '|') exp #Logical
  23. | '(' exps ')' #ParenExprs
  24. | lvalue ':=' exp #Assign
  25. | 'if ' exp 'then' exp ('else' exp)? #IfStmt
  26. | 'while' exp 'do' exp #WhileStmt
  27. | 'for' ID ':=' exp 'to' exp 'do' exp #ForStmt
  28. | 'break' #Break
  29. | 'let' decs 'in' exps 'end' #LET
  30. ;
  31. exps : ( exp (';' exp)* )?;
  32. decs : dec*;
  33. dec : 'type' ID '=' ty #TypeDec
  34. | vardec #VarDecNothing
  35. | 'function' ID '(' tyfields? ')' (':' type_id)? '=' exp #FuncDec
  36. //| 'primitive' ID '(' tyfields? ')' (':' type_id)?
  37. //| 'import' STRING
  38. //| 'class' ID ('extends' type_id)? '{' classfields '}'
  39. ;
  40. vardec : 'var' ID (':' type_id)? ':=' exp #VarDecInner
  41. ;
  42. //classfields : classfield*
  43. // ;
  44. //classfield : vardec
  45. // | 'method' ID '(' tyfields ')' (':' type_id) '=' exp
  46. // ;
  47. ty : type_id
  48. | '{' tyfields? '}'
  49. | 'array' 'of' type_id
  50. // | 'class' ('extends' type_id)? '{' classfields '}'
  51. ;
  52. tyfields : ( ID ':' type_id (',' ID ':' type_id)*)
  53. ;
  54. type_id : ID
  55. ;
  56. lvalue : ID #SimpleVar
  57. | lvalue '.' ID #DotVar
  58. | lvalue '[' exp ']' #BracketVar
  59. ;
  60. INTEGER : DIGIT+;
  61. STRING : '"' (ESC | .)*? '"';
  62. ID : LETTER (LETTER | DIGIT) *;
  63. fragment
  64. ESC : '\\' [btnr"\\];
  65. fragment
  66. LETTER : [a-zA-Z] | '_';
  67. fragment
  68. DIGIT : [0-9];
  69. COMMENT : '/*' .*? '*/' ->skip;
  70. LINE_COMMENT : '//' .*? '\n' ->skip;
  71. WS : [ \n\r\t]+ ->skip;

五、AST测试

5.1 配置测试环境 config.profile

  1. 1 BASE="/Users/whimsycwd/Repo/ANTLR/Tiger/"
  2. 2
  3. 3 export CLASSPATH=".:./lib/antlr-4.2.1-complete.jar:${BASE}lib/antlr-4.2.1-complete.jar:${BASE}classes"
  4. 4
  5. 5 alias antlr4='java org.antlr.v4.Tool'
  6. 6 alias grun='java org.antlr.v4.runtime.misc.TestRig'
  7. 7 alias runTiger='grun Tiger program'

上述代码为Terminal配置了环境变量。只需改变BASE到实际的地址。在Terminal中source config.profile,就可以使用antlr4,grun,runTiger的指令的简称。

5.2 下载测试代码 fetch.sh

  1. 1 URL=http://www.computing.dcu.ie/~hamilton/teaching/CA448/testcases/
  2. 2
  3. 3 rm *.tig
  4. 4
  5. 5 for i in {1..49}
  6. 6 do
  7. 7 curl -O "${URL}test${i}.tig"
  8. 8
  9. 9 done
  10. 10
  11. 11 for name in 'queens.tig' 'merge.tig'
  12. 12 do
  13. 13 curl -O "${URL}$name"
  14. 14 done

新建文件夹testcases, 在该目录下执行上述的代码可以将测试文件批量下载下来。

5.3 编译运行 run.sh

  1. 1 # clean the generated file and recompile
  2. 2 # May 31,2014 whimsycwd
  3. 3
  4. 4
  5. 5 #source config.profile
  6. 6
  7. 7 rm Tiger*.java 2>/dev/null
  8. 8 #rm Tiger*.class 2>/dev/null
  9. 9 rm Tiger*.tokens 2>/dev/null
  10. 10 rm ./classes/* 2>/dev/null
  11. 11
  12. 12 echo "File deleted"
  13. 13
  14. 14 echo "ANTLR Generating"
  15. 15 java org.antlr.v4.Tool Tiger.g4
  16. 16
  17. 17 echo "Compile Start"
  18. 18
  19. 19 #javac Tiger*.java -d ./classes/
  20. 20 javac *.java -d ./classes/

5.4 输出测试AST结果 runAllTest.sh

  1. 1 # RUN ALL TEST
  2. 2 # May 31, 2014 whimsycwd
  3. 3
  4. 4
  5. 5 echo "deleting testcases-result"
  6. 6 rm testcases-result/*
  7. 7
  8. 8 for i in {1..49}
  9. 9 do
  10. 10 echo "test${i}.tig is processing"
  11. 11 java org.antlr.v4.runtime.misc.TestRig Tiger program -tree "testcases/test${i}.tig" > "testcases-result/test${i}.tig.res"
  12. 12 done
  13. 13
  14. 14 for name in 'queens.tig' 'merge.tig'
  15. 15 do
  16. 16 echo "${name} is processing"
  17. 17 java org.antlr.v4.runtime.misc.TestRig Tiger program -tree "testcases/${name}" > "testcases-result/${name}.res"
  18. 18 done

新建testcases-result,利用上述代码能够批量输出测试代码到testcases-result/

5.5 结果示例 1 testcases/test1.tig

  1. 1 /* an array type and an array variable */
  2. 2 let
  3. 3 type arrtype = array of int
  4. 4 var arr1:arrtype := arrtype [10] of 0
  5. 5 in
  6. 6 arr1
  7. 7 end

代码输出了AST结果文件:testcases-result/test.tig.res

  1. (program (exp let (decs (dec type arrtype = (ty array of (type_id int))) (dec (vardec var arr1 : (type_id arrtype) := (exp (type_id arrtype) [ (exp 10) ] of (exp 0))))) in (exps (exp (lvalue arr1))) end))

对应的图形化的结果为:

5.6 #结果示例 2 mytest/error.in 错误提示和行号

  1. 1 let
  2. 2 var a:== 1
  3. 3 var b:= 2
  4. 4 in
  5. 5 let
  6. 6 var c := 3
  7. 7 in
  8. 8 d
  9. 9 end
  10. 10 end

代码输出结果:

  1. whimsyMini:Tiger whimsycwd$ runTiger -tree error.in
  2. line 2:11 no viable alternative at input '='
  3. (program (exp let (decs (dec (vardec var a := (exp = 1))) (dec (vardec var b := (exp 2)))) in (exps (exp let (decs (dec (vardec var c := (exp 3)))) in (exps (exp (lvalue d))) end)) end))

对应的图形化的结果,追到错误的地方,被高亮出来了,并且跳过继续解析。

六、变量作用域检查

为了实现变量声明的检查,两次遍历抽象语法树,第一次遍历抽象语法树,简历变量表,注意在遍历的过程中,还要考虑作用域,进入一个作用域的时候需要创建新的作用域。作用域构成一个链表,resolve一个变量的时候需要跟往上层去查找。

6.1 CheckSymbols.java

  1. ...
  2. 27 public void process(String[] args) throws Exception {
  3. 28 String inputFile = null;
  4. 29 if ( args.length>0 ) inputFile = args[0];
  5. 30 InputStream is = System.in;
  6. 31 if ( inputFile!=null ) {
  7. 32 is = new FileInputStream(inputFile);
  8. 33 }
  9. 34 ANTLRInputStream input = new ANTLRInputStream(is);
  10. 35 TigerLexer lexer = new TigerLexer(input);
  11. 36 CommonTokenStream tokens = new CommonTokenStream(lexer);
  12. 37 TigerParser parser = new TigerParser(tokens);
  13. 38 parser.setBuildParseTree(true);
  14. 39 ParseTree tree = parser.program();
  15. 40 // show tree in text form
  16. 41 // System.out.println(tree.toStringTree(parser));
  17. 42
  18. 43 ParseTreeWalker walker = new ParseTreeWalker();
  19. 44 DefPhase def = new DefPhase();
  20. 45 walker.walk(def, tree);
  21. 46 // create next phase and feed symbol table info from def to ref phase
  22. 47 RefPhase ref = new RefPhase(def.globals, def.scopes);
  23. 48 walker.walk(ref, tree);
  24. 49 //TypePhase type = new TypePhase();
  25. 50 //walker.walk(type, tree);
  26. 51 }
  27. ...

具体的代码 CheckSymbols.java DefPhase.java Scope.java BaseScope.java GlobalScope.java LocalScope.java RefPhase.java

第一阶段DefPhase,如下所示,比如在进入Function的时候currentScope = new LocalScope(currentScope); 新建一个作用域。在退出Function的时候 currentScope = currentScope.getEnclosingScope(); 往链表上层去找。

6.2 DefPhase.java

  1. ...
  2. 44 public void enterFuncDec(TigerParser.FuncDecContext ctx){
  3. 45 // formal parameter
  4. 46 //if (debug)
  5. 47 // System.out.println("Entering FuncDec "+ currentScope);
  6. 48 currentScope = new LocalScope(currentScope);
  7. 49
  8. 50 TigerParser.TyfieldsContext tyfields = ctx.tyfields();
  9. 51 if (tyfields != null){
  10. 52 // if there is formal parameters.
  11. 53 List<TerminalNode> list = tyfields.ID();
  12. 54 for (TerminalNode e : list){
  13. 55 currentScope.define(new VariableSymbol( e.getSymbol().getText() ) ); // 把变量添加到当前作用域
  14. 56 }
  15. 57 }
  16. 58 saveScope(ctx, currentScope);
  17. 59 }
  18. 60 public void exitFuncDec(TigerParser.FuncDecContext ctx){
  19. 61
  20. 62 //if (debug)
  21. 63 //System.out.println("Exiting FuncDec "+ currentScope);
  22. 64 //System.out.println(currentScope);
  23. 65 currentScope = currentScope.getEnclosingScope(); // 退出作用域
  24. 66 }
  25. ...

检查变量varName是否在存在。解析变量代码如下。

6.3 BaseScope.java

  1. 10 public Symbol resolve(String name) {
  2. 11 Symbol s = symbols.get(name);
  3. 12 if ( s!=null ) return s;
  4. 13 // if not here, check any enclosing scope
  5. 14 if ( enclosingScope != null ) return enclosingScope.resolve(name);
  6. 15 return null; // not found
  7. 16 }

在第二阶段RefPhase当变量解析不到该变量,输出该类型的错误。

6.4 RefPhase.java

  1. ...
  2. 212 public void exitSimpleVar(TigerParser.SimpleVarContext ctx){
  3. 213
  4. 214 String name = ctx.ID().getSymbol().getText();
  5. 215
  6. 216 Symbol var = currentScope.resolve(name);
  7. 217 // print(currentScope);
  8. 218 if (var == null){
  9. 219 CheckSymbols.error(ctx.ID().getSymbol(),"no such variable: " + name);
  10. 220 }
  11. ...

七、变量声明测试

7.1 结果示例 mytest/test.in

  1. 1 let
  2. 2 var a:= 1
  3. 3 var b:= 2
  4. 4 in
  5. 5 let
  6. 6 var c := 3
  7. 7 in
  8. 8 d
  9. 9 end
  10. 10 end

注意到这个代码中 d并找不到此变量。可得到输出结果:

  1. whimsyMini:Tiger whimsycwd$ java CheckSymbols mytest/test.in
  2. line 8:8 no such variable: d

八、基本的类型检查

为了实现基本的类型检查,对于每一个抽象语法树上的节点都需要给他一个类型。定义了一个AST节点到Type的映射typeSys。

  1. 'for' ID ':=' exp 'to' exp 'do' exp

下面的代检查了三个exp的类型。 exp1 和 exp2必须是Type.tInt。而对于整个语句的类型定义为exp3。

8.1 RefPhase.java

  1. ...
  2. 170 Type t1 = typeSys.get(ctx.exp(0));
  3. 171 Type t2 = typeSys.get(ctx.exp(1));
  4. 172
  5. 173 if (t1 != Type.tInt){
  6. 174 CheckSymbols.error( ctx.getStart(), "loop pd expression must be tInt" );
  7. 175 typeSys.put(ctx, Type.tVoid);
  8. 176 } else {
  9. 177 typeSys.put(ctx, t2);
  10. 178 }
  11. 179 print("In WhileStmt : " + typeSys.get(ctx) );
  12. 180 }
  13. 181
  14. 182 public void exitForStmt(TigerParser.ForStmtContext ctx){
  15. 183 Type t1 = typeSys.get(ctx.exp(0));
  16. 184 Type t2 = typeSys.get(ctx.exp(1));
  17. 185 Type t3 = typeSys.get(ctx.exp(2));
  18. 186
  19. 187 if (t1 != Type.tInt || t2 != Type.tInt){
  20. 188 CheckSymbols.error( ctx.getStart(), "loop start and end must both be tInt" );
  21. 189 typeSys.put(ctx, Type.tVoid);
  22. 190 } else {
  23. 191 typeSys.put(ctx, t3);
  24. 192 }
  25. 193 print("In ForStmt " + typeSys.get(ctx));
  26. 194 currentScope = currentScope.getEnclosingScope();
  27. 195 }
  28. 196
  29. 197 public void exitLET(TigerParser.LETContext ctx){
  30. 198 typeSys.put(ctx, typeSys.get( ctx.exps() ) );
  31. 199 currentScope = currentScope.getEnclosingScope(); // exit a scope
  32. 200 print("In LET: "+typeSys.get(ctx) );
  33. 201 }
  34. 202 public void exitExps(TigerParser.ExpsContext ctx){
  35. 203 List<TigerParser.ExpContext> list = ctx.exp();
  36. 204 typeSys.put(ctx, typeSys.get( list.get(list.size() -1 ) ) );
  37. 205 print("In exps: "+ typeSys.get(ctx) );
  38. 206
  39. 207 }
  40. ...

九、基本的类型检查测试

9.1 结果示例 mytest/add.in

  1. 1 let
  2. 2 var a := nil
  3. 3 var b := 12
  4. 4 var c := "adfaf"
  5. 5 var d := 133
  6. 6 in
  7. 7 -c;
  8. 8 -b;
  9. 9 b+d;
  10. 10 b-d;
  11. 11 a+c;
  12. 12 b/d;
  13. 13 b*d;
  14. 14 b*(d+b);
  15. 15 d := b+d
  16. 16
  17. 17 end

这个代码的输出结果,发现了其类型的错误。注意到line 7 -c,其中c是一个String错误。line 11 a + c, 只有Int有定义加法。

  1. whimsyMini:mytest whimsycwd$ java CheckSymbols add.in
  2. line 7:4 Expected - Int, got - tString
  3. line 11:4 Expected Int +/- Int got tVoid +/- tString
上传的附件 cloud_download 基于ANTLR实现的Tiger编译器前端.7z ( 1.61mb, 1次下载 )
error_outline 下载需要9点积分

发送私信

这个世界上我只相信两个人,一个是我,另一个不是你

14
文章数
15
评论数
最近文章
eject