fork download
copy 
  1. #include<stdio.h>
  2. #include<ctype.h>
  3. #include<string.h>
  4. void followfirst(char, int, int);
  5. void follow(char c);
  6. void findfirst(char, int, int);
  7. int count, n = 0;
  8. char calc_first[10][100];
  9. char calc_follow[10][100];
  10. int m = 0;
  11. char production[10][10];
  12. char f[10], first[10];
  13. int k;
  14. char ck;
  15. int e;
  16.  
  17. int main(int argc, char **argv)
  18. {
  19. 	int jm = 0;
  20. 	int km = 0;
  21. 	int i, choice;
  22. 	char c, ch;
  23. 	count = 8;
  24.  
  25. 	// The Input grammar
  26. 	strcpy(production[0], "E=TR");
  27. 	strcpy(production[1], "R=+TR");
  28. 	strcpy(production[2], "R=#");
  29. 	strcpy(production[3], "T=FY");
  30. 	strcpy(production[4], "Y=*FY");
  31. 	strcpy(production[5], "Y=#");
  32. 	strcpy(production[6], "F=(E)");
  33. 	strcpy(production[7], "F=i");
  34.  
  35. 	int kay;
  36. 	char done[count];
  37. 	int ptr = -1;
  38.  
  39. 	// Initializing the calc_first array
  40. 	for(k = 0; k < count; k++) {
  41. 		for(kay = 0; kay < 100; kay++) {
  42. 			calc_first[k][kay] = '!';
  43. 		}
  44. 	}
  45. 	int point1 = 0, point2, xxx;
  46.  
  47. 	for(k = 0; k < count; k++)
  48. 	{
  49. 		c = production[k][0];
  50. 		point2 = 0;
  51. 		xxx = 0;
  52.  
  53. 		// Checking if First of c has
  54. 		// already been calculated
  55. 		for(kay = 0; kay <= ptr; kay++)
  56. 			if(c == done[kay])
  57. 				xxx = 1;
  58.  
  59. 		if (xxx == 1)
  60. 			continue;
  61.  
  62. 		// Function call
  63. 		findfirst(c, 0, 0);
  64. 		ptr += 1;
  65.  
  66. 		// Adding c to the calculated list
  67. 		done[ptr] = c;
  68. 		printf("\n First(%c) = { ", c);
  69. 		calc_first[point1][point2++] = c;
  70.  
  71. 		// Printing the First Sets of the grammar
  72. 		for(i = 0 + jm; i < n; i++) {
  73. 			int lark = 0, chk = 0;
  74.  
  75. 			for(lark = 0; lark < point2; lark++) {
  76.  
  77. 				if (first[i] == calc_first[point1][lark])
  78. 				{
  79. 					chk = 1;
  80. 					break;
  81. 				}
  82. 			}
  83. 			if(chk == 0)
  84. 			{
  85. 				printf("%c, ", first[i]);
  86. 				calc_first[point1][point2++] = first[i];
  87. 			}
  88. 		}
  89. 		printf("}\n");
  90. 		jm = n;
  91. 		point1++;
  92. 	}
  93. 	printf("\n");
  94. 	printf("-----------------------------------------------\n\n");
  95. 	char donee[count];
  96. 	ptr = -1;
  97.  
  98. 	// Initializing the calc_follow array
  99. 	for(k = 0; k < count; k++) {
  100. 		for(kay = 0; kay < 100; kay++) {
  101. 			calc_follow[k][kay] = '!';
  102. 		}
  103. 	}
  104. 	point1 = 0;
  105. 	int land = 0;
  106. 	for(e = 0; e < count; e++)
  107. 	{
  108. 		ck = production[e][0];
  109. 		point2 = 0;
  110. 		xxx = 0;
  111.  
  112. 		// Checking if Follow of ck
  113. 		// has already been calculated
  114. 		for(kay = 0; kay <= ptr; kay++)
  115. 			if(ck == donee[kay])
  116. 				xxx = 1;
  117.  
  118. 		if (xxx == 1)
  119. 			continue;
  120. 		land += 1;
  121.  
  122. 		// Function call
  123. 		follow(ck);
  124. 		ptr += 1;
  125.  
  126. 		// Adding ck to the calculated list
  127. 		donee[ptr] = ck;
  128. 		printf(" Follow(%c) = { ", ck);
  129. 		calc_follow[point1][point2++] = ck;
  130.  
  131. 		// Printing the Follow Sets of the grammar
  132. 		for(i = 0 + km; i < m; i++) {
  133. 			int lark = 0, chk = 0;
  134. 			for(lark = 0; lark < point2; lark++)
  135. 			{
  136. 				if (f[i] == calc_follow[point1][lark])
  137. 				{
  138. 					chk = 1;
  139. 					break;
  140. 				}
  141. 			}
  142. 			if(chk == 0)
  143. 			{
  144. 				printf("%c, ", f[i]);
  145. 				calc_follow[point1][point2++] = f[i];
  146. 			}
  147. 		}
  148. 		printf(" }\n\n");
  149. 		km = m;
  150. 		point1++;
  151. 	}
  152. }
  153.  
  154. void follow(char c)
  155. {
  156. 	int i, j;
  157.  
  158. 	// Adding "$" to the follow
  159. 	// set of the start symbol
  160. 	if(production[0][0] == c) {
  161. 		f[m++] = '$';
  162. 	}
  163. 	for(i = 0; i < 10; i++)
  164. 	{
  165. 		for(j = 2;j < 10; j++)
  166. 		{
  167. 			if(production[i][j] == c)
  168. 			{
  169. 				if(production[i][j+1] != '\0')
  170. 				{
  171. 					// Calculate the first of the next
  172. 					// Non-Terminal in the production
  173. 					followfirst(production[i][j+1], i, (j+2));
  174. 				}
  175.  
  176. 				if(production[i][j+1]=='\0' && c!=production[i][0])
  177. 				{
  178. 					// Calculate the follow of the Non-Terminal
  179. 					// in the L.H.S. of the production
  180. 					follow(production[i][0]);
  181. 				}
  182. 			}
  183. 		}
  184. 	}
  185. }
  186.  
  187. void findfirst(char c, int q1, int q2)
  188. {
  189. 	int j;
  190.  
  191. 	// The case where we
  192. 	// encounter a Terminal
  193. 	if(!(isupper(c))) {
  194. 		first[n++] = c;
  195. 	}
  196. 	for(j = 0; j < count; j++)
  197. 	{
  198. 		if(production[j][0] == c)
  199. 		{
  200. 			if(production[j][2] == '#')
  201. 			{
  202. 				if(production[q1][q2] == '\0')
  203. 					first[n++] = '#';
  204. 				else if(production[q1][q2] != '\0'
  205. 						&& (q1 != 0 || q2 != 0))
  206. 				{
  207. 					// Recursion to calculate First of New
  208. 					// Non-Terminal we encounter after epsilon
  209. 					findfirst(production[q1][q2], q1, (q2+1));
  210. 				}
  211. 				else
  212. 					first[n++] = '#';
  213. 			}
  214. 			else if(!isupper(production[j][2]))
  215. 			{
  216. 				first[n++] = production[j][2];
  217. 			}
  218. 			else
  219. 			{
  220. 				// Recursion to calculate First of
  221. 				// New Non-Terminal we encounter
  222. 				// at the beginning
  223. 				findfirst(production[j][2], j, 3);
  224. 			}
  225. 		}
  226. 	}
  227. }
  228.  
  229. void followfirst(char c, int c1, int c2)
  230. {
  231. 	int k;
  232.  
  233. 	// The case where we encounter
  234. 	// a Terminal
  235. 	if(!(isupper(c)))
  236. 		f[m++] = c;
  237. 	else
  238. 	{
  239. 		int i = 0, j = 1;
  240. 		for(i = 0; i < count; i++)
  241. 		{
  242. 			if(calc_first[i][0] == c)
  243. 				break;
  244. 		}
  245.  
  246. 		//Including the First set of the
  247. 		// Non-Terminal in the Follow of
  248. 		// the original query
  249. 		while(calc_first[i][j] != '!')
  250. 		{
  251. 			if(calc_first[i][j] != '#')
  252. 			{
  253. 				f[m++] = calc_first[i][j];
  254. 			}
  255. 			else
  256. 			{
  257. 				if(production[c1][c2] == '\0')
  258. 				{
  259. 					// Case where we reach the
  260. 					// end of a production
  261. 					follow(production[c1][0]);
  262. 				}
  263. 				else
  264. 				{
  265. 					// Recursion to the next symbol
  266. 					// in case we encounter a "#"
  267. 					followfirst(production[c1][c2], c1, c2+1);
  268. 				}
  269. 			}
  270. 			j++;
  271. 		}
  272. 	}
  273. }
  274.  
Success #stdin #stdout 0s 5536KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
 First(E) = { (, i, }

 First(R) = { +, #, }

 First(T) = { (, i, }

 First(Y) = { *, #, }

 First(F) = { (, i, }

-----------------------------------------------

 Follow(E) = { $, ),  }

 Follow(R) = { $, ),  }

 Follow(T) = { +, $, ),  }

 Follow(Y) = { +, $, ),  }

 Follow(F) = { *, +, $, ),  }
https://ideone.com/5y9bIN
language:
C (gcc 8.3)
created:
2 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!