设计题一：算术表达式的语法分析及语义分析程序设计。
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 { scanf("%s", st[i]); //存储文法规则，初始化FIRSTVT集和LASTVT集*/ first[i][0] = 0; /*first[i][0]和last[i][0]分别表示st[i][0]非终极符的FIRSTVT集和LASTVT集中元素的个数*/ last[i][0] = 0; } for (i = 0; i { for (j = 0; st[i][j] != '\0'; j++) { if (st[i][0]<'A' || st[i][0]>'Z') { printf("文法error!\n"); exit(-1); } 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); } } } } for (i = 0; i for (j = 0; st[i][j] != '\0'; j++) if ((st[i][j]<'A' || st[i][j]>'Z') && st[i][j] != '-'&&st[i][j] != '>'&&st[i][j] != '|') lable[k++] = st[i][j]; lable[k] = '#'; lable[k + 1] = '\0'; table();// printf("FIRST集为：\n"); //输出每个非终结符的FIRST集for (i = 0; i { printf("%c: ", st[i][0]); for (j = 0; j printf("%c ", first[i][j + 1]); printf("\n"); } printf("LAST集为：\n"); //输出每个非终结符的LAST集 for (i = 0; i { printf("%c: ", st[i][0]); for (j = 0; j { printf("%c ", last[i][j + 1]); } printf("\n"); } printf("算符优先分析表如下:\n"); for (i = 0; lable[i] != '\0'; i++) printf("\t%c", lable[i]); printf("\n"); for (i = 0; i { printf("%c\t", lable[i]); for (j = 0; j { printf("%c\t", data[i][j]); } printf("\n"); } printf("请输入文法输入符号串以#结束:"); scanf("%s", input); deal(); cout << "逆波兰式为："; for (i = 0; lable[i] != '\0'; i++) cout << output[i] << '\0';// cout << endl; } void table() { 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] != '\0'; j++) { if (st[i][j] == '|')// { text[x][y] = '\0'; 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] = '\0'; x++; y = 0; } r1 = x;// printf("转化后的文法为:\n"); for (i = 0; i printf("%s\n", text[i]); } for (i = 0; i { str[i][0] = text[i][0]; for (j = 3, l = 1; text[i][j] != '\0'; j++, l++) str[i][l] = text[i][j]; str[i][l] = '\0'; } for (i = 0; i { for (j = 1; text[i][j + 1] != '\0'; j++) { if (terminal_symbol(text[i][j]) && terminal_symbol(text[i][j + 1])) { m = location(text[i][j]); n = location(text[i][j + 1]); data[m][n] = '='; } if (text[i][j + 2] != '\0'&&terminal_symbol(text[i][j]) && terminal_symbol(text[i][j + 2]) && !terminal_symbol(text[i][j + 1])) { m = location(text[i][j]); n = location(text[i][j + 2]); data[m][n] = '='; } if (terminal_symbol(text[i][j]) && !terminal_symbol(text[i][j + 1]))//终结符和非终结符相接，用后于关系填表 { for (k = 0; k { if (st[k][0] == text[i][j + 1]) break; } m = location(text[i][j]); for (t = 0; t { n = location(first[k][t + 1]); data[m][n] = '<'; } } if (!terminal_symbol(text[i][j]) && terminal_symbol(text[i][j + 1]))//非终结符和终结符相接，用先于关系填表 { for (k = 0; k { 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) //求FIRSTVT集{ 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])) { first[i][n] = st[i][m + 1]; n++; } else { if (terminal_symbol(st[i][m + 2])) { first[i][n] = st[i][m + 2]; n++; } if (st[i][m + 1] != c) { firstvt(st[i][m + 1]); for (j = 0; j { if (st[j][0] == st[i][m + 1]) break; } for (k = 0; k { int t; for (t = 0; t { if (first[i][t] == first[j][k + 1]) break; } if (t == n) { first[i][n] = first[j][k + 1]; n++; } } } } } m++; } while (st[i][m] != '\0'); first[i][n] = '\0'; first[i][0] = --n; fflag[i] = 1; } } void lastvt(char c) //求LASTVT集{ int i, j, k, m, n; for (i = 0; i { if (st[i][0] == c) break; } if (lflag[i] == 0) { n = last[i][0] + 1; m = 0; do { if (st[i][m + 1] == '\0' || st[i][m + 1] == '|') { if (terminal_symbol(st[i][m])) { last[i][n] = st[i][m]; n++; } else { if (terminal_symbol(st[i][m - 1])) { last[i][n] = st[i][m - 1]; n++; } if (st[i][m] != c) { lastvt(st[i][m]); for (j = 0; j { if (st[j][0] == st[i][m]) break; } for (k = 0; k { int t; for (t = 0; t { if (last[i][t] == last[j][k + 1]) break; } if (t == n) { last[i][n] = last[j][k + 1]; n++; } } } } } m++; } while (st[i][m] != '\0'); last[i][n] = '\0'; 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] != '\0'; i++); //计算输入串的长度z = i--;// i = 0; while ((a = input[i]) != '\0')//a表示要输入的字符 { if (terminal_symbol(s[k])) j = k; else j = k - 1; x = location(s[j]); y = location(a); if (data[x][y] == '>') { if (lable[x] != ')') output[size++] = lable[x]; //将要规约的终结符存起来 out(1, k, s); printf("%c", a); out(i + 1, z, input); printf("规约\n"); do { q = s[j]; if (terminal_symbol(s[j - 1])) j = j - 1; else j = j - 2; x = location(s[j]); y = location(q); } while (data[x][y] != '<'); int m, n, N; for (m = j + 1; m <= k; m++) { for (N = 0; N for (n = 1; str[N][n] != '\0'; n++) { if (!terminal_symbol(s[m]) && !terminal_symbol(str[N][n])) { if(terminal_symbol(s[m + 1]) && terminal_symbol(str[N][n + 1]) && s[m + 1] == str[N][n + 1]) { s[j + 1] = str[N][0]; break; } } else if (terminal_symbol(s[m])) if (s[m] == str[N][n]) { s[j + 1] = str[N][0]; break; } } } k = j + 1; if (k == 2 && a == '#') { out(1, k, s); printf("%c", a); out(i + 1, z, input); printf("结束\n"); 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) //求字符c在算符优先关系表中的下标{ int i; for (i = 0; lable[i] != '\0'; i++) { if (c == lable[i]) return i; } return -1; } int terminal_symbol(char c) //判断字符c是否是终极符{ int i; for (i = 0; lable[i] != '\0'; i++) { if (c == lable[i]) return 1; } return 0; } xx理工大学 《编译原理》 题目语法分析程序 姓名： 学号： 班级： 一、实验目的 编制一个递归下降分析程序，实现对词法分析程序所提供的单词序列的语法检查和结构分析。 二、实验要求 利用C语言编制递归下降分析程序，并对简单语言进行语法分析。 2.1 待分析的简单语言的语法 用扩充的BNF表示如下： ⑴<程序>：：=begin<语句串>end ⑵<语句串>：：=<语句>{；<语句>} ⑶<语句>：：=<赋值语句> ⑷<赋值语句>：：=ID：=<表达式> ⑸<表达式>：：=<项>{+<项> | -<项>} ⑹<项>：：=<因子>{*<因子> | /<因子> ⑺<因子>：：=ID | NUM | （<表达式>） 2.2 实验要求说明 输入单词串，以“#”结束，如果是文法正确的句子，则输出成功信息，打印“success”，否则输出“error”。 例如： 输入begin a:=9; x:=2*3; b:=a+x end # 输出success 输入x:=a+b*c end # 输出error 2.3 语法分析程序的酸法思想 ⑴主程序示意图如图2-1所示。 图2-1 语法分析主程序示意图 ⑵递归下降分析程序示意图如图2-2所示。 ⑶语句串分析过程示意图如图2-3所示。 图2-2 递归下降分析程序示意图 图2-3 语句串分析示意图 ⑷statement 语句分析程序流程如图2-4、2-5、2-6、2-7所示。 图2-4 statement 语句分析函数示意图 图2-5 expression 表达式分析函数示意图 图2-7 factor分析过程示意图三、语法分析程序的C语言程序源代码 #include "stdio.h" #include "string.h" char prog[100],token[8],ch; char *rwtab[6]={"begin","if","then","while","do","end"}; int syn,p,m,n,sum; int kk; factor(); expression(); yucu(); term(); statement(); lrparser(); scaner(); main() { p=kk=0; printf("\nGrade:05 Class:03 Name:Qiyubing Number:200507096 \n"); printf("\n----Please input the string end with '#':-------- \n"); do 《LL（1）分析器的构造》实验报告 一、实验名称 LL(1)分析器的构造 二、实验目的 设计、编制、调试一个LL(1)语法分析器，利用语法分析器对符号串的识别，加深对语法分析原理的理解。 三、实验内容和要求 设计并实现一个LL(1)语法分析器，实现对算术文法: G[E]:E->E+T|T T->T*F|F F->(E)|i 所定义的符号串进行识别，例如符号串i+i*i为文法所定义的句子，符号串ii+++*i+不是文法所定义的句子。 实验要求: 1、检测左递归，如果有则进行消除； 2、求解FIRST集和FOLLOW集； 3、构建LL(1)分析表； 4、构建LL分析程序，对于用户输入的句子，能够利用所构造的分析程序进行分析，并显示出分析过程。 四、主要仪器设备 硬件：微型计算机。 软件： Code blocks（也可以是其它集成开发环境）。 五、实验过程描述 1、程序主要框架 程序中编写了以下函数，各个函数实现的作用如下： void input_grammer(string *G);//输入文法G //将文法G预处理得到产生式集合P，非终结符、终结符集合U、u， int eliminate_1(string *G,string *P,string U,string *GG);//消除文法G中所有直接左递归得到文法GG int* ifempty(string* P,string U,int k,int n);//判断各非终结符是否能推导为空 string* FIRST_X(string* P,string U,string u,int* empty,int k,int n)；求所有非终结符的FIRST集 string FIRST(string U,string u,string* first,string s)；//求符号串s=X1X2...Xn的FIRST集 string** create_table(string *P,string U,string u,int n,int t,int k,string* first)；//构造分析表 void analyse(string **table,string U,string u,int t,string s)；//分析符号串s 2、编写的源程序 #include 一、实验内容和目的 1. 已知待分析的C语言子集的语法，用EBNF表示如下： (1)<程序>→main()<语句块> (2)<语句块>→“{” <语句串>“}” (3)<语句串>→<语句>{;<语句>} ; (4)<语句>→<赋值语句>|<条件语句>|<循环语句> (5)<赋值语句>→ID=<表达式> (6)<条件语句>→if(条件)<语句块> (7)<循环语句>→while(<条件>)<语句块> (8)<条件>→<表达式><关系运算符><表达式> (9)<表达式>→<项>{+<项>}|<项>{-<项>} (10)<项>→<因子>{*<因子>}|<因子>{/<因子>} (11)<因子>→ID|NUM|(<表达式>) (12)<关系运算符>→<|<=|>|>=|==|!= 2. 实验目的、要求实现的功能 实验目的：编制一个语法分析程序，实现对词法分析程序所提供的单词序列进行语法检查和结构分析。 实验要求：在上机(一)词法分析的基础上，采用递归子程序法或其他适合的语法分析方法，实现其语法分析程序。要求编译后能检查出语法错误。 3. 将实验方法改写为适合预测分析法的文法如下： (1) <程序>→main()<语句块> (2)<语句块>→{ <语句串>} (3)<语句串>→<语句>; <语句串> (3_1) <语句串>→ε (4)<语句>→<赋值语句> (5)<语句>→<条件语句> (6) <语句>→<循环语句> (7)<赋值语句>→ID=<表达式> (8)<条件语句>→if(<条件>)<语句块> (9)<循环语句>→while(<条件>)<语句块> (10)<条件>→<表达式><关系运算符><表达式> (11)<表达式>→<项><表达式`> (11_1)<表达式`>→+<项><表达式`> (11_2)<表达式`>→-<项><表达式`> (11_3)<表达式`>→ε (12) <项>→<因子><项`> (12_1) <项`>→*<因子><项`> (12_2)<项`>→/<因子><项`> (12_3)<项`>→ε (13) <因子>→ID (14) <因子>→NUM (15) <因子>→(<表达式>) (16) <关系运算符>→< (17) <关系运算符>→<= 实验三自下而上语法分析及语义分析 一、实验目的： 通过本实验掌握LR分析器的构造过程，并根据语法制导翻译，掌握属性文法的自下而上计算的过程。 二、实验学时： 4学时。 三、实验内容 根据给出的简单表达式的语法构成规则（见五），编制LR分析程序，要求能对用给定的语法规则书写的源程序进行语法分析和语义分析。 对于正确的表达式，给出表达式的值。 对于错误的表达式，给出出错位置。 四、实验方法 采用LR分析法。 首先给出S-属性文法的定义（为简便起见，每个文法符号只设置一个综合属性，即该文法符号所代表的表达式的值。属性文法的定义可参照书137页表6.1），并将其改造成用LR分析实现时的语义分析动作（可参照书145页表6.5）。 接下来给出LR分析表。 然后程序的具体实现： ●LR分析表可用二维数组（或其他）实现。 ●添加一个val栈作为语义分析实现的工具。 ●编写总控程序，实现语法分析和语义分析的过程。 注：对于整数的识别可以借助实验1。 五、文法定义 简单的表达式文法如下： E->E+T|E-T|T T->T*F|T/F|F F->(E)|i 上式中，i 为整数。 六、处理程序例 例1: 正确源程序例： 23+(45+4)* 40分析结果应为：正确的表达式。其值为：1983 例2: 错误源程序例： 5+(56+)-24 分析结果应为：错误的表达式：出错位置为） 附录：源程序 #include LL(1)语法分析实验报告 一、实验题目 LL（1）语法分析 二、实验目的 通过设计、编制、调试一个典型的语法分析程序，实现对词法分析程序所提供的单词序列进行语法检查和结构分析，检查语法错误，进一步掌握常用的语法分析方法。 三、实验内容 构造LL(1)语法分析程序，任意输入一个文法符号串，并判断它是否为文法的一个句子。程序要求为该文法构造预测分析表，并按照预测分析算法对输入串进行语法分析，判别程序是否符合已知的语法规则，如果不符合则输出错误信息。 消除递归前的文法消除递归和提取公因子后的等价文法 S →S ∨ a T | a T | ∨ a T S→aTS’ |vaTS’ T →∧ a T | ∧a S’→vaTS’ |ε T→∧ a T’ T’→∧ aT’ |ε 根据已建立的分析表，对下列输入串：a∧ a∧ a进行语法分析，判断其是否符合文法。 四、实验要求 1.根据已由的文法规则建立LL（1）分析表； 2.输出分析过程。 请输入待分析的字符串: a∧ a∧ a 符号栈输入串所用产生式 #S a∧ a∧ a# #S’Ta a∧ a∧ a# S→aTS’ #S’T ∧ a∧ a# # S’T’a∧∧ a∧ a# T→∧ a T’ # S’T’a a∧ a# # S’T’∧ a# # S’T’a∧∧ a# T’→∧ aT’ # S’ T’a a# # S’ T’# # S’ # T’→ε # # S’→ε 五、程序思路 模块结构： 1、定义部分：定义常量、变量、数据结构。 2、初始化：设立LL(1)分析表、初始化变量空间（包括堆栈、结构体等）； 3、运行程序：让程序分析一个text文件，判断输入的字符串是否符合文法定义的规则； 4、利用LL(1)分析算法进行表达式处理：根据LL(1)分析表对表达式符号串进行堆栈（或其他）操作，输出分析结果，如果遇到错误则显示简单的错误提示。 六、程序源代码 /* 程序名称： LL(1)文法分析程序 */ /* S->S>aT|aT|>aT */ /* T-> 语义分析程序的设计与实现 班号：2008211316姓名：张荣学号：08211627序号：26 实验日期：2010-11-23 一：实验内容： (2) 二：实验要求： (2) 三：实验方法： (2) ◆由LEX建立YACC的词法分析程序 (2) ◆yacc原理介绍 (3) ◆词法分析 (4) ◆解析器如何工作 (5) ◆Yacc环境 (6) ◆常用代码 (7) 第四：YACC内部名称： (7) 第五：运行结果（源代码见附录） (8) 第六：实验总结 (9) 第七：附录 (10) 附录一：yacc程序，加注释 (10) 附录二：词法分析器的工作原理 (16) 一：实验内容： 编写语法分析程序，实现对算术表达式的语法分析，要求所分析的算术表达式由如下的文法产生。 ◆E->E+T|E-T|T ◆T->T*F|T/F|F ◆F->id|(E)|num 二：实验要求： 在对表达式进行分析的同时，输出所采用的产生式。 可以采用多种方法 ◆编写递归调用程序，实现自顶向下的分析。 ◆编写LL(1)语法分析程序，要求： ◇编程实现算法4.2，为给定的文法自动构造预测分析表 ◇编程实现算法4.1，构造LL(1)预测分析程序， ◆编写语法分析程序，实现自底向上的分析，要求： ◇构造识别所有活前缀的DFA ◇构造LR分析表 ◇编程实现算法4.3，构造LR分析程序 ◆利用yacc自动生成语法分析程序，调用LEX自动生成的词法分析器程序 三：实验方法： ◆由LEX建立YACC的词法分析程序 由LEX产生的词法分析程序可用于YACC，LEX编译程序根据LEX 源程序产生词法分析程序yylex(),这个名字就是YACC所需要的词法分析程序的名字。如果YACC要调用LEX产生的词法分析程序，则在YACC源程序的第三部分用语句#include“lex.yy.c”代替函数yylex()的定义，这一yylex()就可以访问YACC中记号的名字，因为LEX的输出时候YACC输出文件的一部分，所有，每个LEX的动作都返回YACC 知道的终结符。 在UNIX的环境下，如果LEX源程序在first.l中，YACC的源程序在second.y中，可以使用以下命令得到所需要的分析程序。 Lex first.l Yacc second.y cc-o yaccdemo y.tab.c lex.yy.c ◆yacc原理介绍 Yacc 是用可移植的C 语言写成的。接受的规定类别是非常一般性的: 带有去歧义规则的LALR(1) 文法。 Yacc 提供了一个通用工具来在计算机程序的输入上施加结构。Yacc 用户准备输入处理的规定；它包括描述输入结构的规则，在识别了这些规则的时候调用的代码，和做基本输入的一个低层例程。Yacc 接着生成一个函数来控制输入处理。这个函数叫做解析器(parser)，它调用用户提供的低层输入例程(词法分析器(analyzer))来从输入流中选取基本项目(叫做记号(token))。依据叫做文法规则的输入结构规则来组织这些记号；在识别了这些规则中的某一个的时候，接着调用为这个规则提供的叫做动作的用户代码；动作有能力返回值并 编译原理实验报告 实验一 一、实验名称：词法分析器的设计 二、实验目的：1，词法分析器能够识别简单语言的单词符号 2，识别出并输出简单语言的基本字.标示符.无符号整数.运算符.和界符。 三、实验要求：给出一个简单语言单词符号的种别编码词法分析器 四、实验原理： 1、词法分析程序的算法思想 算法的基本任务是从字符串表示的源程序中识别出具有独立意义的单词符号，其基本思想是根据扫描到单词符号的第一个字符的种类，拼出相应的单词符号。 2、程序流程图 （1 （2）扫描子程序 3 五、实验内容： 1、实验分析 编写程序时，先定义几个全局变量a[]、token[]（均为字符串数组),c,s( char型)，i,j,k（int型），a[]用来存放输入的字符串，token[]另一个则用来帮助识别单词符号，s用来表示正在分析的字符。字符串输入之后，逐个分析输入字符，判断其是否‘#’，若是表示字符串输入分析完毕，结束分析程序，若否则通过int digit(char c)、int letter(char c)判断其是数字，字符还是算术符,分别为用以判断数字或字符的情况，算术符的判断可以在switch语句中进行，还要通过函数int lookup(char token[])来判断标识符和保留字。 2 实验词法分析器源程序： #include 题目：词法分析器的设计与实现 一、引言................................ 错误!未定义书签。 二、词法分析器的设计 (3) 2.1词的内部定义 (3) 2.2词法分析器的任务及功能 (3) 3 2.2.2 功能： (4) 2.3单词符号对应的种别码： (4) 三、词法分析器的实现 (5) 3.1主程序示意图： (5) 3.2函数定义说明 (6) 3.3程序设计实现及功能说明 (6) 错误!未定义书签。 7 7 四、词法分析程序的C语言源代码： (7) 五、结果分析： (12) 摘要：词法分析是中文信息处理中的一项基础性工作。词法分析结果的好坏将直接影响中文信息处理上层应用的效果。通过权威的评测和实际应用表明,IRLAS是一个高精度、高质量的、高可靠性的词法分析系统。众所周知,切分歧义和未登录词识别是中文分词中的两大难点。理解词法分析在编译程序中的作用，加深对有穷自动机模型的理解，掌握词法分析程序的实 现方法和技术，用c语言对一个简单语言的子集编制一个一遍扫描的编译程序，以加深对编译原理的理解,掌握编译程序的实现方法和技术。Abstract:lexical analysis is a basic task in Chinese information processing. The results of lexical analysis will directly affect the effectiveness of the application of Chinese information processing. The evaluation and practical application show that IRLAS is a high precision, high quality and high reliability lexical analysis system. It is well known that segmentation ambiguity and unknown word recognition are the two major difficulties in Chinese word segmentation. The understanding of lexical analyse the program at compile, deepen of finite automata model for understanding, master lexical analysis program implementation method and technology, using C language subset of a simple language compilation of a scanned again compiler, to deepen to compile the principle solution, master compiler implementation method and technology. 关键词：词法分析器?扫描器?单词符号?预处理 Keywords: lexical analyzer word symbol pretreatment scanner 一、引言 运用C语言设计词法分析器，由指定文件读入预分析的源程序，经过词法分析器的分析，将结果写入指定文件。本程序是在Visual?Studio环境下，使用C语言作为开发工具。基于实验任务 实验五LL(1)文法识别程序设计 一、实验目的 通过LL(1)文法识别程序的设计理解自顶向下的语法分析思想。 二、实验重难点 FIRST集合、FOLLOW集合、SELECT集合元素的求解，预测分析表的构造。 三、实验内容与要求 实验内容： 1．阅读并理解实验案例中LL(1)文法判别的程序实现； 2．参考实验案例，完成简单的LL(1)文法判别程序设计。 四、实验学时 4课时 五、实验设备与环境 C语言编译环境 六、实验案例 1．实验要求 参考教材93页预测分析方法，94页图5.11 预测分析程序框图，编写表达式文法的识别程序。要求对输入的LL(1)文法字符串，程序能自动判断所给字符串是否为所给文法的句子，并能给出分析过程。 表达式文法为： E→E+T|T T→T*F|F F→i|(E) 2．参考代码 为了更好的理解代码，建议将图5.11做如下标注： /* 程序名称：LL(1)语法分析程序*/ /* E->E+T|T */ /* T->T*F|F */ /* F->(E)|i */ /*目的: 对输入LL(1)文法字符串，本程序能自动判断所给字符串是否为所给文法的句子，并能给出分析过程。 /********************************************/ /* 程序相关说明*/ /* A=E' B=T' */ /* 预测分析表中列号、行号*/ /* 0=E 1=E' 2=T 3=T' 4=F */ /* 0=i 1=+ 2=* 3=( 4=) 5=# */ /************************************/ #include"iostream" #include "stdio.h" #include "malloc.h" #include "conio.h" /*定义链表这种数据类型参见： https://www.doczj.com/doc/e717874084.html,/link?url=_owQzf8PRZOt9H-5oXIReh4X0ClHo6zXtRdWrdSO5YBLpKl NvkCk0qWqvFFxjgO0KzueVwEQcv9aZtVKEEH8XWSQCeVTjXvy9lxLQ_mZXeS###*/ struct Lchar{ char char_ch; struct Lchar *next; }Lchar,*p,*h,*temp,*top,*base; /*p指向终结符线性链表的头结点，h指向动态建成的终结符线性链表节点，top和base分别指向非终结符堆栈的顶和底*/ 实验三语法分析器 一、实验目的： 理解和掌握LL(1)语法分析方法的基本原理；根据给出的LL(1)文法，掌握LL(1)分析表的构造及分析过程的实现，掌握语法分析方法和程序设计方法。 二、实验要求： 对每个非终极符按其产生式结构构造相应语法分析子程序，其中终极符产生匹配命令，而非终极符则产生过程调用命令。因为文法递归相应子程序也递归，所以称这种方法为递归子程序下降法或递归下降法。其中子程序的结构与。产生式结构几乎是一致的，通过设计、编程、调试出一个具体语法分析程序。 三、实验原理： 语法分析是编译过程的核心部分。它的任务是在词法分析识别出单词符号串的基础上，分析并判定程序的语法结构是否符合语法规则。语法分析器的工作本质上是按文法的产生式，识别输入串是否是一个句子。自上而下分析法的主旨是，对任何输入串，试图用一切可能的方法，从文法开始符号出发，自上而下地为输入串建立一棵语法树。这种方法本质上是一种试探过程，是反复使用不同产生式谋求匹配输入串的过程。 对于一个文法满足以下三个条件，则称该文法为LL(1)文法。 文法不含有左递归。 对于文法中的每一个非终结符A的各个产生式的侯选首符集两两不相交。即，若A->Q1|Q2|…|Qn 则FIRST(Qi) ^FIRST(Qj)=null (i!=j) 对文法中的每个非终结符号A，若他存在某个侯选首符集包含空串，则FIRST(A)^FOLLOW(A)=null 对于一个文法满足LL(1)条件时，我们就可以对其输入串进行有效的无回溯的自上而下分析程序，这个分析程序是由一组递归过程组成的，每个过程对应文法的一个非终结符号。 四、实验步骤： 1、功能描述： 根据给定的文法，由程序生成项集族和语法分析表，对输入的源程序进行词法分析，得到语法分析的输入串，经过语法分析后得到三个栈，它们分别是状态栈，字符栈，输入栈，从而分析出输入的源程序是否有语法错误。 2、构造自己设计的小语言的语法分析器： (1) 语言的语法描述(语法规则)的设计即文法的设计； (2) 把文法形式符号中所隐含的信息内容挖掘出来并用LL或LR的资料形式(分析表)表示出来； (3) 语法分析的数据输入形式和输出形式的确定； 《编译原理》实验报告题目: 语法分析器的制作 学生姓名:江荣吉 班级: 学号: 指导教师: 成绩: 西安邮电大学计算机学院 2015 年 6 月 7 日 一：实验目的 熟悉语法分析的过程； 理解相关文法的步骤； 熟悉First集和Follow集生成 二：实验要求 对于给定的文法，试编写调试一个语法分析程序： 要求和提示： （1）可选择一种你感兴趣的语法分析方法（LL(1)、算符优先、递归下降、SLR(1)等）作为编制语法分析程序的依据。 （2）对于所选定的分析方法，如有需要，应选择一种合适的数据结构，以构造所给文法的机内表示。 （3）能进行分析过程模拟。如输入一个句子，能输出与句子对应的语法树，能对语法树生成过程进行模拟；能够输出分析过程每一步符号栈的变化情 况。 设计一个由给定文法生成First集和Follow集并进行简化的算法动态模拟。 三：实验过程 1：文法： E->TE’ E’->+TE’|ε T->FT’ T’->*FT’|ε F->(E)|i: 2程序描述（LL(1)文法） 本程序是基于已构建好的某一个语法的预测分析表来对用户的输入字符串进行分析，判断输入的字符串是否属于该文法的句子。 基本实现思想：接收用户输入的字符串（字符串以“#”表示结束）后，对用做分析栈的一维数组和存放分析表的二维数组进行初始化。然后取出分析栈的栈顶字符，判断是否为终结符，若为终结符则判断是否为“#”且与当前输入符号一样，若是则语法分析结束，输入的字符串为文法的一个句子，否则出错若不为“#”且与当前输入符号一样则将栈顶符号出栈，当前输入符号从输入字符串中除去，进入下一个字符的分析。若不为“#”且不与当前输入符号一样，则出错。 学号20102７９8 专业软件工程姓名薛建东 实验日期２013.04.０8 教师签字成绩实验报告 【实验名称】ＬL（1）语法分析 【实验目的】 通过完成预测分析法的语法分析程序,了解预测分析法和递归子程序法的区别和联系。使了解语法分析的功能，掌握语法分析程序设计的原理和构造方法,训练掌握开发应用程序的基本方法。 【实验内容】 ◆根据某一文法编制调试LL ( 1)分析程序，以便对任意输入的符号串进行分析。 ◆构造预测分析表,并利用分析表和一个栈来实现对上述程序设计语言的分析程序。 ◆分析法的功能是利用LＬ（１)控制程序根据显示栈栈顶内容、向前看符号以及LL(1) 分析表,对输入符号串自上而下的分析过程。 【设计思想】 （1）、LL(１)文法的定义 ＬL(1)分析法属于确定的自顶向下分析方法。LＬ（１)的含义是：第一个Ｌ表明自顶向下分析是从左向右扫描输入串，第2个L表明分析过程中将使用最左推导，1表明只需向右看一个符号便可决定如何推导，即选择哪个产生式（规则)进行推导。 LL(1)文法的判别需要依次计算FIRＳT集、FOLＬＯW集和SELLＥＣT集,然后判断是否为LL（1)文法，最后再进行句子分析。 需要预测分析器对所给句型进行识别。即在LＬ(１)分析法中,每当在符号栈的栈顶出现非终极符时，要预测用哪个产生式的右部去替换该非终极符;当出现终结符时，判断其与剩余输入串的第一个字符是否匹配,如果匹配，则继续分析,否则报错。ＬＬ（1）分析方法要求文法满足如下条件：对于任一非终极符A的两个不同产生式Ａ→α，A→β,都要满足下面条件:ＳELEＣＴ(Ａ→α)∩SELＥCT（Ａ→β)＝? (2）、预测分析表构造 LL（1)分析表的作用是对当前非终极符和输入符号确定应该选择用哪个产生式进行推 LR分析程序设计 1实验目的 （1）构造LR 分析程序，利用它进行语法分析，判断给出的符号串是否为 该文法识别的句子； （2）了解LR分析方法是严格的从左向右扫描，和自底向上的语法分析方法。 2实验内容和实验要求 (1)LR分析器能够构造来识别所有能用上下文无关文法写的程序设计语言的结构。 (2)LR分析方法是已知的最一般的无回溯，移进-归约方法，它能够和其他移进-归约方法一样有效地实现。 (3)LR方法能分析的文法类是预测分析法能分析的文法类的真超集。 3 待分析的语法描述 E->vI:T I->I,i|i T->r 4算法描述 LR分析法基本思想 LR分析法是一种能够根据分析栈中的文法符号串（状态）和向右顺序查看第k个输入字符就能够唯一确定LR（k）分析器的动作是移进还是用哪一条产生式归约的分析方法。 采用LR（0）分析法进行本次实验，即无需向前查看输入符号就能够确定分析器的动作。 实现方法 LR（0）分析器由三个部分组成： (1)总控程序，也可以称为驱动程序。对所有的LR分析器总控程序都是相同的。 (2)分析表，不同的文法分析表将不同，同一个文法采用的LR分析器不同时，分析表将不同，分析表又可以分为动作表（ACTION）和状态转换（GOTO）表两个部分，它们都可用二维数组表示。由于它是总控程序的依据，所以在程序的第一部分就已经定义好。 (3)分析栈，包括文法符号栈和相应的状态栈，它们均是先进后出栈。 分析器的动作就是由栈顶状态和当前输入符号所决定。 (4)LR分析器及时察觉语法错误,快到自左向右扫描输入的最大可能。 为了使一个文法是LR的，只要保证当句柄出现在栈顶时，自左向右扫描的移进-归约分析器能够及时识别它便足够了。当句柄出现在栈顶时，LR分析器必须要扫描整个栈就可以知道这一点，栈顶的状态符号包含了所需要的一切信息。如果仅知道栈内的文法符号就能确定栈顶是什么句柄。由于LR分析表的转移函数本 实验三语法分析器的设计 一、实验内容 设计、编写和调试构造LR（0）项目集规范簇或实现基于LR分析表对给定的符号串进行LR 分析的程序。以下两个内容任选其中一项： （1）对于给定的文法，实现构造识别该文法全部活前缀DFA的程序。 （2）对于给定的LR分析表和符号串，设计程序以实现所输入符号串是否为合法符号串。 要求用JAVA语言编程。（可参考实验指导书P149至P156） 二、程序代码 AnalysisOfGrammer.java package analysis; import javax.swing.*; import javax.swing.table.DefaultTableModel; import java.awt.*; import java.awt.event.*; import java.io.*; import java.util.LinkedList; publicclass AnalysisOfGrammer extends JApplet{ private JFileChooser jfc = new JFileChooser(new File(".")); private JButton jbt1 = new JButton("打开文法文件"); private JButton jbt2 = new JButton("构造LR规范簇"); private JButton jbt3 = new JButton("构造LR分析表"); private JButton jbt4 = new JButton("清空"); private JButton jbt5 = new JButton("退出"); private JLabel jl1 = new JLabel("LR(0)项目集规范簇"); private JLabel jl2 = new JLabel("LR(0)分析表"); private JPanel p3 = new JPanel(); private JTextArea jta1 = new JTextArea(); private String[] grammer = new String[50]; privateint count = 0; private LinkedList 基于LR(1)的语法分析程序 1.设计目的： 设计、编制和调试一个典型的LR(1)分析器，进一步掌握LR(1)语法分析方法,掌握用预测分析方法分析LR(1)文法的具体过程，加深对LR(1)文法和预测分析方法的理解。 2.设计要求： （1）根据LR(1)分析法编写一个语法分析程序，.输入已给定文法，直接输入根据己知文法构造的LR(1)分析表。 （2）对于输入的符号串，所编制的语法分析程序应能正确判断此串是否为文法的句子，并要求输出分析过程。 3.设计过程： 3.1 LR(1)文法的含义： LR分析法的规约过程是规范推倒的逆过程，所以LR分析过程是一种规范规约的逆过程，L表示从左到右扫描输入串，R表示最左规约（即最右推导的逆过程），括号中的1表示向右查看输入符号数为1。LR（1）项目可以看成两个部分组成，一部分和LR （0）项目相同，这部分成为心，另一部分为向前搜索符集合。所以只有当面临的输入符属于向前搜索符的集合，才做规约动作，其他情况均出错。LR（1）方法恰好解决SLR（1）方法在某些情况下存在的无效规约问题。 3.2 设计思想： 根据自身实际情况，给定了编译原理书中的一个LR(1)文法，求出其项目集合转换函数，从而得出此LR(1)文法的分析表，在程序中直接输出此分析表，并根据分析表中的内容可对输入的符 号串进行分析，判断是接受还是出错，从而得出该输入的符号串是否为文法的一个句子。 3.3 算法描述： 1.CLOSURE(I)的构造 CLOSURE(I)表示和I中项目可以识别同样活前缀的所有项目的集合。它可以有以下方法得到： (1)I中的所有项目都属于CLOSURE(I)； (2)若项目[A→a.Bβ,a]属于CLOSURE(I)，B→ξ是一个产生式，那么，对于FIRST<βa>中的每一个中介符b,如果[β→.ξ,b]原来不在CLOSURE(I)中，则把它加进去； (3)重复执行步骤（2），直到CLOSURE(I)不再增大为止。 2.GO(I,X)的构造 GO(I,X)=CLOSURE(J) 其中J={任何形如[A→aX.Β,a]的项目[A→a.X.Β,a]属于I} 3.FIRST集合的构造 在这个程序中使用的是FIRST(βa)，这基于每一个非终结符的FRIST集合（终结符的FIRST就是它本身）。所以需要对每一个非终结符构造其FIRST集合。 方法如下： 连续使用下面的规则，直到每个集合FIRST不再增大为止。 （1）若X属于V T，则FIRST(X)={X}。 （2）若X属于V N，且有产生式X→a…，则把A加入到FIRST(X)中；若X→ξ也是一条产生式，则把ξ也加入到FIRST 中。 4.LR(1)分析表的构造 在实现GO(I,X)时，记录下状态的转化。得到分析表中的移进部分。然后再扫描所有的项目集，找到其中包含归约项目的哪些项目集，根据其中项目，得到分析表中那些鬼月的部分。 4 设计内容 4.1 主要变量说明： #define SIZE 20 //宏定义，定义sSIZE为12 #define sSIZE 12 //宏定义，定义sSIZE为12 《编译原理》 课程设计 院系信息科学与技术学院 专业软件工程 年级 2011级 学号 20112723 姓名林苾湲 西南交通大学信息科学与技术学院 2013年 12月 目录 课程设计1 词法分析器 (2) 1.1 设计题目 (2) 1.2 设计容 (2) 1.3 设计目的 (2) 1.4 设计环境 (2) 1.5 需求分析 (2) 1.6 概要设计 (2) 1.7 详细设计 (4) 1.8 编程调试 (5) 1.9 测试 (11) 1.10 结束语 (13) 课程设计2 赋值语句的解释程序设计 (14) 2.1 设计题目 (14) 2.2 设计容 (14) 2.3 设计目的 (14) 2.4 设计环境 (14) 2.5 需求分析 (15) 2.6 概要设计 (16) 2.7 详细设计 (16) 2.8 编程调试 (24) 2.9 测试 (24) 2.10 结束语 (25) 课程设计一词法分析器设计 一、设计题目 手工设计c语言的词法分析器（可以是c语言的子集）。 二、设计容 处理c语言源程序，过滤掉无用符号，判断源程序中单词的合法性，并分解出正确的单词，以二元组形式存放在文件中。 三、设计目的 了解高级语言单词的分类，了解状态图以及如何表示并识别单词规则，掌握状态图到识别程序的编程。 四、设计环境 该课程设计包括的硬件和软件条件如下： 4.1.硬件 （1）Intel Core Duo CPU P8700 （2）存4G 4.2.软件 （1）Window 7 32位操作系统 （2）Microsoft Visual Studio c#开发平台 4.3.编程语言 C#语言 五、需求分析 5.1.源程序的预处理：源程序中，存在许多编辑用的符号，他们对程序逻辑功能无任何影响。例如：回车，换行，多余空白符，注释行等。在词法分析之前，首先要先剔除掉这些符号，使得词法分析更为简单。 5.2.单词符号的识别并判断单词的合法性：将每个单词符号进行不同类别的划分。单词符号可以划分成5中。 (1)标识符：用户自己定义的名字，常量名，变量名和过程名。 (2)常数：各种类型的常数。 (3) 保留字（关键字）：如if、else、while、int、float等。 (4) 运算符：如+、-、*、<、>、=等。 (5)界符：如逗号、分号、括号等。 5.3.将所有合法的单词符号转化为便于计算机处理的二元组形式：（单词分类号，单词自身值）；以图形化界面显示出来。 5.4.可选择性地将结果保存到文件中。 六、概要设计 6.1．数据类型 6.1.1.单词的分类：本词法分析器演示的是C语言的一个子集，故字符集如下： 上海电力学院 编译原理 课程实验报告 实验名称：实验三自下而上语法分析及语义分析 院系：计算机科学和技术学院 专业年级： 学生姓名：学号： 指导老师： 实验日期： 实验三自上而下的语法分析 一、实验目的： 通过本实验掌握LR分析器的构造过程，并根据语法制导翻译，掌握属性文法的自下而上计算的过程。 二、实验学时： 4学时。 三、实验内容 根据给出的简单表达式的语法构成规则（见五），编制LR分析程序，要求能对用给定的语法规则书写的源程序进行语法分析和语义分析。 对于正确的表达式，给出表达式的值。 对于错误的表达式，给出出错位置。 四、实验方法 采用LR分析法。 首先给出S-属性文法的定义（为简便起见，每个文法符号只设置一个综合属性，即该文法符号所代表的表达式的值。属性文法的定义可参照书137页表6.1），并将其改造成用LR分析实现时的语义分析动作（可参照书145页表6.5）。 接下来给出LR分析表。 然后程序的具体实现： ● LR分析表可用二维数组（或其他）实现。 ●添加一个val栈作为语义分析实现的工具。 ●编写总控程序，实现语法分析和语义分析的过程。 注：对于整数的识别可以借助实验1。 五、文法定义 简单的表达式文法如下： (1)E->E+T (2)E->E-T (3)E->T (4)T->T*F (5)T->T/F (6)T->F (7)F->(E) (8)F->i 状态ACTION（动作）GOTO（转换） i + - * / ( ) # E T F 0 S5 S4 1 2 3 1 S6 S1 2 acc 2 R 3 R3 S7 S13 R3 R3 3 R6 R6 R6 R6 R6 R6 4 S 5 S4 8 2 3 5 R8 R8 R8 R8 R8 R8 6 S5 S4 9 3 7 S5 S4 10 8 S6 R12 S11 9 R1 R1 S7 S13 R1 R1 10 R4 R4 R4 R4 R4 R4 11 R7 R7 R7 R7 R7 R7 12 S5 S4 14 3 13 S5 S4 15 14 R2 R2 S7 S13 R2 R2 15 R5 R5 R5 R5 R5 R5 五、处理程序例和处理结果例 示例1：20133191*(20133191+3191)+ 3191#
相关主题
文本预览