编译原理PL/0语言的语法描述分程序程序一►分程序分程序语法描述图表达式语法描述1、PL/0语言文法的EBNF （巴克斯■瑙尔范式）表示〈表达式〉：:=[+i-]〈项〉｛〈加法运算符〉〈项〉｝〈项〉：:=〈因子〉｛〈乘法运算符〉〈因子〉｝〈因子〉：：=〈标识符〉i〈无符号整数〉i '（‘〈表达式〉'）‘ 〈加法运算符〉：：=+i-〈乘法运算符〉：：=*i/〈关系运算符〉：:==i#ii>=〈条件语句〉：：=IF〈条件〉THEN〈语句〉〈过程调用语句〉：:=CALL〈标识符〉〈当型循环语句〉::=WHILE〈条件〉DO〈语句〉〈读语句〉：:=READ '（'〈标识符〉｛，〈标识符〉｝'）'〈写语句〉：:=WRITE '（‘〈表达式〉｛，〈表达式〉｝'）' 〈字母〉：:=a|b|...|X|Y|Z〈数字〉：:=0山...|8|92、PL/0编译程序的结构PL/0语言可以看成PASCAL语言的子集，它的编译程序是一个编译解释执行系统PL/0 的目标程序为假想栈式计算机的汇编语言，与具体计算机无关PL/0的编译程序和目标程序的解释执行程序都是用PASCAL语言书写的，因此PL/0语 言可在配备PASCAL语言的任何机器上实现。
其编译过程采用一趟扫描方式，以语法分析程序为核心，词法分析和代码生成程序都作 为一个独立的过程，当语法分析需要读单词时就调用词法分析程序，而当语法分析正确需要 生成相应的目标代码时，则调用代码生成程序用表格管理程序建立变量、常量和过程表示符的说明与引用之间的信息联系用出错处理程序对词法和语法分析遇到的错误给出在源程序中出错的位置和错位性质 当源程序编译正确时，PL/0编译程序自动调用解释执行程序，对目标代码进行解释执 行，并按用户程序的要求输入数据和输出运行结果PL4）源程序表格管理程序VVFl标弄序岀错处理程序PL/O语h目标程序PMO蛊言解澤执方殍序转入敌据内的中文表不子序或讨稈— ＞表示数据盘►表示调用天系PL/O语言使用PASCAL语言书写的，整个编译程序（包含主程序）是由18个嵌套机并 列的过程或函数组成函数功能说明表：过程或函数名 功能简要说明pio主程序error出错处理，打印出错位置和错误编码getsym词法分析，读取一个单词getch漏掉空格，读取一个字符gen生成目标代码，并送入目标程序区test测试当前单词符是否合法block分析程序处理过程enter登录名字表position（函数）查找标识符在名字表中的位置constdeclaration常量定义处理vardeclaration变量定义处理listcode列出目标代码清单statement语句部分处理expression表达式处理term项处理factor因子处理condition条件处理interpret对目标代码的解释执行程序base（函数）通过静态链求出数据区的基地址过程或函数的嵌套定义结构pioerrorgetsymgetdigmtestblockenterposition(函数) constdeclaration var declaration listcode statementinterpretbase (B Sil)语法分析过程BLOCK是整个编译过程的核心。
编译程序的总体流程如下图:当前单词是否\ N 为療程序的结 V—► 出错 .束符/►打印错误一週用解释过桿INTERPRET 解释执行目标程序3、PL/0编译程序的词法分PL/O的词法分析程序GETSYM是一个独立的过程，其基本功能是为语法分析提供单词, 是语法分析的基础，他把输入的字符串形式的源程序分割成一个个单词符号为此PL/0编 译程序设置了三个全程量的公用单元：SYM:存放每个单词的类别，用内部编码形式表示ID：存放用户所定义的标识符的值及标识符字符串的机内表示NUM：存放用户定义的数单词的种类有五种：基本字：也称为保留字，如BEGIN，END，IF，THEN等运算符：如+、-、*、/、：=、#、＞=、v=等标识符：用户定义的变量名、常数名、过程名常数：如10，25，100等整数界符：如,、.、；（、）等如果把基本字、运算符、界符称为语言固有的单词，而对标识符、常数称为用户定义的 单词那么经词法分析程序分出的单词，对语言固有的单词只给出类别存放在SYM中，而 对用户定义的单词既给出类别又给值，其类别放在SYM中，值放在ID或NUM中，全部 单词种类由编译程序定义的纯量类型SYMBOL给出。
词法分析程序GETSYM将完成下列任务:（1） 空格；（2） 识别保留字；（3） 识别标识符；（4） 拼数；（5） 拼复合词，如： >=、：=、<=等单词；（6） 输出源程序在GETSYM中要调用GETCH,其功能是取字符其过程框图如下:C返回）说明：CH：存放当前读取的字符，初值为空；LINE： 一维数组，其数组元素是字符，界对为1： 80用于读入一行字符的缓冲区；LL和CC：计数器，初值为0；A： —维数组，其数组元素是字符，界对1： 10；ID：同 A；WORD:保留字表，一维数组，数组元素为以字符为元素的一维数组（即字符串），界对为 1： 13，查找方式为二分法4、PL/0编译程序的语法分析语法分析的任务是识别由词法分析给出的单词符号序列在结构 上是否符合给定的文法规则PL/0编译程序的语法分析采用自顶向 下的递归子程序法：对应每个非终结符语法单元，编一个独立的处 理过程（或子程序）语法分析从读入第一个单词开始由非终结符'程序'即开始符 出发，沿语法描述图箭头方向进行分析当遇到非终结符时，调用相应的处理过程从语法描述图看也 就进入了一个语法单元，再沿单迁所进入的语法描述图的箭头方向 进行分析。
当遇到描述图中的终结符时，则判断当前读入的单词是否与图 中的终结符相匹配，若匹配，则执行相应的语义程序（就是翻译程 序），再读下一个单词继续分析遇到分支点时将当前的单词与分支点上的多个终结符逐个相比 较，若不匹配时可能是进入下一个非终结符语法单元或是出错如果一个PL/O语言的单词序列在整个语法分析中，都能逐个得到匹配，直到程序结束 符'•'这就说所输入的程序是正确的对于正确的语法分析作相应的语义翻译，最终得到 目标程序从PL/0的语法描述图可以清楚地看到，对PL/0语言进行语法分析时，各个非终结符语 法单元所对应的分析过程存在相互调用关系这种关系可以用图来描述语法分析主要有两大部分的功能：说明部分的分析与过程体的分析，均在BLOCK过程 中进行：BLOCK背DX, TK直初值，暂时保SC ODE 的下标指针CX值在TAELES中ONSTSY常量说明处理SVM=VARS变臺说明处理在TABLES中 登记过程容的归调用BLOCK,#^LEV+1N试S；是否为语句YM=PROCS在TABLED中反填过程体入口取单词GETSYM出错■ N <处理Y为吾句后跟主成开辟数据段指令IINTO A生成退出数据星指令OPB.O 0卿用列目标程序过程（1）说明部分的分析由于PL/0语言允许过程调用语句，且允许过程嵌套定义。
因此每个过程应有过程首部 以定义局部于它自己过程的常量、变量和过程符号，也称局部变量每个过程所定义的局部 变量只能供它自己和它自己定义的内部过程引用对于同层并列过程的调用关系是先定义的 可以被后定义的引用，反之则不行说明部分的处理任务就是对每个过程（包括主程序，也可以看成一个主过程）的说明对 象造名字表，填写所有层次（主程序为第0层，主程序定义的过程为第1层，随嵌套的深度 增加而层次数加大，PL/0最多允许3层）、标识符的属性和分配的相对位置等登录信息是 调用ENTER过程完成所造表放在全程量一维数组TABLE中，TABLE的元素为记录型数据TX为索引表的 指针，LEV给出层次，DX给出每层局部变量当前已分配到的相对位置，可称位地址指示器, 每说明完一个变量后DX加1例如，一个过程的说明部分为：TX0NAME:AKIND： CONSTANTVAL： 35NAME:BKIND： CONSTANTVAL： 49NAME:CKIND： VARIABLELEVEL： LEVADR:DXNAME:DKIND： VARIABLELEVEL： LEVADR:DX+1NAME:EKIND： VARIABLELEVEL： LEVADR:DX+2NAME:PKIND： PROCEDURELEVEL： LEVADR:SIZE： 4NAME:G111KIND： VARIABLE111LEVEL： LEV+1111ADR:DX111TX—在说明处理后TABLE标中的信息对于过程名的ADR域，是在过程体的目标代码生成const varA=35,B=49;C,D,E;procedure P;var G对其常量，变量和过程说明分析后，在TABLE表中的信息如表所示。
后反填过程体的入口地址例中在处理P过程的说明时对LEV就增加1在P过程中的变 量名的层次为LEV加1值后的值对过程还有一项数据SIZE，记录该过程所需要的数据空 间问题是如何保证过程的局部变量不被外层引用？（参看PL/0的实现代码）TABLE标的表头索引TX和层次单元LEV都以BLOCK的参数形式出现在主程序调 用BLOCK时参数值为0每个过程中变量的相对起始位置在BLOCK内之初值DX： =32）过程体的分析程序的主体是由语句构成的处理完过程的说明后就处理由语句组成的过程体，从语法 上要对语句逐句分析当语法正确时就生成相应语句功能的目标代码当遇到标识符的引用 时就调用POSITION函数查TABLE表，看是否有过正确的定义，若已有，则从表中取相应 的信息，供生成代码用，否则出错5、PL/0编译程序的目标代码结构和代码生成PL/0 编译程序所产生的目标代码是一个假想栈式计算机汇编语言，它不依赖于任何实 际计算机，其指令格式如下：fla其中f为功能码；1表示层次差，即变量或过程被引用的分程序与说明该变量或过程的 分程序之间的层次差；a的含义对不同的指令有所区别，可以是常数值、位移量、操作符代 码等。
目标指令有8条：1LIT0aa为常数a进栈2LODlal为调用层与说 明层的层差a为变量在所说明 层中的相对位置变量进栈3STOlal为调用层与说 明层的层差a为变量在所说明 层中的相对位置栈顶的内容给变量4CALlal为层差a为被调用过程的 目标程序入口地址调用过程5INT0aa为开辟的单兀个为被调用的过程在栈中数开辟数据区6JMP0 aa为转向地址无条件转移7JPC0 aa为转向地址栈顶布尔值非零时转移8OPRl al为层差a为操作符编码（见 附录 A 中 interpret）栈顶与次栈顶的内容进 行运算，结果放次栈顶编译程序的目标代码是分析程序体时生成的，在处理说明部分时并不生成代码，而当分 析程序体的每个语句时，当语法正确则调用目标代码生成过程生成与PL/O语句等价功能的 目标代码，直到编译正常结束PL/0语言的代码生成是由GEN完成GEN由三个参数，分别代表目标代码的功能码、 层差和位移量（或常数值、或操作符编码）生成的代码顺序放在数组CODE中CODE为 一维数组，数组元数为记录型数据的一条记录是一个目录指令CX为指令指针，由0开 始顺序增加目标代码的顺序是内层过程的排在前边，主程序的目标代码排在最后。
例：Run pl0 //运行 pl0 Input file? TEST //输入文件名为 TEST List object code? Y //是否要列出代码，回答 Y 下面试运行结果：const a=10 var b,c;Procedure p;beginend;c:=b+a;2int03〃在栈中开辟3个数据单兀3lod13〃第三个变量b进栈4lit010〃数值10进栈5opr02〃栈顶与次栈顶的兀素出栈并相加（+的编码是2），结果进栈6sto14〃栈顶兀素出栈，值给的四个变量7opr00〃退出（退出的编码是0）begin read(b);while b # 0 dobegincall p; write(2*c);read(b) endend8 int 0 5 〃在栈中开辟5个数据单兀9 opr 0 16 〃从屏幕上（提示符为？）读入一个数进栈10 sto 0 3 〃栈顶元素出栈，值给第三个变量b11 lod 0 3 〃第三个变量b进栈12 lit 0 0 //0 栈13 opr 0 9 〃判断栈顶兀素与次栈顶兀素是否相等，栈顶兀素出栈，〃结果给次栈顶兀素14 jpc 0 24 〃栈顶元素为true就结束15 cal 0 2 〃调用入口地址为2的过程16 lit 0 2 //2 进栈17 lod 0 4 〃第四个变量c进栈18 opr 0 4 〃栈顶兀素与次栈顶兀素相乘（乘法的编码是4）,栈顶兀素出栈,〃结果给次栈顶兀素19 opr 0 14 〃打印栈顶元素，出栈20 opr 0 15 〃打印还行21 opr 0 16 〃从屏幕上（提示符为？）读入一个数进栈22 sto 0 3 〃栈顶元素出栈，值给第三个变量b23 jmp 0 11 〃无条件转移到代码地址为11的地方24 opr 0 0 〃退出start pl0?224?428?0end plO6、PL/0编译程序的语法错误处理错误有：语法错误、语义错误以及运行错误。
PL/0编译程序对语法错误的处理采用两种办法：1、 对于一些易于校正的错误，如丢了逗号、分号等，则指出错误位置，并加以校正2、 对某些错误，编译程序难于确定校正的措施，为了使当前的错误不导致整个程序崩 溃，把错误尽量局限在一个局部的语法单位中这样就需跳过一些单词符号，直到读入一个 能使编译程序恢复正常语法分析的单词为止具体做法是：当语法分析进入某些关键字或终结符号集合为开始符号的语法单元时，在其入口或出口 调用一个测试程序TEST例如，语句的开始符是begin, if, while, cal, read, write,；说明的开 始符为var, const, procedure；因子的开始符是“ （”，ident, nui当语法分析进入这样的语法 单元前，可用测试程序检查当前单词符号是否属于他们开始符号的集合，若不是则出错由于PL/0编译程序是自顶而下的分析方法，一个语法单元分析程序调用别的语法单元I打印出错信息IIJ t£返回)SI： =S1+S2 HGETSYM1TEST测试过程有三个参数，其含义分别为：S1：当语法分析进入或退出某一语法单元 时当前单词符号应属于的集合，他可能是一个 语法单元的开始符号集合，也可能是一个语法 单元的后继符号集合。
S2 :在某一出错状态时，可恢复语法分析 继续工作的补充单词符号集合因为当语法分 析出错时，即当前单词符号不再集合S1中， 为了继续编译，需跳过后遍输入的一写单词符 号，直到当前输入的单词符号属于S1和S2其 和的分析程序时，以参数形式给出被调用的语法分析程序出口时合法的后继单词符号集合，在 出口处也调用测试程序若当前单词符号属于所给集合，则语法分析正确，否则出错PL/0文法非终结符的开始符号与后继符号集合表非终结符名开始符号集合后继符号集合分程序const var Procedure ident if call begin while read write・9语句ident call begin if while read write.;end条件odd + - ( ident numberthen do表达式+ - ( ident number.;rop end then do项ident number (.;)rop + - end then do因子ident number (.;)rop + - * / end then do=,#, <, <=, >, <=注：标中表示关系运算集合，如:n：出错信息编号。
例如，考察因子的语法分析在过程FACTOR的入口处调用一次TEST过程，它的实参S1是因子开始符号集合S2 是每个过程的形参 FSYS 调用时实参的传递值当编译程序第一次调用 BLOCK 时， FSYS 的实参为［．］与说明开始符号和语句开始符号集合的和以后随着调用语法分析程序层次的 深入逐步增加如在调用语句时增加了［；］和［endsym］,在表达式语法分析中调用项时又增 加［+］和［-］，而在项中调用因子时又增加了［*］和［/］，这样在进入因子分析程序时即是当前符 号不是因子开始符，出错后只要跳过一定的符号，遇到当时输入的单词符号在FSYS中或在 因子开始符号集合中，均可继续正常进行语法分析在因子过程的出口处也调用了测试过程，不过这时S1和S2实参恰恰相反说明当时 的FSYS集合的单词符号都是因子正常出口时允许的单词符号而因子的开始符号为可恢复 正常语法分析的补充单词符号对于语义错误，如标识符没加说明就引用，或虽说明，但引用与说明的属性不一致这 时只给出错误信息与错误位置，编译程序继续执行7、PL/0编译程序的目标代码解释执行时的存储分配当编译程序经过语法分析，如果未发现错误时，由编译程序调用解释程序，对放在CODE 中的目标代码从CODE［0］开始进行解释执行。
当解释结束后，记录源程序中标示符的TABLE 表已经没有作用了，因此存储区只需要以数组CODE存放的只读目标代码程序和运行时的 数据区S，S是由解释程序定义的一维整型数组由于PL/0语言的目标代码是一种假想的 栈式计算机的汇编语言，用PASCAL语言解释执行，解释执行时的数据空间S为假栈式计 算机存储空间遵循后进先出规则，对每个过程当被调用时，才分配数据空间，退出程序时， 则所有分配的数据被释放解释程序定义了 4 个寄存器I：指令寄存器存放着当前正在执行的一条目标指令；P：程序地址寄存器指向下一条要执行的目标指令的地址（相当于CODE数组的下标）；T：栈顶寄存器由于每个过程当它运行时，给他分配的数据空间（数据段）可分为两 部分：静态部分包括变量存放区和三个联系单元（SL、DL、RA）；动态部分 作为临时工作单元和累加器使用需要随时分配，用完后立即释放栈顶寄 存器T指出了当前栈中最新分配单元B：基址寄存器指向每个过程被调用时，在数据区S中给它分配的数据段起始地址 为了实现对每个过程调用时给它分配数据段，也就是对即将运行的过程所需数据段进 栈；过程运行结束后释放数据段，即数据段退栈；以及嵌套过程之间对标识符引用的寻址问 题。
每个过程被调用时，在栈顶分配三个联系单元：SL静态链：它指向定义该过程的直接外接过程的数据段基地址；DL 动态链：它指向调用该过程前正在运行过程的数据段基地址；RA返回地址：记录调用该过程是目标程序的断点，即当时程序的地址寄存器P的值， 也就是调用过程指令的下一条指令的地址PL/0编译程序给变量分配的地址只是确定变量在数据段内的相对位置对每个过程从3 开始顺序增加 3以前的三个单元为上面指出的三个联系单元因此静态连接的作用是当一 个过程引用包围它的过程所定义的标识符时，首先沿静态链跳过个数为层差的数据段，找到 定义该标识符过程的数据段基地址，再加上所给标识符分配的相对位置，就得到该标识符在 整个数据栈中的绝对位置动态链和返回地址的作用是当一个过程结束后，为恢复调用该过 程前的执行状态而设置的例如，从后面的图中可以看出，当程序执行进入C过程后，在C中又调用B过程时， 数据取栈中的状况，这时过程B的静态链是指向过程A的基地址的，而不是指向C的基地 址因为过程B是由A定义的，他的名字在A层的名字表中，当在C过程中调用B过程时，层差为2,所以这时应沿C过程数据的静态链，跳过两个数据段后的基地址，才是当前调用 的B过程的静态链之值。
这里可以看出，不管B过程在何时被调用，它的数据段静态链总 是指向定义它的A过程的最新数据段基地址具体的过程调用和结束,对上述寄存器及三个联系单元的填写和恢复有下列目标指令完 成1）INT 0 A每个过程目标程序的入口都有这样一条指令，用以完成开辟数据段的工作A域的值指 出数据段的大小，即为局部变量个数+3（3个联系单元）由编译程序的代码生成给出开 辟数据段的结果是改变栈顶寄存器T的值，T： =T+A一： TDL •DL •SLDL *SL5lE朗局部变童— procccluic A；—proccdue C；■call B :B的局部变量call C ：call B :兰程序变屋区000call A-左対程序结构，上対运行吋数据栈变化情況（2） OPR 0 0是每个过程出口处的一条目标指令用已完成该过程运行结束后释放数据段的工作恢 复调用该过程前正在运行的过程的数据段基地址寄存器的值，和栈顶寄存器的值，并将返回 地址送到指令地址寄存器P中，以使调用前的程序从断点开始继续执行3） CAL L A为调用过程的目标指令，其中：L为层差，他是寻找静态链的依据在解释过程中有 base函数来计算；A为被调用过程的目标程序入口。
CALL指令还完成填写静态链、动态链、 返回地址，给出被调用过程的基地址值，送入基地址寄存器B,目标程序的入口地址A的 值送指令地址寄存器P中，式指令从A开始执行。