编译原理课程设计_算术表达式的语法分析及语义分析程序设计(模版)

时间:2019-05-14 21:00:54下载本文作者:会员上传
简介:写写帮文库小编为你整理了多篇相关的《编译原理课程设计_算术表达式的语法分析及语义分析程序设计(模版)》,但愿对你工作学习有帮助,当然你在写写帮文库还可以找到更多《编译原理课程设计_算术表达式的语法分析及语义分析程序设计(模版)》。

第一篇:编译原理课程设计_算术表达式的语法分析及语义分析程序设计(模版)

设计题一:算术表达式的语法分析及语义分析程序设计。1.目的

通过设计、编制、调试一个算术表达式的语法及语义分析程序,加深对语法及语义分析原理的理解,并实现词法分析程序对单词序列的词法检查和分析。2.设计内容及要求:

算术表达式的文法:

〈无符号整数〉∷= 〈数字〉{〈数字〉} 〈标志符〉∷= 〈字母〉{〈字母〉|〈数字〉} 〈表达式〉∷= [+|-]〈项〉{〈加法运算符〉〈项〉} 〈项〉∷= 〈因子〉{〈乘法运算符〉〈因子〉} 〈因子〉∷= 〈标志符〉|〈无符号整数〉|‘(’〈表达式〉‘)’ 〈加法运算符〉∷= +|- 〈乘法运算符〉∷= *|/

选择算符优先分析方法完成以上任务,生成逆波兰式的中间代码;

(1)写出算术表达式的符合分析方法要求的文法,给出分析方法的思想,完成分析程序设计。

(2)编制好分析程序后,设计若干用例,上机测试并通过所设计的分析程序。

源代码

#define _CRT_SECURE_NO_WARNINGS #include “stdio.h” #include “stdlib.h” #include using namespace std;char data[20][20];//算符优先关系 char s[100];//模拟符号栈s char lable[20];//文法终极符集 char input[100];//文法输入符号串 char str[20][10];//用于输入串的分析 int k,j;char a,q;int r;//文法规则个数 int r1;int m, n, N;//转化后文法规则个数 char st[10][30];//用来存储文法规则 char first[10][10];//文法非终结符FIRSTVT集 char last[10][10];//文法非终结符LASTVT集

int fflag[10] = { 0 };//标志第i个非终结符的FIRSTVT集是否已求出 int lflag[10] = { 0 };//标志第i个非终结符的LASTVT集是否已求出 int deal();//对输入串的分析

int terminal_symbol(char c);//判断字符c是否是终极符 int location(char c);//求字符c在算符优先关系表中的下标 void out(int j, int k, char *s);//打印s栈

void firstvt(char c);//求非终结符c的FIRSTVT集 void lastvt(char c);//求非终结符c的LASTVT集 void table();//创建文法优先关系表 char output[10];//存储逆波兰式 void main(){

int i, j, k = 0;printf(“请输入文法规则数:”);scanf(“%d”, &r);printf(“请输入文法规则:n”);for(i = 0;i

} for(i = 0;i

} for(i = 0;i

for(j = 0;st[i][j]!= '';j++)if((st[i][j]<'A' || st[i][j]>'Z')&& st[i][j]!= '-'&&st[i][j]!= lable[k++] = st[i][j];for(j = 0;st[i][j]!= '';j++){

} if(st[i][0]<'A' || st[i][0]>'Z'){

} if(st[i][j] >= 'A'&&st[i][j] <= 'Z'){

} if(st[i][j + 1] >= 'A'&&st[i][j + 1] <= 'Z'){

} printf(“文法error!n”);exit(-1);printf(“文法error!n”);exit(-1);scanf(“%s”, st[i]);//存储文法规则,初始化FIRSTVT集和LASTVT集*/

first[i][0] = 0;/*first[i][0]和last[i][0]分别表示st[i][0]非终极符的last[i][0] = 0;

FIRSTVT集和LASTVT集中元素的个数*/

'>'&&st[i][j]!= '|')lable[k] = '#';lable[k + 1] = '';

} table();//

printf(“FIRST集为:n”);//输出每个非终结符的FIRST集 for(i = 0;i

} printf(“LAST集为:n”);//输出每个非终结符的LAST集 for(i = 0;i

} printf(“算符优先分析表如下:n”);for(i = 0;lable[i]!= '';i++)printf(“t%c”, lable[i]);printf(“n”);for(i = 0;i

} printf(“请输入文法输入符号串以#结束:”);scanf(“%s”, input);deal();cout << “逆波兰式为:”;for(i = 0;lable[i]!= '';i++)cout << output[i] << '';// cout << endl;printf(“%ct”, lable[i]);for(j = 0;j

char text[20][10];//存储改写后的文法

int i, j, k, t, l, x = 0, y = 0;int m, n;x = 0;for(i = 0;i

firstvt(st[i][0]);

lastvt(st[i][0]);} for(i = 0;i

{

text[x][y] = st[i][0];

y++;

for(j = 1;st[i][j]!= '';j++)

{

if(st[i][j] == '|')//

{

text[x][y] = '';

x++;

y = 0;

text[x][y] = st[i][0];

y++;

text[x][y++] = '-';

text[x][y++] = '>';

}

else

{

text[x][y] = st[i][j];

y++;

}

}

text[x][y] = '';

x++;

y = 0;} r1 = x;//

printf(“转化后的文法为:n”);for(i = 0;i

printf(“%sn”, text[i]);} for(i = 0;i

{

//输出转化后的文法规则串 /*求每个终结符的推导结果(去掉“->”后的

} str[i][0] = text[i][0];for(j = 3, l = 1;text[i][j]!= '';j++, l++)str[i][l] = text[i][j];str[i][l] = '';for(i = 0;i

for(j = 1;text[i][j + 1]!= '';j++){

if(terminal_symbol(text[i][j])&& terminal_symbol(text[i][j + 1])){

} if(text[i][j + 2]!= ''&&terminal_symbol(text[i][j])&& {

} if(terminal_symbol(text[i][j])&&!terminal_symbol(text[i][j + 1]))//终结{

} if(!terminal_symbol(text[i][j])&& terminal_symbol(text[i][j + 1]))//非终{ for(k = 0;k

} m = location(text[i][j]);for(t = 0;t

} n = location(first[k][t + 1]);data[m][n] = '<';if(st[k][0] == text[i][j + 1])

break;m = location(text[i][j]);n = location(text[i][j + 2]);data[m][n] = '=';m = location(text[i][j]);n = location(text[i][j + 1]);data[m][n] = '=';terminal_symbol(text[i][j + 2])&&!terminal_symbol(text[i][j + 1]))符和非终结符相接,用后于关系填表

结符和终结符相接,用先于关系填表

if(st[k][0] == text[i][j])

break;

}

n = location(text[i][j + 1]);

for(t = 0;t

{

m = location(last[k][t + 1]);

data[m][n] = '>';

}

}

} } m = location('#');//#后于所有的终结符规约

for(t = 0;t

n = location(first[0][t + 1]);

data[m][n] = '<';} n = location('#');//

for(t = 0;t

m = location(last[0][t + 1]);

data[m][n] = '>';} data[n][n] = '=';}

void firstvt(char c){ int i, j, k, m, n;for(i = 0;i

{

if(st[i][0] == c)

break;} if(fflag[i] == 0){

n = first[i][0] + 1;

m = 0;

do

{

if(m == 2 || st[i][m] == '|')

{ if(terminal_symbol(st[i][m + 1]))

//求FIRSTVT集

}

}

} {

} else {

} if(terminal_symbol(st[i][m + 2])){

} if(st[i][m + 1]!= c){

}

firstvt(st[i][m + 1]);for(j = 0;j

}

for(k = 0;k

}

int t;

for(t = 0;t

}

if(t == n){

}

first[i][n] = first[j][k + 1];n++;

if(first[i][t] == first[j][k + 1])

break;

if(st[j][0] == st[i][m + 1])

break;

first[i][n] = st[i][m + 2];n++;first[i][n] = st[i][m + 1];n++;m++;} while(st[i][m]!= '');first[i][n] = '';first[i][0] =--n;fflag[i] = 1;

void lastvt(char c)//求LASTVT集 {

int i, j, k, m, n;for(i = 0;i

} if(lflag[i] == 0){

n = last[i][0] + 1;m = 0;do {

if(st[i][m + 1] == '' || st[i][m + 1] == '|'){

if(terminal_symbol(st[i][m])){

} else {

if(terminal_symbol(st[i][m1];n++;last[i][n] = st[i][m];n++;if(st[i][0] == c)break;

}

}

}

}

}

}

}

if(t == n){

}

last[i][n] = last[j][k + 1];n++;m++;} while(st[i][m]!= '');last[i][n] = '';last[i][0] =--n;lflag[i] = 1;int deal(){

int i, j;int size = 0;// int x, y;int z;//输入串的长度 k = 1;s[k] = '#';//栈置初值

for(i = 0;input[i]!= '';i++);//计算输入串的长度 z = i--;// i = 0;while((a = input[i])!= '')//a表示要输入的字符 {

if(terminal_symbol(s[k]))j = k;j = k1]))j = j2;x = location(s[j]);y = location(q);} while(data[x][y]!= '<');int m, n, N;for(m = j + 1;m <= k;m++){

} k = j + 1;if(k == 2 && a == '#'){

out(1, k, s);printf(“%c”, a);out(i + 1, z, input);printf(“结束n”);for(N = 0;N

} if(!terminal_symbol(s[m])&&!terminal_symbol(str[N][n])){

} else

if(terminal_symbol(s[m]))if(s[m] == str[N][n]){

}

s[j + 1] = str[N][0];break;

if(terminal_symbol(s[m + 1])&& terminal_symbol(str[N][n + 1]){

}

s[j + 1] = str[N][0];break;&& s[m + 1] == str[N][n + 1])

}

} printf(“规约成功!n”);return 1;//输入串符合文法的定义

else

if(data[x][y] == '<' || data[x][y] == '='){ //移进

out(1, k, s);

printf(“%c”, a);

out(i + 1, z, input);

printf(“移进n”);

k++;

s[k] = a;

i++;

}

else

{

printf(“n规约失败n”);

return 0;

} } printf(“n规约失败n”);//

return 0;}

void out(int j, int k, char *s){ int n = 0;int i;for(i = j;i <= k;i++){

printf(“%c”, s[i]);

n++;} for(;n<15;n++){

printf(“ ”);} }

int location(char c){ int i;for(i = 0;lable[i]!= '';i++)

//求字符c在算符优先关系表中的下标

} {

} return-1;if(c == lable[i])return i;int terminal_symbol(char c)//判断字符c是否是终极符 {

} int i;for(i = 0;lable[i]!= '';i++){

} return 0;if(c == lable[i])return 1;

第二篇:编译原理语法分析实验报告

实验2:语法分析

1.实验题目和要求

题目:语法分析程序的设计与实现。

实验内容:编写语法分析程序,实现对算术表达式的语法分析。要求所分析算术表达式由如下的文法产生。

EET|ET|TTT*F|T/F|F Fid|(E)|num实验要求:在对输入表达式进行分析的过程中,输出所采用的产生式。方法1:编写递归调用程序实现自顶向下的分析。方法2:编写LL(1)语法分析程序,要求如下。

(1)编程实现算法4.2,为给定文法自动构造预测分析表。(2)编程实现算法4.1,构造LL(1)预测分析程序。

方法3:编写语法分析程序实现自底向上的分析,要求如下。(1)构造识别所有活前缀的DFA。(2)构造LR分析表。

(3)编程实现算法4.3,构造LR分析程序。

方法4:利用YACC自动生成语法分析程序,调用LEX自动生成的词法分析程序。实现(采用方法1)

1.1.步骤:

1)对文法消除左递归

ETE'E'TE'|TE'|TFT'T'*FT'|/FT'|Fid|(E)|num

2)画出状态转换图

化简得:

3)源程序

在程序中I表示id N表示num

1.2.例子:

a)例子1 输入:I+(N*N)输出:

b)例子2 输入:I-NN 输出:

第三篇:编译原理课程设计

课 程 设 计 报 告

设计题目:一个简单文法的编译器前端的设计与实现

级: 计算机1206 组长学号:201239 组长姓名:闫智宣 指导教师:李晓华 设计时间:2014年12月

[在此处键入]

设计分工

组长学号及姓名: 20123974

闫智宣

分工:

语法分析,四元式生成,目标代码优化及生成 组员1学号及姓名:20123977

廖峭 分工:

词法分析,错误处理 组员2学号及姓名:20123959

郭天龙

分工:

符号表生成,语义动作插入,操作界面[在此处键入]

摘要

编译原理课程设计是通过C语言编译器相关子系统的设计,进一步加深对编译器构造的理解;第一部分词法分析,设计各单词的状态转换图,并为不同的单词设计种别码,制作扫描器识别一个个单词,返回值为识别码的序号,返回Token序列。将词法分析器设计成供语法分析器调用的子程序。词法分析器具备预处理功能。将不翻译的注释等符号先滤掉,只保留要翻译的符号串,即要求设计一个供词法分析调用的预处理子程序;第二部分,语法分析,用递归下降法,实现对表达式、各种说明语句、控制语句进行语法分析。若语法正确,则用语法制导翻译法进行语义翻译;生成并打印出语法树;若语法错误,要求指出出错性质和出错位置(行号)。

我们还做了附加功能,即编译后端,有中间代码优化,生成目标代码汇编语言。通过此次课程设计,提高了我们的独立分析问题、解决问题的能力,以及系统软件设计的能力; 提高程序设计能力、程序调试能力,团结协作能力

关键词:词法分析,语法分析,四元式生成,错误处理,符号表生成,语义动作插入,中间代码优化,生成目标代码 [在此处键入]

目录

摘要

1.概述

2.课程设计任务及要求

2.1 设计任务

2.2 设计要求

3.算法及数据结构

3.1算法的总体思想(流程)

3.2 词法分析模块

3.2.1 功能

3.2.2 数据结构

3.2.3 算法

3.3 语法分析模块

3.3.1功能

3.3.2 数据结构

3.3.3算法

3.4 符号表模块

3.4.1功能

3.4.2 数据结构

3.4.3算法

3.5 四元式模块

3.5.1功能

[在此处键入]

3.5.2 数据结构

3.5.3算法

3.6 语义动作分析模块

3.6.1功能 3.6.2 数据结构

3.6.3算法

3.7 错误处理模块

3.7.1功能

3.7.2 数据结构

3.7.3算法

3.8 目标代码模块

3.8.1功能

3.8.2 数据结构

3.8.3算法

4.程序设计与实现

4.1 程序流程图

4.2 程序说明

4.3 实验结果

5.结论 6.参考文献。7.收获、体会和建议。

[在此处键入]

1.概述

编译器是将C语言翻译为汇编语言代码的计算机程序。编译器将源程序(source language)编写的程序作为输入,翻译产生目标语言(target language)机器代码的等价程序。通常地,源程序为高级语言(high-level language),C语言程序,而目标则是 机器语言的目标代码(object code),也就是可以在计算机硬件中运行的机器代码软件程序。这一过程可以表示为:

源程序→编译器 →目标机器代码程序

2.课程设计任务及要求

2.1设计任务

学生在学习《编译原理》课程过程中,结合各章节的构造编译程序的基本理论,要求用C#语言描述及上机调试,实现一个 C编译程序(包括词法分析,语法分析等重要子程序),使学生将理论与实际应用结合起来,受到软件设计等开发过程的全面训练,从而提高学生软件开发的能力。

2.2设计要求 要求:

(1)设计词法分析器

设计各单词的状态转换图,并为不同的单词设计种别码。将词法分析器设计成供语法分析器调用的子程序。功能包括:

a.具备预处理功能。将不翻译的注释等符号先滤掉,只保留要翻译的符号串,即要求设计一个供词法分析调用的预处理子程序;

b.能够拼出语言中的各个单词; [在此处键入]

c.返回(种别码,属性值,行号)。

(2)语法分析

要求用学习过的自底向上或自顶向下的分析方法等,实现对表达式、各种说明语句、控制语句进行语法分析。若语法正确,则用语法制导翻译法进行语义翻译;生成并打印出语法树;若语法错误,要求指出出错性质和出错位置(行号)。

3.算法及数据结构

3.1算法的总体思想(流程)

本节主要分析程序的代码结构和代码工程文件的划分。(程序由几个类组成: Token类和Variable类SymbolTable类ObjectCode类Lexical类Grammar类Four_Yuan类Action类ErrorItem类,分别为词法分析和语法分析类。工程分为几个文件:Form1.cs,Token.cs,Variable.cs,SymbolTable.cs,ObjectCode.cs,Lexical.cs,Grammar.cs,Four_Yuan,cs,Action.cs,ErrorItem.cs分别对应Token类和Variable类SymbolTable类ObjectCode类Lexical类Grammar类Four_Yuan类Action类ErrorItem类的声明和实现文件)。本程序采用C#语言以面向对象的思想编写,程序分为几部分:词法分析(Lexical),语法分析(Grammer),目标代码生成(ObjectCode)。Lexical类主要的工作是词法分析获取Token。Grammer类的主要工作是根据Lexical类词法分析之后的Token进行语法分析,生成语法树,最后并输出语法树。在处理过程中,Token类的对象作为Lexical类的一个成员变量,配合Grammer类进行语法分析。

工程文件总体上是按照九个类的格局分为十个文件,分别是九个类的声明文件和实现文件。十个文件为Form1.cs,Token.cs,Variable.cs,SymbolTable.cs,ObjectCode.cs,Lexical.cs,Grammar.cs,Four_Yuan,cs,Action.cs,ErrorItem.cs,他们分别是Lexical类声明文件、Lexical类实现文件、Grammer类声明文件、Grammer类实现文件。[在此处键入]

程序流程

在程序中,Lexical类的对象(Token)作为Grammer类中的一个成员变量,配合Grammer类进行语法分析。它们的关系是这样的:Grammer类的一个成员变量temp首先对源程序删除注释,然后进行词法分析获取所有Token,并将获取的Token存储在Token对象的tokenList(List类型)中。然后Grammer类的语法分析程序就根据tokenList中的Token进行语法分析,生成语法树,最后打印语法树。同时,这也是程序的流程。[在此处键入]

3.2 词法分析模块 3.2.1功能

Lexical类主要的工作是词法分析获取Token序列。

3.2.2数据结构

词法分析阶段的代码被封装成一个类——Lexical,Token中主要是Lexical类的声明代码,Lexical.cs中主要是Lexical类的实现代码。Lexical类对外提供的函数主要有:

static public int RecogId(string str, int i),static public int RecogDig(string str,int i),static public int RecogOperator(string str, int i),static public int RecogBound(string str, int i),以上几个函数构成了词法分析的骨架,在Lexical类中还有其他成员变量和函数,主要作为这三个函数处理过程的中间步骤,为这三个函数服务。Lexical类的代码结构和主要的成员变量和函数及其含义如下图所示:

3.2.3算法

算法的基本任务是从字符串表示的源程序中识别出具有独立意义的单词符号,其基本思想是[在此处键入]

根据扫描到单词符号的第一个字符的种类,拼出相应的单词符号。

主程序示意图:

主程序示意图如图3-1所示。

⑴ 关键字表的初值。

关键字作为特殊标识符处理,把它们预先安排在一张表格中(称为关键字表),当扫描程序识别出标识符时,查关键字表。如能查到匹配的单词,则该单词为关键字,否则为一般标识符。

(2)程序中需要用到的主要变量为type和number 扫描子程序的算法思想:

首先设置3个变量: [在此处键入]

①token用来存放构成单词符号的字符串; ②number用来整型单词;

③type用来存放单词符号的种别码。

Token定义

Token定义:

Token类型(TokenType):

3.3 语法分析模块

3.3.1功能

语法分析是编译过程的一个逻辑阶段。语法分析的功能是在词法分析的基础上将单词序列组合成各类语法短语,如“程序”,“语句”,“表达式”等等.语法分析程序判断源程序在结构上是否正确.源程序的结构由上下文无关文法描述.3.3.2 数据结构

下图为实现语法分析的类Grammar,属性与方法的作用都已说明 在此处键入]

3.3.3算法

1.文法

下面终结符与非终结符意义

B程序开始

Z 数据类型,如int,char,float等

V 标识符

S 语句

P 语句块

E 加减算术表达式

D 逗号表达式

T 乘除算术表达式

C 关系表达式

L 逻辑表达式

Q 标识符或圆括号

e 表示空

i 表示标识符 a)函数文法

B----ZV()S

[

[在此处键入]

b)语句块文法

P----SP|e

S----{P} c)语句文法

表达式语句文法

S----V=E

goto语句文法

S----i:S

S----goto i

if语句文法

S----if(E)S[else S]

while语句文法

S----while(E)S

声明语句文法

S----ZVD

D----,VD|=ED|e d)表达式文法

E----T|E+T|E-T

T----F|T*F|T/F

C----C|CL|C==C|C<= L|C>=L

L----Q|L&&Q|L||Q

Q----i|(E)|!Q

2.递归下降程序流程图

对应于每个文法编写如下递归下降子程序

主程序(B)[在此处键入] [在此处键入]

3.4 符号表模块

3.4.1功能

进行符号表的储存,添加,更新,查找,保存标识符活跃信息以及输出。3.4.2 数据结构

在此处键入]

3.4.3算法

3.5 四元式模块

3.5.1功能

四元式为中间代码,编译程序进行完语义分析后,先生成中间代码作为过渡,此时中间代码与目标代码已经比较相似

3.5.2 数据结构

[ 在此处键入]

3.5.3算法

3.6语义动作分析模块

3.6.1功能

在语法分析中嵌入相应的语义动作,生成四元式 3.6.2 数据结构

[

[在此处键入]

3.6.3算法 GEQ(+)(-)(*)(/)

(+,i1,i2,t)PUSH(i)ASSI(=)

(=,t,_,POP)LABER(i)

(lb,_,_,i)GOTO(i)

(gt,_,_,i)IF(if)

(if,a,_,_)EL(el)

(el,_,_,_)IE(ie)

(ie,_,_,_)WH()

(wh,_,_,_)DO()

(do,a,_,_)WE(we)

(we,_,_,_)

3.7 错误处理模块

3.7.1功能 保存运行时发现的错误,储存行号已经详细信息并输出。

3.7.2 数据结构

3.7.3算法 [在此处键入]

public static void AddErrorMessage(int lineno,string content)函数用作在发现错误时保存错误信息以及行号。

public static string PrintErrorList()把所有发现的错误格式化后统一输出。

错误信息在语法分析,语义分析,符号表检错中添加。3.8 目标代码模块

3.8.1功能

目标代码生成把优化后的中间代码变换成目标代码,此处的目标代码为汇编代码,采用单寄存器生成目标代码 3.8.2 数据结构[在此处键入]

3.8.3算法

对于一个基本块有如下流程图

W:操作符,B:第一操作数,C:第二操作数,R:寄存器

5.结论

网上找一段话抄上 [在此处键入]

6.测试

测试打开文件

测试保存文件

如果没打开文件,直接敲代码,点保存时会弹出另存为窗口[在此处键入]

测试错误检测,程序缺少main函数的类型,错误列表中显示第一行函数缺少错误类型。

测试错误检测,程序缺少分号,错误列表中显示该行缺少语句结束标志';' 单击错误列表,会自动选定错误行

编译成功,生成并显示token串、符号表、四元式与目标代码 [在此处键入]

测试if与while语句,而且while嵌套在if当中

测试goto语句,结果正确。[在此处键入]

测试优化,输入课件中的代码,结果与课件一样

6.参考文献。

1、陈火旺.《程序设计语言编译原理》(第3版).北京:国防工业出版社.2000.2、美 Alfred V.Aho Ravi Sethi Jeffrey D.Ullman著.李建中,姜守旭译.《编译原理》.24 [在此处键入]

北京:机械工业出版社.2003.3、美 Kenneth C.Louden著.冯博琴等译.《编译原理及实践》.北京:机械工业出版社.2002.4、金成植著.《编译程序构造原理和实现技术》.北京:高等教育出版社.2002.7.收获、体会和建议。

直接拷贝好歹也检查一下错误

对于编译原理的这次课程设计,自己经历了从刚开始的不懂明白任务的要求和内容理论知识的了解开始着手写代码完成基本功能根据DFA及自顶向下等理论修改完善代码等这些过程。

自己着手写词法分析的时候还不清楚词法分析的任务内容,还不知道词法分析的结果是什么,词法分析出错的情况和类型有哪些,也总是将词法分析和语法分析混在一起,不明白哪些错误在词法分析中报,哪些错误在语法分析中判断,后来经过查书、网上资料、请教同学等途径逐步清晰了词法分析的工作内容是从源代码文件中获取出Token,供语法分析使用。在充分了解了语法分析需要哪些信息时,我才真正了解了词法分析的工作内容和目标,才知道词法分析需要完成哪些任务获取到哪些信息。充分了解了词法分析的任务之后,就开始理论知识的学习。经过揣摩书上的例子,自己理解和掌握了怎么设计过滤注释和分析程序中Token的DFA,于是开始根据设计好的DFA进行编码,最后经过调试已经可以正确地完成词法阶段的任务了。这只是词法分析的原始代码,在之后还进行了两次彻底的改动。虽然之前写的词法分析的代码已经完成了词法分析的需求,也是根据DFA的原理编写的,但是在代码结构上却难以体现,在对书上的根据已知DFA写代码的例子进行了详细的研究之后,发现自己的代码并没有像书上那样完全按照所依据的DFA各状态转移的关系进行编写,所以对代码进行了重写,像书上一样严格按照状态之间转移的方式进行编写,将状态划分成11个状态,状态分别按1~11进行标注,程序也按照DFA来编写,也实现了词法分析的功能。再后来写报告的时候,发现分析出Token的那个DFA并不是最简的,有很多多余的状态,完全可以用一个flag标志来标识,从而简化代码结构,于是又重写了一次词法分析函数scan()的代码,将状态缩减为5个,且不再用1-5来表示,而是像书上那样分别取了名字(START、INNUM、INID、INDBSYM、DONE),同时为了简化代码将输出Token到文件的部分从scan()中剥离开来,而在Lexical类中加了一个printToken()的函数,使scan()函数逻辑更加清晰,使读者能够容易地将代码与DFA进行查看比照。

在写语法分析的时候,已经对编译器的语法分析的内容有了一定的了解,所以直接进行了理论的学习。首先自己对递归向下分析法进行了学习,将书上的几个递归向下分析的伪代码看过之后,自己对递归向下的分析方法的原理有了初步的认识,大概知道了根据文法怎么分析,但是对于如何编写代码却还在此处键入]

是难以下手,于是就对照TINY语言的文法看了几遍书后面的TINY语言的递归向下分析的语法分析程序,这样就基本知道了C-语言的语法分析程序怎么写。由于C-语言给出的文法有左递归存在,于是自己将存在左递归的文法改写成EBNF的形式,并据此进行代码编写。由于在编写代码的过程中需要确定分析是否正确或选择多个文法中的某一个文法进行分析,有时必须探测需要的或下一个Token的类型,在这种情况下需要求First集合,在推导中若存在empty,又需要求Follow集合,所以这样又需要我了解First集合和Follow集合,自己在程序中也根据求出的First集合和Follow集合进行判断,以确定程序的走向。在编写过程中,还有一类问题,就是存在公共左因子,如文法expression→ var = expression | simple-expression,左因子为ID,在分析过程中,由于已经取出了一个ID的Token,且生成了一个IdK的节点,但是在当前状态无法确定是哪一个推导,然而IdK节点已经生成,又无法回退,并且是使用自顶向下的分析方法,已经生成的IdK在程序上方无法使用,自己通过查阅资料等途径的学习确定了在这种情形下的处理方式:将已经生成的IdK节点传到下方的处理程序,所以TreeNode * simple_expression(TreeNode * k)、TreeNode * additive_expression(TreeNode * k)等函数都被设计成有节点类型参数的函数,目的就是将已经生成的节点传到下面的分析函数中去。

通过这次的编译原理课程的学习和实践,自己获益良多。首先最基本的成果是完成了课程设计的任务,实现了编译器的词法分析和语法分析阶段的功能,词法分析主要能过滤注释、分析出语法分析阶段需要的Token并满足语法阶段的所有要求,能够判别词法分析阶段是否出错和出错类型和位置。语法分析主要能根据递归向下的分析思想和C-文法对词法分析获取的Token进行语法分析,能够构造出语法树,能够判别语法分析过程中是否出错以及出错位置和错误类型。

由于在编写程序过程中,涉及到了正则表达式、DFA、提取公共左因子、消除左递归、EBNF、求First集合和Follow集合、递归向下分析方法以及编程语言方面的知识,所以,通过本次的课程设计的实践,使得自己对编译原理这门课的许多知识点有了更加深刻和具体的理解,而不再只限制于做题。此外,对以前那些已掌握的知识有了温习和动手锻炼的机会。如:以前在编译原理课上虽然知道First集合和Follow集合怎么求的,却不知道First集合和Follow集合到底是干什么的,通过编写程序自己明白了他们的实际作用,使得自己不仅知其然还知其所以然,从而使得自己加深了对知识点的理解和掌握。由于以前编写代码都是使用JAVA语言,所以C/C++很多内容都忘记了,通过本次的实践,自己又重新拾起了以前的知识。此外,由于在做报告的时候,需要描绘DFA和程序流程图,使得自己初步掌握了使用visio和word画图的能力。此外,对于文档的编写和美化自己也获得了许多有用的经验。[

第四篇:编译原理课程设计报告

武 汉 纺 织 大 学

编译原理课程设计实验报告

学院:数学与计算机 专业:计算机 姓名: 班级: 学号: 编译原理

编译原理课设报告

一、实验目的

加强对编译程序的整体认识和了解,巩固《编译原理》课程所学知识。通过本次课程设计掌握编译程序调试技巧和设计编译程序一般的原则,加深对词法分析、语法分析、语义分析等编译阶段及实用编译系统的认识。使学生能将编译理论与实际应用结合起来,提高学生软件开发的能力。

二、实验内容

1)仔细阅读PL/0编译程序文本(编译原理(第二版)张素琴 吕映芝 蒋维杜 戴桂兰 主编

清华大学出版社),并上机调试通过。

2)对PL/0语言进行下列扩充(1)扩充一维整型数组。

扩充var数组:VAR <数组标识名>(<下界>:<上界>)〈下界〉和〈上界〉可用常量标识名。

(2)扩充条件语句的功能使其为:IF<条件>THEN<语句>[ELSE<语句>](3)增加repeat重复语句: REPEAT<语句>{;<语句>}UNTIL<条件> 可根据自己具体情况从中选择2个以上题目进行扩充。

三、实验原理

PL/0语言可以看成PASCAL语言的子集,它的编译程序是一个编译解释执行系统。PL/0的目标程序为假想栈式计算机的汇编语言,与具体计算机无关。

PL/0的编译程序和目标程序的解释执行程序都是用PASCAL语言书写的,因此PL/0语言可在配备PASCAL语言的任何机器上实现。其编译过程采用一趟扫描方式,以语法分析程序为核心,词法分析和代码生成程序都作为一个独立的过程,当语法分析需要读单词时就调用词法分析程序,而当语法分析正确需要生成相应的目标代码时,则调用代码生成程序。

用表格管理程序建立变量、常量和过程表示符的说明与引用之间的信息联系。

当源程序编译正确时,PL/0编译程序自动调用解释执行程序,对目标代码进行解释执行,并按用户程序的要求输入数据和输出运行结果。

四、实验分析

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

词法分析子程序分析:

词法分析子程序名为GETSYM,功能是从源程序中读出一个单词符号(TOTAKEN),把它的信息放入全局变量 SYM、ID和NUM中,字符变量放入CH中,语法分析器需要单词时,直接从这三个变量中获得。Getch过程通过反复调用Getch子过程从源程序过获取字符,并把它们拼成单词。GETCH过程中使用了行缓冲区技术以提高程序运行效率。

词法分析器的分析过程:调用GETSYM时,它通过GETCH过程从源程序中获得一个字符。如果这个字符是字母,则继续获取字符或数字,最终可以拼成一个单词,查保留字表,如果查到为保留字,则把SYM变量赋成相应的保留字类型值;如果没有查到,则这个单词应是一个用户自定义的标识符(可能是变量名、常量名或是过程的名字),把SYM置为IDENT,把这个单词存入ID变量。查保留字表时使用了二分法查找以提高效率。如果Getch获得的字符是数字,则继续用Getch获取数字,并把它们拼成一个整数或实数,然后把SYM置为 INTEGER或REAL,并把拼成的数值放入NUM变量。如果识别出其它合法的符号(比如:赋值号、大于号、小于等于号等),则把SYM则成相应的类型。如果遇到不合法的字符,把SYM置成NUL。

语法分析子程序分析:

语法分析子程序采用了自顶向下的递归子程序法,语法分析同时也根据程序的语义生成相应三元代码,并提供了出错处理的机制。语法分析主要由分程序分析过程(BLOCK)、参数变量分析过程(ParaDeclaration)、参数变量处理过程(ParaGetSub)、数组处理过程(ParaGetSub)、常量定义分析过程(ConstDeclaration)、变量定义分析过程(Vardeclaration)、语句分析过程(Statement)、表达式处理过程(Expression)、项处理过程(Term)、因子处理过程(Factor)和条件处理过程(Condition)构成。这些过程在结构上构成一个嵌套的层次结构。除此之外,还有出错报告过程(Error)、代码生成过程(Gen)、测试单词合法性及出错恢复过程(Test)、登录名字表过程(Enter)、查询名字表函数(Position)以及列出类 PCODE代码过程(Listcode)作过语法分析的辅助过程。

由PL/0的语法图可知:一个完整的PL/0程序是由分程序和句号构成的。因此,本编译程序在运行的时候,通过主程序中调用分程序处理过程block来分析分程序部分(分程序分析过程中还可能会递归调用block过程),然后,判断最后读入的符号是否为句号。如果是句号且分程序分析中未出错,则是一个合法的PL/0程序,可以运行生成的代码,否则就说明源PL/0程序是不合法的,输出出错提示即可。

if-then-else语句的处理:

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

Repeat语句的处理:

首先用CX1变量记下当前代码段分配位置,作为循环的开始位置。然后通过递归调用语句分析过程分析,直到遇到until保留字,如果未对应until则出错。调用条件表达式处理过程生成相应代码把结果放在数据栈顶,再生成条件转移指令,转移位置为上面记录的CX1。

五、相关代码及运行结果

实验代码; PL0.h代码: #include #include #include #include #include #include

#ifndef WIRTH_ZYC_ #define WIRTH_ZYC_ using namespace std;

const int norw = 16;

// no.of reserved words 保留字的个数

const int txmax = 100;

// length of identifier table 标示符表的长度(容量)const int al = 10;

// length of identifiers 标示符的最大长度

const int nmax = 14;

// max.no.of digits in numbers 数字的最大长度 const int amax = 2047;

// maximum address 寻址空间

const int levmax = 3;

// maximum depth of block nesting 最大允许的块嵌套层数 const int cxmax = 200;

// size of code array 类PCODE目标代码数组长度(可容纳代码行数)

const int lineLength = 82;// 行缓冲区长度

typedef enum {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,ELSESYM,REPEATSYM,UNTILSYM} symbol;// symobl类型标识了不同类型的词汇

typedef char alfa[al+1];

// alfa类型用于标识符 typedef enum {CONSTANT,VARIABLE,PROCEDURE,ARRAY} obj0;

// 三种标识符的类型 typedef enum {LIT,OPR,LOD,STO,CAL,INT,JMP,JPC} fct;

// functions typedef set symset;

struct instruction{ fct f;// function code int l;// level,cann't big than levmax

int a;// displacement address,cann't big than amax };

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

/******************************************* * 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{ alfa name;obj0 kind;union {

struct{int level,adr,size;}inOther;

int val;}other;} Table;

class PL0 {

protected:

bool listswitch,sourceEnd;char ch;

// last character read symbol sym;

// last symbol read alfa id;

// last identifier read int num;

// last number read

int cc;

// character count int ll;

// line length int kk,err;int cx;

// code allocation index int codeNo;

// code line no.static string errStr[];

// error string

char line[lineLength];

// code line vector errorString;

// error array alfa a;

// 词法分析器中用于临时存放正在分析的词

instruction code[cxmax+1];

// destination code array

alfa word[norw+1];

// 保留字表

symbol wsym[norw+1];

// 保留字表中每一个保留字对应的symbol类型

symbol ssym[100];

// 一些符号对应的symbol类型表

合 char mnemonic[8][6];

// 类PCODE指令助记符表

symset declbegsys,statbegsys,facbegsys;// 声明开始、表达式开始和项开始符号集 Table table[txmax+1];

// 符号表

FILE* fin,*fout;

public:

PL0(char* source,char*destination);

~PL0(){fclose(fin),fclose(fout);}

void error(int n);

位置和出错代码

void getsym();

个单词

void getch();

个字符

void gen(fct x,int y,int z);

程序区

void test(symset s1,symset s2,int n);

合法

void block(int lev,int tx,symset fsys);

void enter(obj0 k,int &tx,int &dx,int lev);

int position(alfa id,int tx);的位置

void constdeclaration(int&tx,int&dx,int lev);

void vardeclaration(int&tx,int&dx,int lev);

void listcode(int cx0);

void statement(symset fsys,int tx,int lev);

void expression(symset fsys,int tx,int lev);

void term(symset fsys,int tx,int lev);

void factor(symset fsys,int tx,int lev);

void condition(symset fsys,int tx,int lev);

void arraydeclaration(int& tx,int& dx,int lev);

void interpret();

执行程序

int base(int l,int b,int s[]);

基地址

void SaveCode();

// 构造函数

// 析构函数

// 出错处理,打印出错

// 词法分析,读取一

// 漏掉空格,读取一// 生成目标代码,并送入目标

// 测试当前单词符号是否

// 分程序分析处理过程

// 登入名字表

// 查找标示符在名字表中

// 常量定义处理

// 变量说明处理

// 列出目标代码清单

// 语句部分处理

// 表达式处理

// 项处理

// 因子处理

// 条件处理

// 数组说明处理

// 对目标代码的解释

// 通过静态链求出数据区的 // 保存代码

};#endif PL0.cpp代码: #include “pl0.h”

// 错误字符串数组

string PL0::errStr[]={“",”error 0001: 常数说明中“=”写成“:=”“, ”error 0002: 常数说明中的“=”后应为数字“, ”error 0003: 常数说明中的标识符后应是“=”“, ”error 0004: const,var,procedure后应为标识符“, ”error 0005: 漏掉了‘,’或‘;’“, ”error 0006: 过程说明后的符号不正确(应是语句开始符或过程开始符)“, ”error 0007: 应是语句开始符“, ”error 0008: 过程体内语句部分的后跟符不正确“, ”error 0009: 程序皆为丢了句号‘.’“, ”error 0010: 语句之间漏了‘;’“, ”error 0011: 标识符没说明“, ”error 0012: 赋值语句中,赋值号左部标识符属性应是变量“, ”error 0013: 赋值语句左部标识符应是赋值号:=“, ”error 0014: call后应为标识符“, ”error 0015: call后标识符属性应为过程“, ”error 0016: 条件语句中丢了then“, ”error 0017: 丢了end或;“, ”error 0018: while型循环语句中丢了do“, ”error 0019: 语句后的标识符不正确“, ”error 0020: 应为关系运算符“, ”error 0021: 表达式内标识符属性不能是过程“, ”error 0022: 表达式中漏掉了右括号‘)’“, ”error 0023: 因子后的非法符号“, ”error 0024: 表达式开始符不能是此符号“, ”error 0025: 文件在不该结束的地方结束了“, ”error 0026: 结束符出现在不该结束的地方“, ”error 0027: “,”error 0028: “,”error 0029: “,”error 0030: “, ”error 0031: 数越界“, ”error 0032: read语句括号中标识符不是变量“, ”error 0033: else附近错误“ , ”error 0034: repeat附近错误“};

// PL0构造函数

PL0::PL0(char* source,char*destination){ listswitch=true,sourceEnd=false;

strcpy(word[1],”begin“);

// 初始化存储保留字

strcpy(word[2],”call“);strcpy(word[3],”const“);

strcpy(word[4],”do“);strcpy(word[5],”else“);strcpy(word[6],”end“);strcpy(word[7],”if“);strcpy(word[8],”odd“);strcpy(word[9],”procedure“);strcpy(word[10],”read“);

strcpy(word[11],”repeat“);strcpy(word[12],”then“);strcpy(word[13],”until“);strcpy(word[14],”var“);

strcpy(word[15],”while“);strcpy(word[16],”write“);

wsym[1]= BEGINSYM;

wsym[2]= CALLSYM;留字对应的symbol类型

wsym[3]= CONSTSYM;

wsym[4]= DOSYM;wsym[5]= ELSESYM;

wsym[6]= ENDSYM;wsym[7]= IFSYM;

wsym[8]= ODDSYM;wsym[9]= PROCSYM;

wsym[10]= READSYM;

wsym[11]= REPEATSYM;wsym[12]= THENSYM;wsym[13]= UNTILSYM;wsym[14]= VARSYM;

wsym[15]= WHILESYM;wsym[16]= WRITESYM;

memset(code,0,sizeof(code));memset(ssym,0,100*sizeof(symbol));memset(table,0,sizeof(table));memset(line,0,sizeof(line));

ssym['+']= PLUS;

类型表

ssym['-']= MINUS;ssym['*']= TIMES;ssym['/']= SLASH;ssym['(']= LPAREN;ssym[')']= RPAREN;ssym['=']= EQL;ssym[',']= COMMA;ssym['.']= PERIOD;

// 初始化保留字表中每一个保

// 初始化一些符号对应的symbol

ssym['#']= NEQ;ssym['<']= LSS;ssym['>']= GTR;ssym[';']= SEMICOLON;

strcpy(mnemonic[LIT],” lit “);

// 初始化类PCODE指令助记符表

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.insert(CONSTSYM),declbegsys.insert(VARSYM),declbegsys.insert(PROCSYM);// 初始化声明开始符号集合 statbegsys.insert(BEGINSYM),statbegsys.insert(CALLSYM),statbegsys.insert(IFSYM),statbegsys.insert(WHILESYM);// 初始化表达式开始符号集合facbegsys.insert(IDENT),facbegsys.insert(NUMBER),facbegsys.insert(LPAREN);// 初始化项开始符号集合

err= 0;cc= 0;

// 行缓冲区指针

cx= 0;

// 代码分配指针,代码生成模块总在cx所指位置生成新的代码

ll= 0;

// 行缓冲区长度

ch= ' ';

// last character read

}

kk= al;

// 引入此变量是出于程序性能考虑 codeNo=0;

// code line no.fin=fopen(source,”r“);fout=fopen(destination,”w“);// 出错处理,打印出错位置和出错代码 void PL0::error(int n){ char s[10];sprintf(s,”第 %d 行:“,codeNo);errorString.push_back(s+errStr[n]);err= err+1;//error count }//error end // 词法分析,读取一个单词

void PL0::getsym(){ if(sourceEnd)

return;int i,j,k;while(ch ==' '||ch==9)

getch();

// cls space and tab if(isalpha(ch))// id or reserved word {

k=0;

memset(a,0,al+1);

// 检测一个单词长度 do{ if(k < al){

a[k]= ch;

k= k+1;} getch();if(sourceEnd)

return;}while(isalpha(ch)||isdigit(ch));if(k >= kk)kk = k;else { do{

a[kk]= ' ';

kk= kk-1;}while(kk > k);} strcpy(id,a);i= 1;j= norw;// 判断是否是关键字(二分搜索)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))// number { k= 0;num= 0;sym= NUMBER;do{

num= 10 * num + ch-'0';

k= k+1;

getch();}while(isdigit(ch));if(k > nmax)

error(30);} else if(ch == ':'){ getch();if(ch == '='){

sym= BECOMES;

getch();} else

sym= NUL;} else if(ch == '<')

// extra stuff added to support <= { getch();if(ch== '='){

sym= LEQ;

getch();} else

sym= LSS;} else if(ch == '>'){ getch();if(ch == '='){

sym= GEQ;

getch();} else

sym= GTR;} else

// end of extra stuff { sym= ssym[ch];// 其它符号的赋值

getch();} }

// 漏掉空格,读取一个字符

void PL0::getch(){ if(cc == ll){

if(feof(fin))

{

if(sym!=PERIOD)

error(25);

sourceEnd=true;

return;

}

cc= 0;

fgets(line,lineLength,fin);

codeNo++;

ll=strlen(line);

if(line[ll-1]==10)ll--;} ch= line[cc];cc= cc+1;}

// 生成目标代码,并送入目标程序区void PL0::gen(fct x,int y,int z){ if(cx > cxmax){

cout<<”Program too longn“;

return;}

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

cx= cx+1;}//gen end

// 测试当前单词符号是否合法

void PL0::test(symset s1,symset s2,int n){ if(sourceEnd)

return;if(s1.find(sym)==s1.end()){

error(n);

symset::iterator it;

for(it=s2.begin();it!=s2.end();it++)

s1.insert(*it);//s1=s1+s2

while(s1.find(sym)==s1.end())

getsym();} }//test end

// 分程序分析处理过程

void PL0::block(int lev,int tx,symset fsys){ if(sourceEnd)

return;int dx;// data allocation index int tx0;// initial table index int cx0;// initial code index

dx= 3;

// 变量的个数 tx0= tx;// 表指针

table[tx].other.inOther.adr= cx;gen(JMP,0,0);if(lev>levmax)error(32);do{

if(sym == CONSTSYM)

// 处理常量声明

{

getsym();

do{

constdeclaration(tx,dx,lev);

while(sym == COMMA)

{

}

getsym();

constdeclaration(tx,dx,lev);} if(sym ==SEMICOLON)

getsym();else

error(5);}while(sym==IDENT);if(sym == VARSYM)

// 处理变量声明 { getsym();do{

vardeclaration(tx,dx,lev);

while(sym == COMMA){

getsym();

vardeclaration(tx,dx,lev);

}

if(sym ==SEMICOLON)

getsym();

else

error(5);}while(sym==IDENT);} while(sym ==PROCSYM)

// 处理过程的声明 { getsym();if(sym ==IDENT){

enter(PROCEDURE,tx,dx,lev);

getsym();} else

error(4);if(sym ==SEMICOLON)

getsym();else

error(5);symset tmp = fsys;tmp.insert(SEMICOLON);block(lev+1,tx,tmp);if(sym == SEMICOLON){

getsym();

symset tmp = statbegsys;

for(int i= IDENT;i<=PROCSYM;i++)

tmp.insert((symbol)i);

test(tmp,fsys,6);

}

else

error(5);

}

symset tmp=statbegsys;

tmp.insert(IDENT);

test(tmp,declbegsys,7);}while(declbegsys.find(sym)!=declbegsys.end());

code[table[tx0].other.inOther.adr].a= cx;table[tx0].other.inOther.adr= cx;// start adr of code table[tx0].other.inOther.size=dx;

cx0= cx;gen(INT,0,dx);symset tmp=statbegsys;for(int i=SEMICOLON;i <= ENDSYM;i++)

tmp.insert((symbol)i);statement(tmp,tx,lev);gen(OPR,0,0);// return symset s2;test(fsys,s2,8);listcode(cx0);}// block end

// 登入名字表

void PL0::enter(obj0 k,int &tx,int &dx,int lev){ 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].other.val=num;

break;case VARIABLE:

table[tx].other.inOther.level=lev;

table[tx].other.inOther.adr=dx;

dx++;

break;case PROCEDURE:

table[tx].other.inOther.level=lev;

break;case ARRAY:

table[tx].other.inOther.size = lev;

break;} }//enter end

// 查找标示符在名字表中的位置

int PL0::position(alfa id,int tx)//find identifier id in table { int i;strcpy(table[0].name, id);i= tx;while(strcmp(table[i].name,id)!=0)i--;return i;}//position end

// 常量定义处理

void PL0::constdeclaration(int&tx,int&dx,int lev){ if(sym == IDENT){

getsym();

if(sym>=EQL&&sym<=BECOMES)

{

if(sym ==BECOMES)

error(1);

getsym();

if(sym == NUMBER)

{

enter(CONSTANT,tx,dx,lev);

getsym();

}

else

error(2);

}

else

error(3);} else

error(4);}// constdeclaration end

// 变量说明处理

void PL0::vardeclaration(int&tx,int&dx,int lev){ if(sym == IDENT){

enter(VARIABLE,tx,dx,lev);

getsym();} else

error(4);}//vardeclaration end

// 数组说明处理

void PL0::arraydeclaration(int&tx,int&dx,int lev){

int upscript=0,downscript=0;getsym();if(sym == NUMBER || sym == CONSTSYM){

if(num == 0)

{

upscript = num;

getsym();

}

else

error(32);} if(sym == COMMA)

getsym();else

error(32);if(sym == NUMBER || sym == CONSTSYM){

downscript = num;

getsym();} if(sym!= RPAREN)

} error(32);else { enter(ARRAY,tx,dx,downscript+1);getsym();} // 列出目标代码清单

void PL0::listcode(int cx0)//list code generated for this block { int i;if(listswitch)

for(i= cx0;i

cout<<”“<

<<”“<

// 语句部分处理

void PL0::statement(symset fsys,int tx,int lev){ if(sourceEnd)

return;int i,cx1,cx2;if(sym ==IDENT){

i= position(id,tx);

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,tx,lev);

if(sym!= SEMICOLON)

error(10);

if(i!= 0)

gen(STO,lev-table[i].other.inOther.level,table[i].other.inOther.adr);

} else if(sym == READSYM){ getsym();if(sym!=LPAREN)

error(34);else

do{

getsym();

if(sym==IDENT)

i=position(id,tx);

else

i=0;

if(i==0)

error(35);

else

{

gen(OPR,0,16);

gen(STO,lev-table[i].other.inOther.level,table[i].other.inOther.adr);

}

getsym();

}while(sym == COMMA);

if(sym!= RPAREN)

{

error(33);

while(fsys.find(sym)!=fsys.end())getsym();

}

else

getsym();} else if(sym == WRITESYM){ getsym();if(sym==LPAREN){

do{

getsym();

symset tmp=fsys;

for(int t=RPAREN;t<=COMMA;t++)

tmp.insert((symbol)t);

expression(tmp,tx,lev);

gen(OPR,0,14);

}while(sym==COMMA);

if(sym!=RPAREN)

error(33);

else

getsym();} gen(OPR,0,15);} else if(sym ==CALLSYM){ getsym();if(sym!=IDENT)

error(14);else {

i= position(id,tx);

if(i == 0)

error(11);

else if(table[i].kind = PROCEDURE)

gen(CAL,lev-table[i].other.inOther.level,table[i].other.inOther.adr);

else

error(15);

getsym();} } else if(sym ==IFSYM){ getsym();symset tmp=fsys;for(int i = THENSYM;i<= DOSYM;i++)

tmp.insert((symbol)i);condition(tmp,tx,lev);if(sym == THENSYM)

getsym();else

error(16);cx1= cx;gen(JPC,0,0);tmp.insert(ELSESYM);statement(tmp,tx,lev);getsym();

code[cx1].a= cx;

if(sym == ELSESYM){

getsym();

cx2=cx;

gen(JMP,0,0);

code[cx1].a=cx;

statement(fsys,tx,lev);

code[cx2].a=cx;} } else if(sym ==BEGINSYM){ getsym();symset tmp=fsys;for(int i=SEMICOLON;i<=ENDSYM;i++)

tmp.insert((symbol)i);statement(tmp,tx,lev);tmp=statbegsys;tmp.insert(SEMICOLON);while(tmp.find(sym)!=tmp.end()){

if(sourceEnd)return;

if(sym ==SEMICOLON||sym ==ENDSYM)

getsym();

else if(sym=PERIOD)

{

error(26);

getsym();

}

else

error(10);

tmp=fsys;

for(i=SEMICOLON;i<=ENDSYM;i++)

tmp.insert((symbol)i);

if(sourceEnd)return;

if(sym==ENDSYM)

break;

statement(tmp,tx,lev);} if(sym ==ENDSYM)

getsym();else if(!sourceEnd)

error(17);} else if(sym ==WHILESYM){ cx1= cx;

// 记下当前代码分配位置,这是while循环的开始位置

getsym();symset tmp=fsys;tmp.insert(DOSYM);condition(tmp,tx,lev);

cx2= cx;

// 记下当前代码分配位置,这是while的do中的语句的开始位置

gen(JPC,0,0);

if(sym ==DOSYM)

getsym();

else

error(18);

statement(fsys,tx,lev);

gen(JMP,0,cx1);

code[cx2].a= cx;} else if(sym == REPEATSYM){

symset temp1, temp2;

temp1= fsys,temp1.insert(SEMICOLON),temp1.insert(UNTILSYM);

cx1= cx;

getsym();

statement(temp1,tx,lev);

temp2 = statbegsys;

temp2.insert(SEMICOLON);

while(temp2.find(sym)!= temp2.end())

{

if(sym == SEMICOLON)

getsym();

else

error(34);

statement(temp1,tx,lev);

}

if(sym == UNTILSYM)

{

getsym();

condition(fsys,tx,lev);

gen(JPC,0,cx1);

}

else

error(34);

} symset setT;test(fsys,setT,19);}//statement end

// 表达式处理

void PL0::expression(symset fsys,int tx,int lev){ symbol addop;symset tmp=fsys;for(int t=PLUS;t<=MINUS;t++)

tmp.insert((symbol)t);if(sym>=PLUS&&sym<=MINUS){

addop= sym;

getsym();

term(tmp,tx,lev);

if(addop ==MINUS)

gen(OPR,0,1);} else

term(tmp,tx,lev);while(sym >=PLUS&&sym<=MINUS){

addop= sym;

getsym();

term(tmp,tx,lev);

if(addop ==PLUS)

gen(OPR,0,2);

else

gen(OPR,0,3);} }// expression end

// 项处理

void PL0::term(symset fsys,int tx,int lev){ if(sourceEnd)

return;symbol mulop;symset tmp=fsys;for(int t=TIMES;t<=SLASH;t++)

tmp.insert((symbol)t);factor(tmp,tx,lev);while(sym>=TIMES && sym<=SLASH){

mulop= sym;

getsym();

factor(tmp,tx,lev);

if(mulop ==TIMES)

gen(OPR,0,4);

else

gen(OPR,0,5);} }// term end

// 因子处理

void PL0:: factor(symset fsys,int tx,int lev){ int i;test(facbegsys,fsys,24);while(facbegsys.find(sym)!=facbegsys.end()){

if(sym ==IDENT)

{

i= position(id,tx);

if(i == 0)

error(11);

else

switch(table[i].kind)

{

case CONSTANT:

gen(LIT,0,table[i].other.val);

break;

case VARIABLE:

gen(LOD,lev-table[i].other.inOther.level,table[i].other.inOther.adr);

break;

case PROCEDURE:

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();

symset tmp=fsys;

tmp.insert(RPAREN);

expression(tmp,tx,lev);

if(sym == RPAREN)

getsym();

else

error(22);

}

test(fsys,facbegsys,23);} }//factor end

// 条件处理

void PL0::condition(symset fsys,int tx,int lev){ symbol relop;symset tmp=fsys;tmp.insert(EQL),tmp.insert(NEQ),tmp.insert(LSS),tmp.insert(LEQ),tmp.insert(GTR),tmp.insert(GEQ);

if(sym == ODDSYM){

getsym();

expression(fsys,tx,lev);

gen(OPR,0,6);} else {

expression(tmp,tx,lev);

if(tmp.find(sym)==tmp.end())

error(20);

else

{

relop= sym;

getsym();

expression(fsys,tx,lev);

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;

}

} } }//condition end

// 对目标代码的解释执行程序

void PL0::interpret(){ int err1=errorString.size();if(err1>0){

cout<<”存在%d个错误:“<

cout<

t= t+1;

s[t]= i.a;

break;case OPR:

switch(i.a)//operator

{ case 0:// return 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: if(s[t]%2)

s[t]=1;else

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

s[t]=1;else

s[t]=0;break;case 9: t= t-1;if(s[t]==s[t+1])

s[t]=0;else

s[t]=1;break;

case 10: t= t-1;if(s[t]

s[t]=1;else

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

s[t]= 1;else

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

s[t]= 1;else

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

s[t]= 1;else

s[t]=0;break;case 14: cout<<”“<>s[t];break;};break;case LOD:

t= t+1;

s[t]= s[base(i.l,b,s)+i.a];

break;

case STO:

s[base(i.l,b,s)+i.a]= s[t];

t= t-1;

break;

case CAL:// generate new block mark

s[t+1]= base(i.l,b,s);

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:

if(s[t] == 0)

p= i.a;

t= t-1;

break;

}//switch end

}while(p!=0);

cout<<” End PL/0n“;} // interpret end

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

int PL0::base(int l,int b,int s[]){ int b1;b1= b;//find base l levels down while(l>0){

b1= s[b1];

l= l-1;} return b1;}

// 保存代码

void PL0::SaveCode(){ if(fout)

for(int i=0;i

fprintf(fout,”%d %s %d %dn “,i,mnemonic[code[i].f],code[i].l,code[i].a);} TestPL0.cpp代码: #include ”pl0.h“ void main(){ PL0 cp(”testPas2.txt“,”nasm.txt");

symset fsys;

fsys.insert(PERIOD);fsys.insert(CONSTSYM),fsys.insert(VARSYM),fsys.insert(PROCSYM);fsys.insert(BEGINSYM),fsys.insert(CALLSYM),fsys.insert(IFSYM),fsys.insert(WHILESYM);cp.getsym();

// 词法分析,分析一个词

cp.block(0,0,fsys);

// 分程序分析处理功能

cp.SaveCode();

// 保存代码

cp.interpret();

// 对目标代码的解释执行程序

} 实验运行结果:

运行的的文件见下图右侧:实验中我是固定了文件名的,可以是改写成动态输入,由于在测试中我把所有的测试语句都放在同一个文件中了,没有太多的必要。

六、心得体会

在编译程序实现的过程中反复使用了递归调用的思想,且也使用了模块化处理问题的思想,使用模块化的思想关键是在抽象阶段要抽象出对应的模块,且模块的层次必须是清晰的。

在实现此程序中,由于要实现关键字和符号表中字段的搜索,实现中就必须注意快速查找的方法,而在实现的过程中多次用到了二分搜索的方法,这是个比较快的搜索方法。

由于此程序的实现相对比较复杂,且不方便调试,改进时可以把此程序的词法分析,语法分析和执行原代码作为单独的测试程序来测试,这样也方便大家来调试。

通过本次的课设我知道了一个算法的设计是需要静下心来仔细的研究的,且实现中必须先了解程序的整个流程,也就是说在编程中首先必须看懂那些对应的UML图,只有在图的指导下,编程中才不会盲目,也有一定的方向性。同样在编程中必须注意代码的规范,多写一些对应的注释是很必要的,要时刻想这代码并不是给你自己看的,而是必须要给别人看,因此我觉得代码的规范是相当重要的。

第五篇:编译原理课程设计设计任务书

编译原理课程设计任务书

1、目的学生在学习《程序设计语言编译原理》课程过程中,结合各章节的构造编译程序的基本理论,总共用10个课时完成课程设计。在基本实验完成的基础上,逐步完成课程设计。要求用C或C++语言描述及上机调试,实现一个小编译器(词法分析,语法分析,中间代码产生,优化,目标代码生成等重要子程序,其中词法分析、语法分析及语义分析功能必须完成),使学生将理论与实际应用结合起来,受到软件设计等开发过程的全面训练,从而提高学生软件开发的能力。

2、课程设计的任务

(1)设计符号表

确定符号表的组织方式,一般应包括名字栏和信息栏,其中名字栏作为关键字。要考虑能够存储有关名字的信息,并可以高效地完成如下操作:

a.查找:根据给定的名字,在符号表中查找其信息。如果该名字在符号表中不存在,则将其加入到符号表中,否则返回指向该名字的指针;

b.删除:从符号表中删除给定名字的表项。

(2)设计词法分析器

设计各单词的状态转换图,并为不同的单词设计种别码。将词法分析器设计成供语法分析器调用的子程序。功能包括:

a.具备预处理功能。将不翻译的注释等符号先滤掉,只保留要翻译的符号串,即要求设计一个供词法分析调用的预处理子程序;

b.能够拼出语言中的各个单词;

c.将拼出的标识符填入符号表;

d.返回(种别码,属性值)。

(3)语法分析与中间代码产生器

要求用预测分析法、递归下降分析法、算符优先分析法、SLR分析法(几种方法任选),实现对表达式、各种说明语句、控制语句进行语法分析。

若语法正确,则用语法制导翻译法进行语义翻译:对说明语句,要求将说明的各符号记录到相应符号表中;对可执行语句,应产生出四元式中间代码并填写到三地址码表中;

若语法错误,要求指出出错性质和出错位置(行号)。出错处理应设计成一个出错处理子程序。

(4)优化器

a.局部优化:设计出划分基本块的算法,在每一个基本块中实现:合并已知量、删除多余运算和删除无用赋值三种局部优化。设计构造基本块的DAG图的算法,以及将DAG图还原实现基本块的优化的算法。

b.循环优化:只做一重循环优化,完成代码外提,强度削弱和删除归纳变量等三种优化。要求实现while循环和for循环语句的优化。

(5)目标代码生成器

能完成指定寄存器个数的情况下将一中间代码程序段翻译成汇编语言目标代码(汇编指令应包括加、减、乘、除),要求指令条数最少的情况下,尽量使用寄存器,尽量少访问内存,这样才能做到运行效率高。

3、样本语言

样本语言为C-语言(见附录),其中基本的语句要求必须实现,其余部分可根据自己的实际情况选择实现。

4、要求

各函数和过程应有框图描述,有功能说明,有入口和出口参数说明。

5、参考资料

《程序设计语言编译原理》,陈火旺编著,国防工业出版社

《编译原理》,吕映芝、张素琴、蒋维杜编著,清华大学出版社

《编译原理》,Alfred V.Aho等,李建中译,机械工业出版社

6、考察方式

最终完成一个完整的编译程序。要求输入一小段完整的C-语言源程序,输出各编译阶段的运行结果。在课程设计结束时上机运行,展示运行效果。

7、作业提交

最晚在期末(第17周课程结束时)提交纸质作业及可运行程序,格式参考学院的规定课程设计任务书模板。

下载编译原理课程设计_算术表达式的语法分析及语义分析程序设计(模版)word格式文档
下载编译原理课程设计_算术表达式的语法分析及语义分析程序设计(模版).doc
将本文档下载到自己电脑,方便修改和收藏,请勿使用迅雷等下载。
点此处下载文档

文档为doc格式


声明:本文内容由互联网用户自发贡献自行上传,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任。如果您发现有涉嫌版权的内容,欢迎发送邮件至:645879355@qq.com 进行举报,并提供相关证据,工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。

相关范文推荐

    编译原理课程设计心得体会

    经过一个星期的编译原理课程设计,本人在刘贞老师的指导下,顺利完成该课程设计。通过该课程设计,收获颇多。一、对实验原理有更深的理解通过该课程设计,掌握了什么是编译程序,编译......

    编译原理课程设计报告(格式)

    编译原理课程设计报告课题名称:提交文档学生姓名:提交文档学生学号:同组 成 员 名 单:无指导 教 师 姓 名: 指导教师评阅成绩:指导教师评阅意见: 提交报告时间:年月日 1. 课程设计目......

    编译原理课程设计要求

    题目:书中任选一文法对它进行LR分析和语义分析(语言不限制)文档不可少的内容:  实现原理  程序流程图  子函数说明或者类的说明  程序代码及运行结果  心得体会文档不少于12页......

    99《编译原理》课程设计(最终定稿)

    第 1 页 共 3 页《编译原理》课程设计 《编译原理》课程设计 一、 课程设计的目的 通过课程设计,真正掌握设计和构造编译程序的基本原理和常用的编译技术,具备系统软件调试能......

    编译原理课程设计教案

    黄冈师范学院 《编译原理课程设计》教案 (2011·春) 授 课 教 师: 张 瑞 红 授 课 班 级: 计科2008级 授 课 时 间: 2010-2011 二 课题一 有限自动机的运行 一、设计题目:有限......

    编译原理课程设计心得体会

    编译原理课程设计心得体会 经过一个星期的编译原理课程设计,本人在刘贞老师的指导下,顺利完成该课程设计。通过该课程设计,收获颇多。一、对实验原理有更深的理解通过该课程......

    《编译原理》课程设计要求

    《编译原理》课程设计实施方案 课程设计的具体内容以传至QQ群共享《编译原理课程设计具体内容.ppt》中,由于学校没有足够大的机房供我们课程设计,所以课程设计采取单独辅导形......

    编译原理课程设计2011级

    2011级《编译原理课程设计》任务书一、课程设计的性质和目的 编译原理课程设计是计算机专业课程,通过课程设计使学生进一步巩固课堂所学知识,全面熟悉、掌握编译程序编写的基......