编译原理：算术表达式预测分析程序设计

预测分析程序与LL(1)文法一、预测分析程序1.带预测分析的PDA：1）在PDA中加入预测分析之后，可以消除自上而下分析中出现回溯的现象，此时PDA可以改造为：2）注：a、改造后，整个分析过程都在预测分析程序控制下工作。

B、预测分析程序用了一个预测分析表，它是预测分析程序分析时的主要依据。

3）预测分析表：预测分析表是一矩阵M[A,a]，其中行标A是非终结符，列标a是终结符或串结束符；矩阵元素M[A,a]是存放A的一个候选式，指出当前栈顶符号为A 且面临读入符号为a时应选的候选式；或者存放“出错标志”，指出A不该面临读入符号a。

2.预测分析程序算法描述设栈顶符号为X，读入符号为a，则1）若X=a=‘#’，则表示识别成功，退出分析程序；2）若X=a=‘#’，则表示匹配，弹出栈顶符号X，读头前进一格，让读头指向下一个符号，以读入下一个符号；若X是终结符，但X<>a，则调用error处理；3）若X属于非终结符，则查预测分析表M。

若M[X,a]中存放着关于X的产生式，则弹出X，且将相应产生式右部以自右向左的顺序压入栈，在输出带上记下产生式编号；若M[X,a]中存放着出错标记，则调用相应Error处理。

二、求串α的终结首符集和非终结符A的随符集a) 求串α的终结首符集First(α)i. 定义：假定α是文法G的一个符号串，α属于星闭包，则First(α)={a | α广义推导出a......a,a属于终结符}注：1）若α推导出空串，那么空串就属于First(α)。

2）First(α)集合是α的所有可能推导出的开头终结符或空串所组成的集合。

ii. 算法具体步骤：b) 求非终结符A的随符集Follow(A)i. 定义：假定S是文法G的开始符号，对于G的任何非终结符A，定义：ii. 算法1. 对文法开始符号S，将‘#’加入到Follow(S)中；2. 若B->αAβ是文法G的一个产生式，则将First(β)-空串加入到Folow(A)中；3. 若B->αA是文法G的一个产生式，或B->αAβ是文法G的一个产生式，且β推导出空串，则将Follow(B)加入到Follow(A)中；注：这里的文法必须消除左递归且提取了左因子后的文法。

1课程设计任务书学生姓名: 专业班级:指导教师: 工作单位:题目: 预测分析程序的设计初始条件:1.程序设计语言:主要使用C语言的开发工具, 或者采用LEX、YACC等工具, 也可利用其他熟悉的开发工具。

算法: 可以根据《编译原理》课程所讲授的算法进行设计。

2.要求完成的主要任务: （包括课程设计工作量及其技术要求,说明书撰写等具体要求）3.明确课程设计的目的和重要性, 认真领会课程设计的题目, 读懂课程设计指导书的要求, 学会设计的基本方法与步骤, 学会如何运用前修知识与收集、归纳相关资料解决具体问题的方法。

严格要求自己, 要独立思考, 按时、独立完成课程设计任务。

4.课设任务: 对教材P94中的上下文无关文法, 实现它的预测分析程序, 给出符号串i+i*i的分析过程。

（参考教材P93～96）5.主要功能：对于这个给的LL（1）文法, 假设所有非终结符号P的FIRST集合和FOLLOW集合都是已知的, 构造其预测分析表, 程序显示输出预测分析表, 同时用这个预测分析程序对输入串进行分析, 并给出了栈的变化过程。

进行总体设计, 详细设计：包括算法的设计和数据结构设计。

系统实施、调试, 合理使用出错处理程序。

设计报告: 要求层次清楚、整洁规范、不得相互抄袭。

正文字数不少于0.3万字。

包含内容:①课程设计的题目。

②目录。

③正文: 包括引言、需求分析、总体设计及开发工具的选择, 设计原则（给出语法分析方法及中间代码形式的描述、文法和属性文法的设计）, 数据结构与模块说明（功能与流程图）、详细的算法设计、软件调试、软件的测试方法和结果、有关技术的讨论、收获与体会等。

④结束语。

⑤参考文献。

⑥附录: 软件清单（或者附盘）。

时间安排:消化资料、系统调查、形式描述1天系统分析、总体设计、实施计划3天撰写课程设计报告书1天指导教师签名: 2010年 6月 11日系主任（或责任教师）签名: 2010年6月11日目录1引言 (5)2需求分析 (6)2.1问题的提出 (6)2.2问题的解决 (6)2.3解决步骤 (6)3总体设计 (7)3.1概要设计 (7)3.1.1设计原理 (7)3.1.2构造LL（1）分析表 (8)3.2详细设计 (12)3.2.1程序流程图 (12)3.2.2设计要求 (14)3.2.3设计原理 (14)3.2.3.1FIRST(X)(X∈VN VT)的构造 (14)3.2.3.2函数getFIRST(α) (α=X1X2X3…Xn)的构造. 143.2.3.3FOLLOW(A) (A∈VN)的构造 (15)3.2.3.4分析表M【A,a】的构造 (15)3.2.3.5匹配过程的实现 (15)3.3程序设计 (16)3.3.1总体方案设计 (16)3.3.2各模块的实现 (16)4开发工具的选择 (25)5程序测试 (25)6有关技术的讨论 (27)7收获与体会 (28)8参考文献 (29)1引言一个编译程序在对某个源程序完成了词法分析工作之后, 就进入了语法分析阶段, 分析检查源程序是否语法上正确的程序, 并生成相应的内部中间表供下一阶段使用。

题目：编写识别由下列文法所定义的表达式的预测分析程序。

E→E+T | E-T | TT→T*F | T/F |FF→(E) | i输入：每行含一个表达式的文本文件。

输出：分析成功或不成功信息。

(题目来源：编译原理实验(三)--预测(LL(1))分析法的实现)解答:（1）分析a) ∵E=>E+T=>E+T*F=>E+T*(E)即有E=>E+T*(E)存在左递归。

用直接改写法消除左递归，得到如下：E →TE’ E’ →+TE’ | −TE’|εT →FT’ T’ →*FT’ | /FT’|εF → (E) | i对于以上改进的方法。

可得：对于E’:FIRST( E’ )=FIRST(+TE’)∪FIRST(-TE’)∪{ε}={+，−，ε}对于T’:FIRST( T’ )=FIRST(*FT’)∪FIRST(/FT’)∪{ε}={*，∕，ε} 而且：FIRST( E ) = FIRST( T ) = FIRST( F )=FIRST((E))∪FIRST(i)={(，i }由此我们容易得出各非终结符的FOLLOW集合如下：FOLLOW( E )= { )，#}FOLLOW(E’)= FOLLOW(E)={ )，#}FOLLOW( T )= FIRST(E’)\ε∪FOLLOW(E’)={+，−，)，#}FOLLOW( T’ ) = FOLLOW( T ) ={+，−，)，#}FOLLOW( F )=FIRST(T’)\ε∪FOLLOW(T’)={*，∕，+，−，)，#}由以上FOLLOW集可以我们可以得出SELECT集如下：对E SELECT（E→TE’）=FIRST(TE’)=FIRST(T)={ (，i }对E’ SELECT（E’ →+TE’）={ + }SELECT（E’ →−TE’）={ − }SELECT（E’ →ε）={ε，)，#}对T SELECT（T→FT’）={(，i}对T’ SELECT（T’ →*FT’）={ * }SELECT（T’ →∕FT’）={ ∕ }SELECT（T’ →ε）={ε，+，−，)，#}对F SELECT（F→(E) ）={ ( }SELECT（F→i）={ i }∴SELECT(E’ →+TE’)∩SELECT（E’ →−TE’）∩SELECT（E’ →ε）=ΦSELECT(T’ →*FT’)∩SELECT（T’ →∕FT’）∩SELECT（T’ →ε）=ΦSELECT（F→(E) ）∩SELECT（F→i）= Φ由上可知，有相同左部产生式的SELECT集合的交集为空，所以文法是LL（1）文法。

预测分析法实验报告一、实验项目名称预测分析法二、实验目的根据某一LL(1)文法编制调试预测分析程序，以便对任意输入的符号串进行分析。

本次实验的目的主要是加深对预测分析法的理解。

三、实验环境Windows 10Microsoft Visual Studio 2015四、实验内容本次实验的LL(1)文法为表达式文法：E→E+T | TT→T*F | FF→i | (E)编写识别表达式文法的合法句子的预测分析程序，对输入的任意符号串，给出分析过程及分析结果。

分析过程要求输出步骤、分析栈、剩余输入串和所用产生式。

如果该符号串不是表达式文法的合法句子，要给出尽量详细的错误提示五、源程序清单、测试数据、结果#include<iostream>#include<string>using namespace std;const int NUM = 20;//初始化的栈的大小//非终结符数组集char Var[5] = { 'E','R','T','M','F' };//终结符数组集char Ter[6] = { 'i','+','*','(',')','#' };string pred[5][6] ={ { "TR","","","TR","","" },{ "","+TR","","","@","@" },{ "FM","","","FM","","" },{ ""," @","*FM","","@","@" },{ "i","","","(E)","","" } };typedef struct {char *top;char *base;int stacksize;int num;}Stack;// 栈结构体void init(Stack *ss) {//初始化栈ss->base = (char *)malloc(NUM * sizeof(char));if (!ss->base)exit(1);ss->top = ss->base;ss->stacksize = NUM;ss->num = 0;}void push(Stack *ss, char c) {//入栈操作if (ss->top - ss->base >= ss->stacksize)exit(1);*(ss->top) = c;ss->top++;ss->num++;}void pop(Stack *ss) {//出栈操作if (ss->top == ss->base)exit(1);ss->top--;ss->num--;}char getTop(Stack *ss) {//取得栈顶元素if (ss->top == ss->base)exit(1);return *(ss->top - 1);}int isT(char c) {//判断是否为终结符int i = 0;int ret = 0;for (i = 0; i<6; i++) {if (Ter[i] == c){ret = 1; break;}}return ret;}string isInPred(char v, char t) {//查找预测分析表，并返回产生式右部int i, j;for (i = 0; i<5; i++){if (Var[i] == v)break;}for (j = 0; j<6; j++){if (Ter[j] == t)break;}if (pred[i][j] !=""){return pred[i][j];}elsereturn"";}void displayStack(Stack *stack) { //输出分析站的内容string str;int i = 0;Stack ss = *stack;while (ss.num != 0){str += getTop(&ss);pop(&ss);}for (i = str.length() - 1; i >= 0; i--){cout << str.at(i);}}void predict(Stack stack, string input)//预测分析总函数{int a = 1;char b;char ctop;//当前栈顶符号char cinput;//当前输入符号int i = 0, j = 0, count = 0;int error = 0;cout <<"步骤"<<'\t'<<"栈"<<'\t'<<"输入缓冲区"<<'\t'<<"所用的产生式"<< endl;cout << count++ <<'\t';displayStack(&stack);cout <<'\t'<<input<<'\t'<<""<< endl;while (getTop(&stack) != '#'){string produce = "";ctop = getTop(&stack);cinput = input.at(i);if (isT(ctop))//栈顶符号为终结符{if (ctop == cinput){pop(&stack);i++;}else{error = 1; break;}produce +="\"";produce += ctop;produce +="\"匹配";}else//栈顶符号位非终结符{string str = isInPred(ctop, cinput);if (str !=""){pop(&stack);if (str !="@"){for (j = str.length() - 1; j >= 0; j--)push(&stack, str.at(j));}produce += ctop;produce +="→";produce += str;}else{error = 1; break;}}//栈顶符号位非终结符cout << count++ <<'\t';displayStack(&stack);cout <<'\t'<<input.substr(i) <<"\t\t"<< produce << endl;}if (error)cout <<"不接受"<< endl;elsecout <<"接受"<< endl;}void main(){while (1) {int sel;//继续或者退出程序选择string input;//输入串int i = 0, j = 0;Stack stack;init(&stack);push(&stack, '#');push(&stack, 'E');cout <<"----------------文法如下--------------"<< endl;cout <<"E→E+T | T"<< endl;cout <<"T→T*F | F"<< endl;cout <<" F→i | (E)"<< endl;cout <<"----------------请输入表达式(以#结尾)--------------"<< endl;cin >> input;cout <<"“R表示“E'”,”M“表示“T'”,”@“表示“空”"<< endl;predict(stack, input);sel=0;if (sel == 0)exit(0);elsesystem("cls");}}六、实验小结和思考本次实验的文法是写在程序中的，不可以自行输入，难度不是很难，并没有太大问题，只是一些未初始化的小问题。

基于编译原理的简单计算器的设计与实现
设计计算器的主要任务是定义运算符和相应的优先级，并为它
们编写按优先级计算表达式的算法。

以下是基于编译原理的计算器
的设计和实现步骤：
1. 词法分析：将用户输入的算术表达式分解成一个个词法单元（token），比如加号、数字、括号、减号等。

2. 语法分析：通过使用递归下降分析法，将词法单元按照特定
的规则进行组合，形成一个抽象语法树（AST），表示表达式的结构
和含义。

3. 语义分析：在AST的基础上进行语义分析，检查表达式中是
否存在语义错误，比如除数为零、变量未定义等。

4. 优化处理：对表达式进行优化处理，比如常量折叠、变量合并、代数简化等，以提高计算效率。

5. 生成中间代码：将AST转换成一种中间表示形式，比如三地
址码（three-address code），这种形式可以方便地生成计算机底
层代码。

6. 代码生成：根据中间代码生成目标机器的汇编代码或机器码，执行计算操作。

7. 输出结果：将计算结果显示给用户。

以上是基于编译原理的计算器的设计和实现步骤，其中重点是
语法分析和代码生成，这些步骤需要仔细考虑各种运算符的优先级
和结合性，以保证表达式的计算结果正确无误。

实验二预测分析表一、实验目的预测分析表的实现二、实验内容设有文法G：E→TE’E’→+TE’|εT→FT’T’→*FT’|εF→(E)|i;根据文法编写预测表分析总控程序，分析句子是否为该文法的句型。

当输入字符串：+i时，分析字符串是否为文法的句型三、实验步骤（详细的实验步骤）(1)文法E→TE’E’→+TE’|εT→FT’T’→*FT’|εF→(E)|i;(2)FIRST集FIRST(E)={(,i};FIRST(E’)={+, ε};FIRST(T)={(,i};FIRST(T’)={ *, ε};FIRST(F)={(,i};(3)FALLOW集FOLLOW(E)={),#};FOLLOW(E’)={),#};FOLLOW(T)={+,),#};FOLLOW(T’)={+,),#};FOLLOW(F)={*,+,),#};(4)预测分析表(5)分析过程步骤符号栈输入串应用句型0#E i1*i2+i3#1#E’T i1*i2+i3#E->TE’2#E’T’F i1*i2+i3#E->TE’3#E’T’i i1*i2+i3#F->i4# E’T’i1*i2+i3#5# E’T’F**i2+i3#T’->*FT’6# E’T’F*i2+i3#7# E’T’i i2+i3#F->i8# E’T’i2+i3#9#E’+i3#T’->ε10# E’T++i3#E’->+TE’11#E’T+i3#12# E’T’F i3#T->FT’13# E’T’i i3#F->i14# E’T’i3#15# E’#T’->ε16# #E’->ε(6)程序伪代码BEGIN首先把‘#’然后把文法开始符号推进STACK栈;把第一个输入符号读进a;FLAG:=TRUE;WHILE FLAG DOBEGIN把STACK栈顶符号托出去并放在X中;IF X属于VT THENIF X=a THEN 把下一输入符号读进a;ELSE ERROR;ELSE IF X=’#’ THENIF X=a THEN FLAG:=FALSE ELSE ERROR;ELSE IF M[A,a]={X->X1X2…Xk} THEN把Xk,X(k-1),…,X1一一推进栈ELSE ERROR;END OF WHILESTOPEND(7)运行结果截图注：为了将E和E’区分开，所以就有e来表示E’，因为在处理中E’会被当成两个字符来处理，所以就简化的表示了。

1．实验目的构造文法的语法分析程序实验要求，2．实验要求采用预测分析法对输入的字符串进行语法分析。

3．实验环境VC++6.04．实验原理对文法G进行语法分析，文法G如下所示：*0. S→a */*1. S→^*2. S→(T)*3. T→SW **4. W→,SW*5. W→ε;5．软件设计与编程#include <stdio.h>#include <stdlib.h>#include <string.h>char str[100]; //存储待分析的句子const char T[ ] = "a^(),#"; //终结符，分析表的列符const char NT[ ] = "STW"; //非终结符，分析表的行符/*指向产生式右部符号串*/const char *p[] = {/*0. S→a */ "a",/*1. S→^ */ "^",/*2. S→(T) */ "(T)",/*3. T→SW */ "SW",/*4. W→,SW */ ",SW",/*5. W→ε; */ ""};//设M[i][j]=x，通过p[M[i][j]]=p[x]获取右部符号串。

const int M[][6] = {/* a ^ ( ) , # *//*S*/ { 0, 1, 2, -1, -1, -1 },/*T*/ { 3, 3, 3, -1, -1, -1 },/*W*/ { -1, -1,-1, 5, 4, -1 }};void init()//输入待分析的句子printf("请输入待分析的句子(以$结束)：\n");scanf("%s",str);}int lin(char c);//非终结符转换为行号int col(char c);//终结转换为列号bool isNT(char c);//isNT判断是否是非终结符bool isT(char c);//isT判断是否是终结符。

一、实验目的：熟悉并设计一个表达式的语法分析器二、相关知识：1、形式语言基础及其文法运算2、语法分析原理及4种常用的语法分析方法其中：四种算法为（1）设计算术表达式的递归下降子程序分析算法三、实验内容：1．设计表达式的语法语法分析器算法2．编写代码并上机调试运行通过要求：输入------------ 表达式输出------------ 表达式语法是否正确四、概要设计1.算术表达式的递归下降子程序分析算法（1）算术表达式文法G(E)： E → E ω0 T | TT → T ω1 F | FF → i | (E)（2）文法变换：G’(E) E →T {ω0 T}T →F {ω1 F}F → i | (E)（3）递归下降子程序框图：E: 入口T:入口T Fn ω0? n ω1?y y出口出口read(w) read(w)T FF: 入口主程序：Z →E开始( ? n i ? n errread(w) read(w)EEerr n # ?err n ) ? yyread(w)结束出口（4）数据结构char exp[50]; //算术表达式区int i=0;int err=0 ; //err输出指示char w; //当前单词（5）源程序清单：#include <stdio.h>#include <stdlib.h>void E();void T();void F();int Print();char exp[50];//算术表达式区int i=0;int err=0;char w;//当前单词int Print(){printf("err") ;err=1;return err;}void F(){if((w>='a'&&w<='z')||(w>='0'&&w<='9')){w=exp[i++];//read(w)}else if(w=='('){w=exp[i++];E();if(w!=')'){if(!err)Print();}elsew=exp[i++];//read(w)}else{if(!err)Print();}}void T(){F();while(w=='*'||w=='/'){w=exp[i++];//read(w)F();}}void E(){T();while(w=='+'||w=='-'){w=exp[i++];//read(w)T();}}int main(){printf("please input your expression:");//输入表达式 scanf("%s",exp);w=exp[i++];//read(w)E();if(!err){if(w=='#')printf("OK!"); elseprintf("err"); }return 0;}（6）运行结果。

实验二预测分析表一、实验目的预测分析表的实现二、实验内容设有文法G：E→TE’E’→+TE’|εT→FT’T’→*FT’|εF→(E)|i;根据文法编写预测表分析总控程序，分析句子是否为该文法的句型。

当输入字符串： +i时，分析字符串是否为文法的句型三、实验步骤（详细的实验步骤）(1)文法E→TE’E’→+TE’|εT→FT’T’→*FT’|εF→(E)|i;(2)FIRST集FIRST(E)={(,i};FIRST(E’)={+, ε};FIRST(T)={(,i};FIRST(T’)={ *, ε};FIRST(F)={(,i};(3)FALLOW集FOLLOW(E)={),#};FOLLOW(E’)={),#};FOLLOW(T)={+,),#};FOLLOW(T’)={+,),#};FOLLOW(F)={*,+,),#};(4)预测分析表(5)分析过程步骤符号栈输入串应用句型0 #E i1*i2+i3#1 #E’T i1*i2+i3# E->TE’2 #E’T’F i1*i2+i3# E->TE’3 #E’T’i i1*i2+i3# F->i4 # E’T’i1*i2+i3#5 # E’T’F* *i2+i3# T’->*FT’6 # E’T’F *i2+i3#7 # E’T’i i2+i3# F->i8 # E’T’ i2+i3#9 #E’ +i3# T’->ε10 # E’T+ +i3# E’->+TE’11 #E’T +i3#12 # E’T’F i3# T->FT’13 # E’T’i i3# F->i14 # E’T’ i3#15 # E’ # T’->ε16 # # E’->ε(6)程序伪代码BEGIN首先把‘#’然后把文法开始符号推进STACK栈;把第一个输入符号读进a;FLAG:=TRUE;WHILE FLAG DOBEGIN把STACK栈顶符号托出去并放在X中;IF X属于VT THENIF X=a THEN 把下一输入符号读进a;ELSE ERROR;ELSE IF X=’#’ THENIF X=a THEN FLAG:=FALSE ELSE ERROR;ELSE IF M[A,a]={X->X1X2…Xk} THEN把Xk,X(k-1),…,X1一一推进栈ELSE ERROR;END OF WHILESTOPEND(7)运行结果截图注：为了将E和E’区分开，所以就有e来表示E’，因为在处理中E’会被当成两个字符来处理，所以就简化的表示了。