半路起步，继续学习编译原理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编译器的执行过程

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

PL/0编译器源码注释

pl0.h

#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

// 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编译器源码分析

对上面的源码进行编译，再用一个示例程序进行测试可得到如下结果：

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的跳转jmp、jpc，block中完成程序运行跳转jmp和开栈空间int。

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

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

用到的几个特殊结构：

中间代码存储数组code以及代码分配指针cx

typedef struct
{
    enum fct f;
    long l;
    long a;
} instruction;
instruction code[cxmax+1];
long cx;

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

符号表table以及符号表指针tx

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，处理成中间代码时需要用到lit、sto、lod；

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

数据分配指针dx

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

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

本文生成的中间代码就是一种类似汇编的语言，用到的运行寄存器有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]这个位置是像链表一样指向前一个层级的基地址位置，以应用层级差来找到变量的存储位置。

lod、sto：这里主要是需要用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编译器改写

Chenfan Blog

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