← Back to branch summary

~ubuntu-branches/ubuntu/karmic/pypy/karmic

« back to all changes in this revision

Viewing changes to pypy/rlib/parsing/test/test_deterministic.py

  • Committer: Bazaar Package Importer
  • Author(s): Alexandre Fayolle
  • Date: 2007-04-13 09:33:09 UTC
  • Revision ID: james.westby@ubuntu.com-20070413093309-yoojh4jcoocu2krz
Tags: upstream-1.0.0
Import upstream version 1.0.0

Show diffs side-by-side

added added

removed removed

Lines of Context:
pypy/rlib/parsing/test/test_deterministic.py
 
1
from pypy.rlib.parsing.deterministic import *
 
2
 
 
3
def test_DFA_simple():
 
4
    a = DFA()
 
5
    s0 = a.add_state("start")
 
6
    s1 = a.add_state()
 
7
    s2 = a.add_state(final=True)
 
8
    a[s0, "a"] = s0
 
9
    a[s0, "c"] = s1
 
10
    a[s0, "b"] = s2
 
11
    a[s1, "b"] = s2
 
12
    r = DFARunner(a)
 
13
    assert r.recognize("aaaaaaaaaab")
 
14
    assert r.recognize("b")
 
15
    assert not r.recognize("a")
 
16
    assert not r.recognize("xyza")
 
17
    assert r.recognize("aaaacb")
 
18
    recognize = a.make_code()
 
19
    assert recognize("aaaaaaaaaab")
 
20
    assert recognize("b")
 
21
    assert py.test.raises(LexerError, "recognize('a')")
 
22
    assert py.test.raises(LexerError, "recognize('xzya')")
 
23
    assert recognize("aaaacb")
 
24
 
 
25
def test_compile_recognizer():
 
26
    try:
 
27
        from pypy.translator.interactive import Translation
 
28
    except ImportError:
 
29
        py.test.skip("pypy not found on path")
 
30
    a = DFA()
 
31
    s0 = a.add_state("start")
 
32
    s1 = a.add_state()
 
33
    s2 = a.add_state(final=True)
 
34
    a[s0, "a"] = s0
 
35
    a[s0, "c"] = s1
 
36
    a[s0, "b"] = s2
 
37
    a[s1, "b"] = s2
 
38
    recognize = a.make_code()
 
39
    t = Translation(recognize)
 
40
    t.backendopt([str], backend="c")
 
41
    cfn = t.compile_c()
 
42
    assert cfn("aaaaaaaaaab")
 
43
    assert cfn("b")
 
44
    assert cfn("aaaacb")
 
45
 
 
46
def test_NFA_simple():
 
47
    a = NFA()
 
48
    z0 = a.add_state("z0", start=True)
 
49
    z1 = a.add_state("z1", start=True)
 
50
    z2 = a.add_state("z2", final=True)
 
51
    a.add_transition(z0, z0, "0")
 
52
    a.add_transition(z0, z1, "0")
 
53
    a.add_transition(z0, z0, "1")
 
54
    a.add_transition(z1, z2, "0")
 
55
    r = SetNFARunner(a)
 
56
    assert r.recognize("0")
 
57
    assert r.recognize("100")
 
58
    assert r.recognize("00")
 
59
    assert r.recognize("110100100100100")
 
60
    assert not r.recognize("11010010010010")
 
61
    assert not r.recognize("")
 
62
    assert not r.recognize("100101101111")
 
63
    r = BacktrackingNFARunner(a)
 
64
    assert r.recognize("0")
 
65
    assert r.recognize("100")
 
66
    assert r.recognize("00")
 
67
    assert r.recognize("110100100100100")
 
68
    assert not r.recognize("11010010010010")
 
69
    assert not r.recognize("")
 
70
    assert not r.recognize("100101101111")
 
71
 
 
72
def test_NFA_with_epsilon():
 
73
    a = NFA()
 
74
    z0 = a.add_state("z0", start=True)
 
75
    z1 = a.add_state("z1")
 
76
    z2 = a.add_state("z2", final=True)
 
77
    a.add_transition(z0, z1)
 
78
    a.add_transition(z0, z1, "a")
 
79
    a.add_transition(z1, z2, "b")
 
80
    r = SetNFARunner(a)
 
81
    assert r.recognize("b")
 
82
    assert r.recognize("ab")
 
83
    assert not r.recognize("cab")
 
84
    r = BacktrackingNFARunner(a)
 
85
    assert r.recognize("b")
 
86
    assert r.recognize("ab")
 
87
    assert not r.recognize("cab")
 
88
    fda = a.make_deterministic()
 
89
    r = fda.get_runner()
 
90
 
 
91
def test_NFA_to_DFA_simple():
 
92
    a = NFA()
 
93
    z0 = a.add_state("z0", start=True)
 
94
    z1 = a.add_state("z1", start=True)
 
95
    z2 = a.add_state("z2", final=True)
 
96
    a.add_transition(z0, z0, "0")
 
97
    a.add_transition(z0, z1, "0")
 
98
    a.add_transition(z0, z0, "1")
 
99
    a.add_transition(z1, z2, "0")
 
100
    fda = a.make_deterministic()
 
101
    r = DFARunner(fda)
 
102
    assert r.recognize("0")
 
103
    assert r.recognize("100")
 
104
    assert r.recognize("00")
 
105
    assert r.recognize("110100100100100")
 
106
    assert not r.recognize("11010010010010")
 
107
    assert not r.recognize("")
 
108
    assert not r.recognize("100101101111")
 
109
 
 
110
def test_simplify():
 
111
    #py.test.skip("optimize not working yet")
 
112
    a = DFA()
 
113
    z0 = a.add_state("z0")
 
114
    z1 = a.add_state("z1")
 
115
    z2 = a.add_state("z2")
 
116
    z3 = a.add_state("z3")
 
117
    z4 = a.add_state("z4", final=True)
 
118
    a[z0, "1"] = z2
 
119
    a[z0, "0"] = z1
 
120
    a[z1, "1"] = z2
 
121
    a[z1, "0"] = z4
 
122
    a[z2, "1"] = z2
 
123
    a[z2, "0"] = z3
 
124
    a[z3, "0"] = z4
 
125
    a[z3, "1"] = z0
 
126
    a[z4, "0"] = z4
 
127
    a[z4, "1"] = z4
 
128
    a.optimize()
 
129
    r = a.get_runner()
 
130
    assert r.recognize("11111100")
 
131
    assert r.recognize("01001010011100")
 
132
    assert not r.recognize("0")
 
133
    assert r.recognize("00")
 
134
    assert not r.recognize("111111011111111")
 
135
    newa = eval(repr(a))
 
136
    r = newa.get_runner()
 
137
    assert r.recognize("11111100")
 
138
    assert r.recognize("01001010011100")
 
139
    assert not r.recognize("0")
 
140
    assert r.recognize("00")
 
141
    assert not r.recognize("111111011111111")
 
142
 
 
143
def test_something():
 
144
    a = NFA()
 
145
    z0 = a.add_state("z0", start=True, final=True)
 
146
    z1 = a.add_state("z1")
 
147
    z2 = a.add_state("z2", start=True, final=True)
 
148
    a.add_transition(z0, z1, "a")
 
149
    a.add_transition(z1, z0, "b")
 
150
    a.add_transition(z1, z1, "a")
 
151
    a.add_transition(z1, z1, "b")
 
152
    a.add_transition(z1, z2, "a")
 
153
    fda = a.make_deterministic()
 
154
    
 
155
def test_compress_char_set():
 
156
    assert compress_char_set("ace") == [('a', 1), ('c', 1), ('e', 1)]
 
157
    assert compress_char_set("abcdefg") == [('a', 7)]
 
158
    assert compress_char_set("ABCabc") == [('A', 3), ('a', 3)]