求First和Follow集【编译原理】

前言

最近开始做编译原理的课程设计,我被安排做一个First集和Follow集生成算法模拟软件。我都忘了什么是First和Follow集了,查了回资料开搞明白了First集,Follow集还挺复杂的。
我之前一直有做一个带代码高亮的编辑器的,这次逮到机会了,虽然老师要求没有那么复杂,可是自己还是想来个小挑战(实现最简单的识别文法)。于是决定用Qt去写。

老师要求题目

模拟算法的基本功能实现:

  1. 输入一个文法G;
  2. 输出由文法G构造的FIRST集合;
  3. 输出由文法G构造的FOLLOW集合;
  4. 构造预测分析表,并判断该文法是否为LL(1)文法。(选作)

环境

  • windows7 x64
  • Qt 5.3.1

大体功能简介

主界面

  1. 可以选择从文本读取文法,也可自行输入
  2. 文本读取后会跳到编辑器解析

编辑器

  1. 使用正则表达式解析文档每行字符串里符合标准的文法句子,如果匹配错误给出出错信息,以及行号,同时界面高亮错误位置
  2. 匹配成功后根据对应的终结符或非终结符高亮字符,同时整理代码格式
  3. 可以保存到文本,在退出时自动保存到之前保存的文本

First求解过程

  1. 直接收取:对形如”U->a…”的产生式(其中a是终结符),把a收入到First(U)中
  2. 反复传送:对形入”U->P…”的产生式(其中P是非终结符),应把First(P)中的全部内容传送到First(U)中(递归实现)

Follow求解过程

  1. 设S为文法的开始符号,将加入Follow(U)中
  2. 反复传送:对形如U->…P的产生式(其中P是非终结符),应把Follow(U)中的全部内容传送到Follow(P)中。

界面展示

  • 代码文件展

  • 主界面
  • 编辑器

  • First&Follow显示

源代码

开源地址:点我去vell001的Github

后语

这个代码写得不是很好,特别是Follow集求解那块,由于自己对Follow集的理解不是很深,总感觉写得有问题,不过到目前我的测试数据都是正确的。今天貌似有点发烧,就先这样了,头疼~