From 510b10b96b546fcc6c6b6be85050305ddd192a41 Mon Sep 17 00:00:00 2001 From: JSDurand Date: Sat, 5 Feb 2022 17:30:11 +0800 Subject: replace some hash table usage by tuples Previously I used hash tables, which consume too much memory. Now the critical parts are replaced by a new hand-written library called "tuple.h". Now we can easily parse larger inputs. I haven't tested its limits, though. --- src/bsr.h | 37 ++++++++++++++++++++++++++++--------- 1 file changed, 28 insertions(+), 9 deletions(-) (limited to 'src/bsr.h') diff --git a/src/bsr.h b/src/bsr.h index 64e428a..1b91c3e 100644 --- a/src/bsr.h +++ b/src/bsr.h @@ -77,9 +77,30 @@ I don't know if there are better implementations. If I think of better ways in the future, I will re-implement the BSR sets. */ +/* With the newly written library tuple.h, the implementation changes + as follows. + + The first type is stored as a "luple5", but the coordinates are in + the following order. + + (X, a, i, k, j) => (X, i, j, a, k) + + This is to ensure that we can quickly find BSR's with a given + non-terminal X and given left and right extents i and j. This is + necessary for extracting an SPPF out of it, and for deciding + whether the parser succeeds in parsing the entire input. + + The second type os stored as a "luple6", with the following + coordinates order. + + (X, a, b, i, k, j) => (X, a, b, i, j, k) + + The reason is similar to the above. Though this is not necessary for + deciding if the parser succeeds. */ + typedef struct bsr_s bsr; -bsr *new_bsr(BOOL * const restrict errorp, Grammar *g); +bsr *new_bsr(Grammar *g, NUM input_len, BOOL * const restrict errorp); /* No flag to control the deletion, as the user cannot change how the data is stored. */ @@ -94,18 +115,16 @@ void destroy_bsr(bsr * const restrict bsrp); the right-most terminal or non-terminal in the alternate corresponding to a. */ -BOOL bsr_add(CCR_MOD(Grammar *) g, bsr * const restrict b, - NUM X, NUM a, NUM c, NUM i, NUM k, NUM j); +H_ATTR BOOL bsr_add(CCR_MOD(Grammar *) g, bsr * const restrict b, + pair6 p6); BOOL bsr_find(CCR_MOD(bsr *) b, CCR_MOD(Grammar *) g, BOOL * const restrict errorp, - NUM X, NUM a, NUM c, NUM i, NUM k, NUM j); + pair6 p6); -/* if not found return NULL */ -ht *bsr_lookup(CCR_MOD(bsr *) b, BOOL * const restrict errorp, - NUM X, NUM i, NUM j); +P_ATTR BOOL bsr_lookup(bsr * b, NUM X, NUM i, NUM j); -/* Change to new line after LINE_LEN many elements. */ -void bsr_print(CCR_MOD(bsr *) b, CCR_MOD(Grammar *) g, NUM line_len); +/* Print a new line after LINE_LEN many elements. */ +void bsr_print(bsr *b, Grammar *g, NUM line_len); #endif -- cgit v1.2.3-18-g5258