compiler impletment learn from Jack W. Crenshaw

发表于 更新于 分类于 阅读次数： Waline： 本文字数： 469 阅读时长 ≈ 2 分钟

学习网站

学习过程中的不懂问题

使用栈计算表达式时，‘)’ had different precedence levels,depending upon whether or not it was already on the stack,you had to give it one value before you put it on the stack, and another to decide when to take it off.(不明白为啥右括号有不同优先级，咋还能入栈)
difference between interpreter and compiler : the recognizing of procedure, in the interpreter the recognizing procedure end up being coded as FUNCTIONS that return numeric values to their callers.None of the parsing routines for our compiler did that（不明白解释器和编译器在procedure翻译上的不同）
assembler: 目的是生成object code,normally does that on a one-to-one basis(one object instruction per line of source code),but almost ebery assember also permits expression as arguments.In this case, the expression are always constant expressions, and so the assembler isn’t supposed to issue object code for them. Rather, it “interpreters” the expression and computes the corresponding constant result,which is what it actually emits as object code（此处说的汇编器对常量表达式的处理是“lazy”概念，exap: x = x+3-2-1最后生成时是对 x= x+0甚至是x=x）

阶段1 Single Num expression

只含”+-“的二元表达式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
{
    expr::= term<+-term>
    term::=GetNum
}
{-------------------------------------------------------------}
procedure Expression;
begin
    Term;{MOVE #GetNum,D0;}
    EmitLn('MOVE D0,D1');
    case Look of
    '+': Add;{Match('+');Term;ADD D1,D0;结果存在D0}
    '-': Substract;{Match('-');Term;SUB D1,D0;NEG D0;结果存在D0}
    else Expected('加减操作符');
end;

多个操作数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
{循环解决,将数压栈解决寄存器有限}
{-------------------------------------------------------------}
procedure Expression;
begin
    Term;{MOVE #GetNum,D0;}
    while Look in ['+','-'] do begin
        EmitLn('MOVE D0,-(SP)');{D1=D0;}
        case Look of
        '+': Add;{Match('+');Term; ADD (SP)+,D0;}
        '-': Substract;{Match('-');Term; SUB -(SP),D0; NEG D0 ;}
        else Expected('加减操作符');
        end;
    end;
end;

增加”*/“

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
{
    优先级高，单位更小
    expr::= term <+- term>
    term::= factor <*/ factor>
    factor::= GetNum
}
{------------------------------------------------------------}
procedure Expression;
begin
    Term;
    while Look in ['+','-'] do begin
        EmitLn('MOVE D0,-(SP)');{压栈}
        case Look of
        '+': Add;{Match('+');Term; ADD (SP)+,D0;}
        '-': Substract;{Match('-');Term; SUB (SP)-,D0; NEG D0;}
        else Expected('加减操作符');
        end;
    end;
end;

procedure Term;
begin
    Factor;{GetNum;}
    while Look in ['*','/'] do begin
        case Look of
        '*': Multiply;{Match('*');Factor;MUL (SP)+,D0;}
        '/': Divide;
        else Expected('乘除操作符');
    end;
end;

增加”()”

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
{
    递归
    factor ::= (expr) or GetNum
}
{------------------------------}
procedure Factor;
begin
    if Look ='(' than begin
        Match('(');
        Expression;
        Match(')');
    end
    else
        EmitLn('MOVE'+#GetNum+',D0');
end;

增加”-+作为正负号的数”

增加0-

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
{
    expr::=- or term<+-term>
}
{------------------------------------------------------------}
procedure Expression;
begin
    if Look in ['+','-'] do
        EmitLn('CLR D0');{D0=0;}
    else
        term;
    while Look in ['+','-'] do begin
        EmitLn('MOVE D0,-(SP)');{压栈}
        case Look of
        '+': Add;{Match('+');Term; ADD (SP)+,D0;}
        '-': Substract;{Match('-');Term; SUB (SP)-,D0; NEG D0;}
        else Expected('加减操作符');
        end;
    end;
end;

阶段2 Assignment（name = expression，多位数和标识符Token识别）

增加 单个字母的标识符（以及无参的函数调用C语言格式）

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
{
    factor ::= GetNum | (expre) | Ident
    Ident ::= GetName <'('')'>
}
{-------------------------------------------}
procedure Factor;
begin
    if Look ='(' than begin
        Match('(');
        Expression;
        Match(')');
    end
    else if IsAlpha(Look) then begin
        Ident;{标识符识别}
    end
    else
       EmitLn('MOVE'+#GetNum+',D0');
end;

{----------------------------------------}
procedure Ident;
var Name:Char;
begin
    Name :=GetName;
    if Look = '(' then
        begin
        Match('(');
        Match(')');
        EmitLn('BSR '+Name);{调用函数}
    end
    else EmitLn('MOVE '+Name+'(PC),D0');{将操作数取出来放在D0}
end;

增加赋值语句

1
2
3
4
5
6
7
8
9
10
11
12
13
{
    Assignment ::= GetName = expr
}
procedure Assignment;
var Name:char;
begin
    Name:=GetName;
    Match('=');
    Expression;
    {赋值汇编}
    EmitLn('LEA '+Name+'(PC)',A0);{A0是地址寄存器，存放Name的地址，PC相对寻址}
    EmitLn('MOVE D0,(A0)');
end;

增加多位数和多个字母

1
2
3
4
5
6
7
8
9
10
11
12
13
{
    GetNum，GetName重写while
}
function GetNum:string;
var Value:string;
begin
    Value:='';
    if not isDigit(Look) then Expected('Digit');
    while isDigit(Look) do begin
        Value:=Value+Look;
        GetChar;
    end;
end;

增加空格过滤

1
2
3
4
5
6
7
8
9
{
    识别空格，过滤空格，保证其余的识别开头第一个是非空格字符，即：

    Init 中GetChar后要SkipWhite；

    GetNum/Name 最后要SkipWhite;
    
    tips: LR (#10,^J) CR($13,^M)
}

阶段3：简单的interpreter

interpreter就是等到必要时才打印，否则就一直计算

识别表达式

1
2
3
expr := -/+ term <+/- term>
term := factor <*/ factor>
factor := GetNum | (expr)

一位数字(即时计算)

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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
{-------------------------}
{GetNum}
function GetNum:integer;
begin
    if not isDigit(Look) then Expected('Integer');
    GetNum := Ord(Look)-Ord('0');
    GetChar;
end;

{----------------------------}
{Factor}
function Factor:integer;
begin
    if Look = '(' then
    begin
        Match('(');
        Factor := Expression;
        Match(')');
    end
    else Factor := GetNum;
end;

{-------------------------------}
{ Term }
function Term:integer;
var
    Value :integer;
begin
    Value := Factor;
    while isMulop(Look) do
    begin
        case Look of
        '*': 
        begin
            Match('*');
            Value:=Value * Factor;
        end;
        '/': 
        begin
            Match('/');
            Value:=Value div Factor;
        end;
        end;
    end;
    Term := Value;
end;

{-----------------------------}
{Expression}
function Expression:integer;
var
    Value:integer;
begin
    if isAddop(Look) then begin{能省略吗？不能因为省略后无法识别Term开头的表达式}
        Value:=0;
    end
    else Value:= Term;
    while isAddop(Look) do begin
        case Look of
        '+': 
        begin
            Match('+');
            Value := Value +Term;
        end;
        '-': 
        begin
            Match('-');
            Value := Value -Term;
        end;
        end;
    end
    Expression := Value;
end;

多位数字(改动GetNum)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
procadure GetChar;
begin
    Read(Look);
end;
function GetNum:integer;
var
    Value: integer;
begin
    Value :=0;
    if not isDigit(Look) then Expected("Integer");
    while isDigit(Look) do
    begin
        Value := Value * 10 +Ord(Look)-Ord('0');
        GetChar;
    end;
    GetNum := Value;
end;

NewLine，，WhiteSpace；循环解释，结束符与单字母符号表的初始化和输出

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
{
    在我的电脑上windows的WSL上NewLine只用了LF
    结束符.
    输入符号表命令 ？Name Value
    输出符号表命令 ！Name 
    对于WhiteSpace（在一个单元结束下一个单元开始前跳过中间的空格）：最小读取单元是数字或者单个字符，故在init的GetChar后添加skipWhite，在GetNum和GetName结束添加skipWhite（读到第一个非空格字符）,还需要在match后加上skipWhite
}
{ 符号表 }
var 
Table['A'..'Z'] of integer;
{ Input Table}
procedure Input;
begin
    Match('?');
    Read(Table[GetName]);
end;
{Output}
procedure Output;
begin
    Match('!');
    Write(Table[GetName]);
end;
procedure NewLine;
begin
    if isNewLine(Look) then
        begin
            GetChar;
            SkipWhite;
        end;
end;
{ Main }
begin
    repeat
        case Look of 
        '?': Input;
        '!': Output;
        else Assignment;
        end;
        NewLine;
        until Look = '.';
end.