word
电子科技大学 计算机 学院
标 准 实 验 报 告
〔实验〕课程名称 形式语言与自动机
电子科技大学教务处制表
1 / 13
word 电 子 科 技 大 学
实 验 报 告
学生某某：林怡 学号： 指导教师：吴婧瑾
实验地点： 科研楼A504 实验时间：第七周周日下午 一、实验室名称：计算机学院软件实验室 二、实验项目名称：文法产生语言 三、实验学时：6学时 四、实验原理：
1. 文法的存储
使用两种方式存储文法：程序方式与文件方式。
程序方式是指文法的四元组均固化到程序内，即一个程序只对应于一个文法。
文件方式是指将文法的四元组使用纯文本方式进展存储，并定义好其格式。所设计的程序可处理任意的文法。
2. 文法的表示
使用面向对象程序设计语言可描述除文法的四元式，如：采用字符数组表示其字母表和变量表，字符表示开始符号，字符串数组表示产生式组。注意产生式符号〔即箭头〕在ASCII字符集中没有，可采用“→〞来代替。
人工经常使用的，通过产生式组获得其它三元式的方式不可取，因为需要约定哪些是字母、哪些是变量，工作量很大，反而使其表示更复杂。
3. 句子的产生
根据给定的长度产生不大于该长度的所有串。
两种文法存储方式均需要注意不同产生式可能有一样的左部，如S -> a 与
2 / 13
word S -> aS。要生成所有句子如此不同的产生式均需要使用，因此需要一个数组〔或队列、栈〕来存储当前产生的句型。
五、实验目的
1. 掌握文法的表示方法； 2. 理解文法产生语言的过程； 3. 理解有穷文法可以产生无穷语言。
六、实验内容
1. 使用两种方式存储文法。
2. 使用所表示文法产生所有长度不大于N的串。
七、实验器材〔设备、元器件〕：
PC微机一台 八、实验步骤
给定文法G1: S -> a, S -> aS与G2: S -> ab, S -> aSb〔可替换为其它稍复杂的文法〕。进展如下设计：
1. 设计程序表示的文法G1与G2与其推导句子的方式，并与手工运行结果进展比照；
2. 设计文法的存储格式。用4行文本表示四元式：第一行为开始状态S，第二行为终极符，第三行为产生式，第四行为非终极符；
3. 将文法从文件读入内存；
4. 对于给定的字符串长度上限，获得所有的句子；
5. 进展文法文件的合法性判定〔如产生式中出现了既非字母，又非变量的符号〕。
九、实验数据与结果分析
1. 当输入字符串长度为N=3时，输出文件result.txt中共有三行字符串，分
别为ab, aabb, aaabbb；
2. 当输入字符串长度为N=5时，输出文件result.txt中共有五行字符串，分
3 / 13
相关推荐：
loading