1 | # |
---|
2 | # Recursive Parenthesis Matching |
---|
3 | # |
---|
4 | # |
---|
5 | # Robert D. Cameron |
---|
6 | # October 14, 2012 |
---|
7 | # |
---|
8 | import sys |
---|
9 | import pablo |
---|
10 | |
---|
11 | class Basis_bits(): |
---|
12 | bit_0 = 0 |
---|
13 | bit_1 = 0 |
---|
14 | bit_2 = 0 |
---|
15 | bit_3 = 0 |
---|
16 | bit_4 = 0 |
---|
17 | bit_5 = 0 |
---|
18 | bit_6 = 0 |
---|
19 | bit_7 = 0 |
---|
20 | |
---|
21 | class Lex (): |
---|
22 | LParen = 0 |
---|
23 | RParen = 0 |
---|
24 | |
---|
25 | class Matches() : |
---|
26 | closed = {} |
---|
27 | error = 0 |
---|
28 | |
---|
29 | |
---|
30 | def Classify_bytes(basis_bits, lex): |
---|
31 | temp1 = (basis_bits.bit_0 | basis_bits.bit_1) |
---|
32 | temp2 = (basis_bits.bit_2 &~ basis_bits.bit_3) |
---|
33 | temp3 = (temp2 &~ temp1) |
---|
34 | temp4 = (basis_bits.bit_4 &~ basis_bits.bit_5) |
---|
35 | temp5 = (basis_bits.bit_6 | basis_bits.bit_7) |
---|
36 | temp6 = (temp4 &~ temp5) |
---|
37 | lex.LParen = (temp3 & temp6) |
---|
38 | temp7 = (basis_bits.bit_7 &~ basis_bits.bit_6) |
---|
39 | temp8 = (temp4 & temp7) |
---|
40 | lex.RParen = (temp3 & temp8) |
---|
41 | |
---|
42 | def Match_Parens(lex, matches): |
---|
43 | unmatched = lex.RParen |
---|
44 | pscan = {} |
---|
45 | qscan = {} |
---|
46 | i = 0 |
---|
47 | pscan[0] = pablo.ScanTo(pablo.Advance(lex.LParen), lex.LParen | lex.RParen) |
---|
48 | qscan[0] = pablo.ScanTo(pablo.Advance(lex.RParen), lex.LParen | lex.RParen) |
---|
49 | matches.closed[i] = pscan[i] & lex.RParen |
---|
50 | unclosed = pscan[i] & lex.LParen | qscan[i] & lex.RParen |
---|
51 | matches.error = pscan[i] &~ pablo.EOF_mask |
---|
52 | all_closed = matches.closed[i] |
---|
53 | while unclosed: |
---|
54 | i += 1 |
---|
55 | pscan[i] = pablo.ScanTo(pablo.Advance(unclosed & lex.LParen), unclosed) |
---|
56 | qscan[i] = pablo.ScanTo(pablo.Advance(unclosed & lex.RParen), unclosed) |
---|
57 | matches.closed[i] = pscan[i] & lex.RParen |
---|
58 | unclosed = pscan[i] & lex.LParen | qscan[i] & lex.RParen |
---|
59 | all_closed |= matches.closed[i] |
---|
60 | matches.error |= pscan[i] &~ pablo.EOF_mask |
---|
61 | # |
---|
62 | # Any closing paren that was not actually used to close |
---|
63 | # an opener is in error. |
---|
64 | matches.error |= lex.RParen &~ all_closed |
---|
65 | |
---|
66 | |
---|
67 | |
---|
68 | |
---|
69 | basis_bits = Basis_bits() |
---|
70 | lex = Lex() |
---|
71 | matches = Matches() |
---|
72 | |
---|
73 | if __name__ == "__main__": |
---|
74 | #print "Starting ..." |
---|
75 | if len(sys.argv) > 1: |
---|
76 | u8data = pablo.readfile(sys.argv[1]) |
---|
77 | pablo.EOF_mask = pablo.transpose_streams(u8data, basis_bits) |
---|
78 | Classify_bytes(basis_bits, lex) |
---|
79 | Match_Parens(lex, matches) |
---|
80 | lgth = len(u8data) |
---|
81 | print "data:" + " "*(16-5) + u8data |
---|
82 | i = 0 |
---|
83 | while i in matches.closed.keys(): |
---|
84 | f = "closed[%i]" % i |
---|
85 | print f + (" ") + pablo.bitstream2string(matches.closed[i], lgth) |
---|
86 | i+=1 |
---|
87 | print "errors" + " "*(16-6) + pablo.bitstream2string(matches.error, lgth+1) |
---|
88 | |
---|
89 | else: |
---|
90 | print("Usage: python parenmatch.py <file>") |
---|
91 | |
---|
92 | |
---|
93 | |
---|