summaryrefslogtreecommitdiff
path: root/web/yacco2/library/set.w
diff options
context:
space:
mode:
authorNorbert Preining <norbert@preining.info>2019-09-02 13:46:59 +0900
committerNorbert Preining <norbert@preining.info>2019-09-02 13:46:59 +0900
commite0c6872cf40896c7be36b11dcc744620f10adf1d (patch)
tree60335e10d2f4354b0674ec22d7b53f0f8abee672 /web/yacco2/library/set.w
Initial commit
Diffstat (limited to 'web/yacco2/library/set.w')
-rw-r--r--web/yacco2/library/set.w123
1 files changed, 123 insertions, 0 deletions
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@>=
+@<copyright notice@>;
+@<iyacco2@>;
+@<accrue set code@>;
+
+@ Accrue set code.
+@<accrue set code@>= // acrue set code
+
+@ Some set types used in constructing search sets.
+@<Type def...@>=
+typedef std::map<yacco2::USINT,yacco2::USINT> 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.
+
+@<Structure...@>=
+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.
+@<External rtns and variables@>+=
+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.
+@<accrue set code@>+=
+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;