# # 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 = 0 instring = 0 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 pscan = pablo.AdvanceThenScanTo(lex.LParen, parens) matches.closed = pscan & lex.RParen matches.instring = pablo.ExclusiveSpan(lex.LParen, pscan) matches.error = pablo.atEOF(pscan) # Not matched, still pending. pending_LParen = pscan & lex.LParen RParen_unmatched = lex.RParen &~ matches.closed inPlay = pending_LParen | RParen_unmatched while pending_LParen: pscan = pablo.AdvanceThenScanTo(pending_LParen, inPlay) matches.instring |= pablo.SpanUpTo(pending_LParen, pscan) matches.closed |= pscan & lex.RParen matches.error |= pablo.atEOF(pscan) pending_LParen = pscan & lex.LParen RParen_unmatched = lex.RParen &~ matches.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 &~ matches.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 print "errors" + " "*(16-6) + pablo.bitstream2string(matches.error, lgth+1) print "instring:" + " "*(16-9) + pablo.bitstream2string(matches.instring, lgth) else: print("Usage: python parenmatch.py ")