北邮编译原理语义分析实验报告

时间：2024.4.5

1. 实验题目和要求................................................................................................... 3

2. 实验分析和思考................................................................................................... 3

3. 翻译方案.............................................................................................................. 4

4. LR实现自底向上分析（摘自语法分析实验）................................................... 5

4.1. 构造识别所有活前缀的DFA......................................................................... 5

4.2. 构造LR分析表.............................................................................................. 6

5. S属性定义的自底向上实现................................................................................. 7

5.1. 扩充分析栈....................................................................................................... 7

5.2. 改造分析程序.................................................................................................... 7

5.3. 编程实现........................................................................................................... 8

6. 运行结果截图：................................................................................................. 14

1. 实验题目和要求

题目：语义分析程序的设计与实现。

实验内容：编写语义分析程序，实现对算术表达式的类型检查和求值。要求所分析算术表达式由如下的文法产生。

实验要求：用自底向上的语法制导翻译技术实现对表达式的分析和翻译。

(1) 写出满足要求的语法制导定义或翻译方案。

(2) 编写分析程序，实现对表达式的类型进行检查和求值，并输出：

① 分析过程中所有产生式。

② 识别出的表达式的类型。

③ 识别出的表达式的值。

(3) 实验方法：可以选用以下两种方法之一。

① 自己编写分析程序。

② 利用YACC自动生成工具。

2. 实验分析和思考

由于要求进行类型检查和求值，所以可以定义两个综合属性，一个记录值一个记录类型，存放在结构中，一并传入传出。

输出的产生式可以作为虚拟综合属性，在产生式的最后打印出来。

id认为是定义的变量名，假设是26个小写字母，它们的值存于一个数组里。

将类型检查和求值归于一次扫描，当检查类型出错时则停止，否则继续。

哈希实现输入的映射，模拟词法分析的记号流。

输入格式为每个num和id对应两个输入字符，其他运算符仍对应一个字符。比如第4个num,输入为num4。

由于只具有综合属性，故可以用S属性的自底向上翻译实现，利用LR分析程序来实现，只需扩充分析站和改造分析程序。

PS:这次实验我只是简单模拟了最简单的显式严格匹配，即没有实现隐式类型转换。

3. 翻译方案

4. LR实现自底向上分析（摘自语法分析实验）

4.1. 构造识别所有活前缀的DFA

构造扩展文法

FIRST和FOLLOW集如下

构造识别所有活前缀的DFA如下

4.2. 构造LR分析表

(1) (4) (7)

(2) (5) (8)

(3) (6) (9)

5. S属性定义的自底向上实现

5.1. 扩充分析栈

多定义一个结构栈数组，结构里有两个变量，一个为val, 一个为type。实现时，val其实是定义了两个变量，一个表示int时的值，一个表示real时的值，因为无法公用一个类型的变量。

定义type只有三种，一种为int, 一种为real, 一种为type_error。

val由外部提供。可通过数组搜索。

5.2. 改造分析程序

在归约时完成类型检查和求值。

之所以与归约联系，是因为每一次归约决定着所用的是哪一个产生式。

acc时打印最终求值结果和表达式类型。

5.3. 编程实现

#include <cmath>

#include <stack>

#include <vector>

#include <string>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <iostream>

#include <algorithm>

usingnamespace std;

const int S = 1; //移进

const int R = 2; //归约

const int ACC = 3; //分析成功

const int Vt_num = 9; //终结符和$数

const int Vn_num = 3; //非终结符数

const int State_num = 17; //状态数

const int formula_num = 10; //扩展文法产生式数目

const int Max_input = 1024; //输入记号流长度

const int max_stack = 2500; //栈的最大高度

int token[Max_input]; //记号流

int len; //记号流长度

int pointer; //定义指向输入串的指针

string fm[formula_num]; //存放对应的产生式

int f_vn[formula_num]; //产生式对应的左部的非终结符

int flen[formula_num]; //产生式的长度

stack<int> st; //定义栈

struct action

{

int rs; //初始化表项的动作为0即出错，R归约S移进ACC成功

int no;

}act[State_num][Vt_num]; //action表表项

int gto[State_num][Vn_num];//goto表表项

struct attri

{

int type; //int-1, real-2, type_error-0

int i_val;

double r_val;

}val[max_stack];

int v_top;

void initial_table()

{

//初始化分析表

memset(act, 0,sizeof(act));

memset(gto,-1,sizeof(gto));

//动作表action

act[0][4]={S, 4}; act[0][5]={S, 6}; act[0][6]={S, 5};

act[1][0]={S, 7}; act[1][1]={S, 8}; act[1][8].rs = ACC;

act[5][4]={S, 4}; act[5][5]={S, 6}; act[5][6]={S, 5};

act[7][4]={S, 4}; act[7][5]={S, 6}; act[7][6]={S, 5};

act[8][4]={S, 4}; act[8][5]={S, 6}; act[8][6]={S, 5};

act[9][4]={S, 4}; act[9][5]={S, 6}; act[9][6]={S, 5};

act[10][4]={S, 4}; act[10][5]={S, 6}; act[10][6]={S, 5};

act[11][0]={S, 7}; act[11][1]={S, 8}; act[11][7]={S,16};

act[3][0]= act[3][1]= act[3][2]= act[3][3]= act[3][7]= act[3][8]={R, 6};

act[4][0]= act[4][1]= act[4][2]= act[4][3]= act[4][7]= act[4][8]={R, 7};

act[6][0]= act[6][1]= act[6][2]= act[6][3]= act[6][7]= act[6][8]={R, 9};

act[14][0]= act[14][1]= act[14][2]= act[14][3]= act[14][7]= act[14][8]={R, 4};

act[15][0]= act[15][1]= act[15][2]= act[15][3]= act[15][7]= act[15][8]={R, 5};

act[16][0]= act[16][1]= act[16][2]= act[16][3]= act[16][7]= act[16][8]={R, 8};

act[2][2]={S, 9}; act[2][3]={S, 10};act[2][0]= act[2][1]= act[2][7]= act[2][8]={R, 3};

act[12][2]={S, 9}; act[12][3]={S,10}; act[12][0]= act[12][1]= act[12][7]= act[12][8]={R, 1};

act[13][2]={S, 9}; act[13][3]={S,10}; act[13][0]= act[13][1]= act[13][7]= act[13][8]={R, 2};

//转移表goto

gto[9][2]= 14;

gto[10][2]= 15;

gto[11][2]= 16;

gto[7][1]= 12; gto[7][2]= 3;

gto[8][1]= 13; gto[8][2]= 3;

gto[5][0]= 11; gto[5][1]= 2; gto[5][2]= 3;

gto[0][0]= 1; gto[0][1]= 2; gto[0][2]= 3;

//产生式存入fm数组

//记录产生式对应的左部的非终结符f_vn

//记录产生式右部的长度flen

fm[1]= "E -> E+T \n"; f_vn[1]= 0; flen[1]= 3;

fm[2]= "E -> E-T \n"; f_vn[2]= 0; flen[2]= 3;

fm[3]= "E -> T \n"; f_vn[3]= 0; flen[3]= 1;

fm[4]= "T -> T*F \n"; f_vn[4]= 1; flen[4]= 3;

fm[5]= "T -> T/F \n"; f_vn[5]= 1; flen[5]= 3;

fm[6]= "T -> F \n"; f_vn[6]= 1; flen[6]= 1;

fm[7]= "F -> id \n"; f_vn[7]= 2; flen[7]= 1;

fm[8]= "F -> (E) \n"; f_vn[8]= 2; flen[8]= 3;

fm[9]= "F -> num \n"; f_vn[9]= 2; flen[9]= 1;

}

/*初始化num和id表项的值*/

void initial_entry()

{

//id: A-M为int,N-Z为real

//num:a-m为int,n-z为real

//值为A/a:0, N/n:0.00

}

void lexi_input()

{

//调用词法分析程序

//+ - * / id num ( ) $分别对应从0到8的整数

//A-Z为id(4), a-z为num(5)

//'a'-97, 'A'-65

//处理输入字符串将记号流存到token[]数组里

//并将记号流长度赋给len

//eg: (a+b)*c/(L-E)

//token={6, 97, 0, 98, 7, 2, 99, 3, 6, 76, 1, 69, 7};

//len=13;

//eg:O-N+n

//token={79, 1, 78, 0, 110};

//len=5;

//eg:O-M+m

//token={79, 1, 77, 0, 109};

//len=5;

}

void error()

{

puts("E R R O R !!!");

//错误处理程序

}

int main()

{

initial_table();

initial_entry();

lexi_input();

token[len]=Vt_num-1;

len++;

while(!st.empty())

st.pop(); //清空栈

st.push(0); //0状态入栈

pointer=0; //指针指向输入记号流的第一个记号

v_top=1; //属性值指针

int cur_state, cur_token;

int i, j;

do{

cur_state = st.top(); //栈顶状态

cur_token = token[pointer];//当前指针指向的输入符号

if(cur_token>='a' && cur_token<='z') cur_token=5;

elseif(cur_token>='A' && cur_token<='Z') cur_token=4;

if(act[cur_state][cur_token].rs == S)

{

/*移进，只需让val也同步移进*/

st.push(cur_token);

st.push(act[cur_state][cur_token].no);

if(cur_token==5)

{

if(token[pointer]<'n')val[v_top].type=1, val[v_top].i_val=token[pointer]-'a';

else val[v_top].type=2, val[v_top].r_val=token[pointer]-'a'+0.0;

}

elseif(cur_token==4)

{

if(token[pointer]<'N')val[v_top].type=1, val[v_top].i_val=token[pointer]-'A';

else val[v_top].type=2, val[v_top].r_val=token[pointer]-'A'+0.0;

}

v_top+=2;

pointer++;

printf("s%d\n",act[cur_state][cur_token].no);

}

elseif(act[cur_state][cur_token].rs == R)

{

/*归约，检查类型并计算属性值*/

j=act[cur_state][cur_token].no;

i=2*flen[j];

while(i-->0)

{

st.pop();

}

printf("r%d ", act[cur_state][cur_token].no);

cout<<fm[j];

cur_state=st.top();

st.push(f_vn[j]+ Vt_num);

st.push(gto[cur_state][f_vn[j]]);

if(j==1)//E->E+T

{

if(val[v_top-2].type==val[v_top-6].type)

{

if(val[v_top-6].type==1)

val[v_top-6].i_val+=val[v_top-2].i_val;

else

val[v_top-6].r_val+=val[v_top-2].r_val;

v_top-=4;

}

else

{

printf("TYPE_ERROR !!!\n");

break;

}

elseif(j==2)//E->E-T

{

if(val[v_top-2].type==val[v_top-6].type)

{

if(val[v_top-6].type==1)

val[v_top-6].i_val-=val[v_top-2].i_val;

else

val[v_top-6].r_val-=val[v_top-2].r_val;

v_top-=4;

}

else

{

printf("TYPE_ERROR !!!\n");

break;

}

elseif(j==4)//T->T*F

{

if(val[v_top-2].type==val[v_top-6].type)

{

if(val[v_top-6].type==1)

val[v_top-6].i_val*=val[v_top-2].i_val;

else

val[v_top-6].r_val*=val[v_top-2].r_val;

v_top-=4;

}

else

{

printf("TYPE_ERROR !!!\n");

break;

}

elseif(j==5)//T->T/F

{

if(val[v_top-2].type==val[v_top-6].type)

{

if(val[v_top-6].type==1)

val[v_top-6].i_val/=val[v_top-2].i_val;

else

val[v_top-6].r_val/=val[v_top-2].r_val;

v_top-=4;

}

else

{

printf("TYPE_ERROR !!!\n");

break;

}

elseif(j==8)//F->(E)

{

val[v_top-6]=val[v_top-4];

v_top-=4;

}

elseif(act[cur_state][cur_token].rs == ACC)

{ /*表达式类型检查无误，输出类型及值*/

puts("S U C C E S S !!!");

printf("The expression type is ");

if(val[v_top-2].type==1)printf("integer");

else printf("real");

printf(", the value is ");

if(val[v_top-2].type==1)printf("%d\n\n", val[v_top-2].i_val);

else printf("%lf\n\n", val[v_top-2].r_val);

break;

}

else

{

error();

break;

}

}while(1);

return 0;

}

6. 运行结果截图：

① 输入符号串为 O-N+n

即token={79, 1, 78, 0, 110};

len=5;

② 输入符号串为 (a+b)*c/(L-E)

即token={6, 97, 0, 98, 7, 2, 99, 3, 6, 76, 1, 69, 7};

len=13;

③ 输入符号串O-M+m

即token={79, 1, 77, 0, 109};

len=5;

更多相关推荐：

编译原理语义分析实验报告免费: 编译原理综合训练语义分析实验报告指导老师班级学生zeadom学号学生学号20xx629目录语言文法的形式化描述3语义规则3运行环境介绍5关键算法的流程图及文字解释51本编译器的总框架52在语义分析中的主要函数介...
编译原理语义分析: 编译原理实验报告姓名闫梦丽班级软件工程学号日期语义分析器0901090801010120xx年4月1题目要求11实验目的通过上机实习加深对语法制导翻译原理的理解掌握将语法分析所识别的语法成分变换为中间代码的语义...
编译原理语义分析实验报告——免费!: 语义分析实验报告一实验目的通过上机实习加深对语法制导翻译原理的理解掌握将语法分析所识别的语法成分变换为中间代码的语义翻译方法二实验要求采用递归下降语法制导翻译法对算术表达式赋值语句进行语义分析并生成四元式序列三...
实验三报告：编译原理语义分析: 编译原理实验词义分析指导老师学生学号班级时间20xx541文件构成2代码中宏函数变量宏定义函数变量3简易流程图参见图片函数调用图副本bmp4实验结果使用的源代码生成的词最终代码分析5改进增加注释来表明生成经历的...
语义分析实验报告(实验三): 编译原理语义分析实验报告软工082班兰洁20xx31104044一实验内容二实验目的三实验要求四程序流程图五程序代码与主要过程说明六测试用例七输出结果八实验心得一实验内容定义模拟的简单语言的语义成分将语义分析程...
编译原理_ 语义分析_实验报告: 编译原理实验三语义分析实验报告学院数学与计算机科学技术学院专业计算机科学与技术班级级计算机班小组组员姓名姓名学号姓名学号姓名学号编译原理实验三语义分析实验题目一实验目的要求学生用与实验2相同的语言编制语义分析程...
编译原理实验报告3: 编译原理实验报告表达式语法分析表达式语法分析实验报告一实验题目设计一个简单的表达式语法分析器采用递归下降方法设计实现二实验目的1了解形式语言基础及其文法运算2熟悉语法分析原理及4种常用的语法分析方法其中四种算法...

编译原理语义分析实验报告: 实验3语义分析实验报告一实验目的通过上机实习加深对语法制导翻译原理的理解掌握将语法分析所识别的语法成分变换为中间代码的语义翻译方法二实验要求采用递归下降语法制导翻译法对算术表达式赋值语句进行语义分析并生成四元式...
编译原理实验报告模版-语义分析: 编译原理课程实验报告实验3语义分析
编译原理实验报告: 南华大学计算机科学与技术学院实验报告20xx20xx学年度第二学期课程名称编译原理词法分析语法分析语义分课程设计析以及中间代码的生成姓名胡艳霞学号20xx4440238专业计算机班级计算机092班地点8212教...

北邮编译原理LR语法分析程序实验报告: LR语法分析程序实验报告说明该程序使用实现对算术表达式自底向上的语法分析并且在对输入表达式进行分析的过程中输出分析动作移进或者用哪个产生式进行规约该程序使用的是LR语法分析程序手动构造了识别所有活前缀的DFA为...
编译原理词法分析器语法分析器实验报告: 编译技术课程设计班级学号姓名指导老师二零一零年七月一目的ltlt编译技术gtgt是理论与实践并重的课程而其实验课要综合运用一二年级所学的多门课程的内容用来完成一个小型编译程序从而巩固和加强对词法分析语法分析语义...

编译原理语义分析实验报告（22篇）

热门关注

编译原理实验报告模版-语义分析

20xx广工编译原理实验报告

实验1-3 《编译原理》词法分析程序设计方案

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

编译原理实验报告

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

语义分析实验报告

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