aboutsummaryrefslogtreecommitdiff
path: root/lptree.c
diff options
context:
space:
mode:
authorRoberto Ierusalimschy <roberto@inf.puc-rio.br>2019-04-14 12:04:23 -0300
committerRoberto Ierusalimschy <roberto@inf.puc-rio.br>2019-04-14 12:04:23 -0300
commit3f7797419e4d7493e1364290a5b127d1cb45e3bf (patch)
tree8dd91b0d008d5ea9f9c96eada86510495c97d1e3 /lptree.c
parentd9f83dded93a35fb333c4e1bd371c401f7129fd1 (diff)
downloadlpeg-3f7797419e4d7493e1364290a5b127d1cb45e3bf.tar.gz
lpeg-3f7797419e4d7493e1364290a5b127d1cb45e3bf.tar.bz2
lpeg-3f7797419e4d7493e1364290a5b127d1cb45e3bf.zip
Removed 'unsigned char' limit on number of rules in grammars
Added a new tree-type node 'TXInfo', which follows 'TRule' nodes, to store extra information about a node. (In this case, the rule number, with an 'unsigned short' field.)
Diffstat (limited to 'lptree.c')
-rw-r--r--lptree.c32
1 files changed, 17 insertions, 15 deletions
diff --git a/lptree.c b/lptree.c
index 5c8de94..557090b 100644
--- a/lptree.c
+++ b/lptree.c
@@ -25,7 +25,7 @@ const byte numsiblings[] = {
25 1, /* rep */ 25 1, /* rep */
26 2, 2, /* seq, choice */ 26 2, 2, /* seq, choice */
27 1, 1, /* not, and */ 27 1, 1, /* not, and */
28 0, 0, 2, 1, /* call, opencall, rule, grammar */ 28 0, 0, 2, 1, 1, /* call, opencall, rule, prerule, grammar */
29 1, /* behind */ 29 1, /* behind */
30 1, 1 /* capture, runtime capture */ 30 1, 1 /* capture, runtime capture */
31}; 31};
@@ -906,7 +906,7 @@ static int collectrules (lua_State *L, int arg, int *totalsize) {
906 int size; /* accumulator for total size */ 906 int size; /* accumulator for total size */
907 lua_newtable(L); /* create position table */ 907 lua_newtable(L); /* create position table */
908 getfirstrule(L, arg, postab); 908 getfirstrule(L, arg, postab);
909 size = 2 + getsize(L, postab + 2); /* TGrammar + TRule + rule */ 909 size = 3 + getsize(L, postab + 2); /* TGrammar + TRule + TXInfo + rule */
910 lua_pushnil(L); /* prepare to traverse grammar table */ 910 lua_pushnil(L); /* prepare to traverse grammar table */
911 while (lua_next(L, arg) != 0) { 911 while (lua_next(L, arg) != 0) {
912 if (lua_tonumber(L, -2) == 1 || 912 if (lua_tonumber(L, -2) == 1 ||
@@ -920,11 +920,11 @@ static int collectrules (lua_State *L, int arg, int *totalsize) {
920 lua_pushvalue(L, -2); /* push key (to insert into position table) */ 920 lua_pushvalue(L, -2); /* push key (to insert into position table) */
921 lua_pushinteger(L, size); 921 lua_pushinteger(L, size);
922 lua_settable(L, postab); 922 lua_settable(L, postab);
923 size += 1 + getsize(L, -1); /* update size */ 923 size += 2 + getsize(L, -1); /* add 'TRule + TXInfo + rule' to size */
924 lua_pushvalue(L, -2); /* push key (for next lua_next) */ 924 lua_pushvalue(L, -2); /* push key (for next lua_next) */
925 n++; 925 n++;
926 } 926 }
927 *totalsize = size + 1; /* TTrue to finish list of rules */ 927 *totalsize = size + 1; /* space for 'TTrue' finishing list of rules */
928 return n; 928 return n;
929} 929}
930 930
@@ -936,11 +936,13 @@ static void buildgrammar (lua_State *L, TTree *grammar, int frule, int n) {
936 int ridx = frule + 2*i + 1; /* index of i-th rule */ 936 int ridx = frule + 2*i + 1; /* index of i-th rule */
937 int rulesize; 937 int rulesize;
938 TTree *rn = gettree(L, ridx, &rulesize); 938 TTree *rn = gettree(L, ridx, &rulesize);
939 TTree *pr = sib1(nd); /* points to rule's prerule */
939 nd->tag = TRule; 940 nd->tag = TRule;
940 nd->key = 0; /* will be fixed when rule is used */ 941 nd->key = 0; /* will be fixed when rule is used */
941 nd->cap = i; /* rule number */ 942 pr->tag = TXInfo;
942 nd->u.ps = rulesize + 1; /* point to next rule */ 943 pr->u.n = i; /* rule number */
943 memcpy(sib1(nd), rn, rulesize * sizeof(TTree)); /* copy rule */ 944 nd->u.ps = rulesize + 2; /* point to next rule */
945 memcpy(sib1(pr), rn, rulesize * sizeof(TTree)); /* copy rule */
944 mergektable(L, ridx, sib1(nd)); /* merge its ktable into new one */ 946 mergektable(L, ridx, sib1(nd)); /* merge its ktable into new one */
945 nd = sib2(nd); /* move to next rule */ 947 nd = sib2(nd); /* move to next rule */
946 } 948 }
@@ -976,7 +978,7 @@ static int checkloops (TTree *tree) {
976** twice in 'passed', there is path from it back to itself without 978** twice in 'passed', there is path from it back to itself without
977** advancing the subject. 979** advancing the subject.
978*/ 980*/
979static int verifyerror (lua_State *L, int *passed, int npassed) { 981static int verifyerror (lua_State *L, unsigned short *passed, int npassed) {
980 int i, j; 982 int i, j;
981 for (i = npassed - 1; i >= 0; i--) { /* search for a repetition */ 983 for (i = npassed - 1; i >= 0; i--) { /* search for a repetition */
982 for (j = i - 1; j >= 0; j--) { 984 for (j = i - 1; j >= 0; j--) {
@@ -1001,8 +1003,8 @@ static int verifyerror (lua_State *L, int *passed, int npassed) {
1001** counts the elements in 'passed'. 1003** counts the elements in 'passed'.
1002** Assume ktable at the top of the stack. 1004** Assume ktable at the top of the stack.
1003*/ 1005*/
1004static int verifyrule (lua_State *L, TTree *tree, int *passed, int npassed, 1006static int verifyrule (lua_State *L, TTree *tree, unsigned short *passed,
1005 int nb) { 1007 int npassed, int nb) {
1006 tailcall: 1008 tailcall:
1007 switch (tree->tag) { 1009 switch (tree->tag) {
1008 case TChar: case TSet: case TAny: 1010 case TChar: case TSet: case TAny:
@@ -1014,7 +1016,7 @@ static int verifyrule (lua_State *L, TTree *tree, int *passed, int npassed,
1014 case TNot: case TAnd: case TRep: 1016 case TNot: case TAnd: case TRep:
1015 /* return verifyrule(L, sib1(tree), passed, npassed, 1); */ 1017 /* return verifyrule(L, sib1(tree), passed, npassed, 1); */
1016 tree = sib1(tree); nb = 1; goto tailcall; 1018 tree = sib1(tree); nb = 1; goto tailcall;
1017 case TCapture: case TRunTime: 1019 case TCapture: case TRunTime: case TXInfo:
1018 /* return verifyrule(L, sib1(tree), passed, npassed, nb); */ 1020 /* return verifyrule(L, sib1(tree), passed, npassed, nb); */
1019 tree = sib1(tree); goto tailcall; 1021 tree = sib1(tree); goto tailcall;
1020 case TCall: 1022 case TCall:
@@ -1030,10 +1032,10 @@ static int verifyrule (lua_State *L, TTree *tree, int *passed, int npassed,
1030 /* return verifyrule(L, sib2(tree), passed, npassed, nb); */ 1032 /* return verifyrule(L, sib2(tree), passed, npassed, nb); */
1031 tree = sib2(tree); goto tailcall; 1033 tree = sib2(tree); goto tailcall;
1032 case TRule: 1034 case TRule:
1033 if (npassed >= MAXRULES) 1035 if (npassed >= MAXRULES) /* too many steps? */
1034 return verifyerror(L, passed, npassed); 1036 return verifyerror(L, passed, npassed); /* error */
1035 else { 1037 else {
1036 passed[npassed++] = tree->key; 1038 passed[npassed++] = tree->key; /* add rule to path */
1037 /* return verifyrule(L, sib1(tree), passed, npassed); */ 1039 /* return verifyrule(L, sib1(tree), passed, npassed); */
1038 tree = sib1(tree); goto tailcall; 1040 tree = sib1(tree); goto tailcall;
1039 } 1041 }
@@ -1045,7 +1047,7 @@ static int verifyrule (lua_State *L, TTree *tree, int *passed, int npassed,
1045 1047
1046 1048
1047static void verifygrammar (lua_State *L, TTree *grammar) { 1049static void verifygrammar (lua_State *L, TTree *grammar) {
1048 int passed[MAXRULES]; 1050 unsigned short passed[MAXRULES];
1049 TTree *rule; 1051 TTree *rule;
1050 /* check left-recursive rules */ 1052 /* check left-recursive rules */
1051 for (rule = sib1(grammar); rule->tag == TRule; rule = sib2(rule)) { 1053 for (rule = sib1(grammar); rule->tag == TRule; rule = sib2(rule)) {