app.py

import streamlit as st
import pandas as pd

rules = []
nonterm_userdef = []
term_userdef = []
diction = {}
firsts = {}
follows = {}
start_symbol = None

def removeLeftRecursion(rulesDiction):
    store = {}
    for lhs in rulesDiction:
        alphaRules = []
        betaRules = []
        allrhs = rulesDiction[lhs]
        for subrhs in allrhs:
            if subrhs[0] == lhs:
                alphaRules.append(subrhs[1:])
            else:
                betaRules.append(subrhs)
        if len(alphaRules) != 0:
            lhs_ = lhs + "'"
            while lhs_ in rulesDiction.keys() or lhs_ in store.keys():
                lhs_ += "'"
            for b in range(len(betaRules)):
                betaRules[b].append(lhs_)
            rulesDiction[lhs] = betaRules
            for a in range(len(alphaRules)):
                alphaRules[a].append(lhs_)
            alphaRules.append(['#'])
            store[lhs_] = alphaRules
    for left in store:
        rulesDiction[left] = store[left]
    return rulesDiction

def LeftFactoring(rulesDiction):
    newDict = {}
    for lhs in rulesDiction:
        allrhs = rulesDiction[lhs]
        temp = dict()
        for subrhs in allrhs:
            if subrhs[0] not in list(temp.keys()):
                temp[subrhs[0]] = [subrhs]
            else:
                temp[subrhs[0]].append(subrhs)
        new_rule = []
        tempo_dict = {}
        for term_key in temp:
            allStartingWithTermKey = temp[term_key]
            if len(allStartingWithTermKey) > 1:
                lhs_ = lhs + "'"
                while lhs_ in rulesDiction.keys() or lhs_ in tempo_dict.keys():
                    lhs_ += "'"
                new_rule.append([term_key, lhs_])
                ex_rules = []
                for g in temp[term_key]:
                    ex_rules.append(g[1:])
                tempo_dict[lhs_] = ex_rules
            else:
                new_rule.append(allStartingWithTermKey[0])
        newDict[lhs] = new_rule
        for key in tempo_dict:
            newDict[key] = tempo_dict[key]
    return newDict

def first(rule):
    global term_userdef, diction
    if not rule:
        return ['#']
    if rule[0] in term_userdef:
        return [rule[0]]
    elif rule[0] == '#':
        return ['#']
    
    if rule[0] in diction:
        fres = []
        rhs_rules = diction[rule[0]]
        for itr in rhs_rules:
            indivRes = first(itr)
            if indivRes:
                fres.extend(indivRes)
        
        if '#' in fres and len(rule) > 1:
            fres.remove('#')
            ansNew = first(rule[1:])
            if ansNew:
                fres.extend(ansNew)
        return list(set(fres))
    return []

def follow(nt):
    global start_symbol, diction
    solset = set()
    if nt == start_symbol:
        solset.add('$')
    
    for curNT in diction:
        rhs = diction[curNT]
        for subrule in rhs:
            if nt in subrule:
                while nt in subrule:
                    index_nt = subrule.index(nt)
                    subrule = subrule[index_nt + 1:]
                    if subrule:
                        res = first(subrule)
                        if '#' in res:
                            res.remove('#')
                            if nt != curNT:
                                follow_res = follow(curNT)
                                if follow_res:
                                    res.extend(follow_res)
                        solset.update(res)
                    else:
                        if nt != curNT:
                            follow_res = follow(curNT)
                            if follow_res:
                                solset.update(follow_res)
    return list(solset)

def computeAllFirsts():
    global firsts, diction
    firsts.clear()
    for y in diction:
        firsts[y] = set()
        for sub in diction[y]:
            result = first(sub)
            if result:
                firsts[y].update(result)

def computeAllFollows():
    global follows, diction
    follows.clear()
    for NT in diction:
        follows[NT] = set(follow(NT))

def createParseTable():
    global diction, term_userdef, firsts, follows
    
    # Initialize parse table with empty strings
    parse_table = {}
    for non_term in diction:
        parse_table[non_term] = {}
        for term in term_userdef + ['$']:
            parse_table[non_term][term] = ""
    
    # Fill parse table
    grammar_is_LL = True
    
    for non_term in diction:
        for production in diction[non_term]:
            first_set = first(production)
            
            # If epsilon is in FIRST set, add FOLLOW set
            if '#' in first_set:
                first_set.remove('#')
                first_set.extend(follows[non_term])
            
            for terminal in first_set:
                if parse_table[non_term].get(terminal, "") == "":
                    parse_table[non_term][terminal] = f"{non_term} -> {' '.join(production)}"
                else:
                    grammar_is_LL = False
    
    return parse_table, grammar_is_LL

def validateStringUsingStackBuffer(parse_table, input_string):
    stack = [start_symbol, '$']
    buffer = list(input_string.split()) + ['$']
    
    while stack and buffer:
        top_stack = stack[0]
        current_input = buffer[0]
        
        if top_stack == current_input:
            stack.pop(0)
            buffer.pop(0)
        elif top_stack in term_userdef:
            return "Invalid String: Terminal mismatch"
        elif parse_table[top_stack][current_input]:
            production = parse_table[top_stack][current_input].split('->')[1].strip().split()
            stack.pop(0)
            if production != ['#']:
                stack = production + stack
        else:
            return "Invalid String: No production rule found"
    
    if not stack and not buffer:
        return "Valid String"
    return "Invalid String: Stack or buffer not empty"

# Streamlit UI
st.title("LL(1) Grammar Analyzer")

# Input section
st.header("Grammar Input")
start_symbol = st.text_input("Enter Start Symbol:", "S")

with st.expander("Enter Grammar Rules"):
    num_rules = st.number_input("Number of Rules:", min_value=1, value=3)
    rules = []
    for i in range(num_rules):
        rule = st.text_input(f"Rule {i+1} (format: A -> B c | d)", key=f"rule_{i}")
        if rule:
            rules.append(rule)

nonterm_input = st.text_input("Enter Non-terminals (comma-separated):", "S,A,B")
term_input = st.text_input("Enter Terminals (comma-separated):", "a,b,c")

if nonterm_input.strip():
    nonterm_userdef = [x.strip() for x in nonterm_input.split(',') if x.strip()]
if term_input.strip():
    term_userdef = [x.strip() for x in term_input.split(',') if x.strip()]

if st.button("Analyze Grammar"):
    # Clear previous data
    diction.clear()
    
    # Process rules
    for rule in rules:
        if '->' in rule:
            lhs, rhs = rule.split("->")
            lhs = lhs.strip()
            rhs_parts = [x.strip().split() for x in rhs.split("|")]
            diction[lhs] = rhs_parts
    
    # Remove left recursion and perform left factoring
    st.subheader("Grammar Processing")
    with st.expander("Show Grammar Transformations"):
        st.write("After removing left recursion:")
        diction = removeLeftRecursion(diction)
        st.write(diction)
        
        st.write("After left factoring:")
        diction = LeftFactoring(diction)
        st.write(diction)
    
    # Compute FIRST and FOLLOW sets
    computeAllFirsts()
    computeAllFollows()
    
    with st.expander("Show FIRST and FOLLOW Sets"):
        st.write("FIRST Sets:", {k: list(v) for k, v in firsts.items()})
        st.write("FOLLOW Sets:", {k: list(v) for k, v in follows.items()})
    
    # Create and display parse table
    parse_table, grammar_is_LL = createParseTable()
    
    st.subheader("Parse Table")
    # Convert parse table to pandas DataFrame for better display
    df_data = []
    terminals = term_userdef + ['$']
    
    for non_term in parse_table:
        row = [non_term]  # First column is non-terminal
        for term in terminals:
            row.append(parse_table[non_term].get(term, ""))
        df_data.append(row)
    
    df = pd.DataFrame(df_data, columns=['Non-Terminal'] + terminals)
    st.dataframe(df)
    
    if grammar_is_LL:
        st.success("This grammar is LL(1)!")
    else:
        st.error("This grammar is not LL(1)!")
    
    # String validation section
    st.subheader("String Validation")
    input_string = st.text_input("Enter string to validate (space-separated):", "")
    if input_string:
        result = validateStringUsingStackBuffer(parse_table, input_string)
        if "Valid" in result:
            st.success(result)
        else:
            st.error(result)