diff options
Diffstat (limited to 'web/yacco2/compiler/o2/intro.w')
-rw-r--r-- | web/yacco2/compiler/o2/intro.w | 417 |
1 files changed, 417 insertions, 0 deletions
diff --git a/web/yacco2/compiler/o2/intro.w b/web/yacco2/compiler/o2/intro.w new file mode 100644 index 0000000000..233feef680 --- /dev/null +++ b/web/yacco2/compiler/o2/intro.w @@ -0,0 +1,417 @@ +@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 \O2 --- Yacco${_2}$'s nickname.\fbreak +The compiler / compiler's formal name is \Yacco2 but call me \O2. +\Yacco2 can be morphed many ways; here are some hints: sound of a cold, molecular contortions. +Do your own expletives. +@*2 Component overview running \O2.\fbreak +I use a ``.lex'' extension to distinguish a grammar file. +This is not hard coded. You can choose your own memory mnemonics for any of my files. +The ``.T'' file extension identifies the Terminal vocabulary. +Its components are described later in the document. +The Lrk and Rc terminals are pre-assembled and reside in the +``\Whereyacco2/library/grammars'' account. +My original thought was to allow the compiler writer to experiment with his own +terminal definitions for all classes: LR constants, raw characters, errors, and terminals. +From experience, only the last 2 classes are local to each language being defined. +\fbreak +\fbreak +\convertMPtoPDF{"/usr/local/yacco2/diagrams/o2_overview.1"}{1}{1} +\fbreak +\fbreak +Please note, the ``header'' files are absent from the diagram due to space constraints. +The salient ones to note are:\fbreak +\ptindent{1) the enumeration of the vocabulary's symbols} +\ptindent{2) headers for fsm, and the terminal classifications: lrk,error,rc,and T} +Per compiled ``xxx.lex'' grammar, the 2 status files ``xxx\_tracings.log'' and ``xxx\_errors.log'' +hold the text-only compiled results lodged within the local grammar's folder. +``T-Alphabet'' gets gened when the ``-t'' option is inputted +to gen the Terminal vocabulary. +It is a file by defined order of all the terminals's literal names + used as comments against the outputted lookahead tables +to make sense of their compressed set definitions. +Its file name is built from the grammar's ``T-enumeration'' construct +using its filename and adding +a ``.fsc'' extension. +\Olinker cross checks the number of terminals defined + in the ``no-of-T'' value in each grammar's ``fsc'' file against this file. +Out-of-sync values indicates that new terminals have been added to +either the ``error'' or ``terminal'' class terminals vocabulary + without gening up the grammar with the ``-t'' and/or ``-err'' option(s). +The ``yyy.fsc'' file is the grammar writer's handcrafted file containing +references to these ``xxx.fsc'' files +and the T-Alphabet file for \Olinker to +compile. Its name can be anything but i use the ``.fsc'' as a memory jog. +Please see \Olinker's documentation on its raison d'\^etre and make file comments. + +@*3 Tracing facilities.\fbreak +Some of the more important tracing facilities are as follows where their mnemonic +replaces the ``xx'': \fbreak +\ptindent{TH --- dynamic trace of the grammar's parse stack when its ``debug option is true} +\ptindent{T --- trace terminals fetched across all grammars} +\ptindent{AR --- trace arbitration when grammar's debug switch is true} +\ptindent{MSG --- dynamic threading messages between the co-operatives} +Please see \O2's library documentation concerning +each tracing variable when set to 1 within your +program by the programmer: ``yacco2::YACCO2\_xx\_\_ = 1;'' +starts their specific scribblings. +There are other less important trace variables not listed above. +The turned on \O2's library trace facility will log to ``xxx\_tracings.log' file where `xxx' +represents the grammar being parsed without its extension. +As the ``xxx\_tracings.log'' is text-only content, this allows the use of a general text editor +to browse its material. +If the editor has indigestion due to its volume, a script can be written to postprocess +it for study by the ``sed'' / ``grep'' combo or using just the ``split'' utility. + +@*2 Grammar anatomy.\fbreak +The grammar is composed of your traditional +components: start rule, non-terminal vocabulary, +terminal vocabulary, and 2 additional parts: fsm and syntax directed code. +``fsm'' (short for finite state machine) is a packaging agent. +It houses all the grammar's software generated parts along with +the c++ syntax directed code within the grammar + associated with their directives. +These directives are local to the grammar's rules, subrules, and possibly + the grammar's start-run-finish sequence that is handled within the fsm. +``fsm'' supplies the grammar's c++ namespace, + class name, and filename prefix to output the components to. + +@*2 Terminal vocabulary.\fbreak +From the diagram below, the ``enumeration'' component is a packaging agent that +receives the outputed enumeration definitions for each terminal class. +The counting scheme uses the natural numbers +starting from 0 listing the ``lrk'' constants, followed by each of the +other components's terminals. +The last component ``terminals'' is your regular terminal definitions that gets assembled from +the lexical or syntactical passes, and possibly out into etherland of abstraction. +All vocabulary elements are tagged this way. +It is the glue to all the emitted tables. +For the record, each grammar's non-terminal vocabulary (rules) + are enumerated after the terminal enumeration count +and are defined within the grammar's fsm class definition. +The rules's subrules are also enumerated and defined there. +They are not dependent on the Terminal vocabulary. +\fbreak +\fbreak +\convertMPtoPDF{"/usr/local/yacco2/diagrams/o2_Toverview.1"}{1}{1} +\fbreak + + +@*2 Overview of generating the grammar's pdf and postscript(ps) documents.\fbreak +There are 2 generated documents using the ``-p'' option emitting +``cweave'' content and associated ``mpost'' diagrams for compilation:\fbreak +\INDENT{.35in}{1) grammar with its syntax direct code,} +\INDENT{.5in}{emitted \O2linker file, and gened lr1 state network} +\INDENT{.35in}{2) various cross references against the grammar, and lr1 state network} +\INDENT{.7in}{- symbols used from each rule's subrules symbol string position} +\INDENT{.7in}{- additional information supporting the lr1 state network in the 1st document} +\INDENT{1in}{$\bullet$ each lr1 state's rules follow sets} +\INDENT{1in}{$\bullet$ reducing states subrules with references to their contributors' follow sets} +\INDENT{1in}{$\bullet$ global lookahead sets with their yield used by the parse reduce operation} +The below diagram shows the manufacturing +of a grammar's document. +\fbreak +\fbreak +\fbreak +\convertMPtoPDF{"/usr/local/yacco2/diagrams/docgeneration.1"}{1}{1} +\fbreak +\fbreak +Also for each ``pdf'' document generated there is a postscript document to +remove the dependency of a ``pdf reader'' and its ``gui'' interaction when wanting to +spool the document for print. +For example on my Sun Solaris, the program ``pdftops'' +takes a ``pdf'' document and creates an equivalent ``ps'' document. +Spooling it to a print would use the command line ``lp xxx.ps''. + +@*2 A sample \O2 script where the options are described.\fbreak +\O2's input data template is $[options]$ filename where options are optional as +they have preconfigured values. +Here are the switches that can be inputted to \O2 using the Unix approach to turn +on the specific option. Each option must be inputted with its own $-$ sign.\fbreak +{\bf Options}: if they are not present, do not generate\fbreak +\ptindent{1) -t --- generate the Terminal vocabulary} +\ptindent{2) -err --- generate the Error vocabulary} +\ptindent{3) -lrk --- generate the lr k vocabulary: Deprecated not supported} +\ptindent{4) -rc --- generate the Raw characters vocabulary: Deprecated not supported} +\ptindent{5) -p --- generate the grammar's documents} +Points 1 and 2 are usually stable and do not need to be gened. Do so when these +vocabularies have been modified. Don't forget to regen all the grammars +and re-run \O2{}linker to reprocess the ``fsc'' files if the number of +Terminals in the vocabularies has changed as all the Lookahead sets are now different along +with the enumeration scheme that ties them together. +Points 3 and 4 cannot be used as they reside in ``\Whereyacco2/library/grammars'' pregened. +I included them as a memory jog to my +experiments; if u try to input these deprecated options u'll get an error message. +Other options were experimented with but found boarderline marginal: +gen namespace, gen the grammar, and turn on debug of grammar instead of using the editor cycle to +modify the grammar to be traced. Now namespace and grammar are always generated, and hello editor. +So out damn spot. + +Here is a batch command file that runs on a Microsoft's NT/XP desktop. +The same can be done within a ``Unix'' flavour script language like ``Bash''. +Though it does not illustrate a conditional test as to whether +the script should continue when the grammar is faulty, +\O2 returns a 0 to indicate a healthy grammar +and a 1 to indicate a sick grammar: +The gory details are in the error log. +\let\setuplistinghook = \linenumberedlisting +\listing{"/usr/local/yacco2/diagrams/o2run_example.txt"} +\fbreak +\let\setuplistinghook = \relax +The above example uses line numbers delimited by ``:'' at the start of each +line for commentary purposes. +Line 3 sets the directory where \O2 resides and repository +for the temporary files from \O2, ``mpost'' that draws the grammar diagrams, +while ``cweave'' generates the ``xxx.tex'' file for ``pdftex'' +who completes the document for an ``Adobe'' reader program: for example ``xpdf'' of open source +or Adobe's reader. +``cweave'' is one of the programs by Donald E. Knuth and Silvio Levy +from their book ``The CWEB System of Structured Documentation''. +Go to the web site ``www.tex.org'' for more information on how to obtain +``CWEB''. The same comments apply to ``mpost'' written by John D. Hobby of +`Bell Labs''. +This is a remake of ``MetaFont''language / ``MetaPost'' program by Donald E. Knuth. +These programs are grrrreat! More people should be using them. +The emitted grammar files get placed in the same directory +of the inputted grammar to \O2. + +Line 6 runs \O2 with its inputted grammar file +``/yacco2/compiler/grammars/enumerate\_grammar.lex'' +and switches to gen up the Terminal and Error vocabularies +and gen a printed set of documents. +\O2 also generates the documentation files + ``enumerate\_grammar.mp'' and ``enumerate\_grammar.w'' files. +Lines 7--9 are command lines to create the output document. +In the example, ``enumerate\_grammar.pdf'' is the final +file document for printing. +``enumerate\_grammar.xx'' are figure files generated by mpost from file +``enumerate\_grammar.mp''. +These files are referenced in the ``enumerate\_grammar.w'' +file by cweave who produces an ``enumerate\_grammar.tex'' file for program pdftex. +All this to say that there can be many generated files before the document is complete. +Please note the other cross reference document +is not shown but follows the same run pattern. + +@*2 Some definitions.\fbreak +\fbreak +Non-terminal:\fbreak +This is your normal grammar definition. I interchange this term with ``rule''. +They are the same. Depending on the context, i also use rule +in the same sense of a grammar's production. +To refine the context, the term ``subrule'' indicates one of a rule's productions.\fbreak +\fbreak +Subrule:\fbreak +Equivalent to a grammar's production. +It is one of a rule's right-hand-side string of symbols drawn from +the non-terminal or Terminal alphabets. +The string can be empty indicating epsilon.\fbreak + +Please see the mavelous book ``Formal Languages and Their Relationn to Automata'' +by Hopcroft and Ullman for a complete discussion on grammars and their makeup. +Excellent reading for a 1968 vintage on automata.\fbreak +\fbreak +Here are some basic definitions used by my lr1 generator.\fbreak +\fbreak +First set:\fbreak +Please see |first_set_rules.lex| grammar for a more thorough discussion. +First set is the set of terminals that begins a string of symbols. +When the symbol is a rule, then all its subrules contribute to the first set. +This is a recursive definition as the rule's subrules can also bring in other +rules' subrules string of symbols that contribute to it. +If the string's start symbol is a rule and its epsilonable, +then its right neighbour also contributes. Again if its a rule and epsilonable +its right neighbour is a contributor: ahh recursive definitions. +\fbreak +\fbreak +Follow set:\fbreak +The rule's first set of production strings to the right of a lr state's configuration. +Here is a simple arithmetic grammar to illustrate follow sets for the ``Closure-only'' state +where all production strings have their configuration +position at their very beginning illustrated by ''$ _.$''. +I use a form of Dewey decimal notation to reference the production's configuration. +For example ``E.1.2'' means the production of rule ``E'' referencing subrule 1 +of its second symbol is being refered to. +In this example below the referenced symbol is $+$. +How follow sets are arrived at is discussed in ``Overview of \O2's state generated components''. + \fbreak + +\settabs\+\indent&1in\qquad&\qquad&\qquad&\cr +\+&\it Rule&&{\it subrule's symbols}\cr +\+&S &$\rightarrow$ &$ _.$E $\bot$\cr +\+&E &$\rightarrow$ &$ _.$E $+$ T\cr +\+&&$\rightarrow$ &$ _.$T\cr +\+&T&$\rightarrow$ &$ _.$T $*$ F\cr +\+&&$\rightarrow$ &$ _.$F\cr +\+&F&$\rightarrow$ &$ _.$( E )\cr +\+&&$\rightarrow$ &$ _.$id\cr +\fbreak +\settabs\+\indent&mmmmmm&\qquad&followset&\qquad&R.SR.Pos follow setxxxxxx &\qquad&transitions&\cr +%\settabs 4 \columns +\+&\it Rule&&{\it follow set}&& {\it R.SR.Pos of follow set}&&{\it with transitions}\cr +\+&E && $\bot\ +$ &&$\bot$ by S.1.2, $+$ from E.1.2&& $\bot\ +$\cr +\+&$\uparrow$ && && E.2.2\cr +\+&T&& $*$&&$*$ by T.1.2&&$*\ \bot\ +$\cr +\+&$\uparrow$ && && T.2.2\cr +\+&F&& $\emptyset$&&&&$*\ \bot\ +$\cr +\fbreak +\hbox{\hskip.5in Table of follow sets for the ``Start state'' of the above grammar}\fbreak + +There are 3 subtleties that are watched for in the follow set calculation:\fbreak +\ptindent{1) rule symbol --- use its ``first set''} +\ptindent{2) epsilonable rule symbol --- continue to next symbol in follow string for assessment} +\ptindent{3) end of symbol string reached --- transition} +Point 3 requires some explanation. +Its condition means that the rule's right-hand-side has been consumed (or is epsilon) + so what's +it follow set? Nothing? +No it's the subrule's rule that spawned it that provides more follow set context. +This context resides in the ``closure'' state of this rule. +So now there is a transition to this rule's follow set. +This is the transitive closure of spawning contexts. +The Table of follow sets shows these transitions with the $\uparrow$ symbol. +Epsilon rules are chameleon in nature: they supply their first sets and +also disappear and so u must continue to the next symbol in the follow string +to complete the follow set while observing the +end-of-string condition to follow its transitions. + +@*2 Catalogue of \O2's files.\fbreak +Cweb Documents:\fbreak +\ptindent{1) \Yacco2 parse library} +\ptindent{2) \o2{}extern --- external routines} +\ptindent{3) \Yacco2{}stbl --- symbol table} + +\O2's Input files to |cweb|:\fbreak +\ptindent{1) |o2.w| --- master file that starts things off} +\ptindent{2) |intro.w| --- introduction } +\ptindent{3) |defs.w| --- basic definitions to gen lr1 network} +\ptindent{4) |prog.w| --- \o2 cweb code } +\ptindent{5) |bug.w| --- confessions} +\ptindent{6) |o2_defs.w| --- details} +\ptindent{7) |includes.w| --- bring in those grammars for the parsing} +\ptindent{8) |o2externs.w| --- external routines} +|cweb| generated files:\fbreak +\ptindent{1) |o2.h| --- compiler definitions} +\ptindent{2) |o2.cpp| --- \O2 program} +\ptindent{3) |o2_defs.cpp| --- structure implementations} +\ptindent{4) |o2_externs.h| --- global definitions used across \o2's source code} + +\O2's generated files where xxx is the grammar's name being compiled:\fbreak +\ptindent{1) |xxx.fsc| --- grammar's first set confessions for Linker} +\ptindent{2) |xxx.h| --- grammar's header file} +\ptindent{3) |xxx.cpp| --- automaton code} +\ptindent{4) |xxxsym.cpp| --- automaton symbols} +\ptindent{5) |xxxtbl.cpp| --- automaton's state definitions} + +\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) ``library directory/xxxx'' - xxxx is the debug or release of the object library} + +Dependency files from \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{|o2_externs.h| - external support routines for \O2} + +Grammars\fbreak +\ptindent{|pass3.lex| --- lex and syntactic phase of grammar} +\ptindent{|la_expr_source.lex| --- lexical phase of lookahead expression} +\ptindent{|la_expr.lex| -- syntactic phase of lookahead expression} +\ptindent{|enumerate_T_alphabet.lex| -- logic grammar to assign each T a number from 0..n} +\ptindent{|epsilon_rules.lex| -- grammar determines epsilon per rule and pathological conditions} +\ptindent{|first_set.lex| -- logic grammar to calculate each rule's first set} +\ptindent{|prt_fs_of_rules.lex| -- logic grammar to print each rule's first set} +\ptindent{|enumerate_grammar.lex| -- dump aid: enumerate grammar's components} + +Globals\fbreak +\ptindent{|LR1_STATES| --- list of gened lr1 states} +\ptindent{|LR1_COMMON_STATES| --- common states map having same vectored into symbol} +\ptindent{|START_OF_RULES_ENUM| --- used in shift / reduce conflict evaluation} + +Comments:\fbreak +My external routines use the all upper case approach to names. I know it's like shouting but it +clues the reader where the heck the routine comes from. I could have +tempered the all caps approach to a capital letter +but i'm myopic and becoming +visually golden in age. +So my excuses to the reader for this tasteless approach. + +@*2 \O2's language.\fbreak +There are 3 languages that are actually parsed: 2 in preparation --- +command line and its contents, and the grammar file. +A grammar is divided into 4 parts:\fbreak +\ptindent{a) Finite automaton definition --- basic statements about the grammar} +\ptindent{b) Parallel parse that defines a threading grammar} +\ptindent{c) Terminal vocabulary: errors, lr k, raw characters, and terminals} +\ptindent{d) Rule definitions} + +\let\setuplistinghook = \linenumberedlisting +\listing{"/usr/local/yacco2/diagrams/eol.txt"} +\fbreak +\let\setuplistinghook = \relax + +The above source listing is an example of a threaded grammar. +Starting each source line is a line number suffixed by `:' present +only for discussion purposes. +Line numbers 6--10 defines the fsm component. +Lines 11--19 indicates that the grammar is a thread. +Though the terminal vocabulary definitions are hidden +by line 20, it illustrates the file include feature of \O2. +Lines 22--39 are the rule definitions. +Each grammar's section has a defining keyword like ``fsm'', ``parallel-parser'', ``rules'' +that introduces the part being defined. + + +@*2 C macros.\fbreak +Originally there were conditionally defined trace variables +that controlled the inclusion of trace code. +This was a pain-in-the-seat so now they are global +variables that test their values. +I felt the slight speed bump merited the facility without the +combinatorics of libraries needed for distribution. +|YACCO2_define_trace_variables| macro defines these global variables used +by \O2's tracing purposes. +U can roll your own or just include the macro in your code. +These variables are dormant until their values are not zero. +Without their inclusion, a linker message of unresolved variable will be +regurgitated: they must be present +when using the \O2 library. It's an easy way to define them within your program. +Please see \O2 library documentation for a discussion on each trace variable. +To activate a specific tracing, assignment a non zero value to +the selected trace variable: set it to 1. +Here is their catalogue:\fbreak +\ptindent{|YACCO2_T__| --- trace terminal when fetched} +\ptindent{|YACCO2_TLEX__| --- trace macros of emitted grammar: rules and user emergency macros} +\ptindent{|YACCO2_MSG__| --- trace thread messages} +\ptindent{|YACCO2_MU_TRACING__| --- trace acquire / release of trace mutex} +\ptindent{|YACCO2_MU_TH_TBL__| --- trace acquire / release mutex of thread table} +\ptindent{|YACCO2_MU_GRAMMAR__| --- trace acquire / release each grammar's mutex} +\ptindent{|YACCO2_TH__| --- trace the parse stack: fsa and syntax directed activities } +\ptindent{|YACCO2_AR__| --- trace arbitrator procedure} +\ptindent{|YACCO2_THP__| --- trace thread performance} +They are enrobed by namespace yacco2. +To set the trace variable be sure the namespace is delared: either explicitly +as in: \fbreak +\ptindent{|yacco2::YACCO2_T__| = 1;} + or implicitly by a ``using namespace yacco2;'' statement +somewhere preceding the assignment:\fbreak +\ptindent{using namespace yacco2;} +\ptindent{...} +\ptindent{|YACCO2_T__| = 1;} +\fbreak +Each traced output line identifies its type by the trace variable turned on. +As tracing can be very very volumnious, post evaluating the output thru +a Bash type filter script makes the log output manageable. +I say this from experience as some editors blow up due to the size of the traced file. +Names withheld to protect the innocent. + |