形式语言与自动机实验报告.pdf

电子科技大学计算机学院

标准实验报告

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

电子科技大学教务处制表

电子科技大学

实验报告

学生姓名：林怡学号：2012060020023指导教师：吴婧瑾

实验地点：科研楼A504实验时间：第七周周日下午

一、实验室名称：计算机学院软件实验室

二、实验项目名称：文法产生语言

三、实验学时：6学时

四、实验原理：

1.文法的存储

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

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

法。

文件方式是指将文法的四元组使用纯文本方式进行存储，并定义好其格式。

所设计的程序可处理任意的文法。

2.文法的表示

使用面向对象程序设计语言可描述除文法的四元式，如：采用字符数组表示

其字母表和变量表，字符表示开始符号，字符串数组表示产生式组。注意产生式

符号（即箭头）在ASCII字符集中没有，可采用“→”来代替。

人工经常使用的，通过产生式组获得其它三元式的方式不可取，因为需要约

定哪些是字母、哪些是变量，工作量很大，反而使其表示更复杂。

3.句子的产生

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

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

-aS。要生成所有句子则不同的产生式均需要使用，因此需要一个数组（或队

列、栈）来存储当前产生的句型。

五、实验目的

1.掌握文法的表示方法；

2.理解文法产生语言的过程；

3.理解有穷文法可以产生无穷语言。

六、实验内容

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

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

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

PC微机一台

八、实验步骤

给定文法G:S-a,S-aS与G:S-ab,S-aSb（可替换为其它稍复杂的

12

文法）。进行如下设计：

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

12

进行对比；

2.设计文法的存储格式。用4行文本表示四元式：第一行为开始状态S，第

二行为终极符，第三行为产生式，第四行为非终极符；

3.将文法从文件读入内存；

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

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

符号）。

九、实验数据及结果分析

1.当输入字符串长度为N=3时，输出文件result.txt中共有三行字符串，分

别为ab,aabb,aaabbb；

2.当输入字符串长度为N=5时，输出文件result.txt中共有五行字符串，分

别为ab,aabb,aaabbb,aaaabbbb,aaaaabbbbb；

S-ab,S-aSb，S-Aa,A-a

若给定字符串长度N=5，输出文本中将只有形如aaabbb的结果输出，而不会有

由产生式S-Aa以及A-a所推导出的句子。所以可以把实验的要求改为给定文

法能推导出的句子的长度，而不是输出文本中所有字符串的长度。

报告评分：

指导教师签字：