编译原理课设尝试(一)——PL/0编译器分析

半路起步,继续学习编译原理ing,龙书还在继续看。我向来推崇学习时理论与实践结合,这本书现在带给我最大的感受是:我急于尽快掌握构建技术,而书上大篇幅介绍的还是词法、文法等理论知识,感觉我静心学习的耐心正在耗完中。

唉,这就是没系统上过课的悲剧,虽然知道不打好基础贻害无穷,但是还是决定上手做点实践。希望在实践中能够对编译原理有更多的理解。

这里要感谢挚友Bigballon同学以前分享给我的一份学习资料。他是软件系科班出身,对编程有着自己的理解。于是决定参考他写的一篇课程设计心得《从PL/0到Flex》尝试PL/0编译器的改写。


还记得当年我最早开始接触编程,学习的就是Pascal语言。

PL/0是Pascal语言的一个子集,它只有整数类型,但它是相当完全的可嵌套的分程序(block)的程序结构,分程序中可以有常量定义、变量声明和无参过程声明,过程体又是分程序。PL/0有赋值语句、条件语句、循环语句、过程调用语句、复合语句和空语句。

PL/0的文法定义

  • Program → Block .

  • Block → [ConstDecl][VarDecl][ProcDecl] Stmt
    程序块的基本结构是:常量定义、变量定义、过程定义、语句

  • ConstDecl → const ConstDef {, ConstDef} ;
    常量定义

  • ConstDef → ident = number

  • VarDecl → var ident {, ident} ;
    变量定义

  • ProcDecl → procedure ident ; Block ; {procedure ident ; Block ;}
    过程定义

  • Stmt → ident := Exp | call ident | begin Stmt {; Stmt} end | if Cond then Stmt | while Cond do Stmt | ε
    赋值语句、调用语句、begin-end块语句、判断语句、循环语句

  • Cond → odd Exp | Exp RelOp Exp
    条件表达式

  • RelOp → = | <> | < | > | <= | >=
    关系运算符

  • Exp → [+ | − ] Term {+ Term | − Term}
    表达式

  • Term → Factor {∗ Factor | / Factor}

  • Factor → ident | number | ( Exp )

ident 字母开头的字母/数字串

number 无符号整数

PL/0的指令集定义

PL/0的目标代码放在一个固定的存储数组中,而其中所需的数据组织成一个栈的形式存放。

它的中间语言是一种栈机器代码,其指令集结构如下:

指令/F 含义 L A
LIT 将常数置于栈顶 常量
LOD 将变量的值置于栈顶 层次差 数据地址
STO 将栈顶的值赋予某变量 层次差 数据地址
CAL 过程调用 层次差 程序地址
INT 在数据栈中分配空间 常量
JPC,JMP 条件/无条件转移 程序地址
OPR 一组算术或逻辑运算指令 运算类别

PL/0编译器的执行过程

  1. 编译器启动
  2. 编译器初始化
    包括:对保留字表( word )、保留字表中每一个保留字对应的 symbol 类型( wsym )、部分符号对应的 symbol 类型表( ssym )、类 PCODE 指令助记符表( mnemonic )、声明开始集合( declbegsys )、表达式开始集合( statbegsys )、项开始符号集合( facbegsys )以及一些全局变量的初始化
  3. 首次调用getsym()进行词法分析
  4. 调用block()过程,包括词法分析和语法分析
  5. 调用interpret()解释执行目标程序

PL/0编译器源码注释

pl0.h

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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
#include <stdio.h>

#define norw 11 // 保留字的数量
#define txmax 100 // 标识符表的长度
#define nmax 14 // 允许的最长数字位数
#define al 10 // 标识符的最大长度
#define amax 2047 // 寻址空间
#define levmax 3 // 最大嵌套层数
#define cxmax 2000 // 代码数组的长度

#define nul 0x1 // 空
#define ident 0x2 // 标识符
#define number 0x4 // 数值
#define plus 0x8 // +
#define minus 0x10 // -
#define times 0x20 // *
#define slash 0x40 // /
#define oddsym 0x80 // 奇数判断
#define eql 0x100 // =
#define neq 0x200 // <>
#define lss 0x400 // <
#define leq 0x800 // <=
#define gtr 0x1000 // >
#define geq 0x2000 // >=
#define lparen 0x4000 // (
#define rparen 0x8000 // )
#define comma 0x10000 // ,
#define semicolon 0x20000 // ;
#define period 0x40000 // .
#define becomes 0x80000 // :=
#define beginsym 0x100000 // 保留字:begin
#define endsym 0x200000 // 保留字:end
#define ifsym 0x400000 // 保留字:if
#define thensym 0x800000 // 保留字:then
#define whilesym 0x1000000 // 保留字:while
#define dosym 0x2000000 // 保留字:do
#define callsym 0x4000000 // 保留字:call
#define constsym 0x8000000 // 保留字:const
#define varsym 0x10000000 // 保留字:var
#define procsym 0x20000000 // 保留字:procedure

enum object // 三种标识符的类型
{
constant, variable, proc
};

enum fct // 中间代码指令集
{
lit, opr, lod, sto, cal, Int, jmp, jpc
};

/* lit 0, a : load constant a
opr 0, a : execute operation a
lod l, a : load variable l, a
sto l, a : store variable l, a
cal l, a : call procedure a at level l
Int 0, a : increment t-register by a
jmp 0, a : jump to a
jpc 0, a : jump conditional to a */

typedef struct // 指令类型
{
enum fct f; // 功能
long l; // 层次差
long a; // 数值/地址
} instruction;

char* err_msg[] = // 错误信息
{
/* 0 */ "",
/* 1 */ "Found ':=' when expecting '='.",
/* 2 */ "There must be a number to follow '='.",
/* 3 */ "There must be an '=' to follow the identifier.",
/* 4 */ "There must be an identifier to follow 'const', 'var', or 'procedure'.",
/* 5 */ "Missing ',' or ';'.",
/* 6 */ "Incorrect procedure name.",
/* 7 */ "Statement expected.",
/* 8 */ "Follow the statement is an incorrect symbol.",
/* 9 */ "'.' expected.",
/* 10 */ "';' expected.",
/* 11 */ "Undeclared identifier.",
/* 12 */ "Illegal assignment.",
/* 13 */ "':=' expected.",
/* 14 */ "There must be an identifier to follow the 'call'.",
/* 15 */ "A constant or variable can not be called.",
/* 16 */ "'then' expected.",
/* 17 */ "';' or 'end' expected.",
/* 18 */ "'do' expected.",
/* 19 */ "Incorrect symbol.",
/* 20 */ "Relative operators expected.",
/* 21 */ "Procedure identifier can not be in an expression.",
/* 22 */ "Missing ')'.",
/* 23 */ "The symbol can not be followed by a factor.",
/* 24 */ "The symbol can not be as the beginning of an expression.",
/* 25 */ "",
/* 26 */ "",
/* 27 */ "",
/* 28 */ "",
/* 29 */ "",
/* 30 */ "",
/* 31 */ "The number is too great.",
/* 32 */ "There are too many levels."
};


char ch; // 用于词法分析,存放最近一次从文件中读出的字符
unsigned long sym; // 存放最近一次识别出来的token类型
char id[al+1]; // 存放最近一次识别出来的标识符的名字
long num; // 存放最近一次识别出来的数字
long cc; // 字母计数(列指针)
long ll; // 行长度
long kk, err;
long cx; // 代码分配指针,代码生成模块总在cx所指的位置生成新代码

char line[81]; // 行缓冲区
char a[al+1]; // 词法分析器中用于存放正在分析的词
instruction code[cxmax+1]; // 指令表,存放生成的中间代码
char word[norw][al+1]; // 保留字表
unsigned long wsym[norw]; // 保留字中每一个保留字对应的symbol类型表
unsigned long ssym[256]; // 符号对应的symbol类型表

char mnemonic[8][3+1]; // 中间代码助记符表
unsigned long declbegsys, statbegsys, facbegsys; //声明开始、表达式开始、factor开始符号集合

struct // 符号表
{
char name[al+1]; // 符号名
enum object kind; // 符号类型
long val; // 值
long level; // 层差/偏移地址
long addr; // 地址
}table[txmax+1];

char infilename[80];
FILE* infile;

// the following variables for block
long dx; // 数据分配指针
long lev; // 当前的块深度
long tx; // 当前的符号表指针

// the following array space for interpreter
#define stacksize 50000
long s[stacksize]; // 数据栈

pl0.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
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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
1042
1043
1044
1045
1046
1047
1048
1049
1050
1051
1052
1053
1054
1055
1056
// pl/0 compiler with code generation
#include <stdlib.h>
#include <string.h>
#include "pl0.h"

void error(long n) // 打印错误信息
{
long i;

printf("Error=>");
for (i = 1; i <= cc-1; i++)
{
printf(" ");
}

printf("|%s(%d)\n", err_msg[n], n);

err++;
}

void getch() // 读取下一个字符
{
if(cc == ll) // 判断是否读完一行
{
if(feof(infile)) // 文件结束
{
printf("************************************\n");
printf(" program incomplete\n");
printf("************************************\n");
exit(1);
}

ll = 0; cc = 0;

printf("%5d ", cx);

while((!feof(infile)) && ((ch=getc(infile))!='\n'))
{
printf("%c", ch);
ll = ll + 1;
line[ll] = ch;
}

printf("\n");

ll = ll + 1;
line[ll] = ' ';
}

cc = cc + 1;
ch = line[cc];
}

//---------------------------------
//-------------词法分析
//---------------------------------
//从源文件中读出若干有效字符,组成一个 token 串,识别它的类型为保留字/标识
//符/数字或是其它符号。如果是保留字,把 sym 置成相应的保留字类型,如果是标
//识符,把 sym 置成 ident 表示是标识符,于此同时,id 变量中存放的即为保留
//字字符串或标识符名字。如果是数字,把 sym 置为 number,同时 num 变量中存
//放该数字的值。如果是其它的操作符,则直接把 sym 置成相应类型。经过本过程后
//ch 变量中存放的是下一个即将被识别的字符

void getsym()
{
long i, j, k;

while(ch == ' ' || ch == '\t') // 删除前导空格
{
getch();
}

if(isalpha(ch)) // 当前token的第一个字符为字母,可能是标识符或保留字
{
k = 0; // 用于记录token长度

do // 读完一个token
{
if(k < al) // 保证token长度不超过标识符最大长度
{
a[k] = ch; k = k + 1;
}

getch();
} while(isalpha(ch) || isdigit(ch));

if(k >= kk) // 保证a数组的末尾都是空格
{
kk = k;
}
else
{
do
{
kk = kk-1; a[kk] = ' ';
} while(k < kk);
}

strcpy(id, a); i = 0; j = norw - 1; //存放当前token的名字

do // 在保留字表中二分查找该串是否存在
{
k = (i+j)/2;

if(strcmp(id, word[k]) <= 0)
{
j = k - 1;
}

if(strcmp(id, word[k]) >=0)
{
i = k + 1;
}
} while(i <= j);

if(i-1 > j) // 找到则标记保留字
{
sym = wsym[k];
}
else // 否则标记为标识符
{
sym = ident;
}
}
else if(isdigit(ch)) // 首字符为数字,则将其解析为数值
{
k = 0; num = 0; sym = number;
do // 不断读取、保存数字
{
num = num * 10 + (ch - '0');
k = k + 1;
getch();
} while(isdigit(ch));

if(k > nmax) // 位数超限
{
error(31);
}
}
else if(ch == ':') // 首字符为“:”,则可能是赋值
{
getch();

if(ch == '=')
{
sym = becomes; getch();
}
else
{
sym = nul;
}
}
else if(ch == '<') // 首字符为“<”
{
getch();

if(ch == '=') // <=
{
sym = leq; getch();
}
else if(ch == '>') // <>
{
sym=neq; getch();
}
else // <
{
sym = lss;
}
}
else if(ch == '>') // 首字符为“>”
{
getch();

if(ch == '=') // >=
{
sym=geq; getch();
}
else // >
{
sym=gtr;
}
}
else // 均不是上述情况,则查询符号表,赋值
{
sym = ssym[(unsigned char)ch]; getch();
}
}

//---------------------------------
//-------------中间代码生成
//---------------------------------
//将生成的中间代码写入中间代码数组,供后面的解释器运行

void gen(enum fct x, long y, long z)
{
if(cx > cxmax) // 代码长度超限
{
printf("program too long\n");
exit(1);
}

code[cx].f = x; code[cx].l = y; code[cx].a = z;

cx = cx + 1;
}

//---------------------------------
//-------------测试当前单词是否合法
//---------------------------------
// 参数:s1:当语法分析进入或退出某一语法单元时当前单词符合应属于的集合
// s2:在某一出错状态下,可恢复语法分析正常工作的补充单词集合
// n :出错信息编号,当当前符号不属于合法的 s1 集合时发出的出错信息

void test(unsigned long s1, unsigned long s2, long n)
{
if (!(sym & s1)) // 当前符号不在s1中
{
error(n);
s1 = s1 | s2; // 把s2补充进s1

while(!(sym & s1)) // 循环找到下一个合法的符号
{
getsym(); // 继续词法分析
}
}
}

//---------------------------------
//-------------符号表
//---------------------------------

void enter(enum object k)
{
tx = tx + 1;

strcpy(table[tx].name, id); // 保存符号名字

table[tx].kind = k; // 保存符号类型

switch(k)
{
case constant: // 常量
if(num > amax)
{
error(31);
num = 0;
}
table[tx].val = num;
break;

case variable: // 变量
table[tx].level = lev; // 记录当前层次
table[tx].addr = dx; // 记录层次中的偏移地址
dx = dx + 1; // 只有变量登录时需要用dx在数据栈中预留空间
break;

case proc: // 过程
table[tx].level = lev;
break;
}
}

//---------------------------------
//-------------查找符号在符号表中的位置
//---------------------------------

long position(char* id)
{
long i;

strcpy(table[0].name, id);

i=tx;

while(strcmp(table[i].name, id) != 0)
{
i = i - 1;
}

return i;
}

//---------------------------------
//-------------常量声明
//---------------------------------

void constdeclaration()
{
if(sym == ident)
{
getsym();

if(sym == eql || sym == becomes) // 出现等号或赋值号
{
if(sym == becomes) // 赋值号报错
{
error(1);
}

getsym();

if(sym == number) // 将数字登录到符号表
{
enter(constant);
getsym();
}
else
{
error(2);
}
}
else
{
error(3);
}
}
else
{
error(4);
}
}

//---------------------------------
//-------------变量声明
//---------------------------------

void vardeclaration()
{
if(sym == ident)
{
enter(variable); // 将标识符登录到符号表中
getsym();
}
else
{
error(4);
}
}

//---------------------------------
//-------------输出当前代码块的中间代码
//---------------------------------

void listcode(long cx0)
{
long i;

for(i=cx0; i<=cx-1; i++)
{
printf("%10d%5s%3d%5d\n", i, mnemonic[code[i].f], code[i].l, code[i].a);
}
}

void expression(unsigned long);

//---------------------------------
//-------------factor处理
//---------------------------------
//fsys: 如果出错可用来恢复语法分析的符号集合

void factor(unsigned long fsys)
{
long i;

test(facbegsys, fsys, 24); // 开始因子处理前,先检查当前 token 是否在 facbegsys 集合中
// 如果不是合法的 token,抛 24 号错误,并通过 fsys 集恢复使语法处理可以继续进行

while(sym & facbegsys)
{
if(sym == ident) // 遇到标识符
{
i = position(id); // 查符号表

if(i==0) // 标识符未定义
{
error(11);
}
else
{
switch(table[i].kind)
{
case constant: //常量
gen(lit, 0, table[i].val);
break;

case variable: //变量
gen(lod, lev-table[i].level, table[i].addr);
break;

case proc: //过程
error(21);
break;
}
}

getsym();
}
else if(sym == number) // 遇到数字
{
if(num>amax)
{
error(31); num=0;
}

gen(lit,0,num);
getsym();
}
else if(sym == lparen) // 遇到左括号
{
getsym();
expression(rparen|fsys); // 后面是一个exp

if(sym==rparen) // 子表达式结束,应该遇到右括号
{
getsym();
}
else
{
error(22);
}
}

test(fsys,lparen,23); // 一个因子处理完毕,遇到的 token 应在 fsys 集合中
// 如果不是,抛 23 号错,并找到下一个因子的开始,使语法分析可以继续运行下去
}
}

//---------------------------------
//-------------term处理
//---------------------------------

void term(unsigned long fsys)
{
unsigned long mulop;

factor(fsys|times|slash); // 每个term都应该从factor开始

while(sym==times || sym==slash)// 处理乘除
{
mulop = sym; // 保存当前运算符
getsym();

factor(fsys|times|slash); // 运算符之后是一个factor

if(mulop == times)
{
gen(opr,0,4); // 乘法
}
else{
gen(opr,0,5); // 除法
}
}
}

//---------------------------------
//-------------exp处理
//---------------------------------

void expression(unsigned long fsys)
{
unsigned long addop;

if(sym==plus || sym==minus) // 处理正负号
{
addop=sym; // 保存正负号
getsym();

term(fsys|plus|minus); // 正负号后面是一个term

if(addop==minus)
{
gen(opr,0,1); // 负号,取反运算
}
}
else
{
term(fsys|plus|minus);
}

while(sym==plus || sym==minus) // 处理加减
{
addop=sym; // 保存运算符
getsym();

term(fsys|plus|minus); // 运算符后是一个term

if(addop==plus)
{
gen(opr,0,2); // 加
}
else
{
gen(opr,0,3); // 减
}
}
}

//---------------------------------
//-------------cond处理
//---------------------------------

void condition(unsigned long fsys)
{
unsigned long relop;

if(sym==oddsym) // odd运算符(一元)
{
getsym();
expression(fsys); // 后面是一个exp
gen(opr, 0, 6);
}
else // 否则是个二元运算符
{
expression(fsys|eql|neq|lss|gtr|leq|geq); // 后面是一个exp

if(!(sym&(eql|neq|lss|gtr|leq|geq)))
{
error(20);
}
else
{
relop=sym; // 保存当前运算符
getsym();

expression(fsys); // 处理表达式右边

switch(relop)
{
case eql:
gen(opr, 0, 8);
break;

case neq:
gen(opr, 0, 9);
break;

case lss:
gen(opr, 0, 10);
break;

case geq:
gen(opr, 0, 11);
break;

case gtr:
gen(opr, 0, 12);
break;

case leq:
gen(opr, 0, 13);
break;
}
}
}
}

//---------------------------------
//-------------stmt处理
//---------------------------------

void statement(unsigned long fsys)
{
long i,cx1,cx2;

if(sym==ident) // 标识符
{
i=position(id); // 查符号表
if(i==0)
{
error(11); // 未定义
}
else if(table[i].kind!=variable)
{
error(12); // 非变量
i=0;
}

getsym();

if(sym==becomes) // 赋值
{
getsym();
}
else
{
error(13);
}

expression(fsys); // 后面应该是一个exp

if(i!=0) // 若未出错,则产生一个sto代码
{
gen(sto,lev-table[i].level,table[i].addr);
}
}
else if(sym==callsym) // call语句
{
getsym();
if(sym!=ident)
{
error(14);
}
else
{
i=position(id);
if(i==0)
{
error(11);
}
else if(table[i].kind==proc)
{
gen(cal,lev-table[i].level,table[i].addr);
}
else
{
error(15);
}

getsym();
}
}
else if(sym==ifsym) // if语句
{
getsym();
condition(fsys|thensym|dosym);// 后面是一个cond

if(sym==thensym)
{
getsym();
}
else
{
error(16);
}
cx1=cx;
gen(jpc,0,0);
statement(fsys); // 后面是一个stmt
code[cx1].a=cx;
}
else if(sym==beginsym) // begin语句
{
getsym();
statement(fsys|semicolon|endsym); // 后面是stmt
while(sym==semicolon||(sym&statbegsys)) // 处理分号和语句
{
if(sym==semicolon) // 分号
{
getsym();
}
else
{
error(10);
}
statement(fsys|semicolon|endsym);
}
if(sym==endsym)
{
getsym();
}
else
{
error(17);
}
}
else if(sym==whilesym) // while语句
{
cx1=cx; // 记录中间代码起始指针
getsym();
condition(fsys|dosym); // 后面是一个cond
cx2=cx; // 记录中间代码位置,要放退出地址
gen(jpc,0,0);
if(sym==dosym) // do语句
{
getsym();
}
else
{
error(18);
}

statement(fsys); // 后面是stmt
gen(jmp,0,cx1); // 循环跳转

code[cx2].a=cx; // 把退出地址补上
}

test(fsys,0,19);
}

//---------------------------------
//-------------block处理
//---------------------------------

void block(unsigned long fsys)
{
long tx0;
long cx0;
long tx1;
long dx1;

dx=3;
// 地址寄存器给出每层局部量当前已分配到的相对位置
// 置初始值为 3 的原因是:每一层最开始的位置有三个空间用于存放
// 静态链 SL、动态链 DL 和 返回地址 RA
tx0=tx; // 记录本层开始时符号表的位置
table[tx].addr=cx; // 符号表记下当前层代码的开始地址
gen(jmp,0,0); // block开始时首先写下一句跳转指令,地址到后面再补

if(lev>levmax) // 嵌套层数太大
{
error(32);
}

do // 开始处理声明部分
{
if(sym==constsym) // 常量
{
getsym();

do
{
constdeclaration();// 常量声明
while(sym==comma) // 逗号
{
getsym();
constdeclaration();// 逗号后面继续常量声明
}

if(sym==semicolon) // 分号
{
getsym();
}
else
{
error(5);
}
} while(sym==ident);
}

if(sym==varsym) // 变量
{
getsym();
do
{
vardeclaration(); // 变量声明
while(sym==comma) // 逗号
{
getsym();
vardeclaration();// 逗号后面继续声明变量
}

if(sym==semicolon) // 分号
{
getsym();
}
else
{
error(5);
}
} while(sym==ident);
}

while(sym==procsym) // 过程
{
getsym();
if(sym==ident) // 标识符
{
enter(proc); // 将过程登记进符号表
getsym();
}
else
{
error(4);
}

if(sym==semicolon) // 分号
{
getsym();
}
else
{
error(5);
}

lev=lev+1; // 层级加1
tx1=tx; // 记录当前层级
dx1=dx; // 记录当前数据指针
block(fsys|semicolon); // 处理block
lev=lev-1;
tx=tx1;
dx=dx1; // 恢复

if(sym==semicolon) // 分号
{
getsym();
test(statbegsys|ident|procsym,fsys,6);
// 检查当前 token 是否合法,不合法 则用 fsys 恢复语法分析同时抛 6 号错
}
else
{
error(5);
}
}

test(statbegsys|ident,declbegsys,7);
// 检查当前状态是否合法,不合法则用声明开 始符号作出错恢复、抛 7 号错
} while(sym&declbegsys);

code[table[tx0].addr].a=cx; // 把block开头写下的跳转指令的地址补上
table[tx0].addr=cx; // tx0的符号表存的是当前block的参数
cx0=cx;
gen(Int,0,dx);
statement(fsys|semicolon|endsym);
gen(opr,0,0); // return
test(fsys,0,8);
//listcode(cx0);
}

//---------------------------------
//-------------通过静态链求出数据区基地址
//---------------------------------

long base(long b, long l)
{
long b1;

b1=b;

while (l>0) // 根据层级差来找到基地址
{
b1=s[b1]; l=l-1;
}

return b1;
}

//---------------------------------
//-------------指令集解释器
//---------------------------------

void interpret()
{
long p,b,t; // 程序寄存器PC、基地址寄存器、栈顶寄存器
instruction i; // 指令寄存器

printf("start PL/0\n");
t=0; b=1; p=0;
s[1]=0; s[2]=0; s[3]=0;

do
{
i=code[p]; p=p+1; // 每次在code表中读取一条指令

switch(i.f)
{
case lit: // 常数指令
t=t+1; s[t]=i.a;
break;

case opr: // 运算指令
switch(i.a)
{
case 0: // 返回指令
t=b-1; p=s[t+3]; b=s[t+2];
break;

case 1: // 负号
s[t]=-s[t];
break;

case 2: // 加法
t=t-1; s[t]=s[t]+s[t+1];
break;

case 3: // 减法
t=t-1; s[t]=s[t]-s[t+1];
break;

case 4: // 乘法
t=t-1; s[t]=s[t]*s[t+1];
break;

case 5: // 除法
t=t-1; s[t]=s[t]/s[t+1];
break;

case 6: // odd
s[t]=s[t]%2;
break;

case 8: // ==
t=t-1; s[t]=(s[t]==s[t+1]);
break;

case 9: // !=
t=t-1; s[t]=(s[t]!=s[t+1]);
break;

case 10: // <
t=t-1; s[t]=(s[t]<s[t+1]);
break;

case 11: // >=
t=t-1; s[t]=(s[t]>=s[t+1]);
break;

case 12: // >
t=t-1; s[t]=(s[t]>s[t+1]);
break;

case 13: // <=
t=t-1; s[t]=(s[t]<=s[t+1]);
}
break;

case lod: // 调用变量值指令
t=t+1; s[t]=s[base(b,i.l)+i.a];
break;

case sto: // 将值存入变量指令
s[base(b,i.l)+i.a]=s[t]; printf("%10d\n", s[t]); t=t-1;
break;

case cal: // 过程调用,产生新的块标记
s[t+1]=base(b,i.l);
s[t+2]=b;
s[t+3]=p; // 记录返回地址等参数
b=t+1; p=i.a;
break;

case Int: // 开内存空间
t=t+i.a;
break;

case jmp: // 无条件跳转指令
p=i.a;
break;

case jpc: // 栈顶为0跳转
if(s[t]==0)
{
p=i.a;
}
t=t-1;
}
} while(p!=0);
printf("end PL/0\n");
}

//---------------------------------
//-------------PL/0编译器主函数
//---------------------------------

int main()
{
long i;

//-------------初始化

for(i=0; i<256; i++)
{
ssym[i]=nul;
}

strcpy(word[0], "begin ");// 保留字
strcpy(word[1], "call ");
strcpy(word[2], "const ");
strcpy(word[3], "do ");
strcpy(word[4], "end ");
strcpy(word[5], "if ");
strcpy(word[6], "odd ");
strcpy(word[7], "procedure ");
strcpy(word[8], "then ");
strcpy(word[9], "var ");
strcpy(word[10], "while ");

wsym[0]=beginsym; // 保留字对应的symbol类型表
wsym[1]=callsym;
wsym[2]=constsym;
wsym[3]=dosym;
wsym[4]=endsym;
wsym[5]=ifsym;
wsym[6]=oddsym;
wsym[7]=procsym;
wsym[8]=thensym;
wsym[9]=varsym;
wsym[10]=whilesym;

ssym['+']=plus; // 符号对应的symbol类型表
ssym['-']=minus;
ssym['*']=times;
ssym['/']=slash;
ssym['(']=lparen;
ssym[')']=rparen;
ssym['=']=eql;
ssym[',']=comma;
ssym['.']=period;
ssym[';']=semicolon;

strcpy(mnemonic[lit],"LIT"); // 中间代码助记符表
strcpy(mnemonic[opr],"OPR");
strcpy(mnemonic[lod],"LOD");
strcpy(mnemonic[sto],"STO");
strcpy(mnemonic[cal],"CAL");
strcpy(mnemonic[Int],"INT");
strcpy(mnemonic[jmp],"JMP");
strcpy(mnemonic[jpc],"JPC");

declbegsys=constsym|varsym|procsym;// 声明开始符号集合
statbegsys=beginsym|callsym|ifsym|whilesym;// 表达式开始符号集合
facbegsys=ident|number|lparen; // factor开始符号集合

printf("please input source program file name: ");
scanf("%s",infilename);
printf("\n");

if((infile=fopen(infilename,"r"))==NULL)
{
printf("File %s can't be opened.\n", infilename);
exit(1);
}


//-------------开始语法分析

err=0;
cc=0;
cx=0;
ll=0; // 各个计数器初始化
ch=' '; // 为第一次读取字符作初始化
kk=al;
getsym();
lev=0; tx=0;
block(declbegsys|statbegsys|period);

if(sym!=period) // 点
{
error(9);
}

//-------------语法分析完成

if(err==0) // 程序无错误则开始解释执行
{
// interpret();
listcode(0);
}
else
{
printf("errors in PL/0 program\n");
}

fclose(infile);

return (0);
}

PL/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
50
51
52
53
54
55
56
57
58
59
please input source program file name: test1.pl0

0 const m=7, n=85;
1 var x,y,z,q,r;
1 procedure multiply;
1 var a,b;
2 begin
3 a:=x; b:=y; z:=0;
9 while b>0 do
13 begin
13 if odd b then z:=z+a;
20 a:=2*a; b:=b/2;
28 end
28 end;
30 begin
31 x:=m; y:=n;
35 call multiply;
36 end.

中间代码:
0 JMP 0 30
以下为procedure multiply部分的中间代码:
1 JMP 0 2
2 INT 0 5
3 LOD 1 3
4 STO 0 3
5 LOD 1 4
6 STO 0 4
7 LIT 0 0
8 STO 1 5
9 LOD 0 4
10 LIT 0 0
11 OPR 0 12
12 JPC 0 29
13 LOD 0 4
14 OPR 0 6
15 JPC 0 20
16 LOD 1 5
17 LOD 0 3
18 OPR 0 2
19 STO 1 5
20 LIT 0 2
21 LOD 0 3
22 OPR 0 4
23 STO 0 3
24 LOD 0 4
25 LIT 0 2
26 OPR 0 5
27 STO 0 4
28 JMP 0 9
29 OPR 0 0
以下为主程序部分的中间代码:
30 INT 0 8
31 LIT 0 7
32 STO 0 3
33 LIT 0 85
34 STO 0 4
35 CAL 0 2
36 OPR 0 0

把源码完整地过了一遍之后,感觉确实对编译的整个过程有了更清晰的理解。

整个编译器的编译过程是从上到下,一次完成。


首先程序的开始部分对各项参数进行了初始化,完成之后即根据PL/0语言的文法定义开始语法分析。仔细阅读这里的这段代码可以比较深刻地感受到写编译器之前有个清晰明确的文法定义是多么重要。

写编译器代码时可以把每一条文法定义都写成一个函数,以方便递归调用来完成语法分析

语法分析的基础是词法分析,词法分析即程序中的getsym(),每次完成一段字符的读取,处理得到一个token。根据token的不同属性判断,将其登录进符号表或完成不同的语法功能。

这个编译器的中间代码生成是在语法分析的过程中完成的:

在factor中完成常量的lit或变量的lod,在term中完成乘除的opr,exp中完成加减和负号的opr,cond中完成逻辑运算的opr,stmt中完成赋值sto、过程调用cal、if以及while的跳转jmpjpc,block中完成程序运行跳转jmp和开栈空间int

中间代码使用层级差而不是层级的原因是数据栈中需要一级一级向底部找。

中间代码生成结束后,这段代码还给出了一个解释器用来运行得到的中间代码。

用到的几个特殊结构:

  • 中间代码存储数组code以及代码分配指针cx
1
2
3
4
5
6
7
8
typedef struct
{
enum fct f;
long l;
long a;
} instruction;
instruction code[cxmax+1];
long cx;

cx用来表示下一条生成的中间代码要放到存储数组的哪个位置。

  • 符号表table以及符号表指针tx
1
2
3
4
5
6
7
8
9
10
11
12
13
enum object
{
constant, variable, proc
};
struct
{
char name[al+1];
enum object kind;
long val;
long level;
long addr;
}table[txmax+1];
long tx;

符号表中存放三种类型的token,常量、变量以及代码块。

常量直接记录下val即可,处理成中间代码是直接用lit调取数值的;

变量需要记录下level和addr,处理成中间代码时需要用到litstolod

代码块是进入时addr中先存下当前的cx,代码块的第一条指令都是jmp,之后可能会有常量定义或者其他代码块先生成了代码,结束后需要把jmp指令的跳转地址给补上(即此时的cx),然后addr再重新存一遍cx,这个时候表示存下当前代码块的执行起始位置

  • 数据分配指针dx

dx在语法分析的过程中是用来记录下当前代码块需要开辟的栈空间数,以在生成block代码时,用int开辟栈空间。

这些的具体作用还要再看一下解释器的运行过程。


本文生成的中间代码就是一种类似汇编的语言,用到的运行寄存器有4个:

1
2
3
4
long p;                            // 程序指针寄存器,即汇编中的PC,标识当前执行到哪条指令
long b; // 基地址寄存器,保存的是当前程序块在栈中占用空间的最低位的地址
long t; // 栈顶指针寄存器,即汇编中的SP
instruction i; // 指令寄存器,根据p读出来的一条指令会首先放在i中

jmp:直接改变p寄存器的内容即可

jpc:判断栈顶数据是否为零,再决定是否改变p的内容

lit:栈顶指针+1,将常数放到栈顶

int:栈顶指针+要开的空间数,即先把栈顶指针上移,空出需要的变量空间来

cal:过程调用,调用时首先要把栈顶的3个空间用来存放跳转参数,s[t+1]中存放前一个层级的基地址位置,s[t+2]中存放当前的静态基地址b,s[t+3]中存放当前的程序指针p。s[t+1]这个位置是像链表一样指向前一个层级的基地址位置,以应用层级差来找到变量的存储位置。

lodsto:这里主要是需要用s[base(b,i.l)+i.a]动态基地址以及层级差来计算出对应变量在整个栈中的位置,然后与栈顶元素进行交互。

opr:运算符操作,对栈顶1个或2个元素进行操作,结果仍然存回栈顶。

opr 0 0:这个操作是过程调用的返回操作,需要将3个参数恢复回去,首先把t恢复为b-1即原来的栈顶,p恢复为s[t+3],b恢复为s[t+2]

过程调用这部分感觉还可以作一些改进。

PL/0编译器的拓展

花了好大的精力终于是把PL/0整个编译器的源码解读了一遍,接下来就是上手对这个编译器进行拓展的过程了。

另开一篇写拓展:编译原理课设尝试(二)——PL/0编译器改写

0%