# # Recursive Parenthesis Matching # # # Robert D. Cameron # October 14, 2012 # import sys import pablo class Basis_bits(): bit_0 = 0 bit_1 = 0 bit_2 = 0 bit_3 = 0 bit_4 = 0 bit_5 = 0 bit_6 = 0 bit_7 = 0 class Lex (): LParen = 0 RParen = 0 class Matches() : closed = {} error = 0 def Classify_bytes(basis_bits, lex): temp1 = (basis_bits.bit_0 | basis_bits.bit_1) temp2 = (basis_bits.bit_2 &~ basis_bits.bit_3) temp3 = (temp2 &~ temp1) temp4 = (basis_bits.bit_4 &~ basis_bits.bit_5) temp5 = (basis_bits.bit_6 | basis_bits.bit_7) temp6 = (temp4 &~ temp5) lex.LParen = (temp3 & temp6) temp7 = (basis_bits.bit_7 &~ basis_bits.bit_6) temp8 = (temp4 & temp7) lex.RParen = (temp3 & temp8) def Match_Parens(lex, matches): parens = lex.LParen | lex.RParen i = 0 pscan = pablo.AdvanceThenScanTo(lex.LParen, parens) matches.closed[0] = pscan & lex.RParen all_closed = matches.closed[0] matches.error = pablo.atEOF(pscan) # Not matched, still pending. pending_LParen = pscan & lex.LParen RParen_unmatched = lex.RParen &~ matches.closed[0] inPlay = pending_LParen | RParen_unmatched while pending_LParen: i += 1 pscan = pablo.AdvanceThenScanTo(pending_LParen, inPlay) matches.closed[i] = pscan & lex.RParen all_closed |= matches.closed[i] matches.error |= pablo.atEOF(pscan) pending_LParen = pscan & lex.LParen RParen_unmatched = lex.RParen &~ all_closed inPlay = pending_LParen | RParen_unmatched # # Any closing paren that was not actually used to close # an opener is in error. matches.error |= lex.RParen &~ all_closed def Match_Parens0(lex, matches): parens = lex.LParen | lex.RParen Lscan = {} Rscan = {} i = 0 Lscan[0] = pablo.AdvanceThenScanTo(lex.LParen, parens) Rscan[0] = pablo.AdvanceThenScanTo(lex.RParen, parens) matches.closed[0] = Lscan[0] & lex.RParen matches.error = pablo.atEOF(Lscan[0]) unclosed = Lscan[i] & lex.LParen | Rscan[i] & lex.RParen all_closed = matches.closed[i] while unclosed: i += 1 unclosedLParen = unclosed & lex.LParen unclosedRParen = unclosed & lex.RParen Lscan[i] = pablo.AdvanceThenScanTo(unclosedLParen, unclosed) Rscan[i] = pablo.AdvanceThenScanTo(unclosedRParen, unclosed) matches.closed[i] = Lscan[i] & lex.RParen matches.error |= pablo.atEOF(Lscan[i]) unclosed = Lscan[i] & lex.LParen | Rscan[i] & lex.RParen all_closed |= matches.closed[i] # # Any closing paren that was not actually used to close # an opener is in error. matches.error |= lex.RParen &~ all_closed basis_bits = Basis_bits() lex = Lex() matches = Matches() if __name__ == "__main__": #print "Starting ..." if len(sys.argv) > 1: u8data = pablo.readfile(sys.argv[1]) pablo.EOF_mask = pablo.transpose_streams(u8data, basis_bits) Classify_bytes(basis_bits, lex) Match_Parens(lex, matches) lgth = len(u8data) print "data:" + " "*(16-5) + u8data i = 0 while i in matches.closed.keys(): f = "closed[%i]" % i print f + (" ") + pablo.bitstream2string(matches.closed[i], lgth) i+=1 print "errors" + " "*(16-6) + pablo.bitstream2string(matches.error, lgth+1) else: print("Usage: python parenmatch.py ")