编译原理实验 求first集和follow集1

编译原理实验求first集和follow集 本资源摘要信息将为您详细介绍编译原理实验中求first集和follow集的知识点。 实验目标 本实验的目标是编程实现first集和follow集的计算，以便更好地理解和掌握编译原理中的基本概念。 输入格式 输入格式为每行输入一个产生式，左部右部中间的→用空格代替。非终结符等价于大写字母/^表示空不包含有|的产生式（即含有|的产生式已分成多个产生式）#表示输入右端的结束标记输入到文件结束，或用0 0结尾。 First 集 First集是指给定非终结符或终结符的可能的开头符号集合。计算First集需要遵循以下规则： 1. 若X∈VT，则FIRST(X)＝{X}。即终结符的First集就是它本身。 2. 若X∈VN，且有产生式X→a…，a∈VT，则a∈FIRST(X)。即非终结符X能推导出以终结符a开头的串，那么这个终结符a属于X的First集。 3. X→ε,则ε∈FIRST(X)。即非终结符X能推导出空符号串ε，那么空符号串ε也属于X的First集。 4. X→Y…是一个产生式且Y∈VN，则把FIRST(Y)中的所有非空符号串ε元素都加入到FIRST(X)中。 5. 若X∈VN；Y1，Y2，…，Yi∈VN，且有产生式X→Y1 Y2 … Yn；当Y1 Y2 … Yn-1都能推导出ε时，则FIRST(Y1)、FIRST(Y2)、…、FIRST(Yn-1)的所有非空元素和FIRST(Yn)包含在FIRST(X)中。 Follow 集 Follow集是指给定非终结符的可能的后续符号集合。计算Follow集需要遵循以下规则： 1. 设S为文法中开始符号，把{#}加入FOLLOW(S)中。 2. 若A→αBβ是一个产生式，则把FIRST(β)的非空元素加入FOLLOW(B)中。如果β能够推导出ε则把FOLLOW(A)也加入FOLLOW(B)中。 可能用到的数据结构 在计算First集和Follow集时，可能用到的数据结构包括： * map：用于存储First集和Follow集的元素 * set：用于存储非终结符和终结符的集合 * vector：用于存储产生式的右部符号 * multimap：用于存储非终结符和其对应的First集和Follow集 可能用到的子功能模块 在计算First集和Follow集时，可能用到的子功能模块包括： * 判断大小写：判断终结符与非终结符 * 判断非终结符能否推导出空 * 不考虑左递归的情况（如有左递归出现，可简单的报错处理） * 求follow集时，右侧最后的非终结符（直接或间接）的follow需要加入该条产生式左侧非终结符的follow集中