1.题目:将WHILE语句转换成四元式的程序实现
设计内容及要求:设计一个语法制导翻译器,将WHILE语句翻译成四元式。要求:先确定一个定义WHILE语句的文法,为其设计一个语法分析程序,为每条产生式配备一个语义子程序,按照一遍扫描的语法制导翻译方法,实现翻译程序。对用户输入的任意一个正确的WHILE语句,程序将其转换成四元式输出(可按一定格式输出到指定文件中)。
1、系统描述
通过设计、编制、调试一个WHILE循环语句的语法及语义分析程序,加深对语法
及语义分析原理的理解,并实现词法分析程序对单词序列的词法检查和分析。用语法
制导完成语义分析,并将形成的中间代码以四元式的形式输出。
2 、文法及属性文法的描述
2.1 文法的描述
该文法的产生式如下所示:
(1)S->while(B){E}
(2)E->AE
(3)E->A
(4)A->iPA
(5)A->i
(6)B->iTi
(7)B->i
其中while、( 、) 、{ 、} 、P、T 、;和i均为终结符,而S、A、B、E这些大写字母均为非终结符。T表示比较运算符,P表示算术运算符,i表示合法标识符。
2.2 属性文法的描述
对该文法的属性文法描述如下:
(1) S->while(B){E}prinf(if B goto E else goto next)
(2) E->AE print(E.val = A.val·E.val)
(3) E->A print(E.val = A.val)
(4) A->i P A print(A= i.Val P A.Val)
(5) A->i; A.Val = i;
(7) B->i B.Val = i
3 、语法分析方法描述及语法分析表设计3.1 语法分析表设计
3.1.1 文法的DFA
3.1.2 LR(0)分析方法描述说明
LR分析法的规约过程是规范推到的逆过程,所以LR分析过程是一种规范规约的过程。其分析过程为:由文法构造出该文法项目集,再根据项目集构造该文法的DFA,再判断是否有移进-规约和规约-规约冲突,若没有冲突则该文法为LR(0)的,若有冲突则该文法是SLR(1)的,最后可以构造出LR(0)分析表。然后根据LR(0)分析表进行语法分析,分析过程就是进栈和规约的过程。若能规约出开始符S,则语法正确。反之,语法错误。
4 、中间代码形式的描述及中间代码序列的结构设计
本系统中所采用的中间代码形式是四元式,是一种比较普遍采用的形式。四元式的四个组成成分是:算符op,第一和第二运算对象ARG1和ARG2及运算结果RESULT。
运算对象和运算结果有时指用户自己定义的变量,有时指编译程序引进的临时变量。
例如a:=b*c+b*d的四元式表示如下:
2)(*,b,d,t2)
3)(+,t1,t2,t3)
4)(:=,t3,-,a)
四元式对中间结果的引用必须通过给定的名字,也就是说,四元式的联系是通过临时变量实现的。
将while( B rop C )goto L写成(jrop,B,C,L)
本程序中所用到的四元式语句如下:
1)形如(op,arg1,arg2,result)的赋值语句
2)形如(jrop,B,C,L)的条件转移语句
3)形如(=,arg1,-,result)的复写语句
5、编译系统的概要设计
5.1词法分析
词法分析程序要做的工作是:从源程序的第一个字符开始,顺序读字符,一次读一个,
根据所读进的字符识别各类单词,同时去掉源程序中的空白和注释。词法分析检查的错误主要是挑出源程序中出现的非法符号。所谓非法符号是指不是程序设计语言中允许出现的符号,就像自然语句中的错字。
础上,分析并判定程序的语法结构是否符合语法规则。
流程图如下:
其中SP 为栈顶指针,S[i]为状态栈,X[i]为文法符号栈。状态转换表内容按关系GOTO[Si,X]=Sj 确定,改关系式是指当前栈顶状态为Si 遇到当前文法符号为X 时应转向状态Sj 。X 为终结符或非终结符。
ACTION[Si,a]规定了栈顶状态为Sj 时遇到输入符号c[i]应该执行的动作。动作有以下四种可能:
(1) 移进:当Sj=GOTO[Si ,a]成立,则把Sj 移入到文法符号栈。其中i ,j 表示状态号。 (2) 规约:当在栈顶形成句柄为b 时,则用b 归约为相应的非终结符A ,即当文法中有
A->b 的产生式,而b 的长度为r ,则从状态栈和文法符号栈中自栈顶向下去掉r 个符号。并把A 移入文法符号栈内,再把满足Sj=GOTO[Si ,A]的状态移进状态栈,其中Si 为修改指针后的栈顶状态。
(3) 接受acc :当归约到文法符号栈中只剩下文法的开始符号S 时,并且输入符号串已
结束即当前输入符是‘#’,则为分析成功。
(4) 报错:当遇到状态栈顶为某一状态下出现不该遇到的文法符号时,则报错,说明输
入串不是该分发能接受的句子。
5.3
语法制导翻译
Sp →
#
┋ ┋ ┋ ┋
X[i] S[i] 输出
栈
(或
语义规则描述的语义动作)进行翻译。属性文法的每个符号有属性,所以每个符号入栈时,必须连属性一起入栈,这样,栈符号就由文法符号及存放该符号属性的域所组成。由于属性类型不同,属性域存放的内容就要根据属性的类型来定。有的可能直接存放属性值,也有的存放的是指向属性值的指针。对于综合属性,其属性域不存放其属性值,而是存放一个指针,指向存贮该属性值的单元。对于继承属性,其属性域直接保存其属性值。继承属性的属性域刚入栈时为空,但是在该栈符号变成栈顶符号之前的某一时刻,它们必须接受相应的属性值,即在成为栈顶时,继承属性的属性域必须有值。
6 、详细的算法描述
Main() //主程序算法
{
open("save.txt"); //打开输入文件
open("output.txt"); //打开输出文件
Print(G[S]); //显示文法G[S]
int check,over=0;
int m,k;
char chr;
for(m=0;m for(k=0;k t[m].name[k]='\0'; //初始化t[] initlab(); //初始化LR(0)分析表 get(sym); //取一个字符 while(sym!=结束) { chr=Getsymbol(); //词法分析 if(chr为空格) continue; else { S[num]=chr; //保存词法分析结果 num++; } } S[num++]='#'; print("The while sentence is:"); LR(); //语法分析 if(over==-1||Check!=1) { print("Your input does not tally with the grammar!"); close(文件); return -1; } if(Check==1) { print("Parsing completed!"); close(文件); return -1; } close(文件); return 0; } LR() //语法分析算法 { i=0; int k=0; status.push(0); symbol.push('#'); a=输入串队列队首元素; b=结束符号; c=符号栈栈顶元素; d=状态栈栈顶元素; s=开始符号; while(a!=b&&c!=s) { if(k==0) { k=meet(d,a); continue; } if(k==1) { k=meet(d,c); continue; } if(k==-1) { 出错 break; } if(k==2) { 成功 break; } } k=0; while(a==b) //分析结束 { if(c==s) { if(meet(d,a)==2) { ONE(); //语法正确,输出四元式 成功 break; } } if(c!=s&&(meet(d,c)==1||meet(d,c))==0) continue; else if(meet(d,c)==-1) { 出错 break; } } } meet(int c,char s) //进栈规约算法 { if(s==错误) return -1; int m,k=0; if(规约标志为1) { 规约 return 1; //规约成功} else 进栈 } char Getsymbol() //词法分析算法 { i=0; while(sym!=结束) { if(sym==合法标识符的开头) { int h1=0,h2=0,h3=0; while(sym==字母/数字/下划线) { 保存sym到token[]中; get(sym); //取下一字符 } 判断token[]中的字符串是否为关键字while/rop/op if(是while) return 'w'; //返回while给主程序 else if(是rop) return 'r'; //返回rop给主程序 else if(是op) return 'o'; //返回op给主程序 else return 'i'; } //已经取了下一个字符 else if(sym==数字) { while(sym==数字) { 保存sym到token[]中; get(sym); //取下一字符} return 'i'; //数字 } else if(sym=='(') { 保存sym到token[]中; get(sym); //取下一字符 return '('; } else if(sym==')') { 保存sym到token[]中; get(sym); //取下一字符 return ')'; } else if(sym=='=') { 保存sym到token[]中; get(sym); return '='; } else if(sym==' ') { get(sym); return ' '; } else { get(sym); return 'X'; //错误 } } return 0; } 7 软件的测试方法和测试结果 7.1运行正确时的情况如下: 7.2词法分析的结果保存在cifa.txt中: 7.3语法分析的过程保存在yufa.txt中: 7.4四元式形式的中间代码输出在obj.txt中: 7.5当文法分析出错时的情况如下: 当语法分析进行到第5步时由于在分析表中找不到相应的下一个状态,故会出错! 8 研制报告 通过本次的编译原理的课程设计,我进一步认识了LR分析方法,对于大多数用无二义性的上下文无关文法描述的语言都可以用相应的LR分析器进行识别,而且这种方法还具有分析速度快,能准确、即使地指出出错的位置。但是它有一个很明显的缺点:对于一个实用的高级语言程序,文法的分析器的构造工作量是相当大的。本次课程设计,我就仅仅只是用了一个简单的直接文法来构造分析表实现“WHILE循环语句的翻译程序设计”,因此,有许多的不足之处,例如:改程序只能支持WHILE循环判断中的“>”和“<”两种条件,还有就是表达式的部分只支持简单的赋值语句的运算。 此外,在课程设计的过程中我又复习了一些C++编程的知识点,熟悉了一些常用的库函数,例如:字符函数库 控制台进行数据输入和数据输出的函数,主要是一些用户通过按键盘产生的对应操作,比如getch()函数等等。iomanip.h是I/O流控制头文件,用于格式化的输出。还熟悉了关于Stack类的函数的运用,剩去了我们自己定义stack函数的麻烦,只需在头文件中加入#include 总结下来,此次课程设计使我获益匪浅,在实践中点点滴滴的提升了自己的逻辑分析和编程以及调试程序的能力。 【关键字】教学 《F o r循环语句》教学设计 池州市第八中学杜亦麟 课题 For循环语句 教学内容 粤教版信息技术(选修1)《算法与程序设计》第二章《程序设计根底》第四节《程序的循环结构》第一小节《For循环语句》 教学目标 知识与能力: 1.理解循环结构的基本思想及For语句的执行过程。 2.培养和提高学生逻辑思维能力,使其可以独立完成简单循环结构算法的设计。 3.能够利用For循环语句实现循环结构,解决实际问题。 过程与方法: 1.通过简单的数学问题的分析、讲解,让学生掌握For循环语句语法知识,及其执行原理。 2.以任务驱动,学生分组合作探究的方式,进一步让学生理解For循环语句的基本思想,同时培养学生自主探究和合作学习的能力。 3.通过自评和互评活动,培养学生语言表达能力和归纳总结能力。 情感态度与价值观: 1.提高学生学习兴趣,培养学习的主动性和探究性。 2.培养学生团结协作精神,体验成功的快乐。 教学重点 1.掌握For循环语句的格式和功能; 2.理解For循环语句的执行过程。 教学难点 控制循环的条件、确定循环体的内容 教材分析 第二章是程序设计根底,也是全书的根底。它沿着分析问题、设计算法、编写程序等运用计算机解决问题之路,开始学习如何使用VB程序设计编写程序解决问题。本节课的主要内容For语句的基本格式、执行过程及语句的实际应用。又是本章的重点和难点内容。而循环结构是程序设计的三种基本结构之一,其作用是使一段程序反复执行。For循环语句在程序设计中频繁出现,也是三种结构中较难的一种,因此,学好本节课非常重要,本节课的学习会使学生对算法有一个更深刻的理解,为以后的程序设计打下一个良好的根底,也可以培养学生的创新能力、分析问题和解决问题的能力以及探究精神。 学生分析 1、知识储备根底 在前面的学习中,同学们已经初步掌握了VB编程环境和VB程序的运行方法及程序设计的根底知识,学习了顺序结构和分支结构的程序执行流程和编程。具备一定的算法根底和具有一定的比较、归纳能力。 目录 1 系统描述 (2) 1.1目的 (2) 1.2设计内容: (2) 1.3翻译过程 (2) 1.4初始条件: (3) 1.5 开发平台 (3) 2文法及属性文法的描述 (3) 3 语法分析表设计 (4) 3.1 LR分析概述 (4) 3.2 LR(0)分析表 (5) 3.3 LR语法分析过程的设计思想及算法 (7) 3.4 翻译方法 (8) 4 中间代码形式的描述及中间代码序列的结构设计 (8) 5简要的分析与概要设计 (9) 6详细的算法描述 (9) 6.1 main函数 (10) 6.2词法分析 (10) 6.3 语法分析 (12) 7 测试方法和测试结果 (13) 7.1测试过程 (13) 7.2 测试结论 (14) 8 研制报告 (14) 8.1研制过程 (14) 8.2本设计的评价 (15) 8.3个人心得体会 (15) 9 参考文献 (16) 本科生课程设计成绩评定表 (17) FOR循环语句的翻译程序设计 ——LR方法、输出四元式 1 系统描述 1.1目的 通过设计、编制、调试一个FOR循环语句的语法及语义分析程序,加深对语法及语义分析原理的理解,实现词法分析程序对单词序列的词法检查和分析,并且实现对单词序列的语法分析、语义分析以及中间代码生成。 1.2设计内容: 本设计按照要求设计出for语句的简单文法,并使用LR分析法对用户输入的程序进行分析和翻译。 对下列正确的程序输入: for(i=0;i<10;i++) { m=m+i; } 结果程序要对该输入进行词法分析,然后利用LR分析法对词法分析后得到的单词序列进行语法分析,经过语法制导翻译显示出等价的四元式表示的中间代码。 对于错误的程序输入,如: for(i=0;i<10) { m=m+i; } 结果程序要指出程序出错。 1.3翻译过程 while 循环 语法形式: while(条件) { 需要循环执行的语句; } while 是“当”的意思。 请首先和if语句作一个比较: if(条件) { 条件成立时执行的语句; } 二者除了关键字不一样以外,结构完全一样。但一定要注意,在条件成立时,if语句仅仅执行一遍,而while语句则将反复执行,直到条件不再成立。 请看while循环的流程图: 程序从“前面的语句”开始执行,然后进行条件判断,如果条件成立,则执行一次“每次循环执行 的语句”,再后请特别注意红色部分,这是我们碰上的,第一次会往后走流程:红线就像汽车拐弯, 掉头到条件处(并不包括前面的语句),然后再进行下一次的条件判断……直到某一次判断时条件不 成立了,程序“继续后面的语句”。 我们用while的语法套用生活中的实际例子,可以直观地看出while的用法。 假设有一个爱哭的小娃娃,有一天她要求父母给买一条小红裙,可惜父母不同意,于是她就开始一个循环: while ( 父母不给买小红裙) { 我哭; } 这段“代码”的意思是:当“父母不给买小红裙”,那么,小女孩就一遍一遍地哭。 这就是我们和循环流程的第一个遭遇战。所举的例子看似直观:“小孩一遍遍地哭,直到父母给买裙”,但真正要用程序的语言来正确地表达出来,需要很多方面要考虑到,必竟,程序是严谨的。 首先,一个合适的判断是否继续的条件相当重要。小女孩要继续哭,仅仅“父母不给买小红裙”,这显示不符合事实,想想我们小时候,再会哭,最终也有累的时候,所以,要想继续哭,我们的条件有两个:“父母不给买小红裙”并且“我还没有哭累”。 while ( 父母不给买小红裙&& 我还没有哭累) { 我哭; } 其次,大多数情况下,条件需要被恰当地改变。小女孩在不停地哭,那么她如何知道父母是否买了红裙呢?所以,她不能只顾哭,还得在哭的间隙观察大人是否同意买裙。至于是否哭累,我们假设小女孩有一个疲劳度,每哭一次疲劳度加1,当疲劳度到达200时,可怜的小女孩累了…… while(父母不给买小红裙&& 疲劳度< 200) { 我哭; 我偷看爸妈是否同意买裙; 疲劳度++; } 例一:用while 语句实现求从1到100的累加和。 求1+2的和,我们可以写a = 1 + 2;求1加到100,我们当然可以这样写a = 1 + 2 + 3 + ... 100.不过这样写显然太累人了,要从1写到100啊!所以聪明如高斯的你,当然也知道这样写:a = (1+100) * 50;这确实是个在任何时候都值得称赞的,又快又简的方法,只是今天我们想让计算机累一点,老老实实地从1加到100。首先用我们先学的while式的循环。 请同学们打开CB,然后新建一空白的控制台程序,在main()函数体加入下面黑体部分代码。然后按F9运行。查看运行结果以加深印象。 //--------------------------------------------------------------------------- #include 第33、34课时for循环的嵌套 实验题一: 1、下面有关for循环的正确描述是: D A) for循环只能用于循环次数已经确定的情况 B) for循环是先执行循环体语句,后判断表达式 C) 在for循环中,不能用break语句跳出循环体 D) for循环的循环体语句中, 可以包含多条语句,但必须用花括号括起来 2、对for(表达式1;;表达式3)可理解为:B A) for(表达式1; 0;表达式3) B) for(表达式1;1;表达式3) C) for(表达式1;表达式1;表达式3) D) for(表达式1;表达式3;表达式3) 3、若i为整型变量,则以下循环执行次数是:B for (i=2;2==0;) printf("%d",i-- ); A)无限次B) 0次 C) 1 次 D) 2次 4、以下for循环的执行次数是:C for (x=0,y=0; (y=123)&&(x<4); x++) ; A)是无限循环 B)循环次数不定C)执行4次 D)执行3次 成立,x++x=2 第三次:(y=123)&&(2<4)成立,x++x=3 第四次:(y=123)&&(3<4)成立,x++x=4 第五次:(y=123)&&(4<4)不成立,退出循环。 5、以下不是无限循环的语句为:A A) for (y=0,x=1;x > ++y;x =i++) i=x ; B) for (;1; x++=i); C) while (1) {x ++;} D) for(i=10;1 ;i--) sum+=i; 6、下面程序段的运行结果是:C for (y=1;y<10;) y=((x=3* y,x+1),x-1); printf ("x=%d,y=%d",x,y); A)x=27,y=27 B)x=12,y=13 C)x=15,y=14 D)x=y=27 第一次:1<10为真,x=3,x+1=3+1=4, y=(4,x-1) y=(4,2)=2 第二次: 2<10为真, x=3*2=6,7 y=(7,x-1)=(7,5) y=5 第三次:5<10为真,x=3*5=15 16 y=(16,x-1)=(16,14) y=14 第四次: 14<10为假, 课程设计任务书 学生姓名:辛波专业班级:计算机0707班 指导教师:彭德巍工作单位:计算机科学与技术学院 题目: FOR循环语句的翻译程序设计(递归下降法、输出四元式) 初始条件: 理论:学完编译课程,掌握一种计算机高级语言的使用。 实践:计算机实验室提供计算机及软件环境。如果自己有计算机可以在其上进行设计。 要求完成的主要任务:(包括课程设计工作量及其技术要求,以及说明书撰写等具体要求) (1)写出符合给定的语法分析方法的文法及属性文法。 (2)完成题目要求的中间代码四元式的描述。 (3)写出给定的语法分析方法的思想,完成语法分析和语义分析程序设计。 (4)编制好分析程序后,设计若干用例,上机测试并通过所设计的分析程序。 (5)设计报告格式按附件要求书写。课程设计报告书正文的内容应包括: 1 系统描述(问题域描述); 2 文法及属性文法的描述; 3 语法分析方法描述及语法分析表设计; 4 按给定的题目给出中间代码形式的描述及中间代码序列的结构设计; 5 编译系统的概要设计; 6 详细的算法描述(流程图或伪代码); 7 软件的测试方法和测试结果; 8 研制报告(研制过程,本设计的评价、特点、不足、收获与体会等); 9 参考文献(按公开发表的规范书写)。 时间安排: 设计安排一周:周1、周2:完成系统分析及设计。 周3、周4:完成程序调试及测试。 周5:撰写课程设计报告。 设计验收安排:设计周的星期五第1节课开始到实验室进行上机验收。 设计报告书收取时间:设计周的次周星期一上午10点。 指导教师签名: 2010年 01月 08日 系主任(或责任教师)签名: 2010年 01月 08日 for循环语句 for循环语句也称为计次循环语句,一般用于循环次数已知的情况。例如,要计算1到100之间所有整数的和,就可以使用for循环语句。具体代码如下: int sum=0; for(int i=1;i<=100;i++){ sum+=i; } System.out.println("1到100之间所有整数的和是: "+sum); 在对for循环语句有一个初步的认识后,下面给出for循环语句的语法格式。for循环语句的语法格式如下: for(初始化语句;循环条件;迭代语句){ 语句序列 } 初始化语句:为循环变量赋初始值的语句,该语句在整个循环语句中只执行一次。 循环条件:决定是否进行循环的表达式,其结果为boolean类型,也就是其结果只能是true或false。 迭代语句:用于改变循环变量的值的语句。 语句序列:也就是循环体,在循环条件的结果为true时,重复执行。 说明: for循环语句执行的过程是:先执行为循环变量赋初始值的语句~然后判断循环条件~如果循环条件的结果为true~则执行一次循环体~否则直接退出循环~最 后执行迭代语句~改变循环变量的值~至此完成一次循环,接下来将进行下一次循环~直到循环条件的结果为false~才结束循环。 for循环语句的执行过程如图1所示。 初始化语句 N循环条件 Yfor(初始化语句;循环条件;迭代语句) 语句序列(循环体) 语句序列(循环体) 执行迭代语句 改变循环变量的值 N-S结构化流程图 传统流程图 图1 for循环语句的执行流程图 注意: 在使用for语句时~一定要保证循环可以正常结束~也就是必须保证循环条件的结果存在为false的情况~否则循环体将无休止的执行下去~从而形成死循环。例如~下面的循环语句就会造成死循环~原因是i永远大于等于1。 for(int i=1;i>=1;i++){ System.out.println(i); } 为了使读者更好的理解for语句,下面将以一个具体的实例介绍for语句的应用。本实例主要实现计算100以内所有奇数的和。具体步骤如下。 (1)选择“开始”/“所有程序”/“附件”/“记事本”命令,打开一个无标题的记事本文档。 WHILE循环语句的翻译程序设计(简单优先法、输出四元式) 1 需求说明或问题描述 1.1 问题描述 对C++中while循环语句的理解及分析,通过编译中的词法分析、语法分析、语义分析及中间代码生成等编译过程,用简单优先分析法分析并翻译while语句。 1.2 需求说明 1 写出符合给定的语法分析方法的文法及属性文法 2 完成题目要求的中间代码四元式的描述 3 写出给定的语法分析方法的思想,完成语法分析及语义分析程序设计 4 设计若干用例,上机通过测试 2 文法及语法设计 2.1文法及属性文法: 文法G=(V N ,V T ,P ,S) 其中V N={S , B, E, C, A, B, P, T} V T={w, (, ), { ,}, i, ;} P={ S -> w(B){E} E -> C C -> CA C -> A A -> iPA A -> i; P -> +|-|*|/ B -> iTi B-> i T -> >|<|>=|<=|== } 2.2 语法分析方法描述及语法分析表设计 2.2.1 语法分析方法描述: 简单优先分析法是按照文法符号(终极符和非终极符)的优先关系确定句柄的。 基本思想可设计如下,首先根据已知优先文法构造相应优先关系矩阵,并将【教学】For循环语句
FOR循环语句的翻译程序设计
while循环
c语言for循环的嵌套题(含解析和答案)
for循环语句的翻译
for循环语句
WHILE循环语句的翻译程序设计(简单优先法、输出四元式)