Compiler-语法分析-2

更新于 分类于 阅读次数： 本文字数： 6.9k 阅读时长 ≈ 12 分钟
编译原理-语法分析

Chapter2-语法分析

具体要求

输入：

1
2
3
4
5
const int a = 0;
int main(){
    int f = 0;
    return 0;
}

输出：

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
CONSTTK const
INTTK int
IDENFR a
ASSIGN =
INTCON 0
<Number>
<PrimaryExp>
<UnaryExp>
<MulExp>
<AddExp>
<ConstExp>
<ConstInitVal>
<ConstDef>
SEMICN ;
<ConstDecl>
INTTK int
MAINTK main
LPARENT (
RPARENT )
LBRACE {
INTTK int
IDENFR f
ASSIGN =
INTCON 0
<Number>
<PrimaryExp>
<UnaryExp>
<MulExp>
<AddExp>
<Exp>
<InitVal>
<VarDef>
SEMICN ;
<VarDecl>
RETURNTK return
INTCON 0
<Number>
<PrimaryExp>
<UnaryExp>
<MulExp>
<AddExp>
<Exp>
SEMICN ;
<Stmt>
RBRACE }
<Block>
<MainFuncDef>
<CompUnit>

其实只是在上一次词法分析的基础上，将每一个非终结符也输出，所以要构造每个非终结符的处理函数，形成一颗递归树，当然也可不不用形成递归树，但是递归树有利于之后的代码生成。

实现方式

消除左递归

消除左递归的方法主要有三种：

规则1：（提因子）\(U::=xy|xw|…|xz\)可替换为\(U::=x(y|w|…|z)\)

规则2：\(U::=x|y|…|z|Uv\)可替换为\(U::=(x|y|…|z)\{v\}\)

规则3：

我这里用的是规则三：

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
MulExp → UnaryExp | MulExp ('*' | '/' | '%') UnaryExp
消除左递归：
MulExp → UnaryExp MulExp2
MulExp2 → ('*' | '/' | '%') UnaryExp MulExp2 | e

AddExp → MulExp | AddExp ('+' | '−') MulExp
消除左递归：
AddExp → MulExp AddExp2
AddExp2 → ('+' | '−') MulExp AddExp2 | e

RelExp → AddExp | RelExp ('<' | '>' | '<=' | '>=') AddExp
消除左递归：
RelExp → AddExp RelExp2
RelExp2 → ('<' | '>' | '<=' | '>=') AddExp RelExp2 | e

EqExp → RelExp | EqExp ('==' | '!=') RelExp
消除左递归：
EqExp → RelExp EqExp2
EqExp2 → ('==' | '!=') RelExp EqExp2 | e

LAndExp → EqExp | LAndExp '&&' EqExp
消除左递归：
LAndExp → EqExp LAndExp2
LAndExp2 → '&&' EqExp LAndExp2 | e

LOrExp → LAndExp | LOrExp '||' LAndExp
消除左递归：
LOrExp → LAndExp LOrExp2 
LOrExp2 → '||' LAndExp LOrExp2 | e

其实后面发现用规则二其实更简单...

故消除左递归之后的文法如下：

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
CompUnit → {Decl} {FuncDef} MainFuncDef 
Decl → ConstDecl | VarDecl
ConstDecl → 'const' BType ConstDef { ',' ConstDef } ';'
BType → 'int'
ConstDef → Ident { '[' ConstExp ']' } '=' ConstInitVal
ConstInitVal → ConstExp | '{' [ ConstInitVal { ',' ConstInitVal } ] '}'
VarDecl → BType VarDef { ',' VarDef } ';'
VarDef → Ident { '[' ConstExp ']' }  [‘=’ InitVal]
InitVal → Exp | '{' [ InitVal { ',' InitVal } ] '}'
FuncDef → FuncType Ident '(' [FuncFParams] ')' Block
MainFuncDef → 'int' 'main' '(' ')' Block
FuncType → 'void' | 'int'
FuncFParams → FuncFParam { ',' FuncFParam }
FuncFParam → BType Ident ['[' ']' { '[' ConstExp ']' }]
Block → '{' { BlockItem } '}'
BlockItem → Decl | Stmt
Stmt → LVal '=' Exp ';' 
    | [Exp] ';' 
    | Block | 'if' '(' Cond ')' Stmt [ 'else' Stmt ] 
    | 'while' '(' Cond ')' Stmt 
    | 'break' ';' | 'continue' ';' 
    | 'return' [Exp] ';' 
    | LVal '=' 'getint''('')'';' 
    | 'printf''('FormatString{','Exp}')'';' 
Exp → AddExp
Cond → LOrExp
LVal → Ident {'[' Exp ']'}
PrimaryExp → '(' Exp ')' | LVal | Number
Number → IntConst
UnaryExp → PrimaryExp | Ident '(' [FuncRParams] ')'| UnaryOp UnaryExp  朝前看，因为ident有交集
UnaryOp → '+' | '−' | '!'
FuncRParams → Exp { ',' Exp }
MulExp → UnaryExp MulExp2
MulExp2 → ('*' | '/' | '%') UnaryExp MulExp2 | e
AddExp → MulExp AddExp2
AddExp2 → ('+' | '−') MulExp AddExp2 | e
RelExp → AddExp RelExp2
RelExp2 → ('<' | '>' | '<=' | '>=') AddExp RelExp2 | e
EqExp → RelExp EqExp2
EqExp2 → ('==' | '!=') RelExp EqExp2 | e
LAndExp → EqExp LAndExp2
LAndExp2 → '&&' EqExp LAndExp2 | e
LOrExp → LAndExp LOrExp2 
LOrExp2 → '||' LAndExp LOrExp2 | e
ConstExp → AddExp

构建FIRST集

Node FIRST ps
CompUnit {Decl,FuncDef} 超前判断
BlockItem {Decl,Stmt}
Stmt {Block,if,while,break,return,printf,LVal,Exp} 超前判断
Decl {ConstDecl ,VarDecl}
FuncDef {FuncType }
VarDecl {BType }
ConstInitVal {{,ConstExp}
InitVal {{,Exp}
Cond {LOrExp}
LOrExp {LAndExp }
LAndExp {EqExp }
EqExp {RelExp }
RelExp {AddExp }
FuncFParams {FuncFParam }
FuncFParam {BType }
FuncRParams {Exp }
Exp {AddExp}
ConstExp {AddExp}
AddExp {MulExp }
MulExp {UnaryExp }
UnaryExp {PrimaryExp,IDENT,UnaryOp} 超前判断
PrimaryExp {(,LVal,Number}
ConstDef {IDENT}
VarDef {IDENT}
FuncType {void,int}
Block {{}
BType {INTTK}
Number {INTCON}
LVal {IDENT}
UnaryOp {+，-，！}
MulExp2 {e,*,/,%}
AddExp2 {+,-,e}
MainFuncDef {int}
ConstDecl {const}
RelExp2 {<,>,<=,>=,e}
EqExp2 {==,!=,e}
LAndExp2 {&&,e}
LOrExp2 {OR,e}

构建FIRST集：从下往上写！我将FIRST集写在了Tag 类里面，之后直接调用即可。表格中的超前判断指的是其FIRST集中有交集！！

Tag 类如下：

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
public class Tag {
    public final static ArrayList<String>
            LOrExp2 = new ArrayList<String>() {
                {
                    add("OR");
                }
            },
            LAndExp2 = new ArrayList<String>() {
                {
                    add("AND");
                }
            },
            ...
            ...
            Stmt = new ArrayList<String>() {
                {
                    add("IFTK");
                    add("WHILETK");
                    add("BREAKTK");
                    add("RETURNTK");
                    add("PRINTFTK");
                    add("SEMICN");
                    add("CONTINUETK");
                    addAll(Block);
                    addAll(LVal);
                    addAll(Exp);
                }
            },
            ...
            ...

所以从下往上写就能保证之后的FIRST能够直接调用已经写好的FIRST集，例如stmt里就可以用addAll(Block) 将Block的FIRST集全部加到Stmt 的FIRST集合里。所以构建FIRST集其实很简单，直接看文法构建其实也行，不过还是重新写一张表比较保险.

递归下降法

构造一棵递归树，这颗递归树是由结点Node类构成的，每个结点包含自己的token和childList （用于存放其下面的孩子结点）；而token类包含type，word，line,其实就是词法分析输出的三个hashmap，用来组成Token流。

但是需要注意的是这些token流仅仅只是终结符结点，因此每次走到非终结符，应该自己给这个node填一个标签token上去，例如：

1
2
3
4
5
6
7
8
9
10
11
public Node Decl() {
        Node nDecl = new Node(new Token("<Decl>"));
        if (curToken.match(Tag.ConsDecl)) {
            nDecl.addChild(ConstDecl());
        } else if (curToken.match(Tag.VarDecl)) {
            nDecl.addChild(VarDecl());
        } else {
            //错误处理:Decl
        }
        return nDecl;
    }

同时，递归下降的思路也如上述代码所示，如果当前令牌根据文法在某个非终结符的FIRST集里，则进行解析，调用相应的函数，同时也要为后续的错误处理留有余地。

递归下降处理程序我用的是SyntaxParser 的类，其类图如下所示：

  1. inputStream要在词法分析的时候就处理好，将token流输出，然后输入语法分析；

  2. index是curToken所处输入流中的索引，同时也可以用作超前读入；

  3. stopList和reverseList仅仅是用于输出的时候，在stopList里的结点不输出；在reverseList（消除左递归带来产生的MulExp2之类的结点）里的结点，输出顺序是根-孩子，其余的输出方式就是孩子-根。

方法部分不详述了。

UML图总体实现

注意细节

  1. 每次加入终结符之后，都要nextToken()获得下一个令牌.

  2. {xxx}这种用while判断，注意什么时候并列判断，什么时候嵌套判断。

  3. 对于Stmt：先把if等保留字判断之后再判断LVal,Exp,Block。其中超前判断（LVal后面一定有=,Exp没有）

期中注意事项（关于机房）

Settings

  1. 设置字体

    Editor font 15

  2. 设置自动补全 Keymap 设置按键 Duplicate Mainmenu Code Completion remove ctrl+空格 add shortcut alt+/

  3. 不能debug的问题：

    在c/Users/Administrator/IdeaProjects中创建项目，不要在D盘创建！！

明天就是期中了，FOCUS ON MYSELF！