evap16/Compiler
0
1import streamlit as st2import copy3 4def grammarAugmentation(rules, nonterm_userdef, start_symbol):5 newRules = []6 newChar = start_symbol + "'"7 while (newChar in nonterm_userdef):8 newChar += "'"9 10 newRules.append([newChar, ['.', start_symbol]])11 12 for rule in rules:13 k = rule.split("->")14 lhs = k[0].strip()15 rhs = k[1].strip()16 multirhs = rhs.split('|')17 for rhs1 in multirhs:18 rhs1 = rhs1.strip().split()19 rhs1.insert(0, '.')20 newRules.append([lhs, rhs1])21 return newRules22 23def findClosure(input_state, dotSymbol, separatedRulesList, start_symbol):24 closureSet = []25 26 if dotSymbol == start_symbol:27 for rule in separatedRulesList:28 if rule[0] == dotSymbol:29 closureSet.append(rule)30 else:31 closureSet = input_state32 33 prevLen = -134 while prevLen != len(closureSet):35 prevLen = len(closureSet)36 tempClosureSet = []37 for rule in closureSet:38 indexOfDot = rule[1].index('.')39 if rule[1][-1] != '.':40 dotPointsHere = rule[1][indexOfDot + 1]41 for in_rule in separatedRulesList:42 if dotPointsHere == in_rule[0] and in_rule not in tempClosureSet:43 tempClosureSet.append(in_rule)44 45 for rule in tempClosureSet:46 if rule not in closureSet:47 closureSet.append(rule)48 return closureSet49 50def compute_GOTO(state, statesDict, separatedRulesList, stateMap, stateCount):51 generateStatesFor = []52 for rule in statesDict[state]:53 if rule[1][-1] != '.':54 indexOfDot = rule[1].index('.')55 dotPointsHere = rule[1][indexOfDot + 1]56 if dotPointsHere not in generateStatesFor:57 generateStatesFor.append(dotPointsHere)58 59 if len(generateStatesFor) != 0:60 for symbol in generateStatesFor:61 stateCount = GOTO(state, symbol, statesDict, separatedRulesList, stateMap, stateCount)62 return stateCount63 64def GOTO(state, charNextToDot, statesDict, separatedRulesList, stateMap, stateCount):65 newState = []66 for rule in statesDict[state]:67 indexOfDot = rule[1].index('.')68 if rule[1][-1] != '.':69 if rule[1][indexOfDot + 1] == charNextToDot:70 shiftedRule = copy.deepcopy(rule)71 shiftedRule[1][indexOfDot] = shiftedRule[1][indexOfDot + 1]72 shiftedRule[1][indexOfDot + 1] = '.'73 newState.append(shiftedRule)74 75 addClosureRules = []76 for rule in newState:77 indexDot = rule[1].index('.')78 if rule[1][-1] != '.':79 closureRes = findClosure(newState, rule[1][indexDot + 1], separatedRulesList, start_symbol)80 for rule in closureRes:81 if rule not in addClosureRules and rule not in newState:82 addClosureRules.append(rule)83 84 for rule in addClosureRules:85 newState.append(rule)86 87 stateExists = -188 for state_num in statesDict:89 if statesDict[state_num] == newState:90 stateExists = state_num91 break92 93 if stateExists == -1:94 stateCount += 195 statesDict[stateCount] = newState96 stateMap[(state, charNextToDot)] = stateCount97 else:98 stateMap[(state, charNextToDot)] = stateExists99 return stateCount100 101def generateStates(statesDict, separatedRulesList, stateMap, stateCount):102 prev_len = -1103 called_GOTO_on = []104 105 while (len(statesDict) != prev_len):106 prev_len = len(statesDict)107 keys = list(statesDict.keys())108 109 for key in keys:110 if key not in called_GOTO_on:111 called_GOTO_on.append(key)112 stateCount = compute_GOTO(key, statesDict, separatedRulesList, stateMap, stateCount)113 return stateCount114 115def first(rule, diction, term_userdef):116 if len(rule) != 0 and (rule is not None):117 if rule[0] in term_userdef:118 return rule[0]119 elif rule[0] == '#':120 return '#'121 122 if len(rule) != 0:123 if rule[0] in list(diction.keys()):124 fres = []125 rhs_rules = diction[rule[0]]126 127 for itr in rhs_rules:128 indivRes = first(itr, diction, term_userdef)129 if type(indivRes) is list:130 for i in indivRes:131 fres.append(i)132 else:133 fres.append(indivRes)134 135 if '#' not in fres:136 return fres137 else:138 newList = []139 fres.remove('#')140 if len(rule) > 1:141 ansNew = first(rule[1:], diction, term_userdef)142 if ansNew != None:143 if type(ansNew) is list:144 newList = fres + ansNew145 else:146 newList = fres + [ansNew]147 else:148 newList = fres149 return newList150 fres.append('#')151 return fres152 153def follow(nt, start_symbol, rules, diction):154 solset = set()155 if nt == start_symbol:156 solset.add('$')157 158 for curNT in diction:159 rhs = diction[curNT]160 161 for subrule in rhs:162 if nt in subrule:163 while nt in subrule:164 index_nt = subrule.index(nt)165 subrule = subrule[index_nt + 1:]166 167 if len(subrule) != 0:168 res = first(subrule, diction, term_userdef)169 if '#' in res:170 newList = []171 res.remove('#')172 ansNew = follow(curNT, start_symbol, rules, diction)173 if ansNew != None:174 if type(ansNew) is list:175 newList = res + ansNew176 else:177 newList = res + [ansNew]178 else:179 newList = res180 res = newList181 else:182 if nt != curNT:183 res = follow(curNT, start_symbol, rules, diction)184 185 if res is not None:186 if type(res) is list:187 for g in res:188 solset.add(g)189 else:190 solset.add(res)191 return list(solset)192 193def createParseTable(statesDict, stateMap, T, NT, separatedRulesList, rules, diction):194 rows = list(statesDict.keys())195 cols = T + ['$'] + NT196 197 Table = []198 tempRow = []199 for y in range(len(cols)):200 tempRow.append('')201 for x in range(len(rows)):202 Table.append(copy.deepcopy(tempRow))203 204 for entry in stateMap:205 state = entry[0]206 symbol = entry[1]207 a = rows.index(state)208 b = cols.index(symbol)209 if symbol in NT:210 Table[a][b] = Table[a][b] + f"{stateMap[entry]} "211 elif symbol in T:212 Table[a][b] = Table[a][b] + f"S{stateMap[entry]} "213 214 numbered = {}215 key_count = 0216 for rule in separatedRulesList:217 tempRule = copy.deepcopy(rule)218 tempRule[1].remove('.')219 numbered[key_count] = tempRule220 key_count += 1221 222 for stateno in statesDict:223 for rule in statesDict[stateno]:224 if rule[1][-1] == '.':225 temp2 = copy.deepcopy(rule)226 temp2[1].remove('.')227 for key in numbered:228 if numbered[key] == temp2:229 follow_result = follow(rule[0], start_symbol, rules, diction)230 for col in follow_result:231 index = cols.index(col)232 if key == 0:233 Table[stateno][index] = "Accept"234 else:235 Table[stateno][index] = Table[stateno][index] + f"R{key} "236 237 return Table, cols, rows238 239# Streamlit app240st.title("SLR(1) Parser Generator")241 242# Input section243st.header("Grammar Input")244st.write("Enter grammar rules in the format: A -> B | C")245 246# Initialize session state for rules247if 'rules' not in st.session_state:248 st.session_state.rules = ["E -> E + T | T", "T -> T * F | F", "F -> ( E ) | id"]249 250# Display rules input251rules = []252for i in range(len(st.session_state.rules)):253 rule = st.text_input(f"Rule {i+1}", value=st.session_state.rules[i], key=f"rule_{i}")254 rules.append(rule)255 256# Add/remove rule buttons257col1, col2 = st.columns(2)258with col1:259 if st.button("Add Rule"):260 st.session_state.rules.append("")261 st.experimental_rerun()262with col2:263 if st.button("Remove Rule") and len(st.session_state.rules) > 1:264 st.session_state.rules.pop()265 st.experimental_rerun()266 267# Other inputs268nonterm_userdef = st.text_input("Non-terminal symbols (separated by space)", "E T F").split()269term_userdef = st.text_input("Terminal symbols (separated by space)", "id + * ( )").split()270start_symbol = st.text_input("Start symbol", "E")271 272if st.button("Generate Parser"):273 st.header("Results")274 275 # Display original grammar276 st.subheader("Original Grammar")277 for rule in rules:278 st.write(rule)279 280 # Grammar augmentation281 separatedRulesList = grammarAugmentation(rules, nonterm_userdef, start_symbol)282 283 st.subheader("Augmented Grammar")284 for rule in separatedRulesList:285 st.write(f"{rule[0]} -> {' '.join(rule[1])}")286 287 # Initialize variables288 statesDict = {}289 stateMap = {}290 stateCount = 0291 diction = {}292 293 # Calculate closure294 I0 = findClosure(0, start_symbol, separatedRulesList, start_symbol)295 statesDict[0] = I0296 297 st.subheader("Initial Closure (I0)")298 for rule in I0:299 st.write(f"{rule[0]} -> {' '.join(rule[1])}")300 301 # Generate states302 stateCount = generateStates(statesDict, separatedRulesList, stateMap, stateCount)303 304 # Create parsing table305 rules.insert(0, f"{separatedRulesList[0][0]} -> {separatedRulesList[0][1][1]}")306 for rule in rules:307 k = rule.split("->")308 k[0] = k[0].strip()309 k[1] = k[1].strip()310 rhs = k[1]311 multirhs = rhs.split('|')312 for i in range(len(multirhs)):313 multirhs[i] = multirhs[i].strip()314 multirhs[i] = multirhs[i].split()315 diction[k[0]] = multirhs316 317 Table, cols, rows = createParseTable(statesDict, stateMap, term_userdef, nonterm_userdef, separatedRulesList, rules, diction)318 319 # Display parsing table320 st.subheader("SLR(1) Parsing Table")321 322 # Create DataFrame for better display323 import pandas as pd324 df = pd.DataFrame(Table, columns=cols, index=[f"I{i}" for i in rows])325 st.dataframe(df)