编译原理实验报告

编译原理 实验报告 实验一实验一 词法分析设计词法分析设计 一 实验目的 通过本实验的编程实践 使学生了解词法分析的任务 掌握词法分析程序设 计的原理和构造方法 使学生对编译的基本概念 原理和方法有完整的和清楚的 理解 并能正确地 熟练地运用 二 实验内容及其功能 用 VC VB JAVA 语言实现对 C 语言子集的源程序进行词法分析 通过输 入源程序从左到右对字符串进行扫描和分解 依次输出各个单词的内部编码及单 词符号自身值 若遇到错误则显示 Error 然后跳过错误部分继续显示 同时 进行标识符登记符号表的管理 三 数据结构及算法描述 k 数组 关键字表 每个数组元素存放一个关键字 s 数组 存放分界符表 可事先构造好分界符表 为了简单起见 分界符 算术运算符和关系运算符都放在 s 表中合并成一类 id 和 ci 数组分别存放标识符和常数 instring 数组为输入源程序的单词缓存 void dev string 字符串拼写 int handle 处理函数 void show int num 输出函数 void memset string 清空结构体 算法描述 通过对输入的字符串中的每一个字符进行判断确定其属性以及正误 1 从源程序文件中读入字符 2 统计行数和列数用于错误单词的定位 3 删除空格类字符 包括回车 制表符空格 4 按拼写单词 并用 内码 属性 二元式表示 属性值 token 的机内 表示 5 如果发现错误则报告出错 根据输入单词的第一个字符 有时还需读第二个字符 判断单词类 产生类号 以字符 k 表示关键字 id 表示标识符 ci 表示常数 s 表示分界符 对于标识符和常数 需分别与标识符表和常数表中已登记的元素相比较 如表中已有该元素 则记录其在表中的位置 如未出现过 将标识符按顺序填入 数组 id 中 将常数变为二进制形式存入数组中 ci 中 并记录其在表中的位置 lexical 过程中嵌有两个小过程 一个名为 getchar 其功能为从 instring 中按 顺序取出一个字符 并将其指针 pint 加 1 另一个名为 error 当出现错误时 调用这个过程 输出错误编号 算法流程图 四 实验代码 include include include include using namespace std string k 8 do end for if printf scanf then while 关键字表 char s1 6 分隔符表 char s2 6 运算符表 string s3 6 关系运算符表 string id 50 标识符 float ci 50 常数 struct result string name int zhong string shu string type int r instring 50 结果数组 string s 输入的字符串 int id count 标识符个数 int ci count 常数个数 void dev string int handle void show int num void memset string int main int row 1 while getline cin s 输入一行字符串 包括空格 int x i x handle for i 0 i x i 确定行数 instring i r row show x for i 0 i x i 清空结构体 memset instring i name row return 0 int handle int icount 0 id count 0 ci count 0 int count 0 while icount a 拼写字符串 icount while i 0 p 1 icount continue else 全是数字情况 dev instring count name s icount ci ci count ci ci count 10 s icount 0 icount continue if p 0 常数 instring count shu instring count name instring count type changshu instring count zhong 5 count else if p 1 如 3b 这种情况 instring count shu instring count name instring count type error instring count zhong 9 count ci count continue else if s icount 空格则继续向下遍历 icount continue else if s icount 首字符为其他 dev instring count name s icount icount if s icount s icount 情况 dev instring count name s icount instring count shu instring count name instring count type gxysf instring count zhong 4 icount count else instring count shu instring count name instring count type gxysf instring count zhong 4 count continue else if s icount s icount s icount s icount s icount s icount dev instring count name s icount 分隔符 instring count shu instring count name instring count type fgf instring count zhong 2 count icount continue else if s icount s icount s icount s icount 运算符 dev instring count name s icount icount if s icount s icount s icount s icount 出现 情况 dev instring count name s icount instring count shu instring count name instring count type error instring count zhong 9 icount count else instring count shu instring count name instring count type yunsuanfuu instring count zhong 3 count continue else 出现 instring count shu instring count name instring count type error instring count zhong 5 count icount continue return count void dev string else sss insert sss length 1 ch void show int num 输出函数 int i cout words the order type position endl for i 0 i num i cout instring i name instring i zhong instring i shu instring i type instring i r i 1 t endl void memset string for i 0 i ss length i ss i 0 五 实验结果 六 实验体会 设计的特点是利用结构体对每一个输入的字符进行保存并解析 在判断过程中考虑到了 标识符 运算符的一些特殊情况 利用一些函数对一些相连的单词进行连接使得错误率降 低 实验缺陷还是有很多 1 3b 的 二元序列为 error 不能输出 2 注释没有考虑 3 没有查询标识符表和参数表 4 关键字表不是输入进去 5 输入第二行时 存在一个空格 第一个字符串的类型出现错误 实验收获 1 加强了对词法分析器的了解 并懂得了其使用机制 2 回顾了许多关于 c 语言的知识 3 增强了在编程时的考虑全局的意识 也知道了自己的一些不足 实验二实验二 LL 1 分析法分析法 1 实验目的 通过完成预测分析法的语法分析程序 了解预测分析法和递归子程序法的区 别和联系 使学生了解语法分析的功能 掌握语法分析程序设计的原理和构造方 法 训练学生掌握开发应用程序的基本方法 有利于提高学生的专业素质 为培 养适应社会多方面需要的能力 2 实验内容 根据某一文法编制调试 LL 1 分析程序 以便对任意输入的符号串 进行分析 构造预测分析表 并利用分析表和一个栈来实现对上述程序设计语言的分 析程序 分析法的功能是利用 LL 1 控制程序根据显示栈栈顶内容 向前看符号 以及 LL 1 分析表 对输入符号串自上而下的分析过程 3 数据结构及算法 模块结构 1 定义部分 定义常量 变量 数据结构 2 初始化 设立 LL 1 分析表 初始化变量空间 包括堆栈 结构体 数组 临时变量等 3 控制部分 从键盘输入一个表达式符号串 4 利用 LL 1 分析算法进行表达式处理 根据 LL 1 分析表对表达式符号串进 行堆栈 或其他 操作 输出分析结果 如果遇到错误则显示错误信息 char A 20 分析栈 char B 20 剩余串 char v1 20 i 终结符 char v2 20 E G T S F 非终结符 int j 0 b 0 top 0 l L 为输入串长度 typedef struct type 产生式类型定义 char origin 大写字符 char array 5 产生式右边字符 int length 字符个数 type type e t g g1 s s1 f f1 g2 s2 结构体变量 type C 10 10 预测分析表 算法 四 实验代码 include include include include include using namespace std char A 20 分析栈 char B 20 剩余串 char v1 20 i 终结符 char v2 20 E G T S F 非终结符 int j 0 b 0 top 0 l L 为输入串长度 typedef struct type 产生式类型定义 char origin 大写字符 char array 5 产生式右边字符 int length 字符个数 type type e t g g1 s s1 f f1 g2 s2 结构体变量 type C 10 10 预测分析表 void print 输出分析栈 int a 指针 for a 0 a top 1 a printf c A a printf t t print void print1 输出剩余串 int j for j 0 j b j 输出对齐符 printf for j b j l j printf c B j printf t t t print1 int main int m n k 0 flag 0 finish 0 char ch x type cha 用来接受 C m n 把文法产生式赋值结构体 e origin E strcpy e array TG e length 2 t origin T strcpy t array FS t length 2 g origin G strcpy g array TG g length 3 g1 origin G g1 array 0 g1 length 1 g2 origin G strcpy g2 array TG g2 length 3 s origin S strcpy s array FS s length 3 s1 origin S s1 array 0 s1 length 1 s2 origin S strcpy s2 array FS s2 length 3 f origin F strcpy f array E f length 3 f1 origin F f1 array 0 i f1 length 1 for m 0 m 4 m 初始化分析表 for n 0 n 7 n C m n origin N 全部赋为空 填充分析表 C 0 0 e C 0 3 e C 1 1 g C 1 4 g1 C 1 5 g1 C 2 0 t C 2 3 t C 3 1 s1 C 3 2 s C 3 4 C 3 5 s1 C 4 0 f1 C 4 3 f C 1 7 g2 C 3 6 s2 do 读入分析串 scanf c if ch i exit 1 B j ch j while ch l j 分析串长度 ch B 0 当前分析字符 A top A top E E 进栈 printf 步骤 t t 分析栈 t t 剩余字符 t t 所用产生式 t 动作 n do x A top x 为当前栈顶字符 printf d k printf t t for j 0 j 7 j 判断是否为终结符 if x v1 j flag 1 break if flag 1 如果是终结符 if x finish 1 结束标记 print print1 printf nsuccess n 接受 getchar getchar exit 1 if x ch print print1 printf t printf GETNEXT i n ch B b 下一个输入字符 flag 0 恢复标记 else 出错处理 print print1 printf c 出错 n ch 输出出错终结符 exit 1 else 非终结符处理 for j 0 j 4 j if x v2 j m j 行号 break for j 0 j cha origin 输出产生式 for j 0 j 0 j 产生式逆序入栈 A top cha array j if A top 为空则不进栈 top t 1 else if A top A top else if A top A top if t 0 printf t pop push n else printf t pop t n else 出错处理 print print1 printf c 出错 n x 输出出错非终结符 exit 1 while finish 0 return 0 五 实验结果 对下列文法 用 LL 1 分析法对任意输入的符号串进行分析 1 E TG 2 G TG TG 3 G 4 T FS 5 S FS FS 6 S 7 F E 8 F i 六 实验体会 设计特点 用结构体和二维数组建立表 利用栈的思想一步步化简输入的字符串 其 中利用 ll 1 文法的思想 不过在一些其他的输入字符串中可能存在一些误差 这也是程序 的不足之处 并且对于其他的输入文法 也需要大幅度的修改求出其 FIRST FOLLOW 集 通过对语法分析程序的设计和编写 使自己获得了很大的收获 并且使自己对语法分 析程序的功能有了更进一步认识 虽然在程序的设计和编写过程中出现了一些错误 但是 经过同学的帮助和指导 顺利的将程序中存在的错误顺利解决 从而顺利完成了本程序的 设计和编程 实验三实验三 LR 1 分析法分析法 1 实验目的 构造 LR 1 分析程序 利用它进行语法分析 判断给出的符号串是否为该文 法识别的句子 了解 LR K 分析方法是严格的从左向右扫描 和自底向上的 语法分析方法 2 实验内容 对下列文法 用 LR 1 分析法对任意输入的符号串进行分析 1 E E T 2 E T 3 T T F 4 T F 5 F E 6 F i 3 LR 1 分析法实验设计思想及算法 1 总控程序 也可以称为驱动程序 对所有的 LR 分析器总控程序都是相同的 2 分析表或分析函数 不同的文法分析表将不同 同一个文法采用的 LR 分析器 不同时 分析表将不同 分析表又可以分为动作表 ACTION 和状态转换 GOTO 表两个部分 它们都可用二维数组表示 3 分析栈 包括文法符号栈和相应的状态栈 它们均是先进后出栈 分析器的动作就是由栈顶状态和当前输入符号所决定 LR 分析器由三个部分组成 其中 SP 为栈指针 S i 为状态栈 X i 为文法符号栈 状态转换表用 GOTO i X j 表示 规定当栈顶状态为 i 遇到当前文法符号为 X 时应 转向状态 j X 为终结符或非终结符 ACTION i a 规定了栈顶状态为 i 时遇到输入符号 a 应执行 动作有四种 可能 1 移进 action i a Sj 状态 j 移入到状态栈 把 a 移入到文法符号栈 其中 i j 表 示状态号 2 归约 action i a rk 当在栈顶形成句柄时 则归约为相应的非终结符 A 即文 法中有 A B 的产生式 若 B 的长度为 R 即 B R 则从状态栈和文法符号栈中 自顶向下去掉 R 个符号 即栈指针 SP 减去 R 并把 A 移入文法符号栈内 j GOTO i A 移进状态栈 其中 i 为修改指针后的栈顶状态 3 接受 acc 当归约到文法符号栈中只剩文法的开始符号 S 时 并且输入符号串已结束即 当前输入符是 则为分析成功 4 报错 当遇到状态栈顶为某一状态下出现不该遇到的文法符号时 则报错 说明输 入端不是该文法能接受的符号串 const int MaxLen 20 初始化栈的长度 const int Length 20 初始化数组长度 char ch Y 全局变量 ch 用于读当前字符 Y 用于获取栈顶元素 char strToken Length 存储规约表达式 bool flag true 循环条件 int point 0 step 1 步骤 指针 class stack 栈的构造及初始化 4 实验代码 include using namespace std const int MaxLen 20 初始化栈的长度 const int Length 20 初始化数组长度 char ch Y 全局变量 ch 用于读当前字符 Y 用于获取栈顶元素 char strToken Length 存储规约表达式 bool flag true 循环条件 int point 0 step 1 步骤 指针 class stack 栈的构造及初始化 public stack 初始化 bool empty const 是否为空 bool full const 是否已满 bool get top char 取栈顶元素 bool push const char c 入栈 bool pop void out 输出栈中元素 void out1 stack 析构 v private int count 栈长度 char data MaxLen 栈中元素 stack l r l 代表符号栈 r 代表状态栈 stack stack count 0 bool stack empty const if count 0 return true return false bool stack full const if count MaxLen return true return false bool stack get top char else c data count 1 return true bool stack push const char c if full return false data count c return true bool stack pop if empty return false count return true void stack out for int i 0 i count i cout data i cout t void stack out1 for int i 0 i count i cout int data i cout t void print int i char c 剩余输入串的输出 for int j i j Length j cout c j cout t void Goto int i char c 状态转换函数 对应于表中 GOTO if i 0 if c E r push 1 cout GOTO 0 E 1 入栈 endl else if c T r push 2 cout GOTO 0 T 2 入栈 endl else if c F r push 3 cout GOTO 0 F 3 入栈 endl else flag false else if i 4 if c E r push 8 cout GOTO 4 E 8 入栈 endl else if c T r push 2 cout GOTO 4 T 2 入栈 endl else if c F r push 3 cout GOTO 4 F 3 入栈 endl else flag false else if i 6 if c T r push 9 cout GOTO 6 T 9 入栈 endl else if c F r push 3 cout GOTO 6 F 3 入栈 endl else flag false else if i 7 if c F r push 10 cout GOTO 7 F 10 入栈 endl else flag false else flag false void Action0 状态 0 时 if ch i 下一个操作符为 i 移进 cout step t r out1 l out print point 1 strToken cout ACTION 0 i S5 状态 5 入栈 endl r push 5 l push ch ch strToken point else if ch 下一个操作符为 移进 cout step t r out1 l out print point 1 strToken cout ACTION 0 S4 状态 4 入栈 endl r push 4 l push ch ch strToken point else flag false void Action1 状态 1 if ch 下一个操作符为 i 移进 cout step t r out1 l out print point 1 strToken cout ACTION 1 S6 状态 6 入栈 endl r push 6 l push ch ch strToken point else if ch 分析成功 flag false cout step t r out1 l out print point 1 strToken cout Acc 分析成功 endl else flag false void Action2 状态 2 if ch 下一个操作符为 移进 cout step t r out1 l out print point 1 strToken cout ACTION 2 S7 状态 7 入栈 endl r push 7 l push ch ch strToken point else if ch ch ch 下一个操作符为 规约 cout step t r out1 l out l pop l push E print point 1 strToken cout r2 E T 归约 r pop r get top Y Goto int Y E else flag false void Action3 状态 3 if ch ch ch ch 下一个操作符为 规 约 cout step t r out1 l out l pop l push T print point 1 strToken cout r4 T F 归约 r pop r get top Y Goto int Y T else flag false void Action4 6 7 int x 状态 4 6 7 if ch i 下一个操作符为 i 移进 cout step t r out1 l out print point 1 strToken cout ACTION cout x i S5 状态 5 入栈 endl r push 5 l push ch ch strToken point else if ch 下一个操作符为 移进 cout step t r out1 l out print point 1 strToken cout ACTION cout x S4 状态 4 入栈 endl r push 4 l push ch ch strToken point else flag false void Action5 状态 5 if ch ch ch ch 下一个操作符为 规约 cout step t r out1 l out l pop l push F print point 1 strToken cout r6 F i 归约 r pop r get top Y Goto int Y F else flag false void Action8 状态 8 if ch 下一个操作符为 移进 cout step t r out1 l out print point 1 strToken cout ACTION 8 S6 状态 6 入栈 endl r push 6 l push ch ch strToken point else if ch 下一个操作符为 移进 cout step t r out1 l out print point 1 strToken cout ACTION 8 S11 状态 11 入栈 endl r push 11 l push ch ch strToken point else flag false void Action9 状态 9 if ch 下一个操作符为 移进 cout step t r out1 l out print point 1 strToken cout ACTION 9 S7 状态 7 入栈 endl r push 7 l push ch ch strToken point else if ch ch ch 下一个操作符为 规约 cout step t r out1 l out l pop l pop l pop l pu