Hello PyPy community,
Looks like I have a patch that somehow simplifies automatas generated
by pypy.interpreter.pyparser.{pylexer,genpytokenize}. It's rather
obvious patch that enables:
* Comparing labels in right order;
* Checking for loops;
* Checking for mutual links.
It is mathematically correct, although it does NOT produce minimal
automata in some cases. It reduces number of resulting states, though.
I'm having troubles with pytest (no such option: --assertmode) so I
could not test it.
If someone could test it and commit it, I'd be happy.
If unit tests are required, I'll write 'em.
diff -r 46df7b0c481f pypy/interpreter/pyparser/pylexer.py
--- a/pypy/interpreter/pyparser/pylexer.py Wed Mar 14 20:39:08 2012 -0700
+++ b/pypy/interpreter/pyparser/pylexer.py Thu Mar 15 12:02:24 2012 +0400
@@ -165,18 +165,22 @@
# ______________________________________________________________________
-def sameState (s1, s2):
- """sameState(s1, s2)
+def sameState (s1, s2, n1, n2):
+ """sameState(s1, s2, n1, n2)
Note:
state := [ nfaclosure : Long, [ arc ], accept : Boolean ]
+ n : Int, index of corresponding state
arc := [ label, arrow : Int, nfaClosure : Long ]
"""
if (len(s1[1]) != len(s2[1])) or (s1[2] != s2[2]):
return False
- for arcIndex in range(0, len(s1[1])):
- arc1 = s1[1][arcIndex]
- arc2 = s2[1][arcIndex]
- if arc1[:-1] != arc2[:-1]:
+ for arc1, arc2 in zip(sorted(s1[1]), sorted(s2[1])):
+ if arc1[0] != arc2[0]:
+ return False
+ if arc1[1] == arc2[1] or (arc1[1] == n1 and arc2[1] == n2 or
+ arc1[1] == n2 and arc2[1] == n1):
+ pass
+ else:
return False
return True
@@ -195,7 +199,7 @@
for j in range(0, i):
if j in deletedStates:
continue
- if sameState(tempStates[i], tempStates[j]):
+ if sameState(tempStates[i], tempStates[j], i, j):
deletedStates.append(i)
for k in range(0, len(tempStates)):
if k in deletedStates:
diff -r 46df7b0c481f pypy/interpreter/pyparser/pytokenize.py
--- a/pypy/interpreter/pyparser/pytokenize.py Wed Mar 14 20:39:08 2012 -0700
+++ b/pypy/interpreter/pyparser/pytokenize.py Thu Mar 15 12:02:24 2012 +0400
@@ -26,9 +26,8 @@
accepts = [True, True, True, True, True, True, True, True,
True, True, False, True, True, True, True, False,
False, False, True, False, False, True, False,
- False, True, False, True, False, True, False,
- False, True, False, False, True, True, True,
- False, False, True, False, False, False, True]
+ False, True, False, False, True, False, False,
+ True, False, False, True, True, True, False, True]
states = [
# 0
{'\t': 0, '\n': 13, '\x0c': 0,
@@ -123,9 +122,9 @@
'J': 13, 'L': 13, 'e': 25, 'j': 13,
'l': 13},
# 6
- {'0': 26, '1': 26, '2': 26, '3': 26,
- '4': 26, '5': 26, '6': 26, '7': 26,
- '8': 26, '9': 26},
+ {'0': 24, '1': 24, '2': 24, '3': 24,
+ '4': 24, '5': 24, '6': 24, '7': 24,
+ '8': 24, '9': 24},
# 7
{'*': 12, '=': 13},
# 8
@@ -143,25 +142,25 @@
# 14
{'\n': 13},
# 15
- {automata.DEFAULT: 30, '\n': 27,
- '\r': 27, "'": 28, '\\': 29},
+ {automata.DEFAULT: 29, '\n': 26,
+ '\r': 26, "'": 27, '\\': 28},
# 16
- {automata.DEFAULT: 33, '\n': 27,
- '\r': 27, '"': 31, '\\': 32},
+ {automata.DEFAULT: 32, '\n': 26,
+ '\r': 26, '"': 30, '\\': 31},
# 17
{'\n': 13, '\r': 14},
# 18
- {automata.DEFAULT: 18, '\n': 27, '\r': 27},
+ {automata.DEFAULT: 18, '\n': 26, '\r': 26},
# 19
+ {'0': 33, '1': 33, '2': 33, '3': 33,
+ '4': 33, '5': 33, '6': 33, '7': 33,
+ '8': 33, '9': 33, 'A': 33, 'B': 33,
+ 'C': 33, 'D': 33, 'E': 33, 'F': 33,
+ 'a': 33, 'b': 33, 'c': 33, 'd': 33,
+ 'e': 33, 'f': 33},
+ # 20
{'0': 34, '1': 34, '2': 34, '3': 34,
- '4': 34, '5': 34, '6': 34, '7': 34,
- '8': 34, '9': 34, 'A': 34, 'B': 34,
- 'C': 34, 'D': 34, 'E': 34, 'F': 34,
- 'a': 34, 'b': 34, 'c': 34, 'd': 34,
- 'e': 34, 'f': 34},
- # 20
- {'0': 35, '1': 35, '2': 35, '3': 35,
- '4': 35, '5': 35, '6': 35, '7': 35},
+ '4': 34, '5': 34, '6': 34, '7': 34},
# 21
{'.': 24, '0': 21, '1': 21, '2': 21,
'3': 21, '4': 21, '5': 21, '6': 21,
@@ -169,7 +168,7 @@
'J': 13, 'L': 13, 'e': 25, 'j': 13,
'l': 13},
# 22
- {'0': 36, '1': 36},
+ {'0': 35, '1': 35},
# 23
{'.': 24, '0': 23, '1': 23, '2': 23,
'3': 23, '4': 23, '5': 23, '6': 23,
@@ -178,132 +177,101 @@
# 24
{'0': 24, '1': 24, '2': 24, '3': 24,
'4': 24, '5': 24, '6': 24, '7': 24,
- '8': 24, '9': 24, 'E': 37, 'J': 13,
- 'e': 37, 'j': 13},
+ '8': 24, '9': 24, 'E': 25, 'J': 13,
+ 'e': 25, 'j': 13},
# 25
- {'+': 38, '-': 38, '0': 39, '1': 39,
- '2': 39, '3': 39, '4': 39, '5': 39,
- '6': 39, '7': 39, '8': 39, '9': 39},
+ {'+': 36, '-': 36, '0': 37, '1': 37,
+ '2': 37, '3': 37, '4': 37, '5': 37,
+ '6': 37, '7': 37, '8': 37, '9': 37},
# 26
- {'0': 26, '1': 26, '2': 26, '3': 26,
- '4': 26, '5': 26, '6': 26, '7': 26,
- '8': 26, '9': 26, 'E': 37, 'J': 13,
- 'e': 37, 'j': 13},
+ {},
# 27
- {},
+ {"'": 13},
# 28
- {"'": 13},
+ {automata.DEFAULT: 29, '\n': 13, '\r': 14},
# 29
- {automata.DEFAULT: 40, '\n': 13, '\r': 14},
+ {automata.DEFAULT: 29, '\n': 26,
+ '\r': 26, "'": 13, '\\': 28},
# 30
- {automata.DEFAULT: 30, '\n': 27,
- '\r': 27, "'": 13, '\\': 29},
+ {'"': 13},
# 31
- {'"': 13},
+ {automata.DEFAULT: 32, '\n': 13, '\r': 14},
# 32
- {automata.DEFAULT: 41, '\n': 13, '\r': 14},
+ {automata.DEFAULT: 32, '\n': 26,
+ '\r': 26, '"': 13, '\\': 31},
# 33
- {automata.DEFAULT: 33, '\n': 27,
- '\r': 27, '"': 13, '\\': 32},
+ {'0': 33, '1': 33, '2': 33, '3': 33,
+ '4': 33, '5': 33, '6': 33, '7': 33,
+ '8': 33, '9': 33, 'A': 33, 'B': 33,
+ 'C': 33, 'D': 33, 'E': 33, 'F': 33,
+ 'L': 13, 'a': 33, 'b': 33, 'c': 33,
+ 'd': 33, 'e': 33, 'f': 33, 'l': 13},
# 34
{'0': 34, '1': 34, '2': 34, '3': 34,
'4': 34, '5': 34, '6': 34, '7': 34,
- '8': 34, '9': 34, 'A': 34, 'B': 34,
- 'C': 34, 'D': 34, 'E': 34, 'F': 34,
- 'L': 13, 'a': 34, 'b': 34, 'c': 34,
- 'd': 34, 'e': 34, 'f': 34, 'l': 13},
+ 'L': 13, 'l': 13},
# 35
- {'0': 35, '1': 35, '2': 35, '3': 35,
- '4': 35, '5': 35, '6': 35, '7': 35,
- 'L': 13, 'l': 13},
+ {'0': 35, '1': 35, 'L': 13, 'l': 13},
# 36
- {'0': 36, '1': 36, 'L': 13, 'l': 13},
+ {'0': 37, '1': 37, '2': 37, '3': 37,
+ '4': 37, '5': 37, '6': 37, '7': 37,
+ '8': 37, '9': 37},
# 37
- {'+': 42, '-': 42, '0': 43, '1': 43,
- '2': 43, '3': 43, '4': 43, '5': 43,
- '6': 43, '7': 43, '8': 43, '9': 43},
- # 38
- {'0': 39, '1': 39, '2': 39, '3': 39,
- '4': 39, '5': 39, '6': 39, '7': 39,
- '8': 39, '9': 39},
- # 39
- {'0': 39, '1': 39, '2': 39, '3': 39,
- '4': 39, '5': 39, '6': 39, '7': 39,
- '8': 39, '9': 39, 'J': 13, 'j': 13},
- # 40
- {automata.DEFAULT: 40, '\n': 27,
- '\r': 27, "'": 13, '\\': 29},
- # 41
- {automata.DEFAULT: 41, '\n': 27,
- '\r': 27, '"': 13, '\\': 32},
- # 42
- {'0': 43, '1': 43, '2': 43, '3': 43,
- '4': 43, '5': 43, '6': 43, '7': 43,
- '8': 43, '9': 43},
- # 43
- {'0': 43, '1': 43, '2': 43, '3': 43,
- '4': 43, '5': 43, '6': 43, '7': 43,
- '8': 43, '9': 43, 'J': 13, 'j': 13},
+ {'0': 37, '1': 37, '2': 37, '3': 37,
+ '4': 37, '5': 37, '6': 37, '7': 37,
+ '8': 37, '9': 37, 'J': 13, 'j': 13},
]
pseudoDFA = automata.DFA(states, accepts)
-accepts = [False, False, False, False, False, True]
+accepts = [False, False, False, False, True]
states = [
# 0
{automata.DEFAULT: 0, '"': 1, '\\': 2},
# 1
- {automata.DEFAULT: 4, '"': 3, '\\': 2},
+ {automata.DEFAULT: 0, '"': 3, '\\': 2},
# 2
- {automata.DEFAULT: 4},
+ {automata.DEFAULT: 0},
# 3
- {automata.DEFAULT: 4, '"': 5, '\\': 2},
+ {automata.DEFAULT: 0, '"': 4, '\\': 2},
# 4
- {automata.DEFAULT: 4, '"': 1, '\\': 2},
- # 5
- {automata.DEFAULT: 4, '"': 5, '\\': 2},
+ {automata.DEFAULT: 0, '"': 4, '\\': 2},
]
double3DFA = automata.NonGreedyDFA(states, accepts)
-accepts = [False, False, False, False, False, True]
+accepts = [False, False, False, False, True]
states = [
# 0
{automata.DEFAULT: 0, "'": 1, '\\': 2},
# 1
- {automata.DEFAULT: 4, "'": 3, '\\': 2},
+ {automata.DEFAULT: 0, "'": 3, '\\': 2},
# 2
- {automata.DEFAULT: 4},
+ {automata.DEFAULT: 0},
# 3
- {automata.DEFAULT: 4, "'": 5, '\\': 2},
+ {automata.DEFAULT: 0, "'": 4, '\\': 2},
# 4
- {automata.DEFAULT: 4, "'": 1, '\\': 2},
- # 5
- {automata.DEFAULT: 4, "'": 5, '\\': 2},
+ {automata.DEFAULT: 0, "'": 4, '\\': 2},
]
single3DFA = automata.NonGreedyDFA(states, accepts)
-accepts = [False, True, False, False]
+accepts = [False, True, False]
states = [
# 0
{automata.DEFAULT: 0, "'": 1, '\\': 2},
# 1
{},
# 2
- {automata.DEFAULT: 3},
- # 3
- {automata.DEFAULT: 3, "'": 1, '\\': 2},
+ {automata.DEFAULT: 0},
]
singleDFA = automata.DFA(states, accepts)
-accepts = [False, True, False, False]
+accepts = [False, True, False]
states = [
# 0
{automata.DEFAULT: 0, '"': 1, '\\': 2},
# 1
{},
# 2
- {automata.DEFAULT: 3},
- # 3
- {automata.DEFAULT: 3, '"': 1, '\\': 2},
+ {automata.DEFAULT: 0},
]
doubleDFA = automata.DFA(states, accepts)
_______________________________________________
pypy-dev mailing list
[email protected]
http://mail.python.org/mailman/listinfo/pypy-dev
