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

12. Write a program to convert NFA to DFA.

Converting a Non-Deterministic Finite Automaton (NFA) to a Deterministic Finite Automaton (DFA) involves creating a new DFA where each state corresponds to a set of NFA states reachable under certain conditions. Below is a simple Python program to perform this conversion. I'll explain each line of code: ```python from collections import defaultdict def epsilon_closure(states, transitions, epsilon):     closure = set(states)     stack = list(states)          while stack:         state = stack.pop()         for next_state in transitions[state].get(epsilon, []):             if next_state not in closure:                 closure.add(next_state)                 stack.append(next_state)          return closure def nfa_to_dfa(nfa_states, nfa_transitions, alphabet, start_state, n...