【实验报告】实验一-编写词法分析程序

1 编译原理实验报告 实验名称 编写词法分析程序 实验类型 设计型实验 指导教师 专业班级 姓 名 学 号 实验地点 实验成绩 日期 2017 年 4 月 15 日 2 实验一 编写语法分析程序 一 实验目的 1 通过设计 调试词法分析程序 掌握词法分析程序的设计工具 即有穷自动机 进一步理解自 动机理论 2 掌握正则文法和正则表达式转换成有穷自动机的方法及有穷自动机的实现方法 3 会确定词法分析程序的输出形式及标识符与关键字的区分方法 4 加深对课堂教学的理解 提高词法分析方法的实践能力 掌握使用实验环境的技能技巧以及程 序的调试方法 二 实验设计 1 写出 TEST 语言每条词法规则对应的正则文法或者正则表达式 1 标识符 字母打头 后接任意字母或数字 正则表达式 a b z A B Z 0 1 9 a b z A B Z 2 保留字 标符的子集 包括 if else for while do int write read 正则表达式 if else for while do int write read 3 无符号整数 由数字组成 但最高位不能为 0 允许一位的 0 正则表达式 1 9 0 1 9 0 4 分界符 正则表达式 5 运算符 正则表达式 6 注释符 正则表达式 没有连续的 的任意字符串 2 对每个文法或者正则表达式分别构造 NFA 1 标识符 a b z A B Z 0 1 9 a b z A B Z AA1A2 a b z A B Z 0 1 9 a b z A B Z A3 3 2 无符号整数 1 2 9 0 1 9 0 BB1 B2 B3 1 2 9 0 1 9 0 3 分界符 CC1 4 运算符 D D2 D3 D1 5 注释符 没有连续的 的任意字符串 EE6E1E2 E3 E4 非 E5 非 非 3 将 NFA 合并 确定化 化简得到最终的 DFA NFA 4 A AA1A2 a b z A B Z 0 1 9 a b z A B Z A3 BB1 B2 B3 1 2 9 0 1 9 0 CC1 D D2 D3 D1 E E6E2 E3 E4 非 E5 非 非 E1 DFA 5 A a b z A B Z 0 1 9 a b z A B Z 0 1 9 E3 E1 非 E2 非 非 E 1 2 9 A B B1 0 C D D1 D2 三 实验过程 1 完成整个实验的先后步骤 a 根据 TEST 语言的词法规则 分别写出每条规则的正则文法或者正则表达式 b 将每一个正则文法或者正则表达式转换为 NFA c 将多个 NFA 合并后进行确定化并化简 d 根据化简后的 DFA 画出流程图 e 参阅教材 PP 69 71 的 TEST 语言语法规则 确定单词分类 单词输出方案 f 编写词法分析程序 g 对下面的 TEST 语言源程序进行词法分析 将合法单词存入 lex txt 并报告词法错误及其位 置 注 不能修改源程序 6 This a test program int abc int 123 int A int i int n int b c int 2a int a2 read n n 012345 for i 1 i n i i 1 abc abc i if i n n n i if n b b c The loop ended write abc 2 实验调试记录 问题表现 分析原因 解决方案 解决结果 a 问题表现 1 不能处理除号 2 不能处理不完整的注释符 3 对于 0123 这类字符串的处理不正确 我之前处理为直接报错说一位以上的数字首位 不能为 0 b 分析原因 问题 1 2 的原因都是在 符号处理时出现的问题导致的 程序中出现 bug 使得一遇到 就会进入死循环 问题 3 不应该直接报错说一位以上的数字首位不能为 0 遇到 0 应该直接输出 0 这个单 词 再接着读数字 c 解决方案 d 对于问题 1 2 重新梳理逻辑 一步一步对照流程图和 DFA 来调试修改代码 对于问题 3 遇到 0 应该直接输出 0 这个单词 再接着读数字 e 解决结果 成功解决了程序遇到 进入死循环问题和 0123 这类字符串的处理 三 实验结果 7 列出实验结果并进行分析 含分步测试结果 lex txt 文件 存放编译的合法内容 内容 1 2 This a test program This a test program 3intint 3IDabc 3 4intint 4NUM123 4 5intint 5IDA 5 6intint 6IDi 6 7intint 7IDn 7 8intint 8IDb 8IDc 8 9intint 9NUM2 9IDa 9 10intint 8 10IDa2 10 11read read 11IDn 11 12IDn 12 12NUM0 12NUM12345 12 13forfor 13 13IDi 13 13NUM1 13 13IDi 13 13IDn 13 13IDi 13 13IDi 13 13NUM1 13 14 15IDabc 15 15IDabc 15 15IDi 15 16 9 17ifif 17 17IDi 17 17IDn 17 17IDn 17 17IDn 17 17IDi 17 18ifif 18 18IDn 18 18IDb 18 18IDb 18 18IDc 18 四 讨论与分析 1 你的编写词法分析程序满足最长匹配原则吗 如果满足请给出你的实现方案 如果不满足请给出 改进方案 答 不满足 我的处理先后顺序是 标识符或保留字 数字 分界符 运算符 除开 除或者 注释 我应该吧注释放在前面 因为一般来说注释都比其它类型符号长些 改进措施便是将注释 这一条词法规则最早处理 2 给出你的单词分类方案 并说明理由 答 根据 TEST 语言可将单词分为六类 a 标识符 字母打头 后接任意字母或数字 b 保留字 标识符的子集 包括 if else for while do int write read c 无符号整数 由数字组成 但最高位不能为 0 允许一位的 0 d 分界符 10 e 运算符 f 注释符 3 构建词法分析程序一般过程是怎样的 答 构建词法分析程序的一般过程 1 根据词法规则写出正则文法或者正则文法 2 为每一个正则表达式构造一个 NFA 然后将多个 NFA 合并为一个 NFA 3 将 NFA 转化成 DFA 并且化简最小化 DFA 4 确定单词的输出形式 5 根据化简后的 DFA 和单词输出程序构造词法分析程序 主要部分 通过实验对课程知识点的理解 回答实验指导书的实验思考提出的问题等 五 附录 关键代码 给出适当注释 可读性高 include include include include include using namespace std const int KWN 8 关键字的个数 const int MAXSIZE 400 标识符最长个数 char kword KWN 10 关键字 if else for while do int read write int line 1 行号 int errors 0 记录错误个数 ofstream fout 输出文件流 ifstream fin 输入文件流 11 ofstream lexout 存放合法单词的文件流 char type 6 30 ID 保 留 字 NUM 分 界 符 运 算 符 注 释 符 int main int TEST 函数声明 TEST if errors 0 cout 编译成功 endl else cout 编译失败 共发现 errors 个错误 a return 0 判断是否为无符号整数 12 int is Uint char ch if 0 ch 没有考虑 号 for int i 0 i 8 i if ch Operater i return 1 return 0 输入控制 int in char if n ch line if fin eof ch EOF return 1 输出控制 void out char type char buf if strcmp type ID 0 strcmp type NUM 0 lexout line type buf endl else lexout line buf buf endl cout type buf endl 编译程序主要的函数 int TEST int event 0 用于判断输入是否为文件末 char filename 300 存储文件的路径 打开文件的操作 打开编译程序存放合法单词的文件 lexout open lex txt 打开用户的文件 cout 请输入要编译的文件的路径 endl reinput in cin get filename 300 n 14 char filename 300 D Software Microsoft Visual C 6 0 Microsoft Visual Studio MyProjects 编译原理实验一 in txt fin open in txt if fin NULL cout 文件打开失败 请重新输入文件路径 endl goto reinput in cout 请输入词法分析结果文件存储路径 endl reinput out cin clear 清理输出缓冲 cin sync 清空流 cin get filename 300 n char filename 300 D Software Microsoft Visual C 6 0 Microsoft Visual Studio MyProjects 编译原理实验一 out txt fout open out txt if fout NULL cout 文件打开失败 请重新输入文件路径 endl goto reinput out 开始判断 char buf 300 char ch cin clear 清理输出缓冲 cin sync 清空流 in ch while fin eof while ch ch n ch t ch r in ch 15 判断是否为标识符或保留字 if is Char ch int t 0 while is Char ch buf t ch in ch buf t 0 判断保留字 int j 0 for j KWN while is Char ch is Uint ch buf t ch in ch buf t 0 out type 0 buf 判断是否为数字 else if is Uint ch 16 int t 0 while is Uint ch buf t ch in ch buf t 0 if t 1 out type 2 buf else if buf 0 0 int i 1 while i t out type 2 buf i else out type 2 buf 判断是否为分界符 else if is Deli ch buf 0 ch buf 1 0 out type 3 buf in ch 17 判断是否为运算符 除开 else if is Oper ch if ch ch ch buf 0 ch buf 1 0 out type 4 buf in ch else if ch buf 0 ch in ch if ch buf 1 ch buf 2 0 out type 4 buf in ch else cout error errors line line 不合法的符号 ch ch buf 0 ch in ch if ch buf 1 ch buf 2 0 18 out type 4 buf in ch else buf 1 0 out type 4 buf else if ch 判断是除还是注释 int t 0 buf t ch char ch0 in ch0 while 1 if ch0 EOF cout error errors line line 匹配错误 缺少 endl break ch ch0 buf t ch in ch0 if ch buf t 0 out type 5 buf break 19 in ch else cout error errors line line ch 未知符号 endl in ch fin close fout close lexout close return errors D Software Microsoft Visual C 6 0 Microsoft Visual Studio MyProjects 编译原理实验一 in txt D Software Microsoft Visual C 6 0 Microsoft Visual Studio MyProjects 编译原理实验一 out txt This a test program The loop ended write abc char ch1 getc fin while true if ch1 EOF printf Line d t s t 没有匹配 n line 错误 brea