在我们的编译器模型中，语法分析器从词法分析器获得一个由词法单元组成的串，并验证这个串可以由源语言的文法生成。我们期望语法分析器能够以易于理解的方式报告语法错误，并且能够从常见的错误中恢复并继续处理程序的其余部分。
——《编译原理》（龙书）
语法分析设计
在本次实验中，我采用了自底向上生成和自顶向下输出的方式，利用递归子程序对文法中定义的语法成分进行了分析和输出。本次实验的难点有：语法树的设计、消除左递归、不同语法类型判断。
整体架构
编码前
为了方便之后对语法节点的调用，本次实验将每个语法成分作为AST中的一个类进行存储，其中Node为抽象父类。
1
2
3
4
| public abstract class Node {
public void output(){
};
}
|
对于Ident，FormatString和IntConst，则将其作为Token的子类，方便进行判断：
1
| showToken() instanceof Ident
|
使用showToken()预读取当前的Token，使用getToken()获取当前Token，暂时使用error()输出对应错误的函数。
1
2
3
4
5
6
7
8
9
| public Token showToken(){
return tokens.get(index);
}
public Token showToken(int num){
return tokens.get(index+num);
}
public void error(String str){
System.out.println("--Error--"+str);
}
|
编码后
在语法分析中首先对out进行了重写：
1
2
3
| String output = "output.txt";
PrintStream out = new PrintStream(output);
System.setOut(out);
|
对于每个节点来说，大致设计如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| public class CompUnit extends Node {
private ArrayList<Decl> decl;
private ArrayList<FuncDef> funcDef;
private MainFuncDef mainFuncDef;
public CompUnit(ArrayList<Decl> decl, ArrayList<FuncDef> funcDef, MainFuncDef mainFuncDef) {
this.decl = decl;
this.funcDef = funcDef;
this.mainFuncDef = mainFuncDef;
}
@Override
public void output() {
for(Decl value : decl){
value.output();
}
for(FuncDef value : funcDef){
value.output();
}
mainFuncDef.output();
System.out.print("<CompUnit>");
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| public class FuncDef extends Node{
FuncType funcType;
Ident funcName;
Token left;
FuncFParams params;
Token right;
Block block;
public FuncDef(FuncType funcType, Ident funcName, Token left, FuncFParams params, Token right, Block block) {
this.funcType = funcType;
this.funcName = funcName;
this.left = left;
this.params = params;
this.right = right;
this.block = block;
}
@Override
public void output() {
funcType.output();
funcName.output();
left.output();
if(Objects.nonNull(params)) params.output();
right.output();
block.output();
System.out.println("<FuncDef>");
}
}
|
当前项目架构
项目架构如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
| │ Compiler.java
│
├─frontend
│ ├─lexical
│ │ │ Token.java
│ │ │ Tokenizer.java
│ │ │ TokenList.java
│ │ │
│ │ └─tokens
│ │ FormatString.java
│ │ Ident.java
│ │ IntConst.java
│ │
│ └─syntax
│ │ Parser.java
│ │
│ └─AST
│ AddExp.java
│ Block.java
│ BlockItem.java
│ CompUnit.java
│ Cond.java
│ ConstDecl.java
│ ConstDef.java
│ ConstExp.java
│ ConstInitVal.java
│ Decl.java
│ EqExp.java
│ Exp.java
│ FuncDef.java
│ FuncFParam.java
│ FuncFParams.java
│ FuncRParams.java
│ FuncType.java
│ InitVal.java
│ LAndExp.java
│ LOrExp.java
│ LVal.java
│ MainFuncDef.java
│ MulExp.java
│ Node.java
│ Number.java
│ PrimaryExp.java
│ RelExp.java
│ Stmt.java
│ UnaryExp.java
│ UnaryOp.java
│ VarDecl.java
│ VarDef.java
│
└─utils
Source.java
|
在设计时，我们可以先完成与funcDef和MainFuncDef相关的类，之后完成与Decl相关的类，再完成与Block相关的类，最后完成Stmt相关的类。并随着类的编写不断拓展完善自己的测试用例。
当前Compiler类：
1
2
3
4
5
6
7
8
| public class Compiler {
public static void main(String[] args) throws FileNotFoundException {
Source source = new Source();
Tokenizer.initToken(source);
Parser parser = new Parser(Tokenizer.getTokenList());
parser.analyse().output();
}
}
|
消除左递归
对于以下文法：
1
2
3
4
5
6
7
8
9
10
11
| 乘除模表达式 MulExp → UnaryExp | MulExp ('*' | '/' | '%') UnaryExp
加减表达式 AddExp → MulExp | AddExp ('+' | '−') MulExp
关系表达式 RelExp → AddExp | RelExp ('<' | '>' | '<=' | '>=') AddExp
相等性表达式 EqExp → RelExp | EqExp ('==' | '!=') RelExp
逻辑与表达式 LAndExp → EqExp | LAndExp '&&' EqExp
逻辑或表达式 LOrExp → LAndExp | LOrExp '||' LAndExp
|
我们可以对其进行改写，消除文法的左递归性。
以MulExp为例：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
private MulExp getMulExp() {
ArrayList<UnaryExp> params = new ArrayList<>();
ArrayList<Token> tokens = new ArrayList<>();
params.add(getUnaryExp());
while(showToken().getContent().equals("*")
||showToken().getContent().equals("/")
||showToken().getContent().equals("%")){
tokens.add(getToken());
params.add(getUnaryExp());
}
return new MulExp(params,tokens);
}
|
由于我们对文法进行了修改，所以要特别注意要按照原文法进行输出：
1
2
3
4
5
6
7
8
| @Override
public void output() {
for(int i = 0; i < params.size(); i++){
if(i!=0) tokens.get(i-1).output();
params.get(i).output();
System.out.println("<MulExp>");
};
}
|
语法类型判断
VarDef
1
| VarDef → Ident { '[' ConstExp ']' } | Ident { '[' ConstExp ']' } '=' InitVal
|
可以将文法改写为：
1
| VarDef → Ident { '[' ConstExp ']' } [ '=' InitVal ]
|
1
2
3
4
5
6
7
8
| if(!showToken().getContent().equals("=")){
return new VarDef(1,count, ident,lrs,constExps);
}
else{
Token equal = getToken();
InitVal varInitVal = getInitVal();
return new VarDef(2,count, ident,lrs,constExps,equal,varInitVal);
}
|
Stmt
对Stmt来说，需要注意LVal '=' Exp ';'和[Exp] ';'的FIRST集存在交集，可以采用先确定';'位置，然后确定范围内是否存在'='的方式进行判断。
1
2
3
4
5
6
7
8
| int temp = 0;
boolean notExp = false;
while(!showToken(temp).getContent().equals(";")){
temp++;
}
for(int i = 0; i<temp;i++){
if(showToken(i).getContent().equals("=")) notExp = true;
}
|
分类如下：
结语
本次实验代码还有着不少可优化的空间，重构后应该会对博客内容进行更新。
感谢wxy4869 的博客。
