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
Post a Comment