aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorSérgio Queiroz <sqmedeiros@gmail.com>2017-12-15 13:50:35 -0300
committerSérgio Queiroz <sqmedeiros@gmail.com>2017-12-15 13:50:35 -0300
commitbc071e9fe431347832fd424eb327357f38e60bfd (patch)
tree9a34ad8d53074b002322484504e756b542b3bdf7
parent26c1b9aa78e10b2ed2d36d151033fe94254fa8c5 (diff)
downloadlpeglabel-bc071e9fe431347832fd424eb327357f38e60bfd.tar.gz
lpeglabel-bc071e9fe431347832fd424eb327357f38e60bfd.tar.bz2
lpeglabel-bc071e9fe431347832fd424eb327357f38e60bfd.zip
Updating the recovery mechanism when a label is thrown
-rw-r--r--lpcode.c37
-rw-r--r--lptree.c32
-rw-r--r--lptree.h1
-rw-r--r--lptree.obin0 -> 35552 bytes
-rw-r--r--lpvm.c25
-rw-r--r--lpvm.h3
-rw-r--r--lpvm.obin0 -> 7760 bytes
-rw-r--r--testlabel.lua139
8 files changed, 136 insertions, 101 deletions
diff --git a/lpcode.c b/lpcode.c
index d67d42f..82b8830 100644
--- a/lpcode.c
+++ b/lpcode.c
@@ -459,7 +459,9 @@ int sizei (const Instruction *i) {
459 case IOpenCall: case ICommit: case IPartialCommit: case IBackCommit: 459 case IOpenCall: case ICommit: case IPartialCommit: case IBackCommit:
460 return 2; 460 return 2;
461 case IThrow: /* labeled failure */ 461 case IThrow: /* labeled failure */
462 return 1; 462 return 2;
463 case IThrowRec: /* labeled failure */
464 return 3;
463 case IRecov: case ILabChoice: 465 case IRecov: case ILabChoice:
464 return (CHARSETINSTSIZE - 1) + 2; /* labeled failure */ 466 return (CHARSETINSTSIZE - 1) + 2; /* labeled failure */
465 467
@@ -519,15 +521,6 @@ static int addinstruction (CompileState *compst, Opcode op, int aux) {
519 return i; 521 return i;
520} 522}
521 523
522/* labeled failure */
523static int addthrowinstruction (CompileState *compst, int aux, int key) {
524 int i = addinstruction(compst, IThrow, aux);
525 getinstr(compst, i).i.key = key;
526 return i;
527}
528
529/* labeled failure */
530
531 524
532/* 525/*
533** Add an instruction followed by space for an offset (to be set later) 526** Add an instruction followed by space for an offset (to be set later)
@@ -541,6 +534,22 @@ static int addoffsetinst (CompileState *compst, Opcode op) {
541} 534}
542 535
543 536
537/* labeled failure */
538static void codethrow (CompileState *compst, TTree *throw) {
539 int recov, aux;
540 if (throw->u.s.ps != 0) {
541 recov = addoffsetinst(compst, IThrowRec);
542 } else {
543 recov = addinstruction(compst, IThrow, 0);
544 }
545 aux = nextinstruction(compst);
546 getinstr(compst, aux).i.key = throw->key; /* next instruction keeps only rule name */
547 getinstr(compst, recov).i.key = sib2(throw)->cap; /* rule number */
548 assert(sib2(throw)->tag == TRule);
549}
550/* labeled failure */
551
552
544/* 553/*
545** Set the offset of an instruction 554** Set the offset of an instruction
546*/ 555*/
@@ -920,7 +929,13 @@ static void correctcalls (CompileState *compst, int *positions,
920 else 929 else
921 code[i].i.code = ICall; 930 code[i].i.code = ICall;
922 jumptothere(compst, i, rule); /* call jumps to respective rule */ 931 jumptothere(compst, i, rule); /* call jumps to respective rule */
932 } else if (code[i].i.code == IThrowRec) {
933 int n = code[i].i.key; /* rule number */
934 int rule = positions[n]; /* rule position */
935 assert(rule == from || code[rule - 1].i.code == IRet);
936 jumptothere(compst, i, rule); /* call jumps to respective rule */
923 } 937 }
938
924 } 939 }
925 assert(i == to); 940 assert(i == to);
926} 941}
@@ -1008,7 +1023,7 @@ static void codegen (CompileState *compst, TTree *tree, int opt, int tt,
1008 /*printf("TThrow %s top %d\n", lua_typename(compst->L, -1), lua_gettop(compst->L));*/ 1023 /*printf("TThrow %s top %d\n", lua_typename(compst->L, -1), lua_gettop(compst->L));*/
1009 /*lua_rawgeti(compst->L, -1, tree->key);*/ 1024 /*lua_rawgeti(compst->L, -1, tree->key);*/
1010 /*printf("Throw2 lab = %s\n", lua_tostring(compst->L, -1));*/ 1025 /*printf("Throw2 lab = %s\n", lua_tostring(compst->L, -1));*/
1011 addthrowinstruction(compst, (byte) tree->u.label, tree->key); 1026 codethrow(compst, tree);
1012 break; 1027 break;
1013 } 1028 }
1014 case TRecov: { /* labeled failure */ 1029 case TRecov: { /* labeled failure */
diff --git a/lptree.c b/lptree.c
index fea2ecf..1e8de3e 100644
--- a/lptree.c
+++ b/lptree.c
@@ -52,20 +52,24 @@ static const char *val2str (lua_State *L, int idx) {
52** translate a key to its rule address in the tree. Raises an 52** translate a key to its rule address in the tree. Raises an
53** error if key does not exist. 53** error if key does not exist.
54*/ 54*/
55static void fixonecall (lua_State *L, int postable, TTree *g, TTree *t) { 55static void fixonecall (lua_State *L, int postable, TTree *g, TTree *t, byte tag) { /* labeled failure */
56 int n; 56 int n;
57 lua_rawgeti(L, -1, t->key); /* get rule's name */ 57 lua_rawgeti(L, -1, t->key); /* get rule's name */
58 lua_gettable(L, postable); /* query name in position table */ 58 lua_gettable(L, postable); /* query name in position table */
59 n = lua_tonumber(L, -1); /* get (absolute) position */ 59 n = lua_tonumber(L, -1); /* get (absolute) position */
60 lua_pop(L, 1); /* remove position */ 60 lua_pop(L, 1); /* remove position */
61 if (n == 0) { /* no position? */ 61 if (tag == TOpenCall) {
62 lua_rawgeti(L, -1, t->key); /* get rule's name again */ 62 if (n == 0) { /* no position? */
63 luaL_error(L, "rule '%s' undefined in given grammar", val2str(L, -1)); 63 lua_rawgeti(L, -1, t->key); /* get rule's name again */
64 luaL_error(L, "rule '%s' undefined in given grammar", val2str(L, -1));
65 }
66 t->tag = TCall;
67 t->u.s.ps = n - (t - g); /* position relative to node */
68 assert(sib2(t)->tag == TRule);
69 sib2(t)->key = t->key; /* fix rule's key */
70 } else if (n != 0) { /* labeled failure */
71 t->u.s.ps = n - (t - g); /* position relative to node */
64 } 72 }
65 t->tag = TCall;
66 t->u.s.ps = n - (t - g); /* position relative to node */
67 assert(sib2(t)->tag == TRule);
68 sib2(t)->key = t->key; /* fix rule's key */
69} 73}
70 74
71 75
@@ -105,13 +109,18 @@ static void finalfix (lua_State *L, int postable, TTree *g, TTree *t) {
105 return; 109 return;
106 case TOpenCall: { 110 case TOpenCall: {
107 if (g != NULL) /* inside a grammar? */ 111 if (g != NULL) /* inside a grammar? */
108 fixonecall(L, postable, g, t); 112 fixonecall(L, postable, g, t, TOpenCall);
109 else { /* open call outside grammar */ 113 else { /* open call outside grammar */
110 lua_rawgeti(L, -1, t->key); 114 lua_rawgeti(L, -1, t->key);
111 luaL_error(L, "rule '%s' used outside a grammar", val2str(L, -1)); 115 luaL_error(L, "rule '%s' used outside a grammar", val2str(L, -1));
112 } 116 }
113 break; 117 break;
114 } 118 }
119 case TThrow: { /* labeled failure */
120 if (g != NULL) /* inside a grammar? */
121 fixonecall(L, postable, g, t, TThrow);
122 break;
123 }
115 case TSeq: case TChoice: 124 case TSeq: case TChoice:
116 correctassociativity(t); 125 correctassociativity(t);
117 break; 126 break;
@@ -521,7 +530,7 @@ static TTree *newroot2sib (lua_State *L, int tag) {
521static TTree *newthrowleaf (lua_State *L, int lab) { 530static TTree *newthrowleaf (lua_State *L, int lab) {
522 TTree *tree = newtree(L, 1); 531 TTree *tree = newtree(L, 1);
523 tree->tag = TThrow; 532 tree->tag = TThrow;
524 tree->u.label = lab; 533 tree->u.s.ps = 0;
525 return tree; 534 return tree;
526} 535}
527 536
@@ -726,8 +735,7 @@ static int lp_throw (lua_State *L) {
726 TTree * tree; 735 TTree * tree;
727 luaL_checkstring(L, -1); 736 luaL_checkstring(L, -1);
728 tree = newthrowleaf(L, 0); 737 tree = newthrowleaf(L, 0);
729 tree->u.label = addtonewktable(L, 0, 1); 738 tree->key = addtonewktable(L, 0, 1);
730 tree->key = tree->u.label;
731 /*printf("lp_throw %d %s\n", tree->key, lua_tostring(L, 1));*/ 739 /*printf("lp_throw %d %s\n", tree->key, lua_tostring(L, 1));*/
732 return 1; 740 return 1;
733} 741}
diff --git a/lptree.h b/lptree.h
index d89da4d..bb53c84 100644
--- a/lptree.h
+++ b/lptree.h
@@ -36,6 +36,7 @@ typedef enum TTag {
36 TRunTime, /* run-time capture: 'key' is Lua function; 36 TRunTime, /* run-time capture: 'key' is Lua function;
37 'sib1' is capture body */ 37 'sib1' is capture body */
38 TThrow, /* labeled failure: 'label' = l */ 38 TThrow, /* labeled failure: 'label' = l */
39 TThrowRec, /* labeled failure: 'label' = l */
39 TRecov, /* labed failure: 'sib1' //{labels} 'sib2' */ 40 TRecov, /* labed failure: 'sib1' //{labels} 'sib2' */
40 /* the set of labels is stored in next CHARSETSIZE bytes */ 41 /* the set of labels is stored in next CHARSETSIZE bytes */
41 TLabChoice /* labed failure: 'sib1' /{labels} 'sib2' */ 42 TLabChoice /* labed failure: 'sib1' /{labels} 'sib2' */
diff --git a/lptree.o b/lptree.o
new file mode 100644
index 0000000..9e01066
--- /dev/null
+++ b/lptree.o
Binary files differ
diff --git a/lpvm.c b/lpvm.c
index 61d609a..c408e4c 100644
--- a/lpvm.c
+++ b/lpvm.c
@@ -331,15 +331,32 @@ const char *match (lua_State *L, const char *o, const char *s, const char *e,
331 continue; 331 continue;
332 } 332 }
333 case IThrow: { /* labeled failure */ 333 case IThrow: { /* labeled failure */
334 printf("IThrow here: key=%d aux = %d top = %d\n", p->i.key, p->i.aux, lua_gettop(L)); 334 /*printf("IThrow here: key=%d, key+1=%d aux = %d top = %d\n", p->i.key, (p+1)->i.key, p->i.aux, lua_gettop(L));
335 lua_rawgeti(L, ktableidx(ptop), p->i.key); 335 lua_rawgeti(L, ktableidx(ptop), (p+1)->i.key);
336 printf("IThrow there %s top = %d\n", lua_tostring(L, -1), lua_gettop(L)); 336 printf("IThrow there %s top = %d\n", lua_tostring(L, -1), lua_gettop(L));
337 lua_pop(L, 1); 337 lua_pop(L, 1);*/
338 *labelf = p->i.key; 338 *labelf = (p+1)->i.key;
339 pk = p + 1; 339 pk = p + 1;
340 *sfail = s; 340 *sfail = s;
341 goto fail; 341 goto fail;
342 } 342 }
343 case IThrowRec: { /* labeled failure */
344 /*printf("IThrowRec here: key=%d, key+2=%d aux = %d top = %d\n", p->i.key, (p+2)->i.key, p->i.aux, lua_gettop(L));
345 lua_rawgeti(L, ktableidx(ptop), (p+2)->i.key);
346 printf("IThrowRec there %s top = %d\n", lua_tostring(L, -1), lua_gettop(L));
347 lua_pop(L, 1);*/
348 *labelf = (p+2)->i.key;
349 *sfail = s;
350 if (stack == stacklimit)
351 stack = doublestack(L, &stacklimit, ptop);
352 stack->s = NULL;
353 stack->p = p + 3;
354 stack->ls = NULL;
355 stack->caplevel = captop;
356 stack++;
357 p += getoffset(p);
358 continue;
359 }
343 case IFailTwice: 360 case IFailTwice:
344 assert(stack > getstackbase(L, ptop)); 361 assert(stack > getstackbase(L, ptop));
345 stack--; 362 stack--;
diff --git a/lpvm.h b/lpvm.h
index 713626e..c22e8d7 100644
--- a/lpvm.h
+++ b/lpvm.h
@@ -34,7 +34,8 @@ typedef enum Opcode {
34 IOpenCapture, /* start a capture */ 34 IOpenCapture, /* start a capture */
35 ICloseCapture, 35 ICloseCapture,
36 ICloseRunTime, 36 ICloseRunTime,
37 IThrow, /* "fails" with a specific label labeled failure */ 37 IThrow, /* "fails" with a specific label labeled failure */
38 IThrowRec, /* "fails" with a specific label labeled failure */
38 IRecov, /* stack a recovery; next fail with label 'f' will jump to 'offset' */ 39 IRecov, /* stack a recovery; next fail with label 'f' will jump to 'offset' */
39 ILabChoice /* stack a choice; next fail with label 'f' will jump to 'offset' */ 40 ILabChoice /* stack a choice; next fail with label 'f' will jump to 'offset' */
40} Opcode; 41} Opcode;
diff --git a/lpvm.o b/lpvm.o
new file mode 100644
index 0000000..19a9b1c
--- /dev/null
+++ b/lpvm.o
Binary files differ
diff --git a/testlabel.lua b/testlabel.lua
index 72eb9aa..90a8f9e 100644
--- a/testlabel.lua
+++ b/testlabel.lua
@@ -110,102 +110,95 @@ checklabeq({nil, '11', 1}, p:match("x"))
110checklabeq({nil, '11', 1}, p:match("kx")) 110checklabeq({nil, '11', 1}, p:match("kx"))
111 111
112 112
113-- throws a label that is not caught by the recovery operator 113-- throws a label without a corresponding recovery rule
114p = m.Rec(m.T(2), m.P"a", 1, 3) 114p = m.P{
115r, l, poserr = p:match(s) 115 "S",
116print(r, l, poserr) 116 S = m.T("bola"),
117 bolada = m.P"a"
118}
119r, l, poserr = p:match("abc")
120assert(r == nil and l == 'bola' and poserr == 1)
121
122-- throws a label without a corresponding recovery rule
123-- T(2) indexes key ["2"]
124p = m.P{
125 "S",
126 S = m.T(2),
127 [2] = m.P"a"
128}
129r, l, poserr = p:match("abc")
117assert(r == nil and l == '2' and poserr == 1) 130assert(r == nil and l == '2' and poserr == 1)
118 131
119-- wraps the previous pattern with a recovery that catches label "2" 132-- throws a label with a corresponding recovery rule
120p = m.Rec(p, m.P"a", 2) 133p = m.P{
121assert(p:match(s) == 2) 134 "S",
135 S = m.T("bola"),
136 bola = m.P"a"
137}
138r, l, poserr = p:match("abc")
139assert(r == 2)
122 140
123-- throws a label that is caught by recovery 141-- throws a label with a corresponding recovery rule
124p = m.Rec(m.T(25), m.P"a", 25) 142-- T(2) indexes key ["2"]
125assert(p:match(s) == 2) 143p = m.P{
144 "S",
145 S = m.T(2),
146 ["2"] = m.P"a"^0
147}
148r, l, poserr = p:match("aaabc")
149assert(r == 4)
150
151-- regular failure after the recovery
152p = m.P{
153 "S",
154 S = m.T(2),
155 ["2"] = m.P"a"^0 * m.P"c"
156}
157r, l, poserr = p:match("aaabc")
158assert(r == nil and l == 'fail' and poserr == 4)
126 159
127-- "fail" is label "0"
128-- throws the "fail" label after the recovery
129s = "bola" 160s = "bola"
130r, l, poserr = p:match("bola") 161r, l, poserr = p:match("bola")
131assert(r == nil and l == 0 and poserr == 1) 162assert(r == nil and l == 'fail' and poserr == 1)
132 163
133-- Recovery does not catch "fail" by default 164-- Recovery rules do not catch "fail" by default
134p = m.Rec(m.P"b", m.P"a", 1) 165p = m.P{
166 "S",
167 S = m.P"b" * m.T(2),
168 ["2"] = m.P"a"^0
169}
170r, l, poserr = p:match("c")
171assert(r == nil and l == 'fail' and poserr == 1)
135 172
136r, l, poserr = p:match("abc") 173assert(p:match("baa") == 4)
137assert(r == nil and l == 0 and poserr == 1)
138 174
139assert(p:match("bola") == 2)
140 175
176-- recovery rules for "2" or "3"
177-- when we use V instead of T, a recovery
178-- rule becomes a regular grammar rule
179p = m.P{
180 "S",
181 S = (m.P"a" + m.T(2)) * m.T(3),
182 ["3"] = m.V"2",
183 ["2"] = m.P"a" + m.P"b",
184}
141 185
142-- recovery operator catches "1" or "3"
143p = m.Rec((m.P"a" + m.T(1)) * m.T(3), (m.P"a" + m.P"b"), 1, 3)
144assert(p:match("aac") == 3) 186assert(p:match("aac") == 3)
145assert(p:match("abc") == 3) 187assert(p:match("abc") == 3)
146r, l, poserr = p:match("acc") 188r, l, poserr = p:match("acc")
147assert(r == nil and l == 0 and poserr == 2) 189assert(r == nil and l == 'fail' and poserr == 2)
148 190
149--throws 1, recovery pattern matches 'b', throw 3, and rec pat mathces 'a' 191--throws 2, recovery rule matches 'b', throw 3, and rec rule matches 'a'
150assert(p:match("bac") == 3) 192assert(p:match("bac") == 3)
151 193
152r, l, poserr = p:match("cab") 194r, l, poserr = p:match("cab")
153assert(r == nil and l == 0 and poserr == 1) 195assert(r == nil and l == 'fail' and poserr == 1)
154
155
156-- associativity
157-- (p1 / %1) //{1} (p2 / %2) //{2} p3
158-- left-associativity
159-- ("a" //{1} "b") //{2} "c"
160p = m.Rec(m.Rec(m.P"a" + m.T(1), m.P"b" + m.T(2), 1), m.P"c", 2)
161assert(p:match("abc") == 2)
162assert(p:match("bac") == 2)
163assert(p:match("cab") == 2)
164r, l, poserr = p:match("dab")
165assert(r == nil and l == 0 and poserr == 1)
166
167
168-- righ-associativity
169-- "a" //{1} ("b" //{2} "c")
170p = m.Rec(m.P"a" + m.T(1), m.Rec(m.P"b" + m.T(2), m.P"c", 2), 1)
171assert(p:match("abc") == 2)
172assert(p:match("bac") == 2)
173assert(p:match("cab") == 2)
174r, l, poserr = p:match("dab")
175assert(r == nil and l == 0 and poserr == 1)
176
177
178-- associativity -> in this case the error thrown by p1 is only
179-- recovered when we have a left-associative operator
180-- (p1 / %2) //{1} (p2 / %2) //{2} p3
181-- left-associativity
182-- ("a" //{1} "b") //{2} "c"
183p = m.Rec(m.Rec(m.P"a" + m.T(2), m.P"b" + m.T(2), 1), m.P"c", 2)
184assert(p:match("abc") == 2)
185r, l, poserr = p:match("bac")
186assert(r == nil and l == 0 and poserr == 1)
187assert(p:match("cab") == 2)
188r, l, poserr = p:match("dab")
189assert(r == nil and l == 0 and poserr == 1)
190
191
192-- righ-associativity
193-- "a" //{1} ("b" //{2} "c")
194p = m.Rec(m.P"a" + m.T(2), m.Rec(m.P"b" + m.T(2), m.P"c", 2), 1)
195assert(p:match("abc") == 2)
196r, l, poserr = p:match("bac")
197assert(r == nil and l == 2 and poserr == 1)
198r, l, poserr = p:match("cab")
199assert(r == nil and l == 2 and poserr == 1)
200r, l, poserr = p:match("dab")
201assert(r == nil and l == 2 and poserr == 1)
202
203 196
204 197
205-- tests related to predicates 198-- tests related to predicates
206p = #m.T(1) + m.P"a" 199p = #m.T(1) + m.P"a"
207r, l, poserr = p:match("abc") 200r, l, poserr = p:match("abc")
208assert(r == nil and l == 1 and poserr == 1) 201assert(r == nil and l == '1' and poserr == 1)
209 202
210p = ##m.T(1) + m.P"a" 203p = ##m.T(1) + m.P"a"
211r, l, poserr = p:match("abc") 204r, l, poserr = p:match("abc")