| def compute_first(productions):
|
| first = {nt: set() for nt in productions}
|
| def first_string(s):
|
| r = set()
|
| if s == "": r.add('ε'); return r
|
| for symbol in s:
|
| if not symbol.isupper():
|
| r.add(symbol); break
|
| else:
|
| r |= (first[symbol] - {'ε'})
|
| if 'ε' not in first[symbol]: break
|
| else: r.add('ε')
|
| return r
|
| changed = True
|
| while changed:
|
| changed = False
|
| for nt, prods in productions.items():
|
| for prod in prods:
|
| temp = set()
|
| if prod == 'ε' or prod == '': temp.add('ε')
|
| else:
|
| for symbol in prod:
|
| if not symbol.isupper():
|
| temp.add(symbol); break
|
| else:
|
| temp |= (first[symbol] - {'ε'})
|
| if 'ε' not in first[symbol]: break
|
| else: temp.add('ε')
|
| before = len(first[nt])
|
| first[nt] |= temp
|
| if len(first[nt]) != before: changed = True
|
| return first
|
| def compute_follow(productions, first, start_symbol):
|
| follow = {nt: set() for nt in productions}
|
| follow[start_symbol].add('$')
|
| changed = True
|
| while changed:
|
| changed = False
|
| for nt, prods in productions.items():
|
| for prod in prods:
|
| for i, symbol in enumerate(prod):
|
| if symbol.isupper():
|
| beta = prod[i+1:]
|
| first_beta = set()
|
| if beta == "": first_beta.add('ε')
|
| else:
|
| for s in beta:
|
| if not s.isupper():
|
| first_beta.add(s); break
|
| else:
|
| first_beta |= (first[s] - {'ε'})
|
| if 'ε' not in first[s]: break
|
| else: first_beta.add('ε')
|
| before = len(follow[symbol])
|
| follow[symbol] |= (first_beta - {'ε'})
|
| if 'ε' in first_beta: follow[symbol] |= follow[nt]
|
| if len(follow[symbol]) != before: changed = True
|
| return follow
|
| def build_parsing_table(productions, first, follow, nts_order, terms_order):
|
| table = {nt: {t: None for t in terms_order} for nt in productions}
|
| for nt, prods in productions.items():
|
| for prod in prods:
|
| first_prod = set()
|
| if prod == 'ε' or prod == '': first_prod.add('ε')
|
| else:
|
| for symbol in prod:
|
| if not symbol.isupper():
|
| first_prod.add(symbol); break
|
| else:
|
| first_prod |= (first[symbol] - {'ε'})
|
| if 'ε' not in first[symbol]: break
|
| else: first_prod.add('ε')
|
| for t in (first_prod - {'ε'}):
|
| table[nt][t] = f"{nt}->{prod}"
|
| if 'ε' in first_prod:
|
| for t in follow[nt]:
|
| table[nt][t] = f"{nt}->{prod}"
|
| return table
|
| def simulate_parsing(inp, start, table):
|
| stack = [start, '$']; ip = 0; actions = []
|
| while True:
|
| curr_stack = "".join(stack)
|
| curr_inp = inp[ip:]
|
| top = stack[0]
|
| if not top.isupper():
|
| if top == inp[ip]:
|
| actions.append((curr_stack, curr_inp, "POP ACTION"))
|
| stack.pop(0); ip += 1
|
| else:
|
| actions.append((curr_stack, curr_inp, f"Error: expected '{top}'"))
|
| return actions, False
|
| else:
|
| curr_sym = inp[ip] if ip < len(inp) else '$'
|
| rule = table[top].get(curr_sym)
|
| if rule is None:
|
| actions.append((curr_stack, curr_inp, f"Error: no rule for {top} on '{curr_sym}'"))
|
| return actions, False
|
| else:
|
| actions.append((curr_stack, curr_inp, rule))
|
| stack.pop(0)
|
| prod = rule.split("->")[1]
|
| if prod != 'ε' and prod != '':
|
| for symbol in prod[::-1]:
|
| stack.insert(0, symbol)
|
| if stack == ['$'] and inp[ip:] == '$':
|
| actions.append(("$", "$", "POP ACTION"))
|
| stack.pop(0); ip += 1; break
|
| return (actions, True) if ip == len(inp) else (actions, False)
|
| def print_parsing_table(table, nts_order, terms_order):
|
| print("\n\t\t\t\t\t\t\t The LL(1) Parsing Table for the above grammer :-")
|
| print("\t\t\t\t\t\t\t^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^\n")
|
| sep = " " + "=" * 101
|
| print("\t\t\t" + sep)
|
| print("\t\t\t\t|\t" + "\t\t".join(terms_order))
|
| print("\t\t\t" + sep.replace("=", "-"))
|
| for nt in nts_order:
|
| row = f"\t\t\t {nt}\t|\t" + "\t\t".join(table[nt].get(t) or "" for t in terms_order)
|
| print(row)
|
| print("\t\t\t" + sep.replace("=", "-"))
|
| def print_parsing_steps(actions):
|
| print("\n\t\t\t\t\t===========================================================================\n")
|
| print("\t\t\t\t\t\tStack\t\t\tInput\t\t\tAction")
|
| print("\t\t\t\t\t===========================================================================\n")
|
| for s, i, a in actions:
|
| print(f"\t\t\t\t\t\t{''.join(reversed(s)):<24}{i:<24}{a}")
|
| print("\n\t\t\t\t\t===========================================================================\n")
|
| def main():
|
| count = int(input("How many productions? : "))
|
| print(f"\nEnter {count} productions in form A->B where A and B are grammar symbols:")
|
| productions, order = {}, []
|
| for _ in range(count):
|
| prod_str = input().strip()
|
| if '->' not in prod_str:
|
| print("Incorrect production format. Expected A->B."); return
|
| left, right = map(str.strip, prod_str.split('->', 1))
|
| if left == "":
|
| print("Nonterminal missing in production."); return
|
| if left not in productions:
|
| productions[left] = []; order.append(left)
|
| productions[left].append(right)
|
| start = order[0]
|
| first = compute_first(productions)
|
| follow = compute_follow(productions, first, start)
|
| print("\nFirst sets:")
|
| for nt in order:
|
| print(f"First({nt}) = {{ {', '.join(sorted(first[nt]))} }}")
|
| print("\nFollow sets:")
|
| for nt in order:
|
| print(f"Follow({nt}) = {{ {', '.join(sorted(follow[nt]))} }}")
|
| terms_order = ['+', '*', '(', ')', 'i', '$']
|
| table = build_parsing_table(productions, first, follow, order, terms_order)
|
| print_parsing_table(table, order, terms_order)
|
| inp = input("\nPlease enter the desired INPUT STRING = ").strip()
|
| if inp[-1] != '$': inp += '$'
|
| actions, accepted = simulate_parsing(inp, start, table)
|
| print_parsing_steps(actions)
|
| print("\n\t\t\t" + "=" * 90)
|
| print("\t\t\t\t\t\t\t\tYOUR STRING HAS BEEN ACCEPTED !!" if accepted else "\t\t\t\t\t\t\t\tYOUR STRING HAS BEEN REJECTED !!")
|
| print("\t\t\t" + "=" * 90)
|
| if __name__ == "__main__":
|
| main()
|