From e0c6872cf40896c7be36b11dcc744620f10adf1d Mon Sep 17 00:00:00 2001 From: Norbert Preining Date: Mon, 2 Sep 2019 13:46:59 +0900 Subject: Initial commit --- web/yacco2/library/set.w | 123 +++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 123 insertions(+) create mode 100644 web/yacco2/library/set.w (limited to 'web/yacco2/library/set.w') diff --git a/web/yacco2/library/set.w b/web/yacco2/library/set.w new file mode 100644 index 0000000000..78f1a42d02 --- /dev/null +++ b/web/yacco2/library/set.w @@ -0,0 +1,123 @@ +@q file: set.w@> +@q% Copyright Dave Bone 1998 - 2015@> +@q% /*@> +@q% This Source Code Form is subject to the terms of the Mozilla Public@> +@q% License, v. 2.0. If a copy of the MPL was not distributed with this@> +@q% file, You can obtain one at http://mozilla.org/MPL/2.0/.@> +@q% */@> +@q output wset.cpp@> +@** Set handling. This is an interesting section.\fbreak + The original +Yacco2 generated code to create each thread's tables at startup time by \CPLUSPLUS/ templates. +Well the 10 megabyte gorilla thumped its chest. +By use of the marvelous book ``Efficient \CPLUSPLUS/'' by Bulka and Mayhew, +Yacco2 became a diet marvel. Have you heard any testimonials? +No, well I'm now one. Go groan and sweat, your software will thank you for it and so will its +life span. + +As lookahead sets are rather sparse, to make set processing reasonably efficient, +the following approach was implemented. +The out-of-the-box binary search function is used to search a set. +To minimize set size, the range of enumerated elements is divided up into +8 elements per partition where the remainder is the specific element. + +Now why an 8 element partition? +As Yacco2 currently uses 8 bit ASCII encoding and the density of the sets are sparse +and my machine has 8 bits per byte, I +felt that this was a reasonable compromise in the age of Aquarius. +If the sets were more dense, then the +number of elements per partition could be 16 or greater. +As always, there is a compromise between space and speed. +It's upto the person porting the software to decide. +Hash tables were considered but I decided that space would be +too wasteful. + +Thought: Is there a dynamic hash faclity that +rivals the set space but beats it in accessing speed? +Other thoughts: use of complement sets if set size too big. + +Elements are ordered in ascending sequence + such that the set becomes a binary array of partitions. +The binary functor takes two set structures: one is the key that +is being searched within the set table, and the set table. +To shrink the set size, |LR1_Eolr| is a special element used to signify +`use all terminals defined including self'. It's grammar tag is ``eolr''. + +Output is directed to |wset.cpp|. +@d SET_ELEM_NO_BITS 8 +@(wset.cpp@>= +@; +@; +@; + +@ Accrue set code. +@= // acrue set code + +@ Some set types used in constructing search sets. +@= +typedef std::map yacco2_set_type; +typedef yacco2_set_type::iterator yacco2_set_iter_type; + +@*2 Structure of a set.\fbreak + Current implementation uses 2 bytes of 8 bit size. +The first byte is the partition number with a range of 0..255. +The 2nd byte is the elements where x in ${2^x}$ indicates its position within +the byte. An element's position within the byte is +its remainder of modulo |SET_ELEM_NO_BITS|. +This set structure supports 2048 elements --- 256 partitions by 8 elements. +If there are more terminals to be supported, then there is +2 ways to increase the supported number of terminals: increase +the partition size from a byte to an integer +or expand the size of the number of elements per partition. + +@= +struct Set_entry {// set structure: byte no of set pairs, |partition,set| pair(s) + yacco2::UCHAR partition__;// whole no + yacco2::UCHAR elements__;// 7..0 in bit order due to remainder: 0 = 1 while 7 = 128 value +}; +struct Set_tbl { + yacco2::UCHAR no_entries__; + yacco2::Set_entry first_entry__[1]; +};@/ + +@*2 Set element compare functor.\fbreak +This is just your basic binary search functor whose address is passed +to the binary search routine. +The only interesting part is c's bitwise logical `and' to determine +if the element is in the 2nd byte of the structure. +If the element is not found, it forces the search to continue down a cul-du-sac +by returning a false `less than' comparison. + +Now i roll my own bsearch to speed things up. +The compare functor is just too expensive in run time so out damn spot. +@+= +extern void create_set_entry(yacco2::USINT Enum_id,yacco2::Set_entry& Set); + +@*2 From a terminal's enumeration create a set's key for searching.\fbreak +This routine maps an enumeration into a set's co-ordinates. +@+= +extern void +yacco2::create_set_entry(yacco2::USINT Enum_id,yacco2::Set_entry& Set){ + INT R = Enum_id % SET_ELEM_NO_BITS; + Set.partition__ = Enum_id / SET_ELEM_NO_BITS; + Set.elements__ = 1 << R; +} + +@ |create_set_entry|. +@<|create_set_entry|@>= + INT R = Enum_id % SET_ELEM_NO_BITS; + la_set.partition__ = Enum_id / SET_ELEM_NO_BITS; + la_set.elements__ = 1 << R; + +@ |create_set_entry for RC|. +@<|create_set_entry for Rc|@>= + INT R = sym->enumerated_id__ % SET_ELEM_NO_BITS; + sym->tok_co_ords__.set_entry__.partition__ + = sym->enumerated_id__ / SET_ELEM_NO_BITS; + sym->tok_co_ords__.set_entry__.elements__ = 1 << R; + +@ |create_set_entry for CAbs_lr1_sym|. +@<|create_set_entry for CAbs_lr1_sym|@>= + INT R = Enum_id % SET_ELEM_NO_BITS; + tok_co_ords__.set_entry__.partition__ = Enum_id / SET_ELEM_NO_BITS; + tok_co_ords__.set_entry__.elements__ = 1 << R; -- cgit v1.2.3