fork download
copy 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4.  
  5. #define MAX 100
  6. #define NON_TERMINALS 26
  7. #define TERMINALS 26
  8.  
  9. // Global arrays for the grammar
  10. char nonTerminals[NON_TERMINALS];
  11. char terminals[TERMINALS];
  12. int numNonTerminals = 0;
  13. int numTerminals = 0;
  14.  
  15. // Array of rules
  16. char rules[NON_TERMINALS][MAX][MAX];
  17. int ruleCount[NON_TERMINALS];
  18.  
  19. // Function to check if a character is a terminal symbol
  20. int isTerminal(char c) {
  21.     return c >= 'a' && c <= 'z';
  22. }
  23.  
  24. // Function to find the FIRST set of a non-terminal
  25. void findFirst(char nonTerminal, char FIRST[NON_TERMINALS][TERMINALS], int* visited) {
  26.     int index = nonTerminal - 'A';
  27.  
  28.     if (visited[index]) return;  // Avoid cyclic calls
  29.     visited[index] = 1;  // Mark the current non-terminal as visited
  30.  
  31.     // Traverse all rules for this non-terminal
  32.     for (int i = 0; i < ruleCount[index]; i++) {
  33.         char *rule = rules[index][i];
  34.  
  35.         // Rule could have the form A -> X1 X2 ... Xn
  36.         for (int j = 0; rule[j] != '\0'; j++) {
  37.             char symbol = rule[j];
  38.  
  39.             // If symbol is a terminal, add to FIRST
  40.             if (isTerminal(symbol)) {
  41.                 FIRST[index][symbol - 'a'] = 1;
  42.                 break;
  43.             }
  44.             // If symbol is a non-terminal, recursively find its FIRST set
  45.             else if (symbol >= 'A' && symbol <= 'Z') {
  46.                 findFirst(symbol, FIRST, visited);
  47.                 // If the non-terminal can derive epsilon, continue to next symbols
  48.                 if (FIRST[symbol - 'A'][0] == 1) {
  49.                     continue;
  50.                 }
  51.                 else {
  52.                     break;
  53.                 }
  54.             }
  55.         }
  56.     }
  57. }
  58.  
  59. // Function to print the FIRST sets
  60. void printFirst(char FIRST[NON_TERMINALS][TERMINALS]) {
  61.     printf("FIRST sets:\n");
  62.     for (int i = 0; i < numNonTerminals; i++) {
  63.         printf("FIRST(%c) = {", nonTerminals[i]);
  64.         int firstFound = 0;
  65.         for (int j = 0; j < TERMINALS; j++) {
  66.             if (FIRST[i][j]) {
  67.                 if (firstFound) {
  68.                     printf(", ");
  69.                 }
  70.                 printf("%c", 'a' + j);
  71.                 firstFound = 1;
  72.             }
  73.         }
  74.         if (firstFound == 0) {
  75.             // If no terminal found, it means FIRST set is empty
  76.             printf("ε");
  77.         }
  78.         printf("}\n");
  79.     }
  80. }
  81.  
  82. int main() {
  83.     // Input the number of non-terminals and terminals
  84.     printf("Enter the number of non-terminals: ");
  85.     scanf("%d", &numNonTerminals);
  86.  
  87.     printf("Enter the non-terminals (e.g., S A B): ");
  88.     for (int i = 0; i < numNonTerminals; i++) {
  89.         scanf(" %c", &nonTerminals[i]);
  90.     }
  91.  
  92.     printf("Enter the number of rules for each non-terminal:\n");
  93.     for (int i = 0; i < numNonTerminals; i++) {
  94.         printf("Number of rules for %c: ", nonTerminals[i]);
  95.         scanf("%d", &ruleCount[i]);
  96.         printf("Enter the rules for %c (e.g., A -> a, A -> AB):\n", nonTerminals[i]);
  97.         for (int j = 0; j < ruleCount[i]; j++) {
  98.             scanf("%s", rules[i][j]);
  99.         }
  100.     }
  101.  
  102.     // Initialize the FIRST table
  103.     char FIRST[NON_TERMINALS][TERMINALS] = {0};
  104.  
  105.     // To avoid cyclic calls
  106.     int visited[NON_TERMINALS] = {0};
  107.  
  108.     // Compute FIRST sets for each non-terminal
  109.     for (int i = 0; i < numNonTerminals; i++) {
  110.         findFirst(nonTerminals[i], FIRST, visited);
  111.     }
  112.  
  113.     // Print the FIRST sets
  114.     printFirst(FIRST);
  115.  
  116.     return 0;
  117. }
  118.  
Success #stdin #stdout 0s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Enter the number of non-terminals: Enter the non-terminals (e.g., S A B): Enter the number of rules for each non-terminal:
FIRST sets:
https://ideone.com/8Avh19
language:
C99 (gcc 8.3)
created:
4 days 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!