实验二 语法分析(算符优先)(1)
实验二语法分析实验报告
一、实验题目
算符优先分析程序
二、实验内容及要求
（1）根据给定文法，先求出FirstVt和LastVt集合，构造算符优先关系表（要求算符优先关系表输出到屏幕或者输出到文件）；
（2）根据算法和优先关系表分析给定表达式是否是该文法识别的正确的算术表达式（要求输出归约过程）
（3）给定表达式文法为：
G(E’): E’→#E#
E→E+T | T
T→T*F |F
F→(E)|i
(4)分析的句子为:
(i+i)*i和i+i)*i
三、程序源代码：
#include
#include
#include
#include
#define SIZE 128
char priority[6][6]; //算符优先关系表数组
char input[SIZE]; //存放输入的要进行分析的句子
char remain[SIZE]; //存放剩余串
char AnalyseStack[SIZE]; //分析栈
void analyse();
int testchar(char x); //判断字符X在算符优先关系表中的位置
void remainString(); //移进时处理剩余字符串，即去掉剩余字符串第一个字符
int k;
void init()//构造算符优先关系表，并将其存入数组中
{
priority[0][0]='>';
priority[0][1]='<';
priority[0][2]='<';
priority[0][3]='<';
priority[0][4]='>';
priority[0][5]='>';
priority[1][0]='>';
priority[1][1]='>';
priority[1][2]='<';
priority[1][3]='<';
priority[1][4]='>';
priority[1][5]='>';
priority[2][0]='>';
priority[2][1]='>';
priority[2][2]='$';//无优先关系的用$表示priority[2][3]='$';
priority[2][4]='>';
priority[2][5]='>';
priority[3][0]='<';
priority[3][1]='<';
priority[3][2]='<';
priority[3][3]='<';
priority[3][4]='=';
priority[3][5]='$';
priority[4][0]='>';
priority[4][1]='>';
priority[4][2]='$';
priority[4][3]='$';
priority[4][4]='>';
priority[4][5]='>';
priority[5][0]='<';
priority[5][1]='<';
priority[5][2]='<';
priority[5][3]='<';
priority[5][4]='$';
priority[5][5]='=';
}
void analyse()//对所输入的句子进行算符优先分析过程的函数
{
int i,j,f,z,z1,n,n1,z2,n2;
int count=0;//操作的步骤数
char a; //用于存放正在分析的字符
char p,Q,p1,p2;
f=strlen(input); //测出数组的长度
for(i=0;i<=f;i++)
{
a=input[i];
if(i==0)
remainString();
if(AnalyseStack[k]=='+'||AnalyseStack[k]=='*'||AnalyseStack[k]=='i'||Analys eStack[k]=='('||AnalyseStack[k]==')'||AnalyseStack[k]=='#')
j=k;
else
j=k-1;
z=testchar(AnalyseStack[j]);//从优先关系表中查出s[j]和a的优先关系if(a=='+'||a=='*'||a=='i'||a=='('||a==')'||a=='#')
n=testchar(a);
else //如果句子含有不是终结符集合里的其它字符，不合法
{
printf("错误！该句子不是该文法的合法句子！\n");
break;
}
p=priority[z][n];
if(p=='$')
{
printf("错误！该句子不是该文法的合法句子！\n");
return;
}
if(p=='>')
{ for( ; ; )
{
Q=AnalyseStack[j];
if(AnalyseStack[j-1]=='+'||AnalyseStack[j-1]=='*'||AnalyseStack[j-1]=='i'||Ana lyseStack[j-1]=='('||AnalyseStack[j-1]==')'||AnalyseStack[j-1]=='#')
j=j-1;
else
j=j-2;
z1=testchar(AnalyseStack[j]);
n1=testchar(Q);
p1=priority[z1][n1];
if(p1=='<') //把AnalyseStack[j+1]~AnalyseStack[k]归约为N
{
count++;
printf("(%d) %s\t%10c\t%5c%17s\t 归约\n",count,AnalyseStack,p,a,remain);
k=j+1;
i--;
AnalyseStack[k]='N';
int r,r1;
r=strlen(AnalyseStack);
for(r1=k+1;r1 AnalyseStack[r1]='\0'; break; } else continue; } } else { if(p=='<') //表示移进 { count++; printf("(%d) %s\t%10c\t%5c%17s\t 移进\n",count,AnalyseStack,p,a,remain); k=k+1; AnalyseStack[k]=a; remainString(); } else { if(p=='=') { z2=testchar(AnalyseStack[j]); n2=testchar('#'); p2=priority[z2][n2]; if(p2=='=') { count++; printf("(%d) %s\t%10c\t%5c%17s\t 接受\n",count,AnalyseStack,p,a,remain); printf("该句子是该文法的合法句子。\n"); break; } else { count++; printf("(%d) %s\t%10c\t%5c%17s\t 移进 \n",count,AnalyseStack,p,a,remain); k=k+1; AnalyseStack[k]=a; remainString(); } } else { printf("错误！该句子不是该文法的合法句子！\n"); break; } } } } } int testchar(char x) { int m; if(x=='+') m=0; if(x=='*') m=1; if(x=='i') m=2; if(x=='(') m=3; if(x==')') m=4; if(x=='#') m=5; return m; } void remainString() { int i,j; i=strlen(remain); for(j=0;j remain[j]=remain[j+1]; remain[i-1]='\0'; } void main() { init(); printf("文法为：\n"); printf("(0)E'->#E#\n"); printf("(1)E->E+T\n"); printf("(2)E->T\n"); printf("(3)T->T*F\n"); printf("(4)T->F\n"); printf("(5)F->(E)\n"); printf("(6)F->i\n"); printf("-----------------------------------------\n"); printf(" 算符优先关系表\n"); printf(" + * i ( ) #\n"); printf(" + > < < < > >\n"); printf(" * > > < < > >\n"); printf(" i > > > >\n"); printf(" ( < < < < = \n"); printf(" ) > > > >\n"); printf(" # < < < < =\n"); printf("-----------------------------------------\n"); printf("请输入要进行分析的句子（以#号结束输入）:\n"); gets(input);//将输入的字符串存到数组中 printf("步骤栈优先关系当前符号剩余输入串移进或归约\n"); k=0; AnalyseStack[k]='#'; AnalyseStack[k+1]='\0'; int length,i; //初始化剩余字符串数组为输入串 length=strlen(input);// for(i=0;i remain[i]=input[i]; remain[i]='\0'; analyse();//对所输入的句子进行算符优先分析过程的函数 } 四、测试结果： 输入串(i+i)*i的算符优先分析过程 输入串i+i)*i的算符优先分析过程 五、小结（包括收获、心得体会、存在的问题及解决问题的方法、建议等） 通过此次实验，使我对算符优先分析算法的设计过程有了更深一层的了解：即先对已给定的文法按其产生式构造算符优先关系表，有了算符优先关系表并满足算符优先文法时，我们就可以对任意给定的符号串进行分析，形成句柄时就归约，否则就移进，最后判定输入串是否为该文法的句子。 编译原理实验报告 题目： 算符优先分析法分析器 学 院 计算机科学与技术 专 业 xxxxxxxxxxxxxxxx 学 号 xxxxxxxxxxxx 姓 名 宁剑 指导教师 xxxx 2015年xx 月xx 日 算符优先分析法分析器 装 订 线 一、实验目的 1.理解自底向上优先分析，比较和自顶向下优先分析的不同。 2.理解算符优先分析的特点，体会其和简单优先分析方法的不同。 3.加深对编译器语法分析的理解。 二、实验原理 1.自底向上优先分析方法，也称移进-归约分析，粗略地说它的思想是对输入符号串自左向右进行扫描，并将输入符号逐个移入一个后进先出栈，边移入边分析，一旦栈顶符号串形成某个句型的句柄或可归约串时，就将该产生式的左部非终极符代替相应的右边文法符号串。 2.算符优先分析法的基本思想 首先确定算符（确切地说是终结符）之间的优先关系和结合性质，然后借助这种关系，比较相邻算符之间的优先级来确定句型的可归约串，并进行归约。 注意：算符优先分析过程是自下而上的归约过程，但它的可归约串未必是句柄，也就是说，算符优先分析过程不是一种规归约。 3.终结符号间优先关系的确定，用FIRSTVT和LASTVT计算。 4.最左素短语 所谓素短语是指这样一个短语，它至少含有一个终结符，并且除它自身之外不再含有其它素短语。最左素短语是指处于句型最左边的那个素短语。最左素短语是算符优先分析算法的可归约串。 5.计算得到所给文法的算符优先矩阵 6.算符优先分析的基本过程 三、实验要求 使用算符优先分析算法分析下面的文法： E’→#E# E→E+T|T T→T*F|F F→P^F|P 实验名称： 实验任务： 对下述描述算符表达式的算符优先文法G[E],给出算符优先分析的实验结果。 实验容： 有上下无关文法如下： E->E+T|E-T|T T->T*F|T/F|F F->(E)|i 说明：优先关系矩阵的构造过程： （1） = 关系由产生式 F->(E) 知‘（’=‘）’ FIRSTVT集及LASTVT集 FIRSTVT(E)={ +,-,*,/,(,i } FIRSTVT(F)={ (,i } FIRSTVT(T)={ *,/,(,i } LASTVT(E)={ +,-,*,/,),i } LASTVT(F)={ ),i } LASTVT(T)={ *,/,),i } (2) < 关系 +T 则有：+ < FIRSTVT(T) -T 则有：- < FIRSTVT(T) *F 则有：* < FIRSTVT(F) /F 则有：/ < FIRSTVT(F) (E 则有：( < FIRSTVT(E) (3) > 关系 E+ 则有： LASTVT(E) > + E- 则有： LASTVT(E) > - T* 则有： LASTVT(T) > * T/ 则有： LASTVT(T) > / E) 则有： LASTVT(E) > ) (4)请大家画出优先关系矩阵 终结符之间的优先关系是唯一的，所以该文法是算符优先文法。程序的功能描述：程序由文件读入字符串（以#结束），然后进行算符优先分析，分析过程中如有错误，则终止程序并报告错误位置，最终向屏幕输出移近——规约过程。 (5)依据文法和求出的相应FirstVT和 LastVT 集生成算符优先分析表。算法描述如下： for 每个形如 P->X1X2…Xn的产生式 do for i =1 to n-1 do begin if Xi和Xi+1都是终结符 then Xi = Xi+1 if i<= n-2, Xi和Xi+2 是终结符, 但Xi+1 为非终结符 then Xi = Xi+2 if Xi为终结符, Xi+1为非终结符 then for FirstVT 中的每个元素 a do Xi < a if Xi为非终结符, Xi+1为终结符 then for LastVT 中的每个元素 a do a > Xi+1 end (6)构造总控程序 算法描述如下： stack S; k = 1; //符号栈S的使用深度 华北水利水电学院编译原理实验报告 2010～2011学年第二学期xxxx 级计算机专业 班级：xxxxx 学号：xxxxx 姓名：xxx 一、实验目的 通过设计、编制、调试一个典型的语法分析程序，实现对词法分析程序所提供的单词序列进行语法检查和结构分析，进一步掌握常用的语法分析方法。 二、实验要求 ⑴选择最有代表性的语法分析方法，如LL（1）分析法、算符优先法或LR分析法 ⑵选择对各种常见程序语言都用的语法结构，如赋值语句（尤指表达式）作为分析对象，并且与所选语法分析方法要比较贴切。 ⑶实习时间为6小时。 三、实验内容 选题1：使用预测分析法（LL（1）分析法）实现语法分析： （1）根据给定文法，先求出first集合、follow集合和select集合，构造预测分析表（要求预测分析表输出到屏幕或者输出到文件）； （2）根据算法和预测分析表分析给定表达式是否是该文法识别的正确的算术表达式（要求输出归约过程） （3）给定表达式文法为： G(E): S→TE E→+TE | ε T→FK K→*FK |ε F→(S)|i (4)分析的句子为： (i+i)*i和i+i)*i 四、程序源代码 #include "stdafx.h" #include "SyntaxAnalysis.h" #include "SyntaxAnalysisDlg.h" #ifdef _DEBUG #define new DEBUG_NEW #undef THIS_FILE static char THIS_FILE[] = __FILE__; #endif /////////////////////////////////////////// // CAboutDlg dialog used for App About 编译原理实验代码： 对于任意给定的文法，判断其是否是算符优先文法。 代码如下： #include //判断（A,a）栈是否为空 bool ifEmpty(stack S) { if(S.top==S.bottom) return true; //如果栈为空，则返回true else return false; //否则不为空，返回false } //插入栈顶（A,a）元素 void Insert(stack &S,StackElement e) { if(S.top-S.bottom>=S.stacksize) cout<<"栈已满，无法插入！"< 实验二--语法分析(算符优先)-(2) 编译原理实验报告实验名称：语法分析器设计 专业：计算机科学与技术 姓名：田莉莉 学号：201117906 语法分析—算符优先分析程序 一．实验要求 ⑴ 选择最有代表性的语法分析方法，如算符优先法、递归子程序法或LR 分析法 ⑵ 选择对各种常见程序语言都用的语法结构，如赋值语句（尤指表达式）作为分析对象，并且与所选语法分析方法要比较贴切。 ⑶ 实习时间为6 学时。 二．实验内容及要求 （ 1）根据给定文法，先求出 FirstVt 和 LastVt 集合，构造算符优先关系表（要求算符优先关系表输出到屏幕或者输出到文件）； （ 2）根据算法和优先关系表分析给定表达式是否是该文法识别的正确的算术表达式（要求输出归约过程） （3）给定表达式文法为： G（E ' ）: E'T #E# E—E+T | T T—T*F |F F—（E）|i （4）分析的句子为 : （i+i）*i 和 i+i）*i 三．程序设计思想及实现步骤 程序的设计思想： 按照编译原理教材提供的算法，本程序的设计主要实现三个主要的过程： （1） 求解 FristVT 集和 LastVT 集：利用 CString 数组存放 VT 集，利用数组 下标对应非终结符关系； （2） 输出算符优先分析表：利用 MFC 中的 ClistCtrl 控件输出显示算符表， 比 利用二维数组对应其在内存中的关系。 （3） 利用算符优先分析表进行归约：根据教材所给算法，并对其进行实现在 屏幕上输 出归约过程。 实现步骤： 1、为程序各变量设计存储形式，具体设计如下所示： CString m_strTElem[T_LEN]; CString m_strNTElem[NT_LEN]; // 非终结符 CMapStringToPtr m_mapProdu; // 存放产生式 CMapStringToPtr m_mapProduEX; // 存放 扩展产生式 CString m_strFristVT[NT_LEN]; CString m_strLastVT[NT_LEN]; int m_nPriSheet[T_LEN+1][T_LEN+1]; // 终结符 //fristVT 集 //lastVT 集 实验5 语法分析程序的设计（2） 一、实验目的 通过设计、编制、调试一个典型的语法分析程序，实现对词法分析程序所提供的单词序列进行语法检查和结构分析，进一步掌握常用的语法分析中算法优先分析方法。 二、实验内容 设计一个文法的算法优先分析程序，判断特定表达式的正确性。 三、实验要求 1、给出文法如下： G[E] E->T|E+T; T->F|T*F; F->i|(E); + * ( ) i + * ( ) i 2、计算机中表示上述优先关系，优先关系的机内存放方式有两种1）直接存放，2）为 优先关系建立优先函数，这里由学生自己选择一种方式； 1、给出算符优先分析算法如下： k:=1; S[k]:=‘#’; REPEAT 把下一个输入符号读进a中； IF S[k]∈V T THEN j:=k ELSE j:=k-1; WHILE S[j] a DO BEGIN REPEAT Q:=S[j]; IF S[j-1]∈V T THEN j:=j-1 ELSE j:=j-2 UNTIL S[j] Q 把S[j+1]…S[k]归约为某个N； k:=j+1; S[k]:=N; END OF WHILE; IF S[j] a OR S[j] a THEN BEGIN k:=k+1;S[k]:=a END ELSE ERROR UNTIL a=‘#’ 1、 根据给出算法，利用适当的数据结构实现算符优先分析程序； 2、 利用算符优先分析程序完成下列功能： 1） 手工将测试的表达式写入文本文件，每个表达式写一行，用“；”表示结束； 2） 读入文本文件中的表达式； 3） 调用实验2中的词法分析程序搜索单词； 4） 把单词送入算法优先分析程序，判断表达式是否正确（是否是给出文法的语 言），若错误，应给出错误信息； 5） 完成上述功能，有余力的同学可以对正确的表达式计算出结果。 四、实验环境 PC 微机 DOS 操作系统或 Windows 操作系统 Turbo C 程序集成环境或 Visual C++ 程序集成环境 五、实验步骤 1、 分析文法中终结符号的优先关系； 2、 存放优先关系或构造优先函数； 3、利用算符优先分析的算法编写分析程序； 4、写测试程序，包括表达式的读入和结果的输出； 5、程序运行效果，测试数据可以参考下列给出的数据。 六、测试数据 输入数据： 编辑一个文本文文件expression.txt ，在文件中输入 如下内容： 正确 结果： （1）10; 输出：正确 （2）1+2; 输出：正确 （3）(1+2)*3+(5+6*7); 输出：正确 （4）((1+2)*3+4 10; 1+2; (1+2)*3+(5+6*7); ((1+2)*3+4; 1+2+3+(*4+5); (a+b)*(c+d); ((ab3+de4)**5)+1; 实验二语法分析 一、实验目的： 设计MiniC的上下文无关文法，利用JavaCC生成调试递归下降分析程序，以便对任意输入的符号串进行分析。本次实验的目的主要是加深对递归下降分析法的理解。 二、语法分析器: 按照MiniC语言的语法规则检查词法分析输出的记号流是否符合这些规则，并根据这些规则所体现出的语言中的各种语法结构的层次性。把规则写入到JavaCC的.jjt文件中，可以生成树状的层次结构。 三、JavaCC: 在JavaCC的文法规范文件中，不仅可以描述语言的语法规范，而且可以描述词法规范，本次实习中，利用JavaCC以MiniC语言构造一个不含语义分析的编译器前端，包括词法分析、语法分析，并要考虑语法分析中的错误恢复问题。通过使用JavaCC, 可以体会LL(k)文法的编写特点，掌握编写JavaCC文法规范文件的方法。 内容：利用JavaCC生成一个MiniC的语法分析器； 要求： 1.用流的形式读入要分析的C语言程序，或者通过命令行输入源程序。 2.具有错误检查的能力，如果有能力可以输出错误所在的行号，并简单提示 3.如果输入的源程序符合MiniC的语法规范，输出该程序的层次结构的语法树本次实习仅完成以下语法范畴的语法分析： 1. 写出一个源程序中仅包含if…else, else语句的语法分析。要求能分析其自身 嵌套. 其他语句可简化处理 2. 写出一个源程序中仅包含for语句的语法分析。要求能分析其自身嵌套， 其他语句可简化处理 3. 写出一个源程序中仅包含while语句的语法分析。要求能分析其自身嵌套。 其他语句可简化处理 4. 写出一个源程序中包含上面的12或者13或者23或者123语句的语法分析。 要求能分析除其自身嵌套外，还包括相互嵌套。其他语句可简化处理 具体实施步骤如下： 1.把MiniC转换为文法如下 <程序〉→ main()〈语句块〉 〈语句块〉→{〈语句串〉} 实验三算符优先分析算法的设计与实现 （8学时） 一、实验目的 根据算符优先分析法，对表达式进行语法分析，使其能够判断一个表达式是否正确。通过算符优先分析方法的实现，加深对自下而上语法分析方法的理解。 二、实验要求 1、输入文法。可以是如下算术表达式的文法（你可以根据需要适当改变）： E→E+T|E-T|T T→T*F|T/F|F F→（E）|i 2、对给定表达式进行分析，输出表达式正确与否的判断。 程序输入/输出示例： 输入：1+2; 输出：正确 输入：(1+2)/3+4-(5+6/7); 输出：正确 输入：((1-2)/3+4 输出：错误 输入：1+2-3+(*4/5) 输出：错误 三、实验步骤 1、参考数据结构 char *VN=0,*VT=0;//非终结符和终结符数组 char firstvt[N][N],lastvt[N][N],table[N][N]; typedef struct //符号对(P,a) { char Vn; char Vt; } VN_VT; typedef struct //栈 { VN_VT *top; VN_VT *bollow; int size; }stack; 2、根据文法求FIRSTVT集和LASTVT集 给定一个上下文无关文法，根据算法设计一个程序，求文法中每个非终结符的FirstVT 集和LastVT 集。 算符描述如下： /*求 FirstVT 集的算法*/ PROCEDURE insert(P,a); IF not F[P,a] then begin F[P,a] = true; //(P,a)进栈 end; Procedure FirstVT; Begin for 对每个非终结符 P和终结符 a do F[P,a] = false for 对每个形如 P a…或 P→Qa…的产生式 do Insert(P,a) while stack 非空 begin 栈顶项出栈，记为(Q,a) for 对每条形如 P→Q…的产生式 do insert(P,a) end; end. 同理，可构造计算LASTVT的算法。 3、构造算符优先分析表 依据文法和求出的相应FirstVT和 LastVT 集生成算符优先分析表。 算法描述如下： for 每个形如 P->X1X2…X n的产生式 do for i =1 to n-1 do begin if X i和X i+1都是终结符 then X i = X i+1 if i<= n-2, X i和X i+2 是终结符, 但X i+1 为非终结符 then X i = X i+2 if X i为终结符, X i+1为非终结符 then for FirstVT 中的每个元素 a do X i < a ; if X i为非终结符, X i+1为终结符 then for LastVT 中的每个元素 a do a > X i+1 ; end 4、构造总控程序 算法描述如下： stack S; k = 1; //符号栈S的使用深度 S[k] = ‘#’ REPEAT 实验二语法分析程序设计与实现 一、实验目的 任选一种有代表性的语法分析方法，如算符优先法、递归下降法、LL(1)、SLR(1)、LR(1)等，通过设计、编制、调试实现一个典型的语法分析程序，对实验一所得扫描器提供的单词序列进行语法检查和结构分析，实现并进一步掌握常用的语法分析方法。 二、基本实验内容与要求 选择对各种常见高级程序设计语言都较为通用的语法结构——算术表达式的一个简化子集——作为分析对象，根据如下描述其语法结构的BNF定义G2[<算术表达式>]，任选一种学过的语法分析方法，针对运算对象为无符号常数和变量的四则运算，设计并实现一个语法分析程序。 G2[<算术表达式>]： <算术表达式> → <项> | <算术表达式>+<项> | <算术表达式>-<项> <项> → <因式> | <项>*<因式> | <项>/<因式> <因式> → <运算对象> | (<算术表达式>) 若将语法范畴<算术表达式>、<项>、<因式>和<运算对象>分别用E、T、F 和i代表，则G2可写成： G2[E]：E → T | E+T | E-T T → F | T*F | T/F F → i | (E) 输入：由实验一输出的单词串，例如：UCON，PL，UCON，MU，ID ······ 输出：若输入源程序中的符号串是给定文法的句子，则输出“RIGHT”，并且给出每一步分析过程；若不是句子，即输入串有错误，则输出“ERROR”，并且显示分析至此所得的中间结果，如分析栈、符号栈中的信息等，以及必要的出错说明信息。 要求: 1、确定语法分析程序的流程图，同时考虑相应的数据结构，编写一个语法分析源程序。 2、将词法、语法分析合在一起构成一个完整的程序，并调试成功。 3、供测试的例子应包括符合语法规则的语句，及分析程序能判别的若干错例。对于所输入的字符串，不论对错，都应有明确的信息输出。 华北水利水电学院编译原理实验报告 一、实验题目：语法分析（算符优先分析程序） （1）选择最有代表性的语法分析方法算符优先法； （2）选择对各种常见程序语言都用的语法结构，如赋值语句（尤指表达式）作为分析对象，并且与所选语法分析方法要比较贴切。 二、实验内容 （1）根据给定文法，先求出FirstVt和LastVt集合，构造算符优先关系表（要求算符优先关系表输出到屏幕或者输出到文件）； （2）根据算法和优先关系表分析给定表达式是否是该文法识别的正确的算术表达式（要求输出归约过程） （3）给定表达式文法为： G(E’): E’→#E# E→E+T | T T→T*F |F F→(E)|i (4) 分析的句子为: (i+i)*i和i+i)*i 三、程序源代 #include 实验二、语法分析 一、实验目的： 设计MiniC的上下文无关文法，利用JavaCC生成调试递归下降分析程序，以便对任意输入的符号串进行分析。本次实验的目的主要是加深对递归下降分析法的理解。 二、语法分析器: 按照MiniC语言的语法规则检查词法分析输出的记号流是否符合这些规则，并根据这些规则所体现出的语言中的各种语法结构的层次性。把规则写入到JavaCC的.jjt文件中，可以生成树状的层次结构。 三、JavaCC: 在JavaCC的文法规范文件中，不仅可以描述语言的语法规范，而且可以描述词法规范，本次实习中，利用JavaCC以MiniC语言构造一个不含语义分析的编译器前端，包括词法分析、语法分析，并要考虑语法分析中的错误恢复问题。通过使用JavaCC, 可以体会LL(k)文法的编写特点，掌握编写JavaCC文法规范文件的方法。 内容：利用JavaCC生成一个MiniC的语法分析器； 要求： 1.用流的形式读入要分析的C语言程序，或者通过命令行输入源程序。 2.具有错误检查的能力，如果有能力可以输出错误所在的行号，并简单提示 3.如果输入的源程序符合MiniC的语法规范，输出该程序的层次结构的语法树 具体实施步骤如下： 1.把MiniC转换为文法如下 Procedure()→void main() {WhileStatement()} WhileStatement()→while(Condition()){(WhileStatement()|ass ign())} assign()→ #include 第六章算符优先分析法 课前索引 【课前思考】 ◇什么是自下而上语法分析的策略？ ◇什么是移进-归约分析？ ◇移进-归约过程和自顶向下最右推导有何关系？ ◇自下而上语法分析成功的标志是什么？ ◇什么是可归约串？ ◇移进-归约过程的关键问题是什么？ ◇如何确定可归约串？ ◇如何决定什么时候移进，什么时候归约？ ◇什么是算符文法？什么是算符优先文法？ ◇算符优先分析是如何识别可归约串的？ ◇算符优先分析法的优缺点和局限性有哪些？ 【学习目标】 算符优先分析法是自下而上（自底向上）语法分析的一种，尤其适应于表达式的语法分析，由于它的算法简单直观易于理解，因此，也是学习其它自下而上语法分析的基础。通过本章学习学员应掌握： ◇对给定的文法能够判断该文法是否是算符文法 ◇对给定的算符文法能够判断该文法是否是算符优先文法 ◇对给定的算符文法能构造算符优先关系表，并能利用算符优先关系表判断该文法是否是算符优先文法。 ◇能应用算符优先分析算法对给定的输入串进行移进-归约分析，在分析的每一步能确定当前应移进还是归约，并能判断所给的输入串是否是该文法的句子。 ◇了解算符优先分析法的优缺点和实际应用中的局限性。 【学习指南】 算符优先分析法是自下而上语法分析的一种，它的算法简单、直观、易于理解，所以通常作为学习其它自下而上语法分析的基础。为学好本章内容，学员应复习有关语法分析的知识，如：什么是语言、文法、句子、句型、短语、简单短语、句柄、最右推导、规范归约基本概念。 【难重点】 ◇通过本章学习后，学员应该能知道算符文法的形式。 ◇对一个给定的算符文法能构造算符优先关系分析表，并能判别所给文法是否为算符优先文法。 ◇分清规范句型的句柄和最左素短语的区别，进而分清算符优先归约和规范归约的区别。 ◇算符优先分析的可归约串是句型的最左素短语，在分析过程中如何寻找可归约串是算符优先分析的关键问题。对一个给定的输入串能应用算符优先关系分析表给出分析（归约）步骤，并最终判断所给输入串是否为该文法的句子。 ◇深入理解算符优先分析法的优缺点和实际应用中的局限性。 【知识点】 实习二语法分析－自上而下分析 一、实验目的 使用预测分析方法对输入的表达式进行分析，掌握其具体的使用并且学会去分析一个文法。 二、实验内容 1．设计表达式的语法分析器算法（使用预测分析） 2．编写一段代码并上机调试查看其运行结果 三、实验要求 使用LL（1）分析算法设计表达式的语法分析器 LL（1）文法是一个自上而下的语法分析方法，它是从文法的开始符号出发，生成句子的最左推导，从左到右扫描源程序，每次向前查看一个字符，确定当前应该选择的产生式。 实现LL（1）分析的另一种有效方法是使用一张分析表和一个栈进行联合控制。 预测分析程序的总控程序在任何时候都是按STACK栈顶符号X和当前a的输入符号行事的。对于任何（X，a），总控程序每次都执行三种可能的动作之一。 1.若X＝a＝“#”，则宣布分析成功，停止分析过程 2.若X＝a≠“#”，则把X从STACK栈顶逐出，让a指向下一 个输入符号。 3.若X是一个非终结符，则查看分析表。 四、运行结果 （本程序只能对由'i','+','*','(',')'构成的以'#'结束的字符串进行分析） 五、源程序实现 /*LL(1)分析法源程序，只能在VC++中运行*/ #include 数学与计算机学院编译原理实验报告 年级专业学号姓名成绩 实验题目算符优先分析法分析器的设计实验日期 一、实验目的： 设计一个算符优先分析器，理解优先分析方法的原理。 二、实验要求： 设计一个算符优先分析器 三、实验内容： 使用算符优先分析算法分析下面的文法： E’→#E# E →E+T | T T →T*F | F F →P^F | P P →(E) | i 其中i可以看作是一个终结符，无需作词法分析。具体要求如下： 1、如果输入符号串为正确句子，显示分析步骤，包括分析栈中的内容、优先关系、输入符号串的变化情况； 2、如果输入符号串不是正确句子，则指示出错位置。 四、实验结果及主要代码： 1.主要代码 void operatorp() { char s[100]; char a,Q; int k,j,i,l; string input,temp; cin>>input; cout<<"步骤"<<'\t'<<"栈"<<'\t'<<"优先关系"<<'\t'<<"当前符号"<<'\t'<<"剩余输入串"<<'\t'<<"移进或归约"< for(l=1;l 淮阴工学院 编译原理课程设计报告 选题名称:算符优先分析法 系（院）:计算机工程学院 专业:计算机科学与技术 班级:计算机1075 姓名:学号: 指导教师: 学年学期:2009 ~ 2010 学年第 2 学期2010 年 5 月17 日 设计任务书 指导教师（签章）： 年月日 摘要： 编译原理是计算机系统的基本组成部分之一，而且多数据计算机系统都配有不止一个高级语言的编译程序，对有些高级语言甚至配置了几个不同性能的编译程序。从功能上看，一个编译程序就是一个语言翻译程序。算符优先分析法是一种简单直观、广为使用的自下而上分析法。这种方法特别有利于表达式分析，宜于手工实现。算符优先分析过程是自下而上的归约过程，但这种归约未必是严格的最左归约。也就是说，算符优先分析法不是一种规范归约法。所谓算符优先分析就是定义算符之间(确切地说，终结符之间)的某种优先关系，借助于这种优先关系寻找“可归约串”和进行归约。 关键词：编译原理；归约；算法；算符优先；编译 目录 1需求分析 (1) 2 概要设计 (1) 2.1算符优先分析法的思想及其原理 (1) 2.2算符优先分析算法 (4) 2.3 构建算符优先关系表 (6) 2.4 出错处理 (7) 3 详细设计 (7) 3.1 程序流程图 (7) 3.2 构建算符优先关系表 (8) 3.3 进栈优先函数 (8) 3.4 算符优先规约函数 (10) 3.5 弹出窗体 (12) 4 程序运行、调试及操作说明 (12) 总结 (15) 致谢 (16) 参考文献 (17) 1需求分析 本次课程设计的题目是算符优先分析法。算符优先分析法是一种简单直观、特别方便于表达式分析，易于手式实现的方法。算符优先法只考虑算符（广义为终结符号）之间的优先关系，它是一种自底向上的归约过程，但这种归约未必严格按照句柄归约。它是一种不规范归约法。 根据已知文法： E->E+T|E-T|T T->T*F|T/F|F F->(E)|i(E)|i|d（其中d表示0-9的数字，i表示字母，大小写均包括） 根据算符优先分析法，将表达式进行语法分析，判断一个表达式是否正确 (1)可以使用任何语言来完成，例如：Java、C++。 (2)构造此文法的分析过程 (3)输入测试字符串，输出测试结果 给出关键类类图、整个应用程序的结构描述文档、关键模块流程图、较详细的接口文档、所有源代码。对应用程序进行测试，对测试结果进行分析研究，进而对应用程序进行改进，对关键算法进行尽可能的优化，最终得到一个在windows运行的可以根据算符优先分析法，将表达式进行语法分析，判断一个表达式是否正确，输入测试字符串，输出测试结果的完整应用程序。 2 概要设计 2.1算符优先分析法的思想及其原理 算符优先分析算法算法原理： （1）初始化栈：k=1; S[k]=‘#’； （2）依次从输入串中读入符号a： ①当前单词若为标识符，则a值为i，若为常数则a值为d； 其它a直接取单词值。 ②若a大于等于栈顶第一个终结符的优先级，则a进栈； ③若a小于栈顶第一个终结符的优先级，则重复做： 数学与计算机学院编译原理实验报告 年级09软工学号姓名成绩 专业软件工程实验地点主楼指导教师湛燕 实验项目算符优先关系算法实验日期2012.6.6 一、实验目的和要求 设计一个算符优先分析器，理解优先分析方法的原理。 重点和难点：本实验的重点是理解优先分析方法的原理；难点是如何构造算符优先关系。 二、实验内容 使用算符优先分析算法分析下面的文法： E’→ #E# E → E+T | T T → T*F | F F → P^F | P P → (E) | i 其中i可以看作是一个终结符，无需作词法分析。具体要求如下： 1、如果输入符号串为正确句子，显示分析步骤，包括分析栈中的内容、优先关系、输入符号串的变化情况； 2、如果输入符号串不是正确句子，则指示出错位置。 三、程序设计 全局变量有一下几个： static string input;//记录输入串 char s[20];//栈 int top=-1;//栈顶指针 有三个函数： int analyze(string input);//分析输入的串是否符合标准 void process();//进行归约的函数 int main() input是一个全局变量，记录输入串，用analyze（input）分析输入的是不是符合标准的字符串，（例如“i+i*i^(i+i)”）如果不符合标准，提示用户重新输入。 进行归约的函数主要思想是：先构造优先关系矩阵，有“<”，“>”，“=”和空格四种关系。Char a 记录栈中最高位的终结符，如果栈中是#E+E,则 a 的赋 值是“+”，如果形如“#E+”或“#E+i”则a 赋值“+”或“i”。charnowchar 记录当前的字符。a 与 nowchar 按照算符优先关系矩阵找出优先关系。如果优先关系是“<”,则进行移进;如果优先关系是“>”,则进行归约；如果是“=”，则去掉括号或分析成功。 五、代码和截图 自己编写代码如下： #include 算符优先语法分析设计原理与实现技术 XXX 1028XXX 计科1XXX班 功能描述 能够有效识别以下算符优先文法 E → E+T | E-T T → T*F | T/F | F F → (E) | i 所描述算术表达式． 主要数据结构描述 程序结构描述 设计方法 1.由文法构造算符优先矩阵 2.根据算符优先矩阵算数表达式的词法分析结果进行语法分析，分析算法为： 数据结构： 符号栈S --- 存放所有读进的符号（计数i） K --- 符号栈使用深度 a --- 工作单元 R, Q --- 变量 分析算法：先找最左素短语的尾部（>） 再找最左素短语的头部（<） 以分析表达式i+i*i为例，详细过程如下： 函数定义 ?函数调用关系 ?程序执行图 程序测试 测试用例一： (a+b*c)+d+e+a*c/b 首先调用实验一的词法分析程序，得到如下分析结果： (19, '(') (12, 'a') (14, '+') (12, 'b') (16, '*') (12, 'c') (20, ')') (14, '+') (12, 'd') (14, '+') (12, 'e') (14, '+') (12, 'a') (16, '*') (12, 'c') (17, '/') (12, 'b') 在以此分析结果作为本程序实验结果的输入，得到如下分析结果： 该结果显示了详细的分析过程，且表明该表达式是一个符合该文法的表达式 测试用例二： (a+b*c)+d*-a*c+(a+b 同样调用实验一的词法分析程序，得到如下结果： (19, '(') (12, 'a') (14, '+') (12, 'b') (16, '*') (12, 'c') (20, ')') 编译原理实验二语法分析 输入：token[40] tokenstring[40][30] 输出：检查是否符合文法]； 生成语法树。 样例程序已经对符合以下文法的源程序进行语法分析但不能生成抽象语法树。 要求写出能生成抽象语法树的语法分析程序。 文法：stmt_seq→ stmt_seq ; assign_stmt | assign_stmt assign_stmt →id := exp exp→exp + term | exp – term | term term→term * factor | term / factor | factor factor→ ( exp ) | id | num 语法树的数据结构： typedef enum {stmtk,expk} nodekind; typedef enum {ifk,assignk,declk} stmtkind; typedef enum {opk,constk,idk} expkind; typedef struct treenode { struct treenode * child[3]; struct treenode * sibling; nodekind nodek; union { stmtkind stmt; expkind exp;} kind; union { tokentype op; int val; char * name; } attr; } treenode; 样例程序 #include算符优先分析器设计实验报告--宁剑
实验4 算符优先分析法.
编译原理 语法分析实验二
算符优先文法
实验二--语法分析-
编译原理实验报告5-语法分析程序的设计(2)
编译原理实验二
实验三算符优先分析算法设计与实现
实验二 语法分析程序设计与实现
编译原理_实验报告实验二__语法分析(算符优先) 2
实验二语法分析
c语言实现算符优先语法分析
编译原理 六章 算符优先分析法
语法分析(自上而下分析)实验报告
编译原理算符优先算法语法分析实验报告
算符优先分析法课程设计报告
算符优先分析算法
算符优先语法分析设计原理与实现技术 实验报告 及源代码 北京交通大学
编译原理实验二 语法分析
- 算符优先分析算法(3)
- 简单优先和算符优先分析方法ppt课件
- 编译原理实验报告5-语法分析程序的设计(2)
- 实验二语法分析算符优先法
- 算符优先分析法设计与实现
- 算符优先分析法课程设计报告
- 算符优先实验报告
- 实验二 语法分析(算符优先) (2)
- C.4 算符优先分析法 实验报告
- 实验三算符优先分析算法设计与实现
- 算符优先分析法系统设计应用
- 判定算符优先文法
- C.4-算符优先分析法-实验报告
- 编译原理 实验报告实验二 语法分析(算符优先)
- 算符优先分析器设计实验报告--宁剑
- 编译原理实验报告5-语法分析程序的设计
- c语言实现算符优先语法分析
- 实验报告 算符优先分析器
- 编译原理算符优先算法语法分析实验报告
- 算符优先文法分析器