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
    
    parse_table = {}
    for non_term in diction:
        parse_table[non_term] = {}
        for term in term_userdef + ['$']:
            parse_table[non_term][term] = ""
    
    grammar_is_LL = True
    
    for non_term in diction:
        for production in diction[non_term]:
            first_set = first(production)
            
            if '#' in first_set:
                first_set.remove('#')
                follow_set = follows[non_term]
                first_set.extend(follow_set)
            
            for terminal in first_set:
                if terminal in term_userdef + ['$']:
                    if parse_table[non_term][terminal] == "":
                        parse_table[non_term][terminal] = production
                    else:
                        grammar_is_LL = False
    
    return parse_table, grammar_is_LL

def validateStringUsingStackBuffer(parse_table, input_string, start_sym):
    """Validates a string using the parsing table"""
    # Initialize stack and input buffer
    stack = [start_sym, '$']
    input_tokens = input_string.split()
    input_tokens.append('$')
    buffer = input_tokens
    
    steps = []
    steps.append(("Initial Configuration:", f"Stack: {stack}", f"Input: {buffer}"))
    
    while stack and buffer:
        top_stack = stack[0]
        current_input = buffer[0]
        
        steps.append(("Current Step:", f"Stack Top: {top_stack}", f"Current Input: {current_input}"))
        
        if top_stack == current_input:
            stack.pop(0)
            buffer.pop(0)
            steps.append(("Action:", "Matched and consumed terminal", f"Remaining Input: {buffer}"))
        elif top_stack in parse_table:
            if current_input in parse_table[top_stack]:
                production = parse_table[top_stack][current_input]
                if production:
                    # Pop the non-terminal
                    stack.pop(0)
                    # Push the production in reverse (if it's not epsilon)
                    if production != ['#']:
                        stack = production + stack
                    steps.append(("Production Applied:", f"{top_stack} -> {' '.join(production) if production else '#'}", 
                                f"New Stack: {stack}"))
                else:
                    return False, steps, f"No production for {top_stack} with input {current_input}"
            else:
                return False, steps, f"Input symbol {current_input} not in parse table for {top_stack}"
        else:
            return False, steps, f"Unexpected symbol {top_stack} on stack"
    
    if len(stack) <= 1 and len(buffer) <= 1:
        return True, steps, "String accepted!"
    else:
        return False, steps, "String rejected - incomplete parse"

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

# Session state initialization
if 'test_strings' not in st.session_state:
    st.session_state.test_strings = []
if 'parse_table' not in st.session_state:
    st.session_state.parse_table = None
if 'grammar_processed' not in st.session_state:
    st.session_state.grammar_processed = False

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

with st.expander("Enter Grammar Rules", expanded=True):
    num_rules = st.number_input("Number of Rules:", min_value=1, value=4)
    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,C")
term_input = st.text_input("Enter Terminals (comma-separated):", "a,b,c,d,k,r,O")

# Process Grammar Button
if st.button("Process Grammar"):
    st.session_state.grammar_processed = False
    
    # Clear previous data
    diction.clear()
    nonterm_userdef = [x.strip() for x in nonterm_input.split(',') if x.strip()]
    term_userdef = [x.strip() for x in term_input.split(',') if x.strip()]
    
    # 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
    
    # Grammar Processing
    st.subheader("Grammar Analysis")
    
    with st.expander("Grammar Transformations", expanded=True):
        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("FIRST and FOLLOW Sets", expanded=True):
        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 parse table
    parse_table, grammar_is_LL = createParseTable()
    st.session_state.parse_table = parse_table
    
    # Display parse table
    st.subheader("Parse Table")
    df_data = []
    terminals = term_userdef + ['$']
    
    for non_term in parse_table:
        row = [non_term]
        for term in terminals:
            production = parse_table[non_term].get(term, "")
            if production:
                row.append(' '.join(production))
            else:
                row.append("")
        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)!")
    
    st.session_state.grammar_processed = True

# String Validation Section
if st.session_state.grammar_processed:
    st.header("String Validation")
    
    # Input for new test string
    col1, col2 = st.columns([3, 1])
    with col1:
        new_string = st.text_input("Enter a string to test (space-separated):")
    with col2:
        if st.button("Add String"):
            if new_string and new_string not in st.session_state.test_strings:
                st.session_state.test_strings.append(new_string)
    
    # Display and validate all test strings
    if st.session_state.test_strings:
        st.subheader("Test Results")
        for test_string in st.session_state.test_strings:
            with st.expander(f"String: {test_string}", expanded=True):
                is_valid, steps, message = validateStringUsingStackBuffer(
                    st.session_state.parse_table, test_string, start_symbol)
                
                # Display result
                if is_valid:
                    st.success(message)
                else:
                    st.error(message)
                
                # Display parsing steps
                st.write("Parsing Steps:")
                for i, (step_type, *step_details) in enumerate(steps, 1):
                    st.text(f"Step {i}:")
                    st.text(f"  {step_type}")
                    for detail in step_details:
                        st.text(f"  {detail}")
        
        # Option to clear test strings
        if st.button("Clear All Test Strings"):
            st.session_state.test_strings = []
            st.experimental_rerun()
else:
    st.info("Please process the grammar first before testing strings.")

# Help section
with st.expander("Help & Instructions"):
    st.markdown("""
    ### How to use this LL(1) Grammar Analyzer:
    
    1. **Enter the Grammar**:
       - Specify the start symbol
       - Enter the grammar rules in the format: A -> B c | d
       - List all non-terminals and terminals
    
    2. **Process the Grammar**:
       - Click "Process Grammar" to analyze the grammar
       - View the transformed grammar, FIRST/FOLLOW sets, and parse table
    
    3. **Test Strings**:
       - Enter strings to test in the validation section
       - Add multiple strings to test
       - View detailed parsing steps for each string
    
    ### Example Grammar:
    ```
    S -> A k O
    A -> A d | a B | a C
    C -> c
    B -> b B C | r
    ```
    
    ### Example Test Strings:
    - a r k O
    - a c k O
    - a b r c k O
    """)