用户工具

站点工具


01-基础学习:课程:编译原理:实验:实验一:dfa编程实现

1.2 DFA编程实现

实验题目

实验目的:通过本次实验,加深对DFA及其识别的语言的理解,学习对一般的DFA的表达方法与编程实现方法。
实验任务:编写一个C语言程序,模拟实现DFA识别字符串的过程。
实验内容:

  1. DFA的输入
  2. DFA的存储与读写
  3. DFA的正确性检查
  4. DFA的语言集列表显示
  5. DFA的规则字符串判定;

内容说明:

  1. DFA的输入:
    分别输入DFA的“字符集”、“状态集”、“开始状态”、“接受状态集”、“状态转换表”等内容,并保存在设定的变量中。
  2. DFA的存储与读写:
    将上述DFA的五元组保存在一个文本文件中,扩展名指定为.dfa。请自行设计DFA文件的存储格式,并说明其含义。能将保存在内存变量中的DFA写入DFA文件,也能将DFA文件读入内存中。(思考:对稀疏DFA(转换表中为空的地方较多)或用“或”表达转换的DFA(如下的测试用例三),如何改进DFA转换表的表达。)
  3. DFA的正确性检查:
    检查所有集合的元素的唯一性。
    检查“开始状态”是否唯一,并是否包含在“状态集”中。
    检查“接受状态集”是否为空,并是否包含在“状态集”中。
    检查“状态转换表”是否满足DFA的要求。
    检查“状态转换表”并非填满时的处理是否得当…
  4. DFA的语言集列表显示:
    输入待显示的字符串的最大长度N,输出以上定义的DFA的语言集中长度≤N的所有规则字符串。(提示:注意算法中while循环的次数)
  5. DFA的规则字符串判定:
    输入(或用字符集随机生成)一个字符串,模拟DFA识别字符串的过程判定该字符串是否是规则字符串(属于DFA的语言集)。

测试用例: DFA1 DFA2 DFA3

实验要求:

  • 按照《编译原理及实践》参考书第二章中描述的“while循环+双层case选择”的算法编程实现一般的DFA。
  • 要求能通过以上三个测试用例的测试。
  • 完成内容中(1)(5)部分,可得C。
  • 完成内容中(1)(2)(5)部分,可得B。
  • 完成内容中(1)(2)(4)(5)部分,可得A。
  • 完成全部内容,可得奖励。

判定算法概要:    

准备:开始状态s0, 接受状态集F, 状态转换表T(s, c), sS, c

   c = getchar();
   s = 开始状态s0;
   while ( c != EOF ) // 输入未结束则循环…
   {
     s = T(s, c);
     if (s == NULL)
         error();
     c = getchar();
   }
   if (s  接受状态集F)
       accept ();
   else
       error ();

通用DFA存储格式的建议:

(用以上的第三个测试DFA为例)

3 // 字符集中的字符个数 (以下两行也可合并成一行)
/ * o // 以空格分隔的字符集。O代表任意非/和*的字符
5 // 状态个数 (以下两行也可合并成一行)
1 2 3 4 5 // 状态编号。若约定总是用从1开始的连续数字表示,则此行可省略
1 // 开始状态的编号。若约定为1,则此行可省略
1 // 结束状态个数。若约定为1,则此行可省略
5 // 结束状态的编号
2 -1 -1 // 状态1的所有出去的转换。按字符集中的字符顺序给出。-1表示出错状态
-1 3 -1
3 4 3
5 4 3
-1 -1 -1

列语言算法概要:

(深度优先搜索,类似于M进制的数的进位问题)
   准备:开始状态s0, 接受状态集F, 状态转换表T(s, c), sS, c
   假设:中的元素个数为M个, 存储于char A[M]中;
   准备:长度N>0, 存储语言元素的字符串char L[N] (只存储其编号), 初值全为-1;

   while ( 1 )
   {
      for( i=N-1; i>=0; i-- )
         if ( L[i] >= 0 )
           break; // 找L串中的未用字符
      if ( i < N-1 ) // 有未用字符, 用上它, 串长度加1
      {  L[i+1] = 0; // 用上中的第1个字符
       用判定算法判定字符串A[ L[0] ] ~ A[ L[i+1] ]是否属于语言集中
      continue; }
      if ( i == N-1 && L[i] < M-1 ) // 无未用部分, 但最后的字符未用完
      {  L[i]++; // 用上中的下1个字符
      用判定算法判定字符串A[ L[0] ] ~ A[ L[i] ]是否属于语言集中
      continue; }
      if ( i == N-1 && L[i] == M-1 ) // 无未用部分, 且最后的字符已用完
      {  for ( ; L[i]==M-1; i-- ) // 搜索前面的字符是否已用完
            L[i] = -1; // 改已用完字符为未用字符
         if ( i>=0 ) // 找到未用完字符
         {  L[i]++; // 用上中的下1个字符
        用判定算法判定字符串A[ L[0] ] ~ A[ L[i] ]是否属于语言集中
            continue;  }
         else // 全部字符都已用完
            break; // 算法至此终止
     }
   }

   注1:可增加存储前成经过的状态序列,从而无须调用判定算法,直接使用一步状态转换即可。
   注2:深度优先搜索无法实现相同长度的字符串显示在一块。若要求如此,需用宽度优先搜索。需定义一个函数用指定字符集生成长度刚好为n的字符串,然后定义主函数,让n从0循环到N,并调用判定算法判定所有长度为n的字符串是否属于语言集即可。

提高内容:

  • 图形化的用户界面;
  • 任意DFA的状态转换图、状态转换表的图形绘制;

实验代码

01-基础学习/课程/编译原理/实验/实验一/dfa编程实现.txt · 最后更改: 2020/04/07 06:34 由 annhe