《形式语言与自动机》课程实验¶
版权声明
本项目为 2025-2026 年秋季学期起清华大学计算机系开设的《形式语言与自动机》课程的实验框架。 所有内容（包括文档、代码等）未经作者授权，禁止用作任何其他用途，包括且不限于在其他课程或者其他学校中使用。
如需使用授权，可通过 zhangyq24 at mails dot tsinghua dot edu dot cn 联系作者。作者保留一切追究侵权责任的权利。
前言¶
为了使同学们进一步掌握形式语言与自动机课程中常用的一系列算法，深入理解形式语言与自动机相关概念和算法，培养实践能力，本课程设计了一系列的实验。
本文档是 2025 年清华大学计算机系《形式语言与自动机》的实验说明与指导。实验文档按照课程教学的顺序组织，各实验内容相对独立，首先介绍实验所需要涉及到的知识点，然后再交给同学们实现课程中学习的经典算法的任务。
欢迎同学们完成这些题目，并在评论区反馈体验、意见或建议。
实验概述¶
本实验的一个整体目标是实现一个简单的正则表达式引擎，能够测试正规表达式是否与字符串相匹配。
本实验源代码可以在 https://git.tsinghua.edu.cn/fla/regex_lab.git 下载，当前共包含 5 个小实验，需选择其中 4 个完成并在期末于网络学堂上提交代码，每个小实验均可独立完成和评测，按课程教学的顺序列出如下：
实验 1：最左推导，基于正规表达式转化成的波兰式，进行最左推导，得到语法分析树
实验 2：子集构造法，构造与给定的 ε-NFA 等价的 DFA
实验 3：DFA 的最小化，根据可达性和填表算法最小化 DFA
实验 4：语法分析树转 ε-NFA，根据正规表达式的语法分析树构造等价的 ε-NFA
实验 5：CYK 算法，给定句子生成语法分析树
实验准备¶
环境配置¶
本实验支持以下硬件平台及操作系统：
- x86_64 Linux
- x86_64 Windows
- aarch64 macOS
- aarch64 Linux
本实验依赖于g++-14、cmake、make、git，请在开始实验前准备好这些工具，本实验不支持 clang 和 msvc 系列工具链。
例如，在 Debian 系列发行版（Debian、Ubuntu、Kali、Mint 等）中，你可以使用以下命令安装依赖：
sudo apt update
sudo apt install g++-14 cmake make git
在装有 brew 包管理器的 macOS 上，可以使用如下命令：
brew update
brew install gcc@14 cmake make git
在 Windows 上，你需要安装 g++ 大版本号为14的 MinGW。使用 g++ --version确认 g++ 的版本，如果 g++ 的大版本号为14但找不到 g++-14，可以在 g++ 所在目录下将 g++ 复制一份并改名为 g++-14。
你也可以使用一个已经配置好的 Docker 环境，下载链接如下
下载完成后使用命令docker load -i fla.tar加载 Docker 镜像fla:25到你的计算机，然后运行docker run -ti --network=host fla:25 /bin/bash即可打开一个配置好的新环境。
编译测试¶
建议使用 Tsinghua Gitlab 完成本实验，可以首先使用一个已经部署的服务，创建自己的实验仓库，shell 命令如下（请登录https://git.tsinghua.edu.cn，将 abcdef12 替换为你的 GitLab 用户名，即 abcdef12@mails.tsinghua.edu.cn 的邮箱前缀）：
curl https://zhangyingqi.site/glrc/abcdef12
首次创建仓库成功会返回Created!，然后你可以将regex_lab_abcdef12克隆到本地，以完成各实验。
git clone git@git.tsinghua.edu.cn:fla/fla25/regex_lab_abcdef12.git
cd regex_lab_abcdef12
进入regex_lab_abcdef12目录后，使用如下命令编译项目：
cmake -G "Unix Makefiles" -S . -B build && cd build && make
若环境配置无误，应当能够成功进行编译，输出类似于：
-- The C compiler identification is GNU 14.2.0
-- The CXX compiler identification is GNU 14.2.0
-- Detecting C compiler ABI info
-- Detecting C compiler ABI info - done
-- Check for working C compiler: /usr/bin/cc - skipped
-- Detecting C compile features
-- Detecting C compile features - done
-- Detecting CXX compiler ABI info
-- Detecting CXX compiler ABI info - done
-- Check for working CXX compiler: /usr/bin/c++ - skipped
-- Detecting CXX compile features
-- Detecting CXX compile features - done
-- Configuring done (0.3s)
-- Generating done (0.0s)
-- Build files have been written to: /root/regex_lab_abcdef12/build
[ 16%] Building CXX object CMakeFiles/regex_lab_test.dir/tests/test.cpp.o
[ 33%] Linking CXX executable regex_lab_test
[ 33%] Built target regex_lab_test
[ 50%] Building CXX object CMakeFiles/regex_lab_std_test.dir/tests/std_test_all.cpp.o
[ 66%] Linking CXX executable regex_lab_std_test
[ 66%] Built target regex_lab_std_test
[ 83%] Building CXX object CMakeFiles/CYK_algorithm.dir/tests/CYK_test.cpp.o
[100%] Linking CXX executable CYK_algorithm
[100%] Built target CYK_algorithm
编译完成后，应在build目录下看到生成的可执行文件regex_lab_std_test和CYK_algorithm。
实验更新¶
原始框架代码有更新时，可以使用如下命令合并这些更新：
git remote add upstream git@git.tsinghua.edu.cn:fla/regex_lab.git
git fetch upstream
git merge upstream/main