内容发布更新时间 : 2024/5/10 12:26:08星期一 下面是文章的全部内容请认真阅读。

电子科技大学 计算机 学院

标 准 实 验 报 告

（实验）课程名称 形式语言与自动机

电子科技大学教务处制表

电 子 科 技 大 学

实 验 报 告

学生姓名： 学 号： 指导教师： 实验地点：科A502 实验时间：2014年10月19日 一、实验室名称：计算机学院软件实验室 二、实验项目名称：文法产生语言 三、实验学时：6学时 四、实验原理：

1. 文法的存储

使用两种方式存储文法：程序方式与文件方式。

程序方式是指文法的四元组均固化到程序内，即一个程序只对应于一个文法。

文件方式是指将文法的四元组使用纯文本方式进行存储，并定义好其格式。所设计的程序可处理任意的文法。

2. 文法的表示

使用面向对象程序设计语言可描述除文法的四元式，如：采用字符数组表示其字母表和变量表，字符表示开始符号，字符串数组表示产生式组。注意产生式符号（即箭头）在ASCII字符集中没有，可采用“→”来代替。

人工经常使用的，通过产生式组获得其它三元式的方式不可取，因为需要约定哪些是字母、哪些是变量，工作量很大，反而使其表示更复杂。

3. 句子的产生

根据给定的长度产生不大于该长度的所有串。

两种文法存储方式均需要注意不同产生式可能有相同的左部，如S -> a 与 S

-> aS。要生成所有句子则不同的产生式均需要使用，因此需要一个数组（或队列、栈）来存储当前产生的句型。

五、实验目的

1. 掌握文法的表示方法； 2. 理解文法产生语言的过程； 3. 理解有穷文法可以产生无穷语言。

六、实验内容

1. 使用两种方式存储文法。

2. 使用所表示文法产生所有长度不大于N的串。

七、实验器材（设备、元器件）：

PC微机一台 八、实验步骤

给定文法G1: S -> a, S -> aS与G2: S -> ab, S -> aSb（可替换为其它稍复杂的文法）。进行如下设计：

1. 设计程序表示的文法G1与G2及其推导句子的方式，并与手工运行结果进行对比；

2. 设计文法的存储格式。用4行文本表示四元式； 3. 将文法从文件读入内存；

4. 对于给定的字符串长度上限，获得所有的句子；

5. 进行文法文件的合法性判定（如产生式中出现了既非字母，又非变量的符号）。

九、实验数据及结果分析

1. N = 5时，文法G1能产生句子a, aa, aaa, aaaa, aaaaa。实验结果如下图：

2. N = 7时，文法G2能产生句子ab, aabb, aaabbb。实验结果如下图：

3. 如果不设置上限N，则将产生无穷个句子。

十、实验结论

1. 文法需要用四元式来表示； 2. 文法的存储方式不影响文法本身。

十一、总结及心得体会

通过本实验的练习，熟悉了文法的构造方法，对文法的作用有进一步理解；对抽象模型的实现方式有了整体的了解，进一步提高了程序设计技术水平。

十二、对本实验过程及方法、手段的改进建议

本实验只需构建一个文本文件来储存文法，可通过修改文本文件来实现G1，G2，以及任意DFA的转换。

报告评分：

指导教师签字：

电 子 科 技 大 学

实 验 报 告

学生姓名： 学 号： 指导教师：

实验地点：科A502 实验时间：2014年10月26日 一、实验室名称：计算机学院软件实验室 二、实验项目名称：DFA对句子的识别 三、实验学时：3学时 四、实验原理

DFA对句子的线性识别。

五、实验目的

1. 加深对DFA原理的理解。 2. 学习使用Java进行算法的实现。 3. 掌握一定的图形编程。

六、实验内容

理解DFA的工作原理，进行如下几个方面的设计与实现：

1设计固定DFA。即将DFA使用if-then-else，以及switch-case和for循环的方式表示。一个函数只能表示一个DFA，而整个的程序只围绕该DFA进行。 2 设计文件形式存储DFA。设计文件格式；进行DFA的动态生成；使用一组字符串对所生成DFA的有效性和正确性进行验证。 3 图形化的显示。使用Java的图形模块进行结果的显示。

七、实验器材（设备、元器件）

PC微机一台