实验1 词法分析
1.1 实验目的
（1）理解有穷自动机及其应用。
（2）掌握 NFA 到 DFA 的等价变换方法、DFA 最小化的方法。
（3）掌握设计、编码、调试词法分析程序的技术和方法。
1.2 实验任务
编写一个程序对输入的源代码进行词法分析，并打印分析结果。自己编写一个 PL/0 词法分析程序，使用的语言为C++。
1.3 算法描述
算法描述: 首先把常用关键字放在一个数组变量里，逐个判断输入的一个字符串是否为关键字，然后根据正则表达式来判断数字,字母以及各种标识符,同时对错误的语法做出判断输出
1.4 程序结构:
Main：读入字符串
analyze：词法分析
isLetter：判断是否是字母
isKey：判断是否是关键字
主函数调用analysis，analysis中调用了剩余函数。
1.5 程序清单
#include<iostream> using namespace std; #define MAX 21 /* 保留字|关键字：1 操作符|运算符：2 分界符：3 标识符：4 常数：5 无识别：6 */ char ch = ' '; char* keyWord[21] = { "iostream","void","int","char","string","bool","return","using","namespace","main","break","include","begin","end","if","else","while","switch","for","else if","std" }; char takes[20];//定义获取的字符 //判断是否是关键字 bool isKey(char* takes) { for (int i = 0; i < MAX; i++) { if (strcmp(takes, keyWord[i]) == 0) return true; } return false; } //判断是否是字母 bool isLetter(char letter) { if ((letter >= 'a' && letter <= 'z') || (letter >= 'A' && letter <= 'Z')) return true; else return false; } //判断是否是数字 bool isDigit(char digit) { if (digit >= '0' && digit <= '9') return true; else return false; } //词法分析 void analyze(FILE* fpin) { while ((ch = fgetc(fpin)) != EOF) { if (ch == ' ' || ch == '\t' || ch == '\n') {} //空格 回车 else if (isLetter(ch)) { //首是字母 char takes[30] = { '\0' }; int i = 0; while (isLetter(ch) || isDigit(ch)) { //后面是字母或者数字 takes[i] = ch; i++; ch = fgetc(fpin); } //回退一个指针 fseek(fpin, -1L, SEEK_CUR); if (isKey(takes)) { //关键字 cout << takes << "\t\t1" << "\t关键字" << endl; } else { //标识符 cout << takes << "\t\t4" << "\t标识符" << endl; } } else if (isDigit(ch) || (ch == '.')) //首是数字或者点 { bool mark = true; int i = 0; char takes[20] = { '\0' }; while (isDigit(ch) || isLetter(ch) || (ch == '.' && isDigit(fgetc(fpin)))) { if (isLetter(ch)) { mark = false; if (ch == '.')fseek(fpin, -1L, SEEK_CUR); takes[i] = ch; i++; ch = fgetc(fpin); } else { if (ch == '.')fseek(fpin, -1L, SEEK_CUR); takes[i] = ch; i++; ch = fgetc(fpin); } } fseek(fpin, -1L, SEEK_CUR); //属于无符号常数 if (mark) { cout << takes << "\t\t5" << "\t常数" << endl; } else cout << takes << "\t\t7" << "\t错误的标识符" << endl; } else switch (ch) { //运算符 case '+': { ch = fgetc(fpin); if (ch == '+')cout << "++" << "\t\t2" << "\t运算符" << endl; else { cout << "+" << "\t\t2" << "\t运算符" << endl; fseek(fpin, -1L, SEEK_CUR); } }break; case '-': { ch = fgetc(fpin); if (ch == '-')cout << "--" << "\t\t2" << "\t运算符" << endl; else { cout << "-" << "\t\t2" << "\t运算符" << endl; fseek(fpin, -1L, SEEK_CUR); } }break; case '*':cout << ch << "\t\t2" << "\t运算符" << endl; break; case '/':cout << ch << "\t\t2" << "\t运算符" << endl; break; //分界符 case '\"':cout << ch << "\t\t2" << "\t分界符" << endl; break; case '(':cout << ch << "\t\t3" << "\t分界符" << endl; break; case ')':cout << ch << "\t\t3" << "\t分界符" << endl; break; case '[':cout << ch << "\t\t3" << "\t分界符" << endl; break; case ']':cout << ch << "\t\t3" << "\t分界符" << endl; break; case ';':cout << ch << "\t\t3" << "\t分界符" << endl; break; case '{':cout << ch << "\t\t3" << "\t分界符" << endl; break; case '}':cout << ch << "\t\t3" << "\t分界符" << endl; break; //运算符 case '=': { ch = fgetc(fpin); if (ch == '=')cout << "==" << "\t\t2" << "\t运算符" << endl; else { cout << "=" << "\t\t2" << "\t运算符" << endl; fseek(fpin, -1L, SEEK_CUR); } }break; case '#': { ch = fgetc(fpin); if (ch == '=')cout << "#=" << "\t\t2" << "\t运算符" << endl; else { cout << "#" << "\t\t2" << "\t运算符" << endl; fseek(fpin, -1L, SEEK_CUR); } }break; case ':': { ch = fgetc(fpin); if (ch == '=')cout << ":=" << "\t\t2" << "\t运算符" << endl; else { cout << ":" << "\t\t2" << "\t运算符" << endl; fseek(fpin, -1L, SEEK_CUR); } }break; case '>': { ch = fgetc(fpin); if (ch == '=')cout << ">=" << "\t\t2" << "\t运算符" << endl; else { cout << ">" << "\t\t2" << "\t运算符" << endl; fseek(fpin, -1L, SEEK_CUR); } }break; case '<': { ch = fgetc(fpin); if (ch == '=')cout << "<=" << "\t\t2" << "\t运算符" << endl; else { cout << "<" << "\t\t2" << "\t运算符" << endl; fseek(fpin, -1L, SEEK_CUR); } }break; //无识别 default: cout << ch << "\t\t6" << "\t无识别符" << endl; } } } int main() { char input[30]; FILE* fpin; cout << "请输入源文件名：\n" << endl; for (;;) { cin >> input; if ((fpin = fopen(input, "r")) != NULL) break; else cout << "路径输入错误" << endl; } cout << "词法分析结果: " << endl; analyze(fpin); fclose(fpin); }
1.6 主要变量说明:
#define MAX 21 //定义关键字数量 char takes[20];//定义获取的字符 char*keyWord[21]={"iostream","void","int","char","string","bool","return","using","namespace","main","break","include","begin","end","if","else","while","switch","for","else if","std"};//保存关键字
1.7 调试情况
一个含C++源码的文本文件
调试情况及运行结果截图:
顺利执行,同时错误的语法也可以进行正确的判断
1.8 心得体会
通过完成词法分析程序的过程,更加深入的了解和复习了C++的使用方法,某些函数的运用,以及字符串的提取判别,文件流读取操作等等,也在调用函数过程中出现了许多的问题,通过请教同学和查阅资料都得到了解决.学习了新的函数,对C++有了更加充实的认知.
实验2 基于LL(1)方法的语法分析程序
2.1 实验目的
设计、编制和调试一个典型的语法分析方法，进一步掌握常用的语法分析方法。
2.2 实验要求
根据LL(1)分析法编写一个语法分析程序，直接输入根据已知文法构造的分析表M;
（1）程序具有通用性
所开发的程序可适用于任意输入串，且能判断该文法是否为LL(1)文法。
（2）有运行实例
对于输入符号串，所编制的语法分析程序应能正确判断此串是否为文法的句子，并要求输出分析过程。
2.3 算法描述
给定文法G[S]：表 示 空 串 S − > A T A − > B U T − > + A T ∣ 表示空串 S->AT A->BU T->+AT|表示空串S−>ATA−>BUT−>+AT∣
U->*BU|$
B->(S)|m
计算First集与Follow集合，先建立分析表，读入字符串，初始化分析栈，进入分析函数。
从左到右扫描输入串，采用最左推导，且每次直接推导只向前看一个输入符号，确定选择的规则。用一个变量记录步骤数量，及时输出。用一个变量记录输入字符串下标，作为指针的作用，控制String输出。
从分析栈中取栈顶，判断是否为非终结符号 。若是，找到栈顶在分析表中对应的规则。若为null，报错。存在，则执行输出；若不是，则判断其与输入式子头字符是否相同，相同，则输出匹配。继续读取栈顶，循环直至到底。
2.4 程序结构
Main：读入字符串
Analysis：分析函数
findH：寻找非终结符下标
findL：寻找终结符下标
Error：报错函数
主函数调用analysis，analysis中调用了剩余函数。
2.5 主要变量说明
LL1：LL1文法分析表
H：非终结符
L：终结符
Cmp：分析栈
Str：输入式
2.6 程序清单
#include <iostream> #include <cstring> #include <cstdio> #include <algorithm> #include <stack> using namespace std; //表格数组 char LL1[50][50][100] = { {"->AT", "->AT", "null", "null", "null", "null"}, {"->BU", "->BU", "null", "null", "null", "null"}, {"null", "null", "->$", "->+AT", "null", "->$"}, {"null", "null", "->$", "->$", "->*BU", "->$"}, {"->m", "->(S)", "null", "null", "null", "null"} }; char H[200] = "SATUB"; char L[200] = "m()+*#"; stack<char> cmp; int findH(char a) { //在H中找规则左部 for (int i = 0; i < 5; i++) //找到对应行 { if (a == H[i]) return i; } return -1; } int findL(char b) { //在L中找 找到对应列 for (int i = 0; i < 6; i++) //找到对应列 { if (b == L[i]) return i; } return -1; } int error(int i, int cnt, int len, char p[], char str[]) { //输入的第i个符号 执行第cnt步 输入len长 第一列p列内容 str输入表达式 printf("%d\t%s\t", cnt, p); for (int q = i; q < len; q++) { cout << str[q]; } printf("\t报错\n"); return len; } void analyze(char str[], int len) { //pindex记录stack长度，p为分析栈状态 int cnt = 1; //输出Step专用 int i = 0; char p[200] = "#S"; //输出stack专用 int pindex = 2; printf("Step\tStack\tString\tRule\n"); //输出制表 while (i < len) { int x, y; char ch = cmp.top(); //是规则右部分 出栈 if (ch >= 'A' && ch <= 'Z') { cmp.pop(); x = findH(ch); y = findL(str[i]); if (x != -1 && y != -1) { int len2 = strlen(LL1[x][y]); if (strcmp(LL1[x][y], "null") == 0) { i = error(i, cnt, len, p, str); continue; } printf("%d\t%s\t", cnt, p); if (p[pindex - 1] != '#') { p[pindex] = '\0'; pindex--; } if (LL1[x][y][2] != '$') { for (int q = len2 - 1; q > 1; q--) { p[pindex++] = LL1[x][y][q]; cmp.push(LL1[x][y][q]); //放更新了的字符 } } else { p[pindex] = '\0'; pindex--; } for (int q = i; q < len; q++) cout << str[q]; printf("\t%c%s\n", ch, LL1[x][y]); } else { i = error(i, cnt, len, p, str); continue; ///未找到，报错 } } else { if (ch == str[i]) { cmp.pop(); printf("%d\t%s\t", cnt, p); if (ch == '#' && str[i] == '#') { printf("#\t接受\n"); return; } for (int q = i; q < len; q++) { cout << str[q]; } printf("\t%c匹配\n", ch); pindex--; p[pindex] = '\0'; i++; } else { i = error(i, cnt, len, p, str); continue; ///报错 } } cnt++; } } //取下一个输入字符 int main() { char str[200]; cin >> str; int len = strlen(str); cmp.push('#'); cmp.push('S'); analyze(str, len + 1); system("pause"); return 0; }
2.7 调试情况
文法可以接收的语句示例：
文法不可以接收的语句示例：
根据已知文法构造的分析表，句子以及非句子均得到测试验证。
2.8 设计技巧
实现建立分析表、非终结符以及终结符数组，在匹配规则时，直接到分析表中匹配。建立一个分析栈来显示地实现非递归版本的递归下降分析，通过这个分析栈来实现回溯。在函数中通过变量指示数组位置来进行单个字符分析查找匹配。
2.9 心得体会
深入理解了LL1文法。熟悉掌握了基于LL1文法的语义分析流程。针对特定文法，需要先计算出其First及Follow集合构建LL1文法分析表，并通过分析栈来实现一步步分析。
