当前位置:文档之家› PL0 编译原理词法语法分析介绍

PL0 编译原理词法语法分析介绍

PL0  编译原理词法语法分析介绍
PL0  编译原理词法语法分析介绍

PL/0语言是Pascal语言的一个子集,我们这里分析的PL/0的编译程序包括了对PL/0语言源程序进行分析处理、编译生成类PCODE 代码,并在虚拟机上解释运行生成的类PCODE代码的功能。

PL/0语言编译程序采用以语法分析为核心、一遍扫描的编译方法。词法分析和代码生成作为独立的子程序供语法分析程序调用。语法分析的同时,提供了出错报告和出错恢复的功能。在源程序没有错误编译通过的情况下,调用类PCODE解释程序解释执行生成的类PCODE代码。

词法分析子程序分析:

词法分析子程序名为getsym,功能是从源程序中读出一个单词符号(token),把它的信息放入全局变量sym、id和num中,语法分析器需要单词时,直接从这三个变量中获得。(注意!语法分析器每次用完这三个变量的值就立即调用getsym子程序获取新的单词供下一次使用。而不是在需要新单词时才调用getsym过程。)getsym过程通过反复调用getch子过程从源程序过获取字符,并把它们拼成单词。getch过程中使用了行缓冲区技术以提高程序运行效率。

词法分析器的分析过程:调用getsym时,它通过getch过程从源程序中获得一个字符。如果这个字符是字母,则继续获取字符或数字,最终可以拼成一个单词,查保留字表,如果查到为保留字,则把sym 变量赋成相应的保留字类型值;如果没有查到,则这个单词应是一个用户自定义的标识符(可能是变量名、常量名或是过程的名字),把

sym臵为ident,把这个单词存入id变量。查保留字表时使用了二分法查找以提高效率。如果getch获得的字符是数字,则继续用getch 获取数字,并把它们拼成一个整数,然后把sym臵为number,并把拼成的数值放入num变量。如果识别出其它合法的符号(比如:赋值号、大于号、小于等于号等),则把sym则成相应的类型。如果遇到不合法的字符,把sym臵成nul。

语法分析子程序分析:

语法分析子程序采用了自顶向下的递归子程序法,语法分析同时也根据程序的语意生成相应的代码,并提供了出错处理的机制。语法分析主要由分程序分析过程(block)、常量定义分析过程(constdeclaration)、变量定义分析过程(vardeclaration)、语句分析过程(statement)、表达式处理过程(expression)、项处理过程(term)、因子处理过程(factor)和条件处理过程(condition)构成。这些过程在结构上构成一个嵌套的层次结构。除此之外,还有出错报告过程(error)、代码生成过程(gen)、测试单词合法性及出错恢复过程(test)、登录名字表过程(enter)、查询名字表函数(position)以及列出类PCODE代码过程(listcode)作过语法分析的辅助过程。

由PL/0的语法图可知:一个完整的PL/0程序是由分程序和句号构成的。因此,本编译程序在运行的时候,通过主程序中调用分程序处理过程block来分析分程序部分(分程序分析过程中还可能会递归调用block过程),然后,判断最后读入的符号是否为句号。如果

是句号且分程序分析中未出错,则是一个合法的PL/0程序,可以运行生成的代码,否则就说明源PL/0程序是不合法的,输出出错提示即可。

下面按各语法单元分析PL/0编译程序的运行机制。

分程序处理过程:

语法分析开始后,首先调用分程序处理过程(block)处理分程序。过程入口参数臵为:0层、符号表位臵0、出错恢复单词集合为句号、声明符或语句开始符。进入block过程后,首先把局部数据段分配指针设为3,准备分配3个单元供运行期存放静态链SL、动态链DL和返回地址RA。然后用tx0记录下当前符号表位臵并产生一条jmp 指令,准备跳转到主程序的开始位臵,由于当前还没有知到主程序究竟在何处开始,所以jmp的目标暂时填为0,稍后再改。同时在符号表的当前位臵记录下这个jmp指令在代码段中的位臵。在判断了嵌套层数没有超过规定的层数后,开始分析源程序。首先判断是否遇到了常量声明,如果遇到则开始常量定义,把常量存入符号表。接下去用同样的方法分析变量声明,变量定义过程中会用dx变量记录下局部数据段分配的空间个数。然后如果遇到procedure保留字则进行过程声明和定义,声明的方法是把过程的名字和所在的层次记入符号表,过程定义的方法就是通过递归调用block过程,因为每个过程都是一个分程序。由于这是分程序中的分程序,因此调用block时需把当前的层次号lev加一传递给block过程。分程序声明部分完成后,即将

进入语句的处理,这时的代码分配指针cx的值正好指向语句的开始位臵,这个位臵正是前面的jmp指令需要跳转到的位臵。于是通过前面记录下来的地址值,把这个jmp指令的跳转位臵改成当前cx的位臵。并在符号表中记录下当前的代码段分配地址和局部数据段要分配的大小(dx的值)。生成一条int指令,分配dx个空间,作为这个分程序段的第一条指令。下面就调用语句处理过程statement分析语句。分析完成后,生成操作数为0的opr指令,用于从分程序返回(对于0层的主程序来说,就是程序运行完成,退出)。

常量定义过程:

通过循环,反复获得标识符和对应的值,存入符号表。符号表中记录下标识符的名字和它对应的值。

变量定义过程:

与常量定义类似,通过循环,反复获得标识符,存入符号表。符号表中记录下标识符的名字、它所在的层及它在所在层中的偏移地址。

语句处理过程:

语句处理过程是一个嵌套子程序,通过调用表达式处理、项处理、因子处理等过程及递归调用自己来实现对语句的分析。语句处理过程可以识别的语句包括赋值语句、read语句、write语句、call语句、if

语句、while语句。当遇到begin/end语句时,就递归调用自己来分析。分析的同时生成相应的类PCODE指令。

赋值语句的处理:

首先获取赋值号左边的标识符,从符号表中找到它的信息,并确认这个标识符确为变量名。然后通过调用表达式处理过程算得赋值号右部的表达式的值并生成相应的指令保证这个值放在运行期的数据栈顶。最后通过前面查到的左部变量的位臵信息,生成相应的sto指令,把栈顶值存入指定的变量的空间,实现了赋值操作。

read语句的处理:

确定read语句语法合理的前提下(否则报错),生成相应的指令:第一条是16号操作的opr指令,实现从标准输入设备上读一个整数值,放在数据栈顶。第二条是sto指令,把栈顶的值存入read语句括号中的变量所在的单元。

write语句的处理:

与read语句相似。在语法正确的前提下,生成指令:通过循环调用表达式处理过程分析write语句括号中的每一个表达式,生成相应指令保证把表达式的值算出并放到数据栈顶并生成14号操作的opr指令,输出表达式的值。最后生成15号操作的opr指令输出一个换行。

call语句的处理:

从符号表中找到call语句右部的标识符,获得其所在层次和偏移地址。然后生成相应的cal指令。至于调用子过程所需的保护现场等工作是由类PCODE解释程序在解释执行cal指令时自动完成的。

if语句的处理:

按if语句的语法,首先调用逻辑表达式处理过程处理if语句的条件,把相应的真假值放到数据栈顶。接下去记录下代码段分配位臵(即下面生成的jpc指令的位臵),然后生成条件转移jpc指令(遇0或遇假转移),转移地址未知暂时填0。然后调用语句处理过程处理then 语句后面的语句或语句块。then后的语句处理完后,当前代码段分配指针的位臵就应该是上面的jpc指令的转移位臵。通过前面记录下的jpc指令的位臵,把它的跳转位臵改成当前的代码段指针位臵。

begin/end语句的处理:

通过循环遍历begin/end语句块中的每一个语句,通过递归调用语句分析过程分析并生成相应代码。

while语句的处理:

首先用cx1变量记下当前代码段分配位臵,作为循环的开始位臵。然后处理while语句中的条件表达式生成相应代码把结果放在数据栈

顶,再用cx2变量记下当前位臵,生成条件转移指令,转移位臵未知,填0。通过递归调用语句分析过程分析do语句后的语句或语句块并生成相应代码。最后生成一条无条件跳转指令jmp,跳转到cx1所指位臵,并把cx2所指的条件跳转指令的跳转位臵改成当前代码段分配位臵。

表达式、项、因子处理:

根据PL/0语法可知,表达式应该是由正负号或无符号开头、由若干个项以加减号连接而成。而项是由若干个因子以乘除号连接而成,因子则可能是一个标识符或一个数字,或是一个以括号括起来的子表达式。根据这样的结构,构造出相应的过程,递归调用就完成了表达式的处理。把项和因子独立开处理解决了加减号与乘除号的优先级问题。在这几个过程的反复调用中,始终传递fsys变量的值,保证可以在出错的情况下跳过出错的符号,使分析过程得以进行下去。

逻辑表达式的处理:

首先判断是否为一元逻辑表达式:判奇偶。如果是,则通过调用表达式处理过程分析计算表达式的值,然后生成判奇指令。如果不是,则肯定是二元逻辑运算符,通过调用表达式处理过程依次分析运算符左右两部分的值,放在栈顶的两个空间中,然后依不同的逻辑运算符,生成相应的逻辑判断指令,放入代码段。

判断单词合法性与出错恢复过程分析:

本过程有三个参数,s1、s2为两个符号集合,n为出错代码。本过程的功能是:测试当前符号(即sym变量中的值)是否在s1集合中,如果不在,就通过调用出错报告过程输出出错代码n,并放弃当前符号,通过词法分析过程获取一下单词,直到这个单词出现在s1或s2集合中为止。

这个过程在实际使用中很灵活,主要有两个用法:

在进入某个语法单位时,调用本过程,检查当前符号是否属于该语法单位的开始符号集合。若不属于,则滤去开始符号和后继符号集合外的所有符号。

在语法单位分析结束时,调用本过程,检查当前符号是否属于调用该语法单位时应有的后继符号集合。若不属于,则滤去后继符号和开始符号集合外的所有符号。

通过这样的机制,可以在源程序出现错误时,及时跳过出错的部分,保证语法分析可以继续下去。

语法分析过程中调用的其它子过程相对比较简单,请参考源程序的注释。

类PCODE代码解释执行过程分析

这个过程模拟了一台可以运行类PCODE指令的栈式计算机。它拥有一个栈式数据段用于存放运行期数据、拥有一个代码段用于存放

类PCODE程序代码。同时还拥用数据段分配指针、指令指针、指令寄存器、局部段基址指针等寄存器。

解释执行类PCODE代码时,数据段存储分配方式如下:

对于源程序的每一个过程(包括主程序),在被调用时,首先在数据段中开辟三个空间,存放静态链SL、动态链DL和返回地址RA。静态链记录了定义该过程的直接外过程(或主程序)运行时最新数据段的基地址。动态链记录调用该过程前正在运行的过程的数据段基址。返回地址记录了调用该过程时程序运行的断点位臵。对于主程序来说,SL、DL和RA的值均臵为0。静态链的功能是在一个子过程要引用它的直接或间接父过程(这里的父过程是按定义过程时的嵌套情况来定的,而不是按执行时的调用顺序定的)的变量时,可以通过静态链,跳过个数为层差的数据段,找到包含要引用的变量所在的数据段基址,然后通过偏移地址访问它。

在过程返回时,解释程序通过返回地址恢复指令指针的值到调用前的地址,通过当前段基址恢复数据段分配指针,通过动态链恢复局部段基址指针。实现子过程的返回。对于主程序来说,解释程序会遇到返回地址为0的情况,这时就认为程序运行结束。

解释程序过程中的base函数的功能,就是用于沿着静态链,向前查找相差指定层数的局部数据段基址。这在使用sto、lod等访问局部变量的指令中会经常用到。

类PCODE代码解释执行的部分通过循环和简单的case判断不同的指令,做出相应的动作。当遇到主程序中的返回指令时,指令指针

会指到0位臵,把这样一个条件作为终至循环的条件,保证程序运行可以正常的结束。

以下源程序是以清华大学出版社《编译原理》中的源代码为基础作了少量改动而成。

程序在Turbo Pascal 7.0上编译运行通过。

********************************************************************* ***************

program pl0(fa,fa1,fa2); (* PL/0编译程序与代码生成解释运行程序*) (* PL/0 compiler with code generation *)

label 99; (* 声明出错跳转标记*)

(* 在Turbo Pascal 7.0中已不允许跨过程的GOTO转移,因此后面的GOTO语句均被我去除了,因此这里的label也没有意义了*) const (* 常量定义*)

norw = 13; (* of reserved words *) (* 保留字的个数*)

txmax = 100; (* length of identifier table *) (* 标识符表的长度(容量)*)

nmax = 14; (* max number of digits in numbers *) (* 数字允许的最长位数*)

al = 10; (* length of identifiers *) (* 标识符最长长度*) amax = 2047; (* maximum address *) (* 寻址空间*)

levmax = 3; (* max depth of block nesting *) (* 最大允许的块嵌套层数*)

cxmax = 200; (* size of code array *) (* 类PCODE目标代码数组长度(可容纳代码行数)*)

type (* 类型定义*)

symbol = (nul, ident, number, plus, minus, times, slash, oddsym,

eql, neq, lss, leq, gtr, geq, lparen, rparen, comma,

semicolon, period, becomes, beginsym, endsym, ifsym,

thensym, whilesym, writesym, readsym, dosym, callsym,

constsym, varsym, procsym); (* symobl类型标识了不同类型的词汇*)

alfa = packed array[1..al] of char; (* alfa类型用于标识符*)

object1 = (constant, variable, procedur); (* object1为三种标识符的类型*)

(* 原程序在此使用object作为类型名称,在支持面向对象的Turbo Pascal 7.0中编译不能通过*)

(* wirth used the word "procedure" there, whick won't work! *)

(* 上面一行是课本上的程序清单中的注释,说本程序的原作者Wirth在这里用了procedure这个词作为标识符类型,是不可以的。

事实上Wirth原本在这里用的词是prozedure,是可以的。*)

symset = set of symbol; (* symset是symbol类型的一个集合类型,可用于存放一组symbol *)

fct = (lit, opr, lod, sto, cal, int, jmp, jpc); (* fct类型分别标识类PCODE 的各条指令*)

instruction = packed record

f: fct; (* function code *)

l: 0..levmax; (* level *)

a: 0..amax; (* displacement addr *)

end; (* 类PCODE指令类型,包含三个字段:指令f、层差l和另一个操作数a *)

(*

lit 0, a load constant a

opr 0, a execute opr 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

*)

var (* 全局变量定义*)

fa: text; (* 文本文件fa用于列出源程序*)

fa1, fa2: text; (* 文本文件fa1用于列出类PCODE代码、fa2用于记录解释执行类PCODE代码的过程*)

listswitch: boolean; (* true set list object code *) (* 如果本变量臵true,程序编译后将为列出类PCODE代码,

否则不列出类PCODE代码*)

ch: char; (* last char read *) (* 主要用于词法分析器,存放最近一次从文件中读出的字符*)

sym: symbol; (* last symbol read *) (* 词法分析器输出结果之用,存放最近一次识别出来的token的类型*)

id: alfa; (* last identifier read *) (* 词法分析器输出结果之用,存放最近一次识别出来的标识符的名字*)

num: integer; (* last number read *) (* 词法分析器输出结果之用,存放最近一次识别出来的数字的值*)

cc: integer; (* character count *) (* 行缓冲区指针*)

ll: integer; (* line length *) (* 行缓冲区长度*)

kk: integer; (* 引入此变量是出于程序性能考虑,见getsym过程注释*)

cx: integer; (* code allocation index *) (* 代码分配指针,代码生成模块总在cx所指位臵生成新的代码*)

line: array[1..81] of char; (* 行缓冲区,用于从文件读出一行,供词法分析获取单词时之用*)

a: alfa; (* 词法分析器中用于临时存放正在分析的词*)

code: array[0..cxmax] of instruction; (* 生成的类PCODE代码表,存放编译得到的类PCODE代码*)

word: array[1..norw] of alfa; (* 保留字表*)

wsym: array[1..norw] of symbol; (* 保留字表中每一个保留字对应的symbol类型*)

ssym: array[' '..'^'] of symbol; (* 一些符号对应的symbol类型表*)

(* wirth uses "array[char]" here *)

mnemonic: array[fct] of packed array[1..5] of char;(* 类PCODE指令助记符表*)

declbegsys, statbegsys, facbegsys: symset; (* 声明开始、表达式开始和项开始符号集合*)

table: array[0..txmax] of record (* 符号表*)

name: alfa; (* 符号的名字*)

case kind: object1 of (* 符号的类型*)

constant: (* 如果是常量名*)

(val: integer); (* val中放常量的值*)

variable, procedur: (* 如果是变量名或过程名*)

(level, adr, size: integer) (* 存放层差、偏移地址和大小*)

(* "size" lacking in orginal. I think it belons here *)

end;

fin, fout: text; (* fin文本文件用于指向输入的源程序文件,fout程序

中没有用到*)

fname: string; (* 存放PL/0源程序文件的文件名*)

(* 我修改的代码:原程序在此处使用alfa类型,无法在Turbo Pascal 7.0中通过,readln函数的参数不能为alfa型*)

err: integer; (* 出错总次数*)

(* 出错处理过程error *)

(* 参数:n:出错代码*)

procedure error(n: integer);

begin

writeln('****', ' ': cc-1, '!', n:2); (* 在屏幕cc-1位臵显示!与出错代码提示,由于cc

是行缓冲区指针,所以!所指位臵即为出错位臵*)

writeln(fa1, '****', ' ': cc-1, '!', n:2); (* 在文件cc-1位臵输出!与出错代码提示*)

err := err + 1 (* 出错总次数加一*)

end (* error *);

(* 词法分析过程getsym *)

procedure getsym;

var

i, j, k: integer;

(* 读取原程序中下一个字符过程getch *)

procedure getch;

begin

if cc = ll then (* 如果行缓冲区指针指向行缓冲区最后一个字符就从文件读一行到行缓冲区*)

begin

if eof(fin) then (* 如果到达文件末尾*)

begin

write('Program incomplete'); (* 出错,退出程序*)

close(fa);

close(fa1);

close(fin);

halt(0);

{goto 99}

(* 我修改的代码,由于Turbo Pascal 7.0中不允许跨过程的goto,就只能用上面的方法退出程序了。*)

end;

ll := 0; (* 行缓冲区长度臵0 *)

cc := 0; (* 行缓冲区指针臵行首*)

write(cx: 4, ' '); (* 输出cx值,宽度为4 *)

write(fa1, cx: 4, ' '); (* 输出cx值,宽度为4到文件*)

while not eoln(fin) do (* 当未到行末时*)

begin

ll := ll + 1; (* 行缓冲区长度加一*)

read(fin, ch); (* 从文件读入一个字符到ch *)

write(ch); (* 在屏幕输出ch *)

write(fa1, ch); (* 把ch输出到文件*)

line[ll] := ch; (* 把读到的字符存入行缓冲区相应的位臵*)

end;

(* 可见,PL/0源程序要求每行的长度都小于81个字符*)

writeln;

ll := ll + 1; (* 行缓冲区长度加一,用于容纳即将读入的回车符CR *)

read(fin, line[ll]);(* 把#13(CR)读入行缓冲区尾部*)

read(fin, ch); (* 我添加的代码。由于PC上文本文件换行是以#13#10(CR+LF)表示的,

所以要把多余的LF从文件读出,这里放在ch变量中是由于ch变量的

值在下面即将被改变,把这个多余值放在ch中没有问题*)

writeln(fa1);

end;

cc := cc + 1; (* 行缓冲区指针加一,指向即将读到的字符*)

ch := line[cc] (* 读出字符,放入全局变量ch *)

end (* getch *);

begin (* getsym *)

while (ch = ' ') or (ch = #13) do (* 我修改的代码:这句原来是用于读一个有效的字符

(跳过读出的字符中多余的空格),但实际上还要跳

过多余的回车*) getch;

if ch in ['a'..'z'] then (* 如果读出的字符是一个字母,说明是保留字或标识符*)

begin

k := 0; (* 标识符缓冲区指针臵0 *)

repeat (* 这个循环用于依次读出源文件中的字符构成标识符*)

if k < al then (* 如果标识符长度没有超过最大标识符长度(如果超过,就取前面一部分,把多余的抛弃) *)

begin

k := k + 1;

a[k] := ch;

end;

getch (* 读下一个字符*)

until not (ch in ['a'..'z','0'..'9']); (* 直到读出的不是字母或数字,由此可知PL/0的标识符构成规则是:

以字母开头,后

面跟若干个字母或数字*)

if k >= kk then (* 如果当前获得的标识符长度大于等于kk *)

kk := k (* 令kk为当前标识符长度*)

else

repeat (* 这个循环用于把标识符缓冲后部没有填入相应字母或空格的空间用空格补足*)

a[kk] := ' ';

kk := kk - 1

until kk = k;

(* 在第一次运行这个过程时,kk的值为al,即最大标识符长度,如果读到的标识符长度小于kk,

就把a数组的后部没有字母的空间用空格补足。

这时,kk的值就成为a数组前部非空格字符的个数。以后再运行getsym时,如果读到的标识符长度大于等于kk,

就把kk的值变成当前标识符的长度。

这时就不必在后面填空格了,因为它的后面肯定全是空格。反之如果最近读到的标识符长度小于kk,那就需要从kk位臵向前,把超过当前标识长度的空间填满空格。

以上的这样一个逻辑,完全是出于程序性能的上考虑。其实完全可以简单的把a数组中a[k]元素以后的空间不管三七二十一全填空格。

*)

(* 下面开始二分法查找看读出的标识符是不是保留字之一*)

id := a; (* 最后读出标识符等于a *)

i := 1; (* i指向第一个保留字*)

j := norw; (* j指向最后一个保留字*)

repeat

k := (i + j) div 2; (* k指向中间一个保留字*)

if id <= word[k] then (* 如果当前的标识符小于k所指的保留字*)

j := k - 1; (* 移动j指针*)

if id >= word[k] then (* 如果当前的标识符大于k所指的保留字*)

i := k + 1 (* 移动i指针*)

until i > j; (* 循环直到找完保留字表*)

if i - 1 > j then (* 如果i - 1 > j表明在保留字表中找到相应的项,id中存的是保留字*)

sym := wsym[k] (* 找到保留字,把sym臵为相应的保留字值*) else

sym := ident (* 未找到保留字,把sym臵为ident类型,表示是标识符*)

end(* 至此读出字符为字母即对保留字或标识符的处理结束*) else (* 如果读出字符不是字母*)

if ch in ['0'..'9'] then (* 如果读出字符是数字*)

编译原理课程设计-词法语法分析器

编译原理课程设计Course Design of Compiling (课程代码3273526) 半期题目:词法和语法分析器 实验学期:大三第二学期 学生班级:2014级软件四班 学生学号:2014112218 学生姓名:何华均 任课教师:丁光耀 信息科学与技术学院 2017.6

课程设计1-C语言词法分析器 1.题目 C语言词法分析 2.内容 选一个能正常运行的c语言程序,以该程序出现的字符作为单词符号集,不用处理c语言的所有单词符号。 将解析到的单词符号对应的二元组输出到文件中保存 可以将扫描缓冲区与输入缓冲区合成一个缓冲区,一次性输入源程序后就可以进行预处理了 3.设计目的 掌握词法分析算法,设计、编制并调试一个词法分析程序,加深对词法分析原理的理解 4.设计环境(电脑语言环境) 语言环境:C语言 CPU:i7HQ6700 内存:8G 5.概要设计(单词符号表,状态转换图) 5.1词法分析器的结构 词法分析程序的功能:

输入:所给文法的源程序字符串。 输出:二元组(syn,token或sum)构成的序列。 词法分析程序可以单独为一个程序;也可以作为整个编译程序的一个子程序,当需要一个单词时,就调用此法分析子程序返回一个单词. 为便于程序实现,假设每个单词间都有界符或运算符或空格隔开,并引入下面的全局变量及子程序: 1) ch 存放最新读进的源程序字符 2) strToken 存放构成单词符号的字符串 3) Buffer 字符缓冲区 4)struct keyType 存放保留字的符号和种别 5.2待分析的简单词法 (1)保留字 break、case、char、const、int、do、while… (2)运算符和界符 = 、+、-、* 、/、%、,、;、(、)、?、# 5.3各种单词符号对应的种别码

编译原理语法分析实验报告

编译原理语法分析实验报告 - 班级:XXX 学号:XXX 姓名:XXX 年月日 1、摘要: 用递归子程序法实现对pascal的子集程序设计语言的分析程序 2、实验目的: 通过完成语法分析程序,了解语法分析的过程和作用 3、任务概述 实验要求:对源程序的内码流进行分析,如为文法定义的句子输出”是”否则输出”否”,根据需要处理说明语句填写写相应的符号表供以后代码生成时使用 4、实验依据的原理 递归子程序法是一种自顶向下的语法分析方法,它要求文法是LL(1)文法。通过对文法中每个非终结符编写一个递归过程,每个过程的功能是识别由该非终结符推出的串,当某非终结符的产生式有多个候选式时,程序能够按LL(1)形式唯一地确定选择某个候选式进行推导,最终识别输入串是否与文法匹配。 递归子程序法的缺点是:对文法要求高,必须满足LL(1)文法,当然在某些语言中个别产生式的推导当不满足LL(1)而满足LL(2)时,也可以采用多向前扫描一个符号的办法;它的另一个缺点是由于递归调用多,所以速度慢占用空间多,尽管这样,它还是许多高级语言,例如PASCAL,C等编译系统常常采用的语法分析方法。

为适合递归子程序法,对实验一词法分析中的文法改写成无左递归和无左共因子的,,,如下: <程序>?<程序首部><分程序>。 <程序首部>?PROGRAM标识符; <分程序>?<常量说明部分><变量说明部分><过程说明部分> <复合语句> <常量说明部分>?CONST<常量定义><常量定义后缀>;|ε <常量定义>?标识符=无符号整数 <常量定义后缀>?,<常量定义><常量定义后缀> |ε <变量说明部分>?VAR<变量定义><变量定义后缀> |ε <变量定义>?标识符<标识符后缀>:<类型>; <标识符后缀>?,标识符<标识符后缀> |ε <变量定义后缀>?<变量定义><变量定义后缀> |ε <类型>?INTEGER | LONG <过程说明部分>?<过程首部><分程序>;<过程说明部分后缀>|ε <过程首部>?PROCEDURE标识符<参数部分>; <参数部分>?(标识符: <类型>)|ε <过程说明部分后缀>?<过程首部><分程序>;<过程说明部分后缀>|ε <语句>?<赋值或调用语句>|<条件语句>|<当型循环语句>|<读语句> |<写语句>|<复合语句>|ε <赋值或调用语句>?标识符<后缀> <后缀>?:=<表达式>|(<表达式>)|ε <条件语句>?IF<条件>THEN<语句> <当型循环语句>?WHILE<条件>DO <语句> <读语句>?READ(标识符<标识符后缀>)

编译原理词法分析器语法分析器实验报告

编译技术 班级网络0802 学号3080610052姓名叶晨舟 指导老师朱玉全2011年 7 月 4 日

一、目的 编译技术是理论与实践并重的课程,而其实验课要综合运用一、二年级所学的多门课程的内容,用来完成一个小型编译程序。从而巩固和加强对词法分析、语法分析、语义分析、代码生成和报错处理等理论的认识和理解;培养学生对完整系统的独立分析和设计的能力,进一步培养学生的独立编程能力。 二、任务及要求 基本要求: 1.词法分析器产生下述小语言的单词序列 这个小语言的所有的单词符号,以及它们的种别编码和内部值如下表: 单词符号种别编码助记符内码值 DIM IF DO STOP END 标识符 常数(整)= + * ** , ( )1 2 3 4 5 6 7 8 9 10 11 12 13 14 $DIM $IF $DO $STOP $END $ID $INT $ASSIGN $PLUS $STAR $POWER $COMMA $LPAR $RPAR - - - - - - 内部字符串 标准二进形式 - - - - - - 对于这个小语言,有几点重要的限制: 首先,所有的关键字(如IF﹑WHILE等)都是“保留字”。所谓的保留字的意思是,用户不得使用它们作为自己定义的标示符。例如,下面的写法是绝对禁止的: IF(5)=x 其次,由于把关键字作为保留字,故可以把关键字作为一类特殊标示符来处理。也就是说,对于关键字不专设对应的转换图。但把它们(及其种别编码)预先安排在一张表格中(此表叫作保留字表)。当转换图识别出一个标识符时,就去查对这张表,确定它是否为一个关键字。 再次,如果关键字、标识符和常数之间没有确定的运算符或界符作间隔,则必须至少用一个空白符作间隔(此时,空白符不再是完全没有意义的了)。例如,一个条件语句应写为

编译原理-编写递归下降语法分析器

学号107 成绩 编译原理上机报告 名称:编写递归下降语法分析器 学院:信息与控制工程学院 专业:计算机科学与技术 班级:计算机1401班 姓名:叶达成 2016年10月31日

一、上机目的 通过设计、编制、调试一个递归下降语法分析程序,实现对词法分析程序所提供的单词序列进行语法检查和结构分析,掌握常用的语法分析方法。通过本实验,应达到以下目标: 1、掌握从源程序文件中读取有效字符的方法和产生源程序的内部表示文件的方法。 2、掌握词法分析的实现方法。 3、上机调试编出的词法分析程序。 二、基本原理和上机步骤 递归下降分析程序实现思想简单易懂。程序结构和语法产生式有直接的对应关系。因为每个过程表示一个非终结符号的处理,添加语义加工工作比较方便。 递归下降分析程序的实现思想是:识别程序由一组子程序组成。每个子程序对应于一个非终结符号。 每一个子程序的功能是:选择正确的右部,扫描完相应的字。在右部中有非终结符号时,调用该非终结符号对应的子程序来完成。 自上向下分析过程中,如果带回溯,则分析过程是穷举所有可能的推导,看是否能推导出待检查的符号串。分析速度慢。而无回溯的自上向下分析技术,当选择某非终结符的产生时,可根据输入串的当前符号以及各产生式右部首符号而进行,效率高,且不易出错。 无回溯的自上向下分析技术可用的先决条件是:无左递归和无回溯。 无左递归:既没有直接左递归,也没有间接左递归。 无回溯:对于任一非终结符号U的产生式右部x1|x2|…|x n,其对应的字的首终结符号两两不相交。 如果一个文法不含回路(形如P?+ P的推导),也不含以ε为右部的产生式,那么可以通过执行消除文法左递归的算法消除文法的一切左递归(改写后的文法可能含有以ε为右部的产生式)。 三、上机结果 测试数据: (1)输入一以#结束的符号串(包括+—*/()i#):在此位置输入符号串例如:i+i*i# (2)输出结果:i+i*i#为合法符号串 (3)输入一符号串如i+i*#,要求输出为“非法的符号串”。 程序清单: #include #include char str[50]; int index=0; void E(); //E->TX; void X(); //X->+TX | e void T(); //T->FY void Y(); //Y->*FY | e void F(); //F->(E) | i int main() /*递归分析*/ { int len; int m;

编译原理实验报告《LL(1)语法分析器构造》

《LL(1)分析器的构造》实验报告 一、实验名称 LL(1)分析器的构造 二、实验目的 设计、编制、调试一个LL(1)语法分析器,利用语法分析器对符号串的识别,加深对语法分析原理的理解。 三、实验内容和要求 设计并实现一个LL(1)语法分析器,实现对算术文法: G[E]:E->E+T|T T->T*F|F F->(E)|i 所定义的符号串进行识别,例如符号串i+i*i为文法所定义的句子,符号串ii+++*i+不是文法所定义的句子。 实验要求: 1、检测左递归,如果有则进行消除; 2、求解FIRST集和FOLLOW集; 3、构建LL(1)分析表; 4、构建LL分析程序,对于用户输入的句子,能够利用所构造的分析程序进行分析,并显示出分析过程。 四、主要仪器设备 硬件:微型计算机。 软件: Code blocks(也可以是其它集成开发环境)。 五、实验过程描述 1、程序主要框架 程序中编写了以下函数,各个函数实现的作用如下: void input_grammer(string *G);//输入文法G

//将文法G预处理得到产生式集合P,非终结符、终结符集合U、u, int eliminate_1(string *G,string *P,string U,string *GG);//消除文法G中所有直接左递归得到文法GG int* ifempty(string* P,string U,int k,int n);//判断各非终结符是否能推导为空 string* FIRST_X(string* P,string U,string u,int* empty,int k,int n);求所有非终结符的FIRST集 string FIRST(string U,string u,string* first,string s);//求符号串s=X1X2...Xn的FIRST集 string** create_table(string *P,string U,string u,int n,int t,int k,string* first);//构造分析表 void analyse(string **table,string U,string u,int t,string s);//分析符号串s 2、编写的源程序 #include #include #include using namespace std; void input_grammer(string *G)//输入文法G,n个非终结符 { int i=0;//计数 char ch='y'; while(ch=='y'){ cin>>G[i++]; cout<<"继续输入?(y/n)\n"; cin>>ch; } } void preprocess(string *G,string *P,string &U,string &u,int &n,int &t,int &k)//将文法G预处理产生式集合P,非终结符、终结符集合U、u, { int i,j,r,temp;//计数 char C;//记录规则中()后的符号 int flag;//检测到() n=t=k=0; for( i=0;i<50;i++) P[i]=" ";//字符串如果不初始化,在使用P[i][j]=a时将不能改变,可以用P[i].append(1,a) U=u=" ";//字符串如果不初始化,无法使用U[i]=a赋值,可以用U.append(1,a) for(n=0;!G[n].empty();n++) { U[n]=G[n][0]; }//非终结符集合,n为非终结符个数 for(i=0;i

编译原理 语法分析器 (java完美运行版)(精选.)

实验二语法分析器 一、实验目的 通过完成预测分析法的语法分析程序,了解预测分析法和递归子程序法的区别和联系。使学生了解语法分析的功能,掌握语法分析程序设计的原理和构造方法,训练学生掌握开发应用程序的基本方法。有利于提高学生的专业素质,为培养适应社会多方面需要的能力。 二、实验内容 ◆根据某一文法编制调试LL (1 )分析程序,以便对任意输入的符号串 进行分析。 ◆构造预测分析表,并利用分析表和一个栈来实现对上述程序设计语言的分 析程序。 ◆分析法的功能是利用LL(1)控制程序根据显示栈栈顶内容、向前看符号 以及LL(1)分析表,对输入符号串自上而下的分析过程。 三、LL(1)分析法实验设计思想及算法 ◆模块结构: (1)定义部分:定义常量、变量、数据结构。 (2)初始化:设立LL(1)分析表、初始化变量空间(包括堆栈、结构体、数组、临时变量等); (3)控制部分:从键盘输入一个表达式符号串; (4)利用LL(1)分析算法进行表达式处理:根据LL(1)分析表对表达式符号串进行堆栈(或其他)操作,输出分析结果,如果遇到错误则显示错误信息。

四、实验要求 1、编程时注意编程风格:空行的使用、注释的使用、缩进的使用等。 2、如果遇到错误的表达式,应输出错误提示信息。 3、对下列文法,用LL(1)分析法对任意输入的符号串进行分析:(1)E->TG (2)G->+TG|—TG (3)G->ε (4)T->FS (5)S->*FS|/FS (6)S->ε (7)F->(E) (8)F->i 输出的格式如下:

五、实验源程序 LL1.java import java.awt.*; import java.awt.event.*; import javax.swing.*; import javax.swing.table.DefaultTableModel; import java.sql.*; import java.util.Vector; public class LL1 extends JFrame implements ActionListener { /** * */ private static final long serialVersionUID = 1L; JTextField tf1; JTextField tf2; JLabel l; JButton b0; JPanel p1,p2,p3; JTextArea t1,t2,t3; JButton b1,b2,b3;

编译原理词法分析和语法分析报告+代码(C语言版)

词法分析 一、实验目的 设计、编制并调试一个词法分析程序,加深对词法分析原理的理解。 二、实验要求 2.1 待分析的简单的词法 (1)关键字: begin if then while do end 所有的关键字都是小写。 (2)运算符和界符 : = + - * / < <= <> > >= = ; ( ) # (3)其他单词是标识符(ID)和整型常数(SUM),通过以下正规式定义: ID = letter (letter | digit)* NUM = digit digit* (4)空格有空白、制表符和换行符组成。空格一般用来分隔ID、SUM、运算符、界符和关键字,词法分析阶段通常被忽略。 2.2 各种单词符号对应的种别码: 输入:所给文法的源程序字符串。 输出:二元组(syn,token或sum)构成的序列。 其中:syn为单词种别码; token为存放的单词自身字符串; sum为整型常数。 例如:对源程序begin x:=9: if x>9 then x:=2*x+1/3; end #的源文件,经过词法分析后输出如下序列: (1,begin)(10,x)(18,:=)(11,9)(26,;)(2,if)…… 三、词法分析程序的算法思想: 算法的基本任务是从字符串表示的源程序中识别出具有独立意义的单词符号,其基本思想是根据扫描到单词符号的第一个字符的种类,拼出相应的单词符号。

3.1 主程序示意图: 主程序示意图如图3-1所示。其中初始包括以下两个方面: ⑴关键字表的初值。 关键字作为特殊标识符处理,把它们预先安排在一张表格中(称为关键字表),当扫描程序识别出标识符时,查关键字表。如能查到匹配的单词,则该单词为关键字,否则为一般标识符。关键字表为一个字符串数组,其描述如下: Char *rwtab[6] = {“begin”, “if”, “then”, “while”, “do”, “end”,}; 图3-1 (2)程序中需要用到的主要变量为syn,token和sum 3.2 扫描子程序的算法思想: 首先设置3个变量:①token用来存放构成单词符号的字符串;②sum用来整型单词;③syn用来存放单词符号的种别码。扫描子程序主要部分流程如图3-2所示。

编译原理实验报告(语法分析器)

. 编译原理实验专业:13级网络工程

语法分析器1 一、实现方法描述 所给文法为G【E】; E->TE’ E’->+TE’|空 T->FT’ T’->*FT’|空 F->i|(E) 递归子程序法: 首先计算出五个非终结符的first集合follow集,然后根据五个产生式定义了五个函数。定义字符数组vocabulary来存储输入的句子,字符指针ch指向vocabulary。从非终结符E函数出发,如果首字符属于E的first集,则依次进入T函数和E’函数,开始递归调用。在每个函数中,都要判断指针所指字符是否属于该非终结符的first集,属于则根据产生式进入下一个函数进行调用,若first集中有空字符,还要判断是否属于该非终结符的follow集。以分号作为结束符。 二、实现代码 头文件shiyan3.h #include #include

#include using namespace std; #define num 100 char vocabulary[num]; char *ch; void judge_E(); void judge_EE(); void judge_T(); void judge_TT(); void judge_F(); 源文件 #include"shiyan3.h" void judge_E() { if(*ch==';') { cout<<"该句子符合此文法!"<

int a=0; cout<<"按1结束程序"<>a; if(a==1) exit(0); } else if(*ch=='('||*ch=='i') { judge_T(); judge_EE(); } else { cout<<"该句子不匹配此文法!"<>a; if(a==1) exit(0); }

编译原理词法分析和语法分析报告 代码(C语言版)

词法分析 三、词法分析程序的算法思想: 算法的基本任务是从字符串表示的源程序中识别出具有独立意义的单词符号,其基本思想是根据扫描到单词符号的第一个字符的种类,拼出相应的单词符号。 3.1 主程序示意图: 扫描子程序主要部分流程图 其他

词法分析程序的C语言程序源代码: // 词法分析函数: void scan() // 数据传递: 形参fp接收指向文本文件头的文件指针; // 全局变量buffer与line对应保存源文件字符及其行号,char_num保存字符总数。 void scan() { char ch; int flag,j=0,i=-1; while(!feof(fp1)) { ch=fgetc(fp1); flag=judge(ch); printf("%c",ch);//显示打开的文件 if(flag==1||flag==2||flag==3) {i++;buffer[i]=ch;line[i]=row;} else if(flag==4) {i++;buffer[i]='?';line[i]=row;} else if(flag==5) {i++;buffer[i]='~';row++;} else if(flag==7) continue; else cout<<"\n请注意,第"<

编译原理-语法分析-算符优先文法分析器

编译原理实验报告 实验名称:编写语法分析分析器实验类型: 指导教师: 专业班级: 学号: 电子邮件: 实验地点: 实验成绩:

一、实验目的 通过设计、编制、调试一个典型的语法分析程序,实现对词法分析程序所提供的单词序列进行语法检查和结构分析,进一步掌握常用的语法分析方法。 1、选择最有代表性的语法分析方法,如LL(1) 语法分析程序、算符优先分析程序和LR分析分析程序,至少选一题。 2、选择对各种常见程序语言都用的语法结构,如赋值语句(尤指表达式)作为分析对象,并且与所选语法分析方法要比较贴切。 二、实验过程 编写算符优先分析器。要求: (a)根据算符优先分析算法,编写一个分析对象的语法分析程序。读者可根据自己的能力选择以下三项(由易到难)之一作为分析算法中的输入: Ⅰ:通过构造算符优先关系表,设计编制并调试一个算法优先分析程序Ⅱ:输入FIRSTVT,LASTVT集合,由程序自动生成该文法的算符优先关系矩阵。 Ⅲ:输入已知文法,由程序自动生成该文法的算符优先关系矩阵。(b)程序具有通用性,即所编制的语法分析程序能够使用于不同文法以及各种输入单词串,并能判断该文法是否为算符文法和算符优先文法。 (c)有运行实例。对于输入的一个文法和一个单词串,所编制的语法分析程序应能正确地判断,此单词串是否为该文法的句子,并要求输出分析过程。 三、实验结果 算符优先分析器: 测试数据:E->E+T|T T->T*F|F F->(E)|i 实验结果:(输入串为i+i*i+i)

四、讨论与分析 自下而上分析技术-算符优先分析法: 算符文法:一个上下无关文法G,如果没有且没有P→..QR...(P ,Q ,R属于非终结符),则G是一个算符文法。 FIRSTVT集构造 1、若有产生式P →a...或P →Qa...,则a∈FIRSTVT(P)。 2、若有产生式P→...,则FIRSTVT(R)包含在FIRSTVT(P)中。由优先性低于的定义和firstVT集合的定义可以得出:若存在某个产生式:…P…,则对所有:b∈firstVT(P)都有:a≦b。 构造优先关系表: 1、如果每个非终结符的FIRSTVT和LASTVT集均已知,则可构造优先关系表。 2、若产生式右部有...aP...的形式,则对于每个b∈FIRSTVT(P)都有

编译原理LL(1)语法分析实验报告

学号20102798 专业软件工程姓名薛建东 实验日期2013.04.08 教师签字成绩实验报告 【实验名称】LL(1)语法分析 【实验目的】 通过完成预测分析法的语法分析程序,了解预测分析法和递归子程序法的区别和联系。使了解语法分析的功能,掌握语法分析程序设计的原理和构造方法,训练掌握开发应用程序的基本方法。 【实验内容】 ◆根据某一文法编制调试LL ( 1)分析程序,以便对任意输入的符号串进行分析。 ◆构造预测分析表,并利用分析表和一个栈来实现对上述程序设计语言的分析程序。 ◆分析法的功能是利用LL(1)控制程序根据显示栈栈顶内容、向前看符号以及LL(1) 分析表,对输入符号串自上而下的分析过程。 【设计思想】 (1)、LL(1)文法的定义 LL(1)分析法属于确定的自顶向下分析方法。LL(1)的含义是:第一个L表明自顶向下分析是从左向右扫描输入串,第2个L表明分析过程中将使用最左推导,1表明只需向右看一个符号便可决定如何推导,即选择哪个产生式(规则)进行推导。 LL(1)文法的判别需要依次计算FIRST集、FOLLOW集和SELLECT集,然后判断是否为LL(1)文法,最后再进行句子分析。 需要预测分析器对所给句型进行识别。即在LL(1)分析法中,每当在符号栈的栈顶出现非终极符时,要预测用哪个产生式的右部去替换该非终极符;当出现终结符时,判断其与剩余输入串的第一个字符是否匹配,如果匹配,则继续分析,否则报错。LL(1)分析方法要求文法满足如下条件:对于任一非终极符A的两个不同产生式A→α,A→β,都要满足下面条件:SELECT(A→α)∩SELECT(A→β)=? (2)、预测分析表构造 LL(1)分析表的作用是对当前非终极符和输入符号确定应该选择用哪个产生式进行推

编译原理LL(1)语法分析实验报告

学号 20102798 专业软件工程姓名薛建东 实验日期2013.04.08 教师签字成绩 实验报告 【实验名称】LL(1)语法分析 【实验目的】 通过完成预测分析法的语法分析程序,了解预测分析法和递归子程序法的区别和联系。使了解语法分析的功能,掌握语法分析程序设计的原理和构造方法,训练掌握开发应用程序的基本方法。 【实验内容】 ◆根据某一文法编制调试LL (1 )分析程序,以便对任意输入的符号串进行分析。 ◆构造预测分析表,并利用分析表和一个栈来实现对上述程序设计语言的分析程序。 ◆分析法的功能是利用LL(1)控制程序根据显示栈栈顶内容、向前看符号以及LL (1)分析表,对输入符号串自上而下的分析过程。 【设计思想】 (1)、LL(1)文法的定义 LL(1)分析法属于确定的自顶向下分析方法。LL(1)的含义是:第一个L表明自顶向下分析是从左向右扫描输入串,第2个L表明分析过程中将使用最左推导,1表明只需向右看一个符号便可决定如何推导,即选择哪个产生式(规则)进行推导。 LL(1)文法的判别需要依次计算FIRST集、FOLLOW集和SELLECT集,然后判断是否为LL(1)文法,最后再进行句子分析。 需要预测分析器对所给句型进行识别。即在LL(1)分析法中,每当在符号栈的栈顶出现非终极符时,要预测用哪个产生式的右部去替换该非终极符;当出现终结符时,判断其与剩余输入串的第一个字符是否匹配,如果匹配,则继续分析,否则报错。LL(1)分析方法要求文法满足如下条件:对于任一非终极符A的两个不同产生式A→α,A→β,都要满足下面条件:SELECT(A→α)∩SELECT(A→β)=? (2)、预测分析表构造 LL(1)分析表的作用是对当前非终极符和输入符号确定应该选择用哪个产生式进行推导。它的行对应文法的非终极符,列对应终极符,表中的值有两种:一是产生式的右部的字符串,一是null。若用M表示LL(1)分析表,则M可表示如下:

编译原理词法分析器

一、实验目的 了解词法分析程序的两种设计方法:1.根据状态转换图直接编程的方式;2.利用DFA 编写通用的词法分析程序。 二、实验内容及要求 1.根据状态转换图直接编程 编写一个词法分析程序,它从左到右逐个字符的对源程序进行扫描,产生一个个的单词的二元式,形成二元式(记号)流文件输出。在此,词法分析程序作为单独的一遍,如下图所示。 具体任务有: (1)组织源程序的输入 (2)拼出单词并查找其类别编号,形成二元式输出,得到单词流文件 (3)删除注释、空格和无用符号 (4)发现并定位词法错误,需要输出错误的位置在源程序中的第几行。将错误信息输出到屏幕上。 (5)对于普通标识符和常量,分别建立标识符表和常量表(使用线性表存储),当遇到一个标识符或常量时,查找标识符表或常量表,若存在,则返回位置,否则返回0并且填写符号表或常量表。 标识符表结构:变量名,类型(整型、实型、字符型),分配的数据区地址 注:词法分析阶段只填写变量名,其它部分在语法分析、语义分析、代码生成等阶段逐步填入。 常量表结构:常量名,常量值 2.编写DFA模拟程序 算法如下: DFA(S=S0,MOVE[][],F[],ALPHABET[]) /*S为状态,初值为DFA的初态,MOVE[][]为状态转换矩阵,F[] 为终态集,ALPHABET[] 为字母表,其中的字母顺序与MOVE[][] 中列标题的字母顺序一致。*/ { Char Wordbuffer[10]=“”//单词缓冲区置空 Nextchar=getchar();//读 i=0; while(nextchar!=NULL)//NULL代表此类单词 { if (nextcha r!∈ALPHABET[]){ERROR(“非法字符”),return(“非法字符”);} S=MOVE[S][nextchar] //下一状态 if(S=NULL)return(“不接受”);//下一状态为空,不能识别,单词错误 wordbuffer[i]=nextchar ;//保存单词符号 i++; nextchar=getchar(); } Wordbuffer[i]=‘\0’;

昆明理工大学 编译原理 实验二 语法分析器

昆明理工大学信息工程与自动化学院学生实验报告 (2011 —2012 学年第 1 学期) 课程名称:编译原理开课实验室: 445 2011年 12 月 19日年级、专业、 班 计科093 学号200910405310 姓名孙浩川成绩 实验项目名称语法分析器指导教师严馨 教 师评语 该同学是否了解实验原理: A.了解□ B.基本了解□ C.不了解□ 该同学的实验能力: A.强□ B.中等□ C.差□ 该同学的实验是否达到要求: A.达到□ B.基本达到□ C.未达到□ 实验报告是否规范: A.规范□ B.基本规范□ C.不规范□ 实验过程是否详细记录: A.详细□ B.一般□ C.没有□ 教师签名: 年月日 一、实验目的及内容 实验目的:编制一个语法分析程序,实现对词法分析程序所提供的单词序列进行语法检 查和结构分析。 实验内容:在上机(一)词法分析的基础上,采用递归子程序法或其他适合的语法分析方法,实现其语法分析程序。要求编译后能检查出语法错误。 已知待分析的C语言子集的语法,用EBNF表示如下: <程序>→main()<语句块> <语句块> →‘{’<语句串>‘}’ <语句串> → <语句> {; <语句> }; <语句> → <赋值语句> |<条件语句>|<循环语句> <赋值语句>→ID=<表达式>

<条件语句>→if‘(‘条件’)’<语句块> <循环语句>→while’(‘<条件>’)‘<语句块> <条件> → <表达式><关系运算符> <表达式> <表达式> →<项>{+<项>|-<项>} <项> → <因子> {* <因子> |/ <因子>} <因子> →ID|NUM| ‘(’<表达式>‘)’ <关系运算符> →<|<=|>|>=|==|!= 二、实验原理及基本技术路线图(方框原理图或程序流程图)

编译原理词法分析实验报告

词法分析器实验报告 一、实验目的 选择一种编程语言实现简单的词法分析程序,设计、编制并调试一个词法分析程序,加深对词法分析原理的理解。 二、实验要求 2、1 待分析的简单的词法 (1)关键字: begin if then while do end 所有的关键字都就是小写。 (2)运算符与界符 : = + - * / < <= <> > >= = ; ( ) # (3)其她单词就是标识符(ID)与整型常数(SUM),通过以下正规式定义: ID = letter (letter | digit)* NUM = digit digit* (4)空格有空白、制表符与换行符组成。空格一般用来分隔ID、SUM、运算符、界符与关键字,词法分析阶段通常被忽略。 2、2 各种单词符号对应的种别码: 表2、1 各种单词符号对应的种别码 2、3 词法分析程序的功能: 输入:所给文法的源程序字符串。 输出:二元组(syn,token或sum)构成的序列。 其中:syn为单词种别码; token为存放的单词自身字符串; sum为整型常数。 例如:对源程序begin x:=9: if x>9 then x:=2*x+1/3; end #的源文件,经过词法分析后输出如下序列: (1,begin)(10,x)(18,:=)(11,9)(26,;)(2,if)…… 三、词法分析程序的算法思想: 算法的基本任务就是从字符串表示的源程序中识别出具有独立意义的单词符号,其基本思想就是根据扫描到单词符号的第一个字符的种类,拼出相应的单词符号。 3、1 主程序示意图:

主程序示意图如图3-1所示。其中初始包括以下两个方面: ⑴ 关键字表的初值。 关键字作为特殊标识符处理,把它们预先安排在一张表格中(称为关键字表),当扫描程序识别出标识符时,查关键字表。如能查到匹配的单词,则该单词为关键字,否则为一般标识符。关键字表为一个字符串数组,其描述如下: Char *rwtab[6] = {“begin ”, “if ”, “then ”, “while ”, “do ”, “end ”,}; (2)3、2 扫描子程序的算法思想: 首先设置3个变量:①token 用来存放构成单词符号的字符串;②sum 用来整型单词;③syn 用来存放单词符号的种别码。扫描子程序主要部分流程如图3-2所示。

编译原理课程设计报告C语言词法与语法分析器的实现

编译原理课程设计报告 课题名称:编译原理课程设计 C-语言词法与语法分析器的实现

C-词法与语法分析器的实现 1.课程设计目标 (1)题目实用性 C-语言拥有一个完整语言的基本属性,通过编写C-语言的词法分析和语法分析,对于理解编译原理的相关理论和知识有很大的作用。通过编写C-语言词法和语法分析程序,能够对编译原理的相关知识:正则表达式、有限自动机、语法分析等有一个比较清晰的了解和掌握。(2)C-语言的词法说明 ①语言的关键字: else if int return void while 所有的关键字都是保留字,并且必须是小写。 ②专用符号: + - * / < <= > >= == != = ; , ( ) [ ] { } /* */ ③其他标记是ID和NUM,通过下列正则表达式定义: ID = letter letter* NUM = digit digit* letter = a|..|z|A|..|Z digit = 0|..|9 注:ID表示标识符,NUM表示数字,letter表示一个字母,digit表示一个数字。 小写和大写字母是有区别的。 ④空格由空白、换行符和制表符组成。空格通常被忽略。 ⑤注释用通常的c语言符号/ * . . . * /围起来。注释可以放在任何空白出现的位置(即注释不能放在标记)上,且可以超过一行。注释不能嵌套。

(3)程序设计目标 能够对一个程序正确的进行词法及语法分析。 2.分析与设计 (1)设计思想 a.词法分析 词法分析的实现主要利用有穷自动机理论。有穷自动机可用作描述在输入串中识别模式的过程,因此也能用作构造扫描程序。通过有穷自动机理论能够容易的设计出词法分析器。b.语法分析 语法分析采用递归下降分析。递归下降法是语法分析中最易懂的一种方法。它的主要原理是,对每个非终结符按其产生式结构构造相应语法分析子程序,其中终结符产生匹配命令,而非终结符则产生过程调用命令。因为文法递归相应子程序也递归,所以称这种方法为递归子程序下降法或递归下降法。其中子程序的结构与产生式结构几乎是一致的。 (2)程序流程图 程序主流程图: 词法分析: 语法分析:

编译原理语法分析器实验

语法分析器的设计 一、实验内容 语法分析程序用LL(1)语法分析方法。首先输入定义好的文法书写文件(所用的文法可以用LL(1)分析),先求出所输入的文法的每个非终结符是否能推出空,再分别计算非终结符号的FIRST集合,每个非终结符号的FOLLOW集合,以及每个规则的SELECT集合,并判断任意一个非终结符号的任意两个规则的SELECT 集的交集是不是都为空,如果是,则输入文法符合LL(1)文法,可以进行分析。对于文法: G[E]: E->E+T|T T->T*F|F F->i|(E) 分析句子i+i*i是否符合文法。 二、基本思想 1、语法分析器实现 语法分析是编译过程的核心部分,它的主要任务是按照程序的语法规则,从由词法分析输出的源程序符号串中识别出各类语法成分,同时进行词法检查,为语义分析和代码生成作准备。这里采用自顶向下的LL(1)分析方法。 语法分析程序的流程图如图5-4所示。 语法分析程序流程图 该程序可分为如下几步: (1)读入文法 (2)判断正误 (3)若无误,判断是否为LL(1)文法 (4)若是,构造分析表; (5)由句型判别算法判断输入符号串是为该文法的句型。 三、核心思想 该分析程序有15部分组成: (1)首先定义各种需要用到的常量和变量;

(2)判断一个字符是否在指定字符串中; (3)读入一个文法; (4)将单个符号或符号串并入另一符号串; (5)求所有能直接推出&的符号; (6)求某一符号能否推出‘& ’; (7)判断读入的文法是否正确; (8)求单个符号的FIRST; (9)求各产生式右部的FIRST; (10)求各产生式左部的FOLLOW; (11)判断读入文法是否为一个LL(1)文法; (12)构造分析表M; (13)句型判别算法; (14)一个用户调用函数; (15)主函数; 下面是其中几部分程序段的算法思想: 1、求能推出空的非终结符集 Ⅰ、实例中求直接推出空的empty集的算法描述如下: void emp(char c){ 参数c为空符号 char temp[10];定义临时数组 int i; for(i=0;i<=count-1;i++)从文法的第一个产生式开始查找 { if 产生式右部第一个符号是空符号并且右部长度为1, then将该条产生式左部符号保存在临时数组temp中 将临时数组中的元素合并到记录可推出&符号的数组empty中。 } Ⅱ、求某一符号能否推出'&' int _emp(char c) { //若能推出&,返回1;否则,返回0 int i,j,k,result=1,mark=0; char temp[20]; temp[0]=c; temp[1]='\0'; 存放到一个临时数组empt里,标识此字符已查找其是否可推出空字 如果c在可直接推出空字的empty[]中,返回1 for(i=0;;i++) { if(i==count) return(0); 找一个左部为c的产生式 j=strlen(right[i]); //j为c所在产生式右部的长度 if 右部长度为1且右部第一个字符在empty[]中. then返回1(A->B,B可推出空) if 右部长度为1但第一个字符为终结符,then 返回0(A->a,a为终结符) else

编译原理词法分析及语法分析

编译原理 实验报告 实验名称:词法分析及语法分析专业班级: 姓名: 学号: 完成日期:

实验一、sample语言的词法分析 一、实验目的 给出SAMPLE文法规范,要求编写SAMPLE语言的词法分析程序。 二、实验准备 了解sample语言单词的定义,选择任一种编程语言实现词法分析。 三、实验内容 给出SAMPLE语言文法,输出单词(关键字、专用符号以及其它标记)。 1、格式 输入:源程序文件。输出:关键字、专用符号以及其它标记。 2、实现原理 程序中先判断这个句语句中每个单元为关键字、常数、运算符、界符,对与不同的单词符号给出不同编码形式的编码,用以区分之。 3、实验方法 读懂Sample源代码,自己重点独立实现对常量的判别。 四、实验设计 1、设计SAMPLE语言的词法分析器 A、字符集定义 1. <字符集> → <字母>│<数字>│<单界符> 2. <字母> → A│B│…│Z│a│b│…│z 3. <数字> → 0│1│2│…│9 4. <单界符> → +│-│*│/│=│<│>│(│)│[│]│:│. │; │, │' B、单词集定义 5.<单词集> → <保留字>│<双界符>│<标识符>│<常数>│<单界符> 6.<保留字> → and│array│begin│bool│call│case│char│constant│dim│do│else │end│false│for│if│input│integer│not│of│or│output│procedure│program │read│real│repeat│set│stop│then│to│true│until│var│while│write 7.<双界符> → <>│<=│>=│:= │/*│*/│.. 8.<标识符> → <字母>│<标识符> <数字>│<标识符> <字母> 9.<常数> → <整数>│<布尔常数>│<字符常数> 10.<整数> → <数字>│<整数> <数字> 11.<布尔常数> → true│false 12.<字符常数> → ' 除 {'} 外的任意字符串 ' 2、词法分析系统流程设计

(完整版)《编译原理》词法分析程序设计方案

实验1-4 《编译原理》S语言词法分析程序设计方案 一、实验目的 了解词法分析程序的两种设计方法:1.根据状态转换图直接编程的方式;2.利用DFA 编写通用的词法分析程序。 二、实验内容 1.根据状态转换图直接编程 编写一个词法分析程序,它从左到右逐个字符的对源程序进行扫描,产生一个个的单词的二元式,形成二元式(记号)流文件输出。在此,词法分析程序作为单独的一遍,如下图所示。 具体任务有: (1)组织源程序的输入 (2)拼出单词并查找其类别编号,形成二元式输出,得到单词流文件 (3)删除注释、空格和无用符号 (4)发现并定位词法错误,需要输出错误的位置在源程序中的第几行。将错误信息输出到屏幕上。 (5)对于普通标识符和常量,分别建立标识符表和常量表(使用线性表存储),当遇到一个标识符或常量时,查找标识符表或常量表,若存在,则返回位置,否则返回0并且填写符号表或常量表。 标识符表结构:变量名,类型(整型、实型、字符型),分配的数据区地址 注:词法分析阶段只填写变量名,其它部分在语法分析、语义分析、代码生成等阶段逐步填入。 常量表结构:常量名,常量值 2.编写DFA模拟程序 算法如下: DFA(S=S0,MOVE[][],F[],ALPHABET[]) /*S为状态,初值为DFA的初态,MOVE[][]为状态转换矩阵,F[] 为终态集,ALPHABET[] 为字母表,其中的字母顺序与MOVE[][] 中列标题的字母顺序一致。*/ { Char Wordbuffer[10]=“”//单词缓冲区置空 Nextchar=getchar();//读 i=0; while(nextchar!=NULL)//NULL代表此类单词 { if (nextcha r!∈ALPHABET[]){ERROR(“非法字符”),return(“非法字符”);} S=MOVE[S][nextchar] //下一状态 if(S=NULL)return(“不接受”);//下一状态为空,不能识别,单词错误 wordbuffer[i]=nextchar ;//保存单词符号 i++; nextchar=getchar(); } Wordbuffer[i]=‘\0’; If(S∈F)return(wordbuffer);//接受 Else return(“不接受”);

相关主题
相关文档 最新文档