summaryrefslogtreecommitdiff
path: root/web/yacco2/o2linker/intro.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/o2linker/intro.w
Initial commit
Diffstat (limited to 'web/yacco2/o2linker/intro.w')
-rw-r--r--web/yacco2/o2linker/intro.w394
1 files changed, 394 insertions, 0 deletions
diff --git a/web/yacco2/o2linker/intro.w b/web/yacco2/o2linker/intro.w
new file mode 100644
index 0000000000..ddd81631c5
--- /dev/null
+++ b/web/yacco2/o2linker/intro.w
@@ -0,0 +1,394 @@
+@q file: intro.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% */@>
+@** Summary of Yacco2's Linker --- threads and their bit maps.\fbreak
+\Olinker produces ``thread bit maps'' for each terminal
+ and a global table of to-run threads, and
+a linker document describing all the processed grammars
+extracted from their grammar's ``fsm-comments''
+ and their called threads.
+Standalone grammars: monolithic y, are also traversed to
+add their thread booty to the global bit maps.
+As Linker is a companion program of Yacco2, please see Yacco2's documentation
+for appropriate development of data structures that are germain to both.
+
+Linker receives its input either interactively or as a command line.
+The file to compile contains a list of grammar first set control files
+generated by Yacco2.
+Each grammar's ``first set'' file generated by Yacco2 uses a naming convention
+of the ``thread name'' supplied by the grammar's |fsm-filename| with an extension of ``fsc''
+indicating a ``first set'' control file.
+At present, Linker's inputted file is handcrafted by the grammar writer
+due to Yacco2 not having a generation database of compiled grammars.
+The below diagram shows \O2{}Linker's manufacturing assembly line for the
+``bit maps'' object file within an Unix context where the ``ld'' linker program
+resolves the globals described in the following section.
+The ``pdf'' generated document provides an overview description of all the grammars in use.
+``CC'' is the c++ compiler on my Sun Solaris work station.
+\fbreak
+\fbreak
+\convertMPtoPDF{"/usr/local/yacco2/diagrams/o2linker_overview.1"}{1}{1}
+\fbreak
+\fbreak
+The ``O2linker\_doc.pdf'' document provides an index of all grammars compiled
+with comments about their claim-to-fame.
+It is a nice overview document of your language software
+when debugging or just getting a feel for all those defined grammars.
+It demarks the threaded grammars from their monolithic brethren.
+
+@*2 Globals --- those unresolved static variables used by Yacco2's library.\fbreak
+The following variables are made global for Yacco2's parse library usuage and
+placed within |yacco2| namespace:\fbreak
+\ptindent{1) |THDS_STABLE__| - vector of threads for the running}
+\ptindent{2) |T_ARRAY_HAVING_THD_IDS__| - terminals' thread sets}
+\ptindent{3) |BIT_MAPS_FOR_SALE__| - block of 32 bit words for bit map manufacture}
+\ptindent{4) |BIT_MAP_IDX__| - index used to dispense bit maps}
+\ptindent{5) |TOTAL_NO_BIT_WORDS__| - total number of words for sale}
+
+To speed things up and not be involved
+with the |malloc| issues of new / delete, |BIT_MAPS_FOR_SALE__|
+is a constant size of bit map words.
+Its size is controlled by the |TOTAL_NO_BIT_WORDS| macro and indicated at
+run-time by the |TOTAL_NO_BIT_WORDS__| global.
+Why not use c++ template containers?
+Depending on the context, they are not very efficient and in some cases they are not robust
+depending on whose compiler one uses.
+So ``roll your own'' is my mode of operandi. At least I can bark at myself
+instead of dealing with charades of good-citizenship a la Microsoft
+and their bug reporting - fixes: their stated policy of 24 hours response after submitting
+the bug report and now its 2 weeks and I'm still waiting for an acknowledgement.
+Have you seen their latest website
+for bug reporting? No direct button to send the report, only the platitude of
+how wastefull it is at their cost to deal with bug reports so make sure that you review their
+stated digest of bugs before submitting.
+How does democracy come into play when bugs are bugs: Fix them!
+Ranking bugs by developer votes is just (you substitute one of the
+following adjectives: stupid, senseless, witless, dull, brainless, weak-brained,
+muddle-headed, beef-witted, unentertaining). You get my sentiment.
+
+Each global will be developed in their appropriate sections.
+
+
+@*2 Some definitions within Linker's context.\fbreak
+What is a ``first set'' within the linker's context?\fbreak
+It is the terminals within the Start state configuration
+(aka ``Closure only'' state) of an automaton.
+There is some subtlety to this statement as an epsilon rule (empty right-hand-side),
+special terminals ${\vert+\vert}$ and ${\vert.\vert}$,
+ and threads being called
+from within the ``Closure only'' state require special treatment as their
+terminals are outside of this state.
+These situations require going into other state configurations to determine the
+terminals.
+Possibly an epsilon rule and special terminals but definitely
+threads presents a more difficult problem as the
+grammar being parsed does not have access to the called thread's first set.
+Why? A called thread is another grammar requiring compilation.
+This is why Linker is required to post process all grammars in a global context to
+calculate the first sets for grammars calling threads out of their ``Closure only'' state.
+\fbreak
+\fbreak
+Why first sets anyway?\fbreak
+Originally this was not programmed. I wanted to prove my concepts first before
+optimizing for speed.
+Reality demands that a good idea be also practical.
+What good is parsing with threads when they are orders of magnitude slower
+than the current crop of parsing paradigns?
+So to overcome slowness, first sets provide the potential of whether a thread
+should run.
+How? If the current token to be parsed is in the first set of the thread then
+launch it from the running parse context.
+This optimization prevents false thread starts.
+\fbreak
+\fbreak
+Why the name \Olinker instead of for example ``first setter'' or jet?\fbreak
+I checked to the current name of tools required to
+prepare a program as an executable.
+In a sense Linker in my mind's eye was a concept that
+brought together the loose ends of the grammars and made it ready to parse.
+First setter is also appropriate.
+\fbreak
+\fbreak
+How are first sets generated?\fbreak
+The basic problem solved by Linker is the following:
+within a grammar, threads can be called.
+If threads called are within the Start state of a grammar,
+ the grammar's
+first set now has a dependence on another thread's first set.
+Of course this call sequence is transitive: thread A can call thread B can call thread C.
+Both threads B and C can have a call thread dependency within their
+first sets.
+It is this thread dependency that the Linker resolves by applying the
+transitive closure operation across a graph of thread nodes
+to outcome the explicit first set of terminals per dependent thread.
+The output from Linker is a global vector of threads to be run, and their
+global first set bit maps optimized against all terminals. That is, what
+threads can be run by this current terminal.
+
+
+@*2 Overview of \Olinker's generated components.\fbreak
+Threads are just your normal procedures that get launched
+under the guidance of the threading facility native to the operating system
+instead of being called directly.
+Yacco2's parse library documentation goes into the detail between each
+run-time advantages threads versus procedure calls: After experimenting with a stop watch,
+the winner is the threads approach due to c++'s overhead of object birth-run-destructor cycle.
+
+Now the issue becomes ``how to determine and provide a thread id?'' that
+can be referenced globally and locally.
+Why the distinction between global and local contexts?
+Local contexts are the individual grammars that can reference other threads
+who are defined globally outside of its domain.
+As raised before, Linker's raison-d'\^etre is post-processing in a global context all the
+compiled threads.
+As the \o2 compiler / compiler processes the grammar in a local parsing context, references
+to threads within the grammar must be delayed thru indirection in its generated tables.
+This indirection comes from objects whose references are globally defined
+via the ``extern'' c(++) language facility and resolved by the appropriate language linker.
+
+An entente between the global and local contexts was signed in 1066 whereby the
+ charter of thread rights
+ defined the |Thread_entry| structure.
+Each |Thread_entry| uses a naming convention
+of: Ixxx where xxx is the thread name without its namespace drawn from the grammar.
+\o2 generates references to these thread entries whilst Linker creates the
+actual thread entry entities.
+The |Thread_entry| contains a pointer to the literal thread name
+used in \o2's tracings,
+the address to its called procedure, and its thread id that
+is a key to appropriate tables and thread maps.
+Thread ids are positive whole numbers starting from 0.
+The thread names are sorted in ascending sequence. Each thread's id is its
+relative position within this sorted sequence.
+
+
+@*2 Thread bit maps.\fbreak
+To give speed and economy of space, 32 bit words are used whereby
+each bit within a word represents the presence or absence of a specific thread.
+Why 32 bit words? This falls nicely in the current crop of CPUs.
+As 64 bit envy becomes mainstream, the number of bits per word can be changed
+by |cweb|'s macro facility.
+The mapping of a thread id into its bit map, uses modulo 32 on the thread id.
+The quotient indicates which word to access and the remainder indicates
+which specific bit within the word represents the thread.
+Due to the open number of threads being defined,
+the total number of words making up a thread map is
+specific to each parsing environment. For example, the
+current number of threads for \o2 is under 50. So, each thread map
+is 2 words long.
+
+Use of bit maps allows set processing with its operators like intersection to take place.
+Due to other optimizations to be discussed later, the number of words per bit map
+for \Yacco2's parsing library
+is calculated at runtime from the global |THDS_STABLE__| structure
+ that carries the total number of threads being
+supported for the current parse environment.
+The globals |TOTAL_NO_OF_BIT_WORDS__|, |BIT_MAPS_FOR_SALE__|, and |BIT_MAP_IDX__| are used to
+manufacture bit maps.
+Why not manufacture bit maps at time of \o2 running?
+Neither the local grammar or \o2 has any notion to what its or other threads ids are.
+Also, I did not want to impose on the grammar writer an unique thread id assignment within each
+grammar nor an approximation of the total number of threads being developed.
+
+Now, \Yacco2's runtime library has a just-in-time thread map manufacture process.
+Each parsing thread's state keeps a list of threads to possibly run but list processing
+to launch threads is too slow.
+So when a parsing thread arrives at a state configuration needing thread bit maps,
+\Yacco2's library will
+manufacture it using the globals |BIT_MAPS_FOR_SALE__| and |BIT_MAP_IDX__|.
+|BIT_MAP_IDX__| controls the current index into |BIT_MAPS_FOR_SALE__| that houses
+the words for the bit maps.
+This newly minted thread map is now available throughout the balance of the parsing
+of the thread by storing the map address in the state configuration.
+
+The below diagram depicts a partial bit map configuration:\fbreak
+\fbreak
+\fbreak
+\convertMPtoPDF{"/usr/local/yacco2/diagrams/linker.2"}{1}{1}
+\fbreak
+\fbreak
+The word 0 above is in ``big endian'' sequence composed of 4 bytes: byte 0 is the first
+covering
+the most significant bit 31 thru to bit 24 while
+byte 3 contains the least significant bit 0
+where its bits range from 7 thru to 0.
+It illustrates threads 31, 23, 15, 7, and 0 as
+being available for the running as their bits are ``turned on'' represented
+by ``1''.
+Word 1 would have the
+thread id range of 63 thru to 32. Each thread id in a word
+ is just a replay of the modulo: Q is the word map no * 32 + the R the remainder
+ indicating the specific bit from 0..31.
+
+
+@*2 Linker's languages.\fbreak
+There are 3 separate languages to be parsed by Linker:\fbreak
+\ptindent{1) Terminal alphabet --- literal names of each terminal}
+\ptindent{2) Each grammar's first set control file generated by \o2 --- xxx.fsc}
+\ptindent{3) Linker's input control file}
+
+These languages are simplistic but requires proper
+parsing that, of course, will use Yacco2's parse library.
+
+@*2 Terminal alphabet.\fbreak
+This is your terminal vocabulary defined by the 4 classes of terminals:
+LR constants, raw characters, errors, and ``user created'' terminals.
+Its content provides the literal description per terminal used for annotated
+comments in the emitted file. Their input order is also their enumeration.
+This file is outputted by \o2 when one requests the terminals to be compiled
+using one of its gen options: ``-t'' for user terminals or ``-err'' for errors.
+It uses the filename provided by the grammar's T-enumeration's file-name construct
+with a ``fsc'' extension (aka first set control).
+For the \o2 grammars, it looks like this:\fbreak
+\listing{"/usr/local/yacco2/diagrams/intro1.txt"}
+\fbreak
+The outputted vocabulary file is ``|yacco2_T_enumeration.fsc|'' from this above example.
+
+The language uses a bracketing construct
+``T-alphabet'' ... ``end-T-alphabet''
+to contain the list of terminals by their name defined by the grammar's ``terminals'' constructs:
+Lrk, raw characters, errors, and terminals.
+Below is an example:\fbreak
+\listing{"/usr/local/yacco2/diagrams/intro2.txt"}
+
+@*3 Terminal enumeration.\fbreak
+As the inputted terminals are by name, to be more efficient,
+an enumeration scheme is used whereby each terminal's relative position within this list
+starting at 0 becomes their assigned number working
+ out along the positive whole numbers.
+From the example above, the |LR1_questionable_shift_operator| terminal is assigned 0,
+|LR1_eog| terminal is assigned 1 and so on.
+In \Yacco2's documentation you'll find
+``how it applies'' this enumeration to the shifting and reducing sets
+within the automaton tables.
+The storage for these sets favors space economy over speed.
+
+@*3 First set declarations.\fbreak
+\o2 outputs per grammar their first set files having
+a file naming convention of the grammar name with an extension of ``fsc''.
+Below is ``subrule\_def.fsc'' first set control file
+outputted by the subrule\_def.lex grammar.\fbreak
+\let\setuplistinghook = \linenumberedlisting
+\listing{"/usr/local/yacco2/diagrams/intro3.txt"}
+
+This is a summary of what was found within the grammar.
+I included line numbers each delimited by a ``:'' to the left of the language's
+individual source lines as reference points for the
+discussion that follows.
+Lines 5 -- 11 above are the prelude declarations of the compiled grammar.
+The 2 items of interest within the prelude are the keywords ``transitive'' and ``monolithic''.
+Both use a boolean declaration of ``y'' or ``n''.
+The ``transitive'' keyword indicates whether this grammar needs transitive processing.
+The ``monolithic'' keyword indicates whether the grammar is stand alone
+or threaded.
+
+The 3 components following the prelude indicate the intent by their names.
+Lines 12 -- 13 houses the ``list-of-native-first-set-terminals'' component:
+the grammar's explicitly used terminals within its first set where there this
+example has none.
+The ``list-of-transitive-threads'' component: lines 14 -- 16
+indicates the directly called threads from their first set.
+This list is recursively called
+by assessing their called threads's ``fsc'' files:
+the transitive adjective is a memory jog to recursion.
+Please see |first_set_for_threads| grammar on how the
+thread's first set is calculated as
+there is a subtle difference caused by the \INVshift
+in its first set calculation versus
+the regular first set calcaluation of a rule or lr state.
+Lines 17 -- 28 is a cross reference
+list of used threads throughout the grammar
+ and not just the first set.
+Lines 29 -- 30 is the extracted fsm-comments from the grammar.
+It is used in generating the Linker's document indexing
+all the grammars with their comments, and
+their called thread graph with highlighting of nested grammars.
+
+@*2 Linker's control language.\fbreak
+There is not much to this control file.
+It provides the terminal vocabulary file,
+the file to output by Linker,
+a preamble that allows the grammar writer to insert code
+ahead of the ``to be emitted'' code, and finally
+the list of grammars' ``fsc'' files to process.
+Here is a sample of a handcrafted Linker control file drawn from the \o2
+parsing environment.\fbreak
+\let\setuplistinghook = \relax
+\listing{"/usr/local/yacco2/diagrams/intro4.txt"}
+\fbreak
+Basicly, Linker builds a graph by grammar and does its transitive moves to
+produce concrete first sets for each unresolved grammar or thread.
+To improve performance, a global thread map per terminal will be created
+indicating the potential threads that can be run.
+
+@*2 Catalogue of Linker's files.\fbreak
+Linker's Input files to |cweb|:\fbreak
+\ptindent{1) |o2linker.w| --- master Linker file that starts things off}
+\ptindent{2) |intro.w| --- inroduction }
+\ptindent{3) |prog.w| --- linker cweb code }
+\ptindent{4) |o2linker_externs.w| --- external procedures }
+\ptindent{5) |pms.w| --- running comments of life}
+\ptindent{6) |bugs.w| --- yep i do them}
+\ptindent{7) |testsuites.w| --- self proof of code}
+\ptindent{8) |sampleoutput.w|}
+\ptindent{9) |types.w| --- provides a way around burping output formats}
+\ptindent{10) |includes.w| --- C++ include code}
+\ptindent{11) /usr/local/yacco2/externals/common\_defs.w --- external procedures }
+\ptindent{12) |o2linker_defs.w| --- external procedures }
+
+|cweb| generated files:\fbreak
+\ptindent{1) |o2linker.h| --- linker definitions}
+\ptindent{2) |o2linker.cpp| --- linker program}
+\ptindent{3) |xxx.cpp| --- first sets for grammars provided by the input file}
+
+\Yacco2 library memorabilia:\fbreak
+\ptindent{1) yacco2 --- library namespace}
+\ptindent{2) ``\Whereyacco2/library'' --- \yacco2's library directory}
+\ptindent{3) ${< yacco2.h >}$ --- Yacco2's library header file}
+\ptindent{4) ``\Whereyacco2/library/lib/xxxx'' - xxxx is the Debug or Release of the object library}
+\ptindent{5) ``yacco2build.a'' - static \yacco2's library}
+
+Dependency files from other Yacco2 sub-systems:\fbreak
+\ptindent{|yacco2.h| - basic definitions used by Yacco2}
+\ptindent{|yacco2_T_enumeration.h| - terminal enumeration for \Yacco2's terminal grammar alphabet}
+\ptindent{|yacco2_err_symbols.h| - error terminal definitions from \Yacco2's grammar alphabet}
+\ptindent{|yacco2_characters.h| - raw character definitions from \Yacco2's grammar alphabet}
+\ptindent{|yacco2_k_symbols.h| - constant terminal definitions from \Yacco2's grammar alphabet}
+\ptindent{|yacco2_terminals.h| - regular terminal definitions from \Yacco2's grammar alphabet}
+\ptindent{|*.h| - assorted grammar definitions from \Yacco2 to parse}
+\ptindent{|o2linker_externs.h| - external support routines common for \olinker}
+
+Dictionaries\fbreak
+\ptindent{|T_DICTIONARY| --- terminals}
+\ptindent{|GRAMMAR_DICTIONARY|}
+\ptindent{|YACCO2_STBL| --- symbol table}
+\ptindent{|USED_THREADS_LIST|}
+\ptindent{|THREAD_ID_FIRST_SET|}
+\ptindent{|T_THREAD_ID_LIST|}
+Grammars\fbreak
+\ptindent{|T_alphabet.lex|}
+\ptindent{|linker_pass3.lex| --- control file parser }
+\ptindent{|link_cleanser.lex| --- lexical grammar stripping off comments etc}
+\ptindent{|fsc_file.lex| --- syntactic grammar of fsc file}
+Document\fbreak
+\ptindent{|o2linker_doc.w| --- overall index describing the grammars processed: cweave / pdftex}
+
+@*2 Global macro definitions.\fbreak
+@d SPECULATIVE_NO_BIT_WORDS 20
+@d LR1_QUESTIONABLE_SHIFT_OPERATOR 0
+@d LR1_EOG 1
+@d LR1_EOLR 2
+@d LR1_PARALLEL_OPERATOR 3
+@d LR1_REDUCE_OPERATOR 4
+@d LR1_PROCEDURE_CALL_OPERATOR 7
+@d LR1_INVISIBLE_SHIFT_OPERATOR 5
+@d LR1_ALL_SHIFT_OPERATOR 6
+@d LR1_FSET_TRANSIENCE_OPERATOR 7
+@d SMALL_BUFFER_4K 1024*4
+@d BITS_PER_WORD 32
+@d TOTAL_NO_BIT_WORDS 1024*2*100
+