#
# 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 ")