BYR Achieve · 镜像论坛

【问题】北邮OJ110 first集怎么求，感觉好麻烦，自己感觉有递归

2017/3/15镜像同步1 回复

题目描述对于文法，给出求first集的算法，让大家求first集。输入中大写字母表示非终结符，小写字母表示终结符，#表示空也是终结符。 First集求解算法如下：为了求每个符号的first集，连续使用以下规则，直到每个符号的first集不再增大为止。 1.对于终结符，它的first集就是它自己。 2.对于非终结符，如果有产生式 X -> a... ，把a加入first（X）中，如果X-># ,即X可以推出空，那么把空加入first（X）中。 3.对于X->Y... 这样的产生式，且X,Y都是非终结符，把first（Y）中的所有非空的元素加入到first（X）中。对于X->Y1Y2...Yk产生式,X,Y1,Y2...Yk都是非终结符，对于某个i（i<=k），如果first（Y1），first（Y2），...first（Yi-1）都含有空，那么将first（Yi）中的所有非空元素加入到first（X）中。若所有的first（Yi）（i=1，2，...k）中都有空，那么将空加入first（X）中。 Input 多组数据，以EOF结束。第一行一个数字n，表示有n个文法式，（0<n<=10）。下面n行，每行第一个是一个大写字母，表示产生式的左边，然后一个字符串，由大写字母（非终结符），小写字母（终结符）和#（空）组成。输入格式多组数据，以EOF结束。第一行一个数字n，表示有n个文法式，（0<n<=10）。下面n行，每行第一个是一个大写字母，表示产生式的左边，然后一个字符串，由大写字母（非终结符），小写字母（终结符）和#（空）组成。输出格式按照字典序输出每个非终结符的first（集）。每行表示一个first集。第一个字母输出表示非终结符(按字母序排列)，然后按字母顺序输出first集，如果包含空的话，最后输出#。一行中每两个字符间有一个空格。

订阅后，新回复会通过你的通知中心匿名送达。