i have written the code for a syntax analyzer generator for my lab exercise. I need to…
- User
i have written the code for a syntax analyzer generator for my lab exercise. I need to write a syntax analyzer now that will use the generator. I will provide the code for the generator and instructinos for the syntax analyzer. please write the code for the syntax analyzer for me
Generator code:
def read_grammar(file_path): with open(file_path, 'r') as file: lines = file.readlines() non_terminals = [] terminals = set() sync_tokens = set() productions = {} current_lhs = None # Initialize current LHS to None start_symbol = None # To hold the start symbol for line in lines: line = line.rstrip('\n') # Remove only the newline character, keep leading spaces if line.startswith('%V'): tokens = line[2:].strip().split() non_terminals.extend(tokens) if tokens and start_symbol is None: start_symbol = tokens[0] # Set the first non-terminal as start symbol elif line.startswith('%T'): tokens = line[2:].strip().split() terminals.update(tokens) elif line.startswith('%Syn'): tokens = line[4:].strip().split() sync_tokens.update(tokens) elif line.startswith('<'): # LHS line current_lhs = line.strip() if current_lhs not in productions: productions[current_lhs] = [] elif line.startswith(' ') or line.startswith('\t'): # RHS line, associated with current LHS if current_lhs is not None: rhs = line.strip().split() productions[current_lhs].append(rhs) else: print("Error: RHS without current LHS.") else: continue # Skip empty lines or unrecognized lines non_terminals = set(non_terminals) return non_terminals, terminals, sync_tokens, productions, start_symbol non_terminals, terminals, sync_tokens, productions, start_symbol = read_grammar('grammar.txt') # Augment the grammar by adding a new start symbol augmented_start_symbol = start_symbol + "'" while augmented_start_symbol in non_terminals: augmented_start_symbol += "'" non_terminals.add(augmented_start_symbol) productions[augmented_start_symbol] = [[start_symbol]] print('Augmented Start Symbol:', augmented_start_symbol) print('Non-terminals:', non_terminals) print('Terminals:', terminals) print('Synchronization Tokens:', sync_tokens) print('Productions:') for lhs, rhs_list in productions.items(): for rhs in rhs_list: print(f'{lhs} -> {" ".join(rhs)}') # Initialize FIRST sets FIRST = {} for terminal in terminals: FIRST[terminal] = set([terminal]) # FIRST(terminal) = {terminal} for non_terminal in non_terminals: FIRST[non_terminal] = set() # FIRST(non_terminal) = empty set class LR1Item: def __init__(self, lhs, rhs, dot_position, lookahead): self.lhs = lhs self.rhs = rhs self.dot_position = dot_position self.lookahead = lookahead # This is a single terminal symbol def __eq__(self, other): return (self.lhs == other.lhs and self.rhs == other.rhs and self.dot_position == other.dot_position and self.lookahead == other.lookahead) def __hash__(self): return hash((self.lhs, tuple(self.rhs), self.dot_position, self.lookahead)) def __str__(self): before_dot = ' '.join(self.rhs[:self.dot_position]) after_dot = ' '.join(self.rhs[self.dot_position:]) return f"{self.lhs} -> {before_dot} • {after_dot}, {self.lookahead}" def __repr__(self): return self.__str__() def first_of_sequence(symbols): result = set() for symbol in symbols: if symbol in terminals: result.add(symbol) return result elif symbol in non_terminals: result |= (FIRST[symbol] - set(['$'])) if '$' not in FIRST[symbol]: return result else: # Handle special cases, e.g., epsilon pass result.add('$') return result def epsilon_closure(items): closure_set = set(items) stack = list(items) while stack: item = stack.pop() if item.dot_position < len(item.rhs): symbol = item.rhs[item.dot_position] if symbol in non_terminals: beta = item.rhs[item.dot_position + 1:] lookahead_symbols = first_of_sequence(beta + [item.lookahead]) for prod in productions[symbol]: for la in lookahead_symbols: new_item = LR1Item(symbol, prod, 0, la) if new_item not in closure_set: closure_set.add(new_item) stack.append(new_item) return closure_set def goto(items, symbol): goto_set = set() for item in items: if item.dot_position < len(item.rhs) and item.rhs[item.dot_position] == symbol: goto_item = LR1Item(item.lhs, item.rhs, item.dot_position + 1, item.lookahead) goto_set.add(goto_item) return epsilon_closure(goto_set) # Define the grammar # non_terminals = {'<A>', '<B>', '<C>', '<D>', '<E>'} # terminals = {'a', 'b', 'c', 'd', 'e', 'f'} # productions = { # '<A>': [['<B>', '<C>', 'c'], ['e', '<D>', '<B>']], # '<B>': [['$'], ['b', '<C>', '<D>', '<E>']], # '<C>': [['<D>', 'a', '<B>'], ['c', 'a']], # '<D>': [['$'], ['d', '<D>']], # '<E>': [['e', '<A>', 'f'], ['c']] # } # Initialize FIRST sets FIRST = {} for terminal in terminals: FIRST[terminal] = set([terminal]) # FIRST(terminal) = {terminal} for non_terminal in non_terminals: FIRST[non_terminal] = set() # FIRST(non_terminal) = empty set def compute_first(): changed = True while changed: changed = False # For each production LHS -> RHS for lhs in productions: for rhs in productions[lhs]: # Keep track if all previous symbols can derive epsilon nullable = True i = 0 while i < len(rhs): symbol = rhs[i] if symbol == '$': # RHS is epsilon production if '$' not in FIRST[lhs]: FIRST[lhs].add('$') changed = True break else: before_change = len(FIRST[lhs]) # Add FIRST(symbol) - epsilon to FIRST(lhs) FIRST[lhs] |= (FIRST[symbol] - set(['$'])) if '$' in FIRST[symbol]: nullable = True else: nullable = False if len(FIRST[lhs]) > before_change: changed = True if not nullable: break i += 1 else: # If we reached the end and all symbols can be nullable if nullable: if '$' not in FIRST[lhs]: FIRST[lhs].add('$') changed = True compute_first() # Print the FIRST sets print("FIRST sets:") for symbol in sorted(non_terminals): print(f"FIRST({symbol}) = {FIRST[symbol]}") from collections import deque # Start with the epsilon-closure of the start state start_state = epsilon_closure([LR1Item(augmented_start_symbol, productions[augmented_start_symbol][0], 0, '$')]) dfa_states = [] state_indices = {} transitions = {} dfa_states.append(start_state) state_indices[frozenset(start_state)] = 0 queue = deque() queue.append(0) while queue: state_index = queue.popleft() state = dfa_states[state_index] symbols = set() for item in state: if item.dot_position < len(item.rhs): symbols.add(item.rhs[item.dot_position]) for symbol in symbols: move_items = set() for item in state: if item.dot_position < len(item.rhs) and item.rhs[item.dot_position] == symbol: new_item = LR1Item(item.lhs, item.rhs, item.dot_position + 1, item.lookahead) move_items.add(new_item) # Compute the epsilon-closure of the move new_state = epsilon_closure(move_items) frozen_new_state = frozenset(new_state) if frozen_new_state not in state_indices: new_state_index = len(dfa_states) dfa_states.append(new_state) state_indices[frozen_new_state] = new_state_index queue.append(new_state_index) else: new_state_index = state_indices[frozen_new_state] transitions[(state_index, symbol)] = new_state_index productions_list = [] production_numbers = {} index = 0 for lhs in productions: for rhs in productions[lhs]: productions_list.append((lhs, rhs)) production_numbers[(lhs, tuple(rhs))] = index index += 1 action_table = {} goto_table = {} for state_index, state in enumerate(dfa_states): for item in state: if item.dot_position < len(item.rhs): symbol = item.rhs[item.dot_position] if symbol in terminals: # Shift action next_state = transitions.get((state_index, symbol)) if next_state is not None: action_key = (state_index, symbol) action_value = ('shift', next_state) if action_key in action_table and action_table[action_key] != action_value: print(f"Conflict at state {state_index}, symbol '{symbol}'") action_table[action_key] = action_value else: if item.lhs == augmented_start_symbol and item.lookahead == '$': # Accept action action_table[(state_index, '$')] = ('accept',) else: # Reduce action prod_num = production_numbers[(item.lhs, tuple(item.rhs))] action_key = (state_index, item.lookahead) action_value = ('reduce', prod_num) if action_key in action_table and action_table[action_key] != action_value: print(f"Conflict at state {state_index}, symbol '{item.lookahead}'") action_table[action_key] = action_value for symbol in non_terminals: next_state = transitions.get((state_index, symbol)) if next_state is not None: goto_table[(state_index, symbol)] = next_state print("\nStates:") for i, state in enumerate(dfa_states): print(f"State {i}:") for item in state: print(f" {item}") print("\nACTION Table:") for key in sorted(action_table.keys()): print(f"State {key[0]}, Symbol '{key[1]}': {action_table[key]}") print("\nGOTO Table:") for key in sorted(goto_table.keys()): print(f"State {key[0]}, Symbol '{key[1]}': {goto_table[key]}")Instructions for the syntax analyzer:
3.2 Sintaksni analizator Uloga sintaksnog analizatora u ovoj laboratorijskoj vježbi bit će parsiranje niza uniform- nih znakova. Drugim riječima, sintaksni analizator treba provjeravati zadovoljava li niz uniformnih znakova sintaksna pravila zadana gramatikom u Ulaznoj Datoteci i konstru- irati generativno stablo za dani program. Sintaksni analizator treba generativno stablo ispisati na standardni izlaz prema uputi u poglavlju 3.2.3. U nastavku je opisan način rada sintaksnog analizatora kojeg je potrebno ostvariti za ovu laboratorijsku vježbu. 3.2.1 Ulaz u sintaksni analizator Analizator čita niz uniformnih znakova sa standardnog ulaza. Niz uniformnih znakova bit će oblikovan identično kao izlaz iz prve laboratorijske vježbe. U ulazu će se pojavljivati isključivo oni uniformni znakovi koji su definirani kao završni znakovi gramatike u Ulaznoj Datotoeci koja je predana generatoru. Leksičke jedinke neće započinjati ili završavati zna- kom praznine ili tabom i neće se protezati kroz više redaka, ali mogu sadržavati praznine (vidi primjere). Za sam postupak sintaksne analize važni su jedino uniformni znakovi, a broj retka i leksička jedinka služe za prijavljivanje grešaka i dodatno za ispis generativnog stabla kao što je opisano u nastavku. 3.2.2 Simulator LR parsera Središnji algoritam generiranog sintaksnog analizatora je simulator LR parsera. Koristeći tablice Akcija i NovoStanje, simulator čita uniformne znakove iz niza uniformnih znakova i provjerava sintaksnu ispravnost ulaznog programa u jezični procesor. Dodatno, simulator gradi generativno stablo niza uniformnih znakova. Listovi generativnog stabla označeni su uniformnim znakovima ili epsilonom (znakom $) u slučaju da list predstavlja desnu stranu ε-produkcije. Kad bi se generativno stablo obišlo dubinskim pretraživanjem uz obradu djece s lijeva na desno i uz ispisivanje listova, opet bismo dobili (isti) niz unifor- mnih znakova (epsilon predstavlja prazan niz). Uz sam uniformni znak, list generativnog stabla treba biti označen i retkom u kojem se pripadna leksička jedinka nalazila u ulaz- nom programu i samom leksičkom jedinkom2 . Unutrašnji čvorovi generativnog stabla su označeni nezavršnim znakovima zadane gramatike. U ovoj laboratorijskoj vježbi, generativno stablo gradit će se eksplicitno. S tim ciljem, na stogu simulatora LR parsera trebaju se nalaziti čvorovi generativnog stabla (uz ostale podatke nužne za rad samog simulatora). Prilikom provodenja akcije Pomakni, simulator gradi novi list generativnog stabla i označava ga u skladu s ranijim opisom. Prilikom provodenja akcije Reduciraj, simulator gradi novi unutrašnji čvor stabla i čvorove sa stoga 1 Ovo se očito neće provjeravati pri automatskoj evaluaciji rješenja na sustavu SPRUT. Alternativno, list može biti označen i nekim drugim podacima pomoću kojih je moguće rekonstruirati ova tri podatka. 2 32koji odgovaraju uzorku za zamjenu povezuje kao djecu novog unutrašnjeg čvora. U skladu s pravilima rada simulatora LR parsera, uzorak za zamjenu uklanja se sa stoga i zamje- njuje se znakom lijeve strane produkcije uz pripadno stanje i čvor stabla. Slijedeći ovaj postupak, prilikom izvodenja akcije Prihvati, na stogu simulatora nalazit će se korijen generativnog stabla označen početnim nezavršnim znakom gramatike. 3.2.3 Ispis generativnog stabla U ovoj laboratorijskoj vježbi, sintaksni analizator na standardni izlaz treba ispisati kons- truirano generativno stablo. Ispis treba obaviti dubinskim obilaskom generativnog stabla, pri čemu se prvo ispisuje oznaka čvora roditelja, a nakon toga se ispisuju podstabla čiji korijeni su djeca čvora roditelja, s lijeva na desno. Na svakoj sljedećoj razini stabla, ispis treba prefiksirati jednim dodatnim razmakom. Pri ispisu oznaka unutrašnjih čvorova stabla treba ispisivati nezavršni znak gramatike kojim je čvor označen. Pri ispisu oznaka listova treba ispisati ili znak $ ako se radi o čvoru označenom epsilonom ili uniformni znak, broj retka i leksičku jedinku identično kao što je ista leksička jedinka opisana u ulazu analizatoru. Drugim riječima, nakon odgovarajućeg broja praznina (ovisno o dubini u generativnom stablu), treba ispisati uniformni znak, jedan znak razmaka, broj retka, jedan znak razmaka i leksičku jedinku. 3.2.4 Oporavak od pogreške Za potrebe ove laboratorijske vježbe, u simulator LR parsera treba ugraditi jednostavan postupak oporavka od pogreške traženjem sinkronizacijskog znaka. Kada naide na po- grešku u nizu uniformnih znakova, simulator treba ispisati poruku o pogrešci u kojoj su navedeni3 : 1. broj retka u kojem se pogreška dogodila 2. očekivani uniformni znakovi (oni znakovi koji ne bi izazvali pogrešku) 3. pročitani uniformni znak iz niza uniformnih znakova i odgovarajući znakovni prikaz iz izvornog koda programa (dohvaćen iz tablice znakova). Nakon ispisa pogreške, simulator treba preskočiti sve znakove u nizu uniformnih zna- kova do prvog sljedećeg sinkronizacijskog znaka. Sinkronizacijski znakovi za gramatiku definirani su u Ulaznoj Datoteci. Kada je pronašao prvi sljedeći sinkronizacijski znak, simulator sa stoga odbacuje stanja (i pripadne podatke i čvorove stabla) dok ne dode do nekog stanja s u kojem je definirana Akcija[s, sinkronizacijski znak]. Nakon toga simulator nastavlja s normalnim radom4 . 3 Ovo se neće provjeravati u automatskoj evaluaciji putem sustava SPRUT, ali se može provjeravati na usmenom odgovaranju vježbe. 4 Ovaj postupak oporavka od pogreške vrlo je jednostavan, ali očito daje i vrlo slabe rezultate, tj. za veliku većinu sintaksnih pogrešaka oporavak neće biti osobito uspješan. 333.3 Primjeri U ispisu 3.3 je prikazana Ulazna Datoteka za gramatiku sa 148. stranice udžbenika, pri čemu je izbačen nezavrnšni znak S i pripadna prva produkcija, a nezavršni znak A je postavljen za početni nezavršni znak. Znak S je u toj gramatici služio kao “novi početni nezavršni znak”, a njega sintaksni analizator iz ove vježbe samostalno dodaje. %V <A> <B> 2 %T a b 3 %Syn b 4 <A> 5 <B> <A> 6 <B> 7 a <B> 8 b 9 <A> 10 $ 1 Ispis 3.3: Ulazna Datoteka za gramatiku sa 148. stranice udžbenika. Sinkronizacijski znak je ovdje arbitrarno postavljen na b, ali na ovom primjeru nećemo promatrati oporavak od pogreške. Završni znakovi gramatike a i b predstavljaju uniformne znakove leksičkih jedinki. Primjer ulaza u sintaksni analizator generiran za prethodnu Ulaznu Datoteku prikazan je u ispisu 3.4. U primjeru su nizu uniformnih znakova arbitrarno pridruženi brojevi redaka i leksičke jedine - recimo da uniformni znak a predstavlja leksičke jedinke koje se sastoje od uzastopnih znakova x (opcionalno odvojenih prazninama), a uniformni znak b predstavlja leksičke jedinke koje se sastoje od uzastopnih znakova y (opcionalno odvojenih prazninama). a 1 x x x 2 b 2 y y 3 a 3 xx xx 4 a 4 xx xx xx 5 b 4 y 1 Ispis 3.4: Ulaz u analizator za gramatiku sa 148. stranice udžbenika. Ispis sintaksnog analizatora za dani primjer prikazan je u ispisu 3.5. Ispis prikazuje stvoreno generativno stablo u skladu s opisom u poglavlju 3.2.3. <A> <B> 3 a 1 x x x 4 <B> 5 b 2 y y 6 <A> 7 <B> 1 2 348 9 10 11 12 13 14 a 3 xx xx <B> a 4 xx xx xx <B> b 4 y <A> $ Ispis 3.5: Ispis analizatora za gramatiku sa 148. stranice udžbenika i ulaz is ispisa 3.4. Primjer Ulazne Datoteke generatora za podskup jezika C nalazi se ovdje5 . U ispisu 3.6 prikazan je “C program” sa sintaksnom pogreškom. 1 2 int x = 3 &; int y = 2; Ispis 3.6: Jednostavan C program sa sintaksnom greškom. Za prikazani program, sintaksni analizator bi na standardni ulaz dobio ulaz prikazan u nastavku. KR_INT 1 int 2 IDN 1 x 3 OP_PRIDRUZI 1 = 4 BROJ 1 3 5 OP_BIN_I 1 & 6 TOCKAZAREZ 1 ; 7 KR_INT 2 int 8 IDN 2 y 9 OP_PRIDRUZI 2 = 10 BROJ 2 2 11 TOCKAZAREZ 2 ; 1 Ispis 3.7: Ulaz za sintaksni analizator za program 3.6. Do sintaksne greške ovdje dolazi kada analizator čita uniformni znak TOCKAZAREZ koji odgovara znaku ; iz prvog retka programa6 . Kako je TOCKAZAREZ jedan od sinkronizacijskih znakova, u postupku oporavka od pogreske se ne odbacuje niti jedan uniformni znak iz ulaza. U drugom koraku postupka oporavka od pogreške sa stoga se izbacuje list stabla koji predstavlja znak OP_BIN_I tj. znak & iz ulaznog programa. Nakon izbacivanja tog znaka, parser može prihvatiti znak TOCKAZAREZ pa ga i prihvaća i nastavlja s radom, tj. postupak oporavka od pogreške je bio uspješan. Očekivani ispis analizatora može se vidjeti ovdje. 5 Za ovaj primjer generator generira ε-NKA s 3115 stanja i 6343 prijelaza iz čega nastaje DKA sa 691 stanja i 5404 prijelaza uz jedno Pomakni/Reduciraj proturječje vezano uz else dio naredbe grananja. 6 Ponovno, izvorni kod je ovdje prikazan samo kako bi bilo lakse pratiti primjer — niti jedan program u ovoj vježbi neće dobiti taj izvorni kod, već će sintaksni analizator izravno dobiti niz uniformnih znakova iz ispisa 3.7 35Svi ovi kao i nekoliko složenijih primjera nalaze se u ovoj arhivi. Za jednostavnije pri- mjere je dana i datoteka imena *_gen.txt koja sadrži dio kontrolnog ispisa generatora što možda može biti korisno kod uklanjanja pogrešaka pri razvoju generatora. U tim datote- kama su navedene izračunate relacije i generirani konačni automati, a za najjednostavniji primjer i tablice LR-parsera. Ulazne Datoteke za generator u arhivi imaju nastavak .san, a ulazi i očekivani ispisi iz analizatora imaju nastavke .in i .out. Dodatno, uz primjere je priložen i .gif ge- nerativnog stabla kako biste mogli dobiti osjećaj za to kako stablo izgleda, pogotovo za primjer podskupa jezika C što će biti važno za treću laboratorijsku vježbu. 3.4 Savjeti za implementaciju U ovom poglavlju navedene su neke napomene koje mogu pomoći u ostvarenju ove labo- ratorijske vježbe. Poglavlje će biti prošireno ako se za tim pokaže potreba u skladu sa čestim pitanjima. 3.4.1 Računanje refleksivnog tranzitivnog okruženja relacije Prilikom računanja skupova ZAPOČINJE, potrebno je izračunati relaciju ZapočinjeZnakom koja je refleksivno tranzitivno okruženje relacije ZapočinjeIzravnoZnakom. Na stranici 102 udžbenika na visokoj razini je opisano kako se spomenuto okruženje može izračunati. Ko- risno je relaciju ZapočinjeZnakom zamisliti kao usmjereni graf u kojem su znakovi čvorovi, a bridovi su članovi relacije ZapočinjeZnakom. Drugim riječima, ako i samo ako je u tablici relacije ZapočinjeZnakom za neki par znakova navedena jedinica, ti znakovi su u grafu spojeni usmjerenim bridom. Neki par znakova (X, Y) će biti u tranzitivnom okruženju dane relacije ako i samo ako u usmjerenom grafu postoji put od znaka X do znaka Y. Dodatno, s obzirom da tražimo refleksivno tranzitivno okruženje, u relaciji će biti i svi parovi (X, X). U skladu s ovom interpretacijom, postupak računanja opisan u knjizi trebalo bi po- navljati iterativno dok god se tablica nove relacije ne prestane mijenjati ili jednostavno ponoviti ga n puta gdje je n dimenzija tablice. Takoder, bilo koji drugi postupak za traženje puteva u grafu može se iskoristiti za računanje nove relacije.primjer ulaza i izlaza: in
OPERAND 2 3 OP_MINUS 2 - UMINUS 2 - OPERAND 2 0x12 OP_MINUS 2 - LIJEVA_ZAGRADA 2 ( OPERAND 4 3 OP_MINUS 4 - UMINUS 4 - UMINUS 5 - UMINUS 5 - OPERAND 5 076 DESNA_ZAGRADA 5 )out
<expr> <expr> <expr> <atom> OPERAND 2 3 OP_MINUS 2 - <atom> UMINUS 2 - <atom> OPERAND 2 0x12 OP_MINUS 2 - <atom> LIJEVA_ZAGRADA 2 ( <expr> <expr> <atom> OPERAND 4 3 OP_MINUS 4 - <atom> UMINUS 4 - <atom> UMINUS 5 - <atom> UMINUS 5 - <atom> OPERAND 5 076 DESNA_ZAGRADA 5 )san
%V <expr> <atom> %T OPERAND OP_MINUS UMINUS LIJEVA_ZAGRADA DESNA_ZAGRADA %Syn OPERAND UMINUS LIJEVA_ZAGRADA <atom> OPERAND UMINUS <atom> LIJEVA_ZAGRADA <expr> DESNA_ZAGRADA <expr> <atom> <expr> OP_MINUS <atom> - Assistant
Here's the code for the syntax analyzer, as per your requirements:
# We assume that all the previous code (from the generator) has been run and the following variables are available: # action_table, goto_table, productions_list, sync_tokens, augmented_start_symbol # Define the ParseTreeNode class class ParseTreeNode: def __init__(self, symbol, children=None, token_info=None): self.symbol = symbol # Non-terminal or terminal symbol self.children = children if children is not None else [] # List of child ParseTreeNodes self.token_info = token_info # For leaves: (token_name, line_number, lexeme) def print_tree(self, indent=0): print(' ' * indent + self.node_repr()) for child in self.children: child.print_tree(indent + 1) def node_repr(self): if self.token_info: token_name, line_number, lexeme = self.token_info return f"{token_name} {line_number} {lexeme}" else: return self.symbol # Read the tokens from standard input tokens = [] try: while True: line = input() if not line.strip(): continue parts = line.strip().split(' ', 2) if len(parts) == 3: token_name, line_number, lexeme = parts tokens.append((token_name, int(line_number), lexeme)) else: # Handle error or skip continue except EOFError: pass # Append EOF symbol to the tokens tokens.append(('$', None, None)) # We can use None for line_number and lexeme for EOF # Now, implement the syntax analyzer def syntax_analyzer(action_table, goto_table, productions_list, sync_tokens): input_index = 0 stack = [(0, None)] # Each item is a tuple (state, ParseTreeNode) errors = False # Flag to indicate if there was an error while True: state = stack[-1][0] token_name, line_number, lexeme = tokens[input_index] # Handle EOF symbol a = token_name action = action_table.get((state, a)) if action: if action[0] == 'shift': next_state = action[1] # Create a leaf node for the token node = ParseTreeNode(a, [], (a, line_number, lexeme)) stack.append((next_state, node)) input_index += 1 elif action[0] == 'reduce': production_num = action[1] lhs, rhs = productions_list[production_num] if rhs == ['$']: # Epsilon production children = [ParseTreeNode('$')] else: rhs_len = len(rhs) children = [] for _ in range(rhs_len): stack.pop() # Pop state state_node = stack.pop() children.insert(0, state_node[1]) # Insert at beginning # Now, create the new node new_node = ParseTreeNode(lhs, children) # Now, find the goto t = stack[-1][0] next_state = goto_table.get((t, lhs)) if next_state is None: # Should not happen in valid parser print(f"Error: goto not found for state {t} and symbol {lhs}") errors = True break stack.append((next_state, new_node)) elif action[0] == 'accept': # Parsing successful parse_tree_root = stack[-1][1] # Now, print the parse tree parse_tree_root.print_tree() if errors: exit(1) else: exit(0) else: # Error handling and recovery errors = True # Expected tokens expected_tokens = [sym for (st, sym) in action_table if st == state] # Read the current token current_token = tokens[input_index] token_name, line_number, lexeme = current_token print(f"Syntax error at line {line_number}: unexpected {token_name}") # Discard input symbols until a synchronization symbol is found while token_name not in sync_tokens and token_name != '$': input_index += 1 current_token = tokens[input_index] token_name, line_number, lexeme = current_token # Pop states from the stack until we find a state where action is defined for the synchronization symbol recovered = False while stack: state = stack[-1][0] action = action_table.get((state, token_name)) if action: recovered = True break else: stack.pop() if not recovered: # Cannot recover print("Cannot recover from error") break else: # Continue parsing pass # Now, call the syntax_analyzer function syntax_analyzer(action_table, goto_table, productions_list, sync_tokens)This code will read tokens from standard input, use the
action_tableandgoto_tablefrom the generator code, and simulate the LR parser as per your instructions. It builds the parse tree and outputs it in the specified format.The error handling is implemented as specified in the instructions: it reports the error, then skips tokens until a synchronization token is found, and continues parsing from there.
This code assumes that the
action_table,goto_table,productions_list, andsync_tokensare available in the global scope, as they are in the code you provided. TheParseTreeNodeclass represents nodes in the parse tree, and includes methods to print the tree recursively with proper indentation.Please make sure to integrate this code with the generator code you provided, and ensure that the variables are appropriately populated.