Skip to main content

14. Write a program to find the First and Follow of any given grammar.


Sure, I can provide you with a simple example of a program to find the First and Follow sets of a given grammar using Python. I'll explain each line of the code as well.


```python

# Define the grammar rules

grammar = {

    'E': ['T E\''],

    'E\'': ['+ T E\'', 'epsilon'],

    'T': ['F T\''],

    'T\'': ['* F T\'', 'epsilon'],

    'F': ['( E )', 'id']

}


# Initialize First and Follow sets

first_sets = {}

follow_sets = {}


# Initialize terminals and non-terminals

terminals = set(['+', '*', '(', ')', 'id'])

non_terminals = set(grammar.keys())


# Initialize First sets with empty sets

for symbol in non_terminals:

    first_sets[symbol] = set()


# Helper function to calculate First set of a symbol

def calculate_first(symbol):

    if symbol in terminals:

        return set([symbol])

    first = set()

    for production in grammar[symbol]:

        for char in production:

            first.update(calculate_first(char))

            if 'epsilon' not in first_sets[char]:

                break

    return first


# Calculate First sets for all symbols

for symbol in non_terminals:

    first_sets[symbol] = calculate_first(symbol)


# Print First sets

print("First Sets:")

for symbol in non_terminals:

    print(symbol, ":", first_sets[symbol])


# Initialize Follow sets with empty sets

for symbol in non_terminals:

    follow_sets[symbol] = set()


# Helper function to calculate Follow set of a symbol

def calculate_follow(symbol):

    follow = set()

    if symbol == 'E':

        follow.add('$')  # $ represents end of input

    for non_term in non_terminals:

        for production in grammar[non_term]:

            if symbol in production:

                idx = production.index(symbol)

                if idx == len(production) - 1:

                    if non_term != symbol:

                        follow.update(calculate_follow(non_term))

                else:

                    next_symbol = production[idx + 1]

                    if next_symbol in terminals:

                        follow.add(next_symbol)

                    else:

                        follow.update(first_sets[next_symbol])

                        if 'epsilon' in first_sets[next_symbol]:

                            follow.update(calculate_follow(next_symbol))

    return follow


# Calculate Follow sets for all symbols

for symbol in non_terminals:

    follow_sets[symbol] = calculate_follow(symbol)


# Print Follow sets

print("\nFollow Sets:")

for symbol in non_terminals:

    print(symbol, ":", follow_sets[symbol])

```


Explanation of the code:


1. We define the grammar rules using a dictionary named `grammar`, where keys are non-terminals and values are lists of productions for each non-terminal.


2. We initialize `first_sets` and `follow_sets` dictionaries to store the calculated First and Follow sets.


3. We initialize the `terminals` and `non_terminals` sets.


4. We define a helper function `calculate_first(symbol)` to calculate the First set of a given symbol.


5. We iterate through the non-terminals and calculate their First sets using the `calculate_first` function.


6. We print the calculated First sets.


7. We define a helper function `calculate_follow(symbol)` to calculate the Follow set of a given symbol.


8. We iterate through the non-terminals and calculate their Follow sets using the `calculate_follow` function.


9. We print the calculated Follow sets.


The code calculates the First and Follow sets for a simple grammar. It iterates through the non-terminals, terminals, and productions to calculate these sets. The First set of a non-terminal includes all the terminals that can appear as the first symbol in any of its productions. The Follow set of a non-terminal includes all the terminals that can appear immediately after that non-terminal in any of the productions.


Comments

Popular posts from this blog

6. Generate a YACC specification to recognize a valid arithmetic expression that uses operators +, – , *,/ and parenthesis.

Below is a YACC specification for recognizing valid arithmetic expressions that involve operators (+, -, *, /) and parentheses. I'll explain each line of the code afterward: ```yacc %{ #include <stdio.h> %} %token NUMBER %left '+' '-' %left '*' '/' %% expression: expression '+' expression            | expression '-' expression            | expression '*' expression            | expression '/' expression            | '(' expression ')'            | NUMBER            ; %% int yylex() {     // Code for tokenizing input and returning tokens } void yyerror(const char *s) {     fprintf(stderr, "Error: %s\n", s); } int main() {     yyparse();     return 0; } ``` Now, let's break down the YACC specification line by line: 1. `%{` ... `%}`: This is the C code section where y...

1, Design and implement a lexical analyzer using C language to recognize all valid tokens in the input program. The lexical analyzer should ignore redundant spaces, tabs and newlines. It should also ignore comments

#include <stdio.h> #include <ctype.h> int main() {     char c;     while ((c = getchar()) != EOF) {         if (isspace(c)) {             // Ignore whitespace, tabs, and newlines             continue;         }         if (c == '/') {             // Check for comments             char nextChar = getchar();             if (nextChar == '/') {                 while ((nextChar = getchar()) != '\n');         ...

17. Write a program to perform constant propagation.

Sure, I can provide you with a basic example of a constant propagation program along with explanations for each line. Please note that this example is simplified and might not cover all possible cases of constant propagation. ```c #include <stdio.h> #include <stdbool.h> // Structure to represent an assignment statement struct Assignment {     char variable;     int value;     bool isConstant; }; int main() {     // Example assignments (variable, value, isConstant)     struct Assignment assignments[] = {         {'a', 10, true},         {'b', 20, true},         {'c', 0, true},         {'d', 30, false},         {'e', 0, false}     };     int numAssignments = sizeof(assignments) / sizeof(assignments[0]);     // Perform constant propagation     for (int i = 0; i < numAssignments; i++) { ...