summaryrefslogtreecommitdiff
path: root/support/splint/examples/ld/ldman.w
blob: b6eb733dbde514c0069f258b7f69a297d50a7924 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
% Copyright 2012-2020, Alexander Shibakov
% Copyright 2002-2014 Free Software Foundation, Inc.
% This file is part of SPLinT
%
% SPLinT is free software: you can redistribute it and/or modify
% it under the terms of the GNU General Public License as published by
% the Free Software Foundation, either version 3 of the License, or
% (at your option) any later version.
%
% SPLinT is distributed in the hope that it will be useful,
% but WITHOUT ANY WARRANTY; without even the implied warranty of
% MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
% GNU General Public License for more details.
%
% You should have received a copy of the GNU General Public License
% along with SPLinT.  If not, see <http://www.gnu.org/licenses/>.
@s TeX_ TeX
\def\MRI{{\sc MRI}}
\def\optimization{5}
\input ldman.sty
\modenormal
\input ldfrontmatter.sty
\input noweb.sty
    \xreflocaltrue
    \readlxrefs % read the reference file if exists before any sections appear
    \newwrite\xrefstream % references for noweb like style of sectioning.
    \immediate\openout\xrefstream=\jobname.xxr
% multi-column output
\input dcols.sty

\let\oldN\N
\let\N\chapterN
\let\M\textM

\showlastactiontrue
\immediate\openout\gindex=\jobname.gdx
@** Introduction.
\setupfootnotes
This is a manual documenting the development of a parser that can be
used to typeset \ld\ files (linker scripts) with or without the help
of \CWEB. An existing parser for \ld\ has been adopted as a base, with
appropriately designed actions specific to the task of
typesetting. The appendix to this manual contains the full source code
(including the parts written in \Cee) of both the scanner and the parser for \ld,
used in the original program. Some very minor modifications have been
made to make the programs more `presentable' in \CWEB\ (in particular, the
file had to be split into smaller chunks to satisfy \CWEAVE's
limitations). 

Nearly every aspect of the design is discussed, including the
supporting \TeX\ macros that make both the parser and this
documentation possible. The \TeX\ macros presented here are collected
in \.{ldman.sty} which is later included in the \TeX\ file produced by \CWEAVE.
@<Set up the generic parser machinery@>=
@G(t)
\ifx\optimization\UNDEFINED %/* this trick is based on the premise that \.{\\UNDEFINED} */
    \def\optimization{0}    %/* is never defined nor created with \.{\\csname$\ldots$\\endcsname} */
\fi

\let\nx\noexpand    %/* convenient */

\input limbo.sty    %/* general setup macros */
\input yycommon.sty %/* general routines for stack and array access */
\input yymisc.sty   %/* helper macros (stack manipulation, table processing, value stack pointers */
                    %/* parser initialization, optimization) */
\input yyinput.sty  %/* input functions */
\input yyparse.sty  %/* parser machinery */
\input flex.sty     %/* lexer functions */

\ifnum\optimization>\tw@
    \input yyfaststack.sty
\else
    \let\stashnext\stashnextwithnothing
\fi

\input yystype.sty  %/* scanner auxiliary types and functions */
\input yyunion.sty  %/* parser data structures */
\input yxunion.sty  %/* extended parser data structures */
\expandafter\def    %/* adjust the \.{\\yyinput} to recognize \.{\\yyendgame} */
    \expandafter\multicharswitch\expandafter
    {\multicharswitch\yyendgame{\yyinput\yyeof\yyeof\endparseinput\removefinalvb}}
\input ldunion.sty  %@>/* \ld\ parser data structures */@+
@g

@*1 Bootstrapping. 
To produce a usable parser/scanner duo, several pieces of code must
be generated. The most important of these are the {\it table files\/}
(\.{ptab.tex} and \.{ltab.tex}) for the parser and the scanner. These
consist of the integer tables defining the operation of the parser and
scanner automata, the values of some constants, and the `action switch'.

Just like in the case of `real' parsers and scanners, in order to
make the parser and the scanner interact seamlessly, some amount of `glue'
is required. As an example, a file containing the (numerical)
definitions of the token values is generated by \bison\ to be used by
a \flex\ generated scanner. Unfortunately, this file has too little
structure for our purposes (it contains definitions of token values
mixed in with other constants making it hard to distinguish one kind of
definition from another). Therefore, the `glue' is generated by
parsing our grammar once again, this time with a \bison\ grammar
designed for typesetting \bison\ files. A special {\it
bootstrapping\/} mode is used to extract the appropriate
information. The name `bootstrapping' notwithstanding, the parser and
lexer used in the bootstrapping phase are not the minimized versions
used in bootstrapping the \bison\ parser.

The first component generated during the bootstrapping pass is a list
of `token equivalences' (or `aliases') to be used by the lexer. Every
token (to be precise, every {\it named token type}) used in
a \bison\ grammar is declared using one of the 
\prodstyle{\%token}, \prodstyle{\%left}, \prodstyle{\%right},
\prodstyle{\%precedence}, or \prodstyle{\%nonassoc} declarations. If
no {\it alias\/} (see below) has been declared using a
\prodstyle{\%token} declaration, this name ends up in the |yytname|
array output by \bison\ and can be used by the lexer after associating
the token names with their numerical values (accomplished by
\.{\\settokens}). If all tokens are named tokens, no token equivalence
list is necessary to set up the interaction between the lexer and the
parser. In this case (the present \ld\ parser is a typical
example), the token list serves a secondary role: it provides hints
for the macros that typeset the grammar terms, after the \.{\\tokeneq}
macro is redefined to serve this purpose.

On the other hand, after a declaration such as `\prodstyle{\%token}
\.{CHAR} \.{"char"}' the string \.{"char"} becomes an alias
for the named token \.{CHAR}. Only the string version gets recorded in
the |yytname| array. Establishing the equivalence between the two
token forms can now only be accomplished by examining the grammar
source file and is delegated to the bootstrapping phase parser.

\leavevmode\namedspot{bootstrapstates}The other responsibility of the bootstrapping parser is to extract
the information about \flex\ {\it states\/} used by the lexer from the
appropriate source file. As is the case with token names, this
information is output in a rather chaotic fashion by the scanner
generator and is all but useless for our purposes. The original
bootstrapping macros were designed to handle \flex's \prodstyle{\%x}
and \prodstyle{\%s} state declarations and produce a \Cee\ file with the
appropriate definitions. This file can later be included by the
`driver' routine to produce the appropriate table file for the lexer.
To round off the bootstrapping mode we only need to establish the
output streams for the tokens and the states, supply the appropriate file
names for the two lists, flag the bootstrapping mode for the
bootstrapping macros and inline typesetting (\.{\\prodstyle} macros)
and input the appropriate machinery. 

This is done by the macros
below. The bootstrap lexer setup (\.{\\bootstraplexersetup}) consists
of inputting the token equivalence table for the \bison\ parser
(i.e.~the parser that processes the \bison\ grammar file) and defining
a robust token output function which simply ignores the token values
the lexer is not aware of (it should not be necessary in our case
since we are using full featured lexer and parser).
@<Define the bootstrapping mode@>=
@G(t)
\newwrite\tokendefs %/* token list */
\newwrite\stlist    %/* \flex\ state list */
\newwrite\gindex    %/* index entries */

\def\modebootstrap{%
    \edef\bstrapparser{dyytab.tex}%
    \bootstrapmodetrue
    \def\bootstraplexersetup{%
        \input bo.tok%
        \let\yylexreturn\yylexreturnbootstrap /* only return tokens whose value is known */
        %\let\yylexreturn\yylexreturnregular /* should also work */
    }%
    \input yybootstrap.sty%
    \input yytexlex.sty%
}
@g

@*1 Namespaces and modes. 
Every parser/lexer pair (as well as some other macros) operates
within a set of dedicated {\it namespaces\/}. This simply means that the macros
that output token values, switch lexer states and access various
tables `tack on' the string of characters representing the current
namespace to the `low level' control sequence name that performs the
actual output or access. Say, \.{\\yytname} becomes an alias of
\.{\\yytname[main]} while in the \.{[main]} namespace. When a parser
or lexer is initialized, the appropriate tables are aliased with a
generic name in the case of an `unoptimized' parser or lexer. The
optimized parser or lexer handles the namespace referencing internally.

The mode setup macros for this manual define several separate
namespaces:
{%
\def\aterm#1{\item{\sqebullet}{\ttl #1}: \ignorespaces}%
\setbox0=\hbox{\sqebullet\enspace}
\parindent=0pt
\advance\parindent by \wd0
\smallskip
\aterm{main}the \.{[main]} namespace is established for the parser
that does the typesetting of the grammar.

\aterm{ld}every time a term name is
processed, the token names are looked up in the \.{[ld]}
namespace. The same namespace is used by the parser that typesets \ld\
script examples in the manual (i.e.~the parser described here). This
is done to provide visual consistency between the description of the
parser and its output.

\aterm{small{ \rm and} ldsmall}the \.{[small]}namespace is used by the term
name parser itself. Since we use a customized version of the name parser, we
dedicate a separate namespace for this purpose, \.{[ldsmall]}.

\aterm{prologue}the parser based on a subset of the full \bison\
grammar describing prologue declarations uses the \.{[prologue]}
namespace.

\aterm{index}the \.{[index]} namespace is used for typesetting the
index entries and is not necessarily associated with any parser or
lexer. Somewhat confusingly, the macros that typeset \TeX\ entries, use
\.{index} (without the brackets) as a pseudonamespace to display \TeX\
terms in the index (due to the design of these typesetting macros, many
of them take parameters, which can lead to chaos in the index). These
two namespaces are not related but due to `hystorical' reasons (and the
poorly thought out \TeX\ typesetting macro design) the \.{index} name has
been retained. In addition, \.{index:visual} is used to adjust the sort order
of \TeX\ terms (similar to the way \.{\\prettywordpairwvis} macro does).


\aterm{flexre{\rm, }flexone{, \rm and} flextwo}the parsers for
\flex\ input use the \.{[flexre]}, \.{[flexone]}, and~\.{[flextwo]} namespaces for
their operation. Another convention is to use  the \.{\\flexpseudonamespace}
to typeset \flex\ state names, and the \.{\\flexpseudorenamespace} for typesetting
the names of \flex\ regular
expressions. Currently, \.{\\flexpseudo...} namespaces are set equal to
their non-\.{pseudo} versions by default. This setting may be changed
whenever several parsers are used in the same document and tokens with
the same names must be typeset in different styles.
All \flex\ namespaces, as well as~\.{[main]}, \.{[small]},
and~\.{[ldsmall]} are defined by the \.{\\genericparser}
macros. 

\aterm{cwebclink}finally, the \.{[cwebclink]} namespace is used for
typesetting the variables {\it inside\/} \ld\ scripts. This way, the
symbols exported by the linker may be typeset in a style similar to
\Cee\ variables, if desired (as they play very similar roles).

}
@<Begin namespace setup@>=
@G(t)
\def\indexpseudonamespace{[index]}
\def\cwebclinknamespace{[cwebclink]}
\let\parsernamespace\empty
@g

@ After all the appropriate tables and `glue' have been generated, the
typesetting of this manual can be handled by the {\tt normal} mode. Note
that this requires the \ld\ parser, as well as the \bison\ parser,
including all the appropriate machinery.

The normal mode is started by including the tables and lists and
initializing the \bison\ parser (accomplished by inputting
\.{yyinit.sty}), followed by handling the token typesetting for the
\ld\ grammar. 
@<Define the normal mode@>=
@G(t)
\newtoks\ldcmds

\def\modenormal{%
    \def\appendr##1##2{\edef\appnext{##1{\the##1##2}}\appnext}%
    \def\appendl##1##2{\edef\appnext{##1{##2\the##1}}\appnext}%
    \input yyinit.sty%
    \input yytexlex.sty% /* \TeX\ typesetting macros */
    \input ldtexlex.sty% /* \TeX\ typesetting specific to \ld */
    \let\hostparsernamespace\ldnamespace /* the namespace where tokens are looked up for typesetting purposes */
    @>@[@<Initialize \ld\ parsers@>@]
    @>@[@<Modified name parser for \ld\ grammar@>@]
}
@g

@ The \ld\ parser initialization requires setting a few global
variables, as well as entering the \.{INITIAL} state for the \ld\
lexer. The latter is somewhat counterintuitive and is necessitated by
the ability of the parser to switch lexer states. Thus, the parser can
switch the lexer state before the lexer is invoked for the first time
wreaking havoc on the lexer state stack.
@<Define the normal mode@>=
@G(t)
\def\ldparserinit{%
    \basicparserinit
    \includestackptr=\@@ne
    \versnodenesting=\z@@
    \ldcmds{}%
    \yyBEGIN{INITIAL}%
}
@g

@ This is the \ld\ parser invocation routine. It is coded according to
a straightforward sequence initialize-invoke-execute-or-fall back.
@<Define the normal mode@>=
@G(t)
\def\preparseld{%
    \let\postparse\postparseld
    \expandafter\hidecs\expandafter{\ldunion}% /* inhibit expansion so that fewer \.{\\noexpand}s are necessary */
    \toldparser
    \ldparserinit
    \yyparse
}

\def\postparseld{%
    \ifsaveparseoutput
        {\newlinechar=`^^J\immediate\write\exampletable{^^J\harmlesscomment
         parsed table: \the\ldcmds^^J^^J\harmlesscomment
         stashed stream:^^J\the\yystash^^J^^J\harmlesscomment
         format stream: ^^J\the\yyformat}%
        }%
    \fi
    \ifchecktable 
        \errmessage{parsed table: \the\ldcmds^^J^^J%
                    stashed stream: \the\yystash^^J^^J%
                    format stream: \the\yyformat}%
    \fi
    \restorecslist{ld-parser:restash}\ldunion % /* mark variables, preprocess stash */
    \setprodtable
    \the\ldcmds
    \restorecslist{ld-display}\ldunion
    \setprodtable /* use the \bison's parser typesetting definitions */
    \restorecs{ld-display}{\anint\bint\hexint} % /* $\ldots$ except for integer typesetting */
    \the\ldcmds
    \par
    \vskip-\baselineskip
    \the\lddisplay
}

\fillpstack{l}{%
    \preparseld
    {\preparsefallback{++}}% /* skip this section if parsing failed, put \.{++} on the screen */
    \relax %                 /* this \.{\\relax} serves as a `guard' for the braces */
}
@g

@ Unless they are being bootstrapped, the \ld\ parser and its
term parser are initialized by the normal mode. The token typesetting
of \ld\ grammar tokens is adjusted at the same time (see the remarks
above about the mechanism that is responsible for this). Most nonterminals
(such as keywords, etc.) may be displayed unchanged (provided the
names used by the lexer agree with their appearance in the script file,
see below), while the typeseting of others is modified in
\.{ltokenset.sty}. 

In the original \bison-\flex\ interface, token names are
defined as straightforward macros (a poor choice as will be seen
shortly) which can sometimes clash with the standard \Cee\ macros. 
This is why \ld\ lexer returns \prodstyle{ASSERT} as
\prodstyle{ASSERT\_K}. The name parser treats \.{K} as a suffix to
supply a visual reminder of this flaw. Note that the `suffixless' part
of these tokens (such as \prodstyle{ASSERT}) is never declared and
thus has to be entered in \.{ltokenset.sty} by hand.

The tokens that never appear as part of the input (such as
\prodstyle{END} and \prodstyle{UNARY}) or those that do but have no
fixed appearance (for example, \prodstyle{NAME}) are typeset in a
style that indicates their origin. The details can be found by
examining \.{ltokenset.sty}.
@<Initialize \ld\ parsers@>=
@G(t)
\genericparser 
    name: ld, 
    ptables: ptab.tex, 
    ltables: ltab.tex, 
    tokens: {}, 
    asetup: {}, 
    dsetup: {}, 
    rsetup: {},
    optimization: {};% /* the parser and lexer are optimized when output */
\genericprettytokens 
    namespace: ld, 
    tokens: ldp.tok, 
    correction: ltokenset.sty, 
    host: ld;%
@g

@ The macros are collected in a single file included at the beginning
of this documentation.
@(ldman.stx@>=
@<Set up the generic parser machinery@>@;
@<Begin namespace setup@>@;
@<Define the bootstrapping mode@>@;
@<Define the normal mode@>@;
@<Additional macros for the \ld\ lexer/parser@>@;

@i ldgram.x
@i ldlex.x

@** Example output. Here is an example output of the \ld\ parser designed in this
document. The original linker script is presented in the section that
follows. The same parser can be used to present examples of \ld\ scripts
in text similar to the one below.
\beginldprod
MEMORY
{
  RAM (xrw) : ORIGIN = 0x20000000, LENGTH = 20K
  FLASH (rx) : ORIGIN = 0x8000000, LENGTH = 128K
  ASH (rx) : ORIGIN = 8000000, LENGTH = 128K
  CLASH (rx) : ORIGIN = 700000, LENGTH = 128K
  ASH (rx) : ORIGIN = $8000000, LENGTH = 128K
  CLASH (rx) : ORIGIN = 700000B, LENGTH = 128K
  INCLUDE file.mem
}
\endprod
\noindent The syntax of \ld\ is modular enough so there does not seem to be a
need for a `parser stack' as in the case of the \bison\
parser. If one must be able to display still smaller segments of \ld\
code, using `hidden context' tricks (discussed elsewhere) seems to be
a better approach. 
%
@<Example \ld\ script@>=
@i ldexample_l.hx

@ @<The same example of an \ld\ script@>=
@i ldexample_b.hx

@ @<Some random portion of \ld\ code@>=

@i ldnp.x

@** Appendix. The original code of the \ld\ parser and lexer is reproduced below. It
is mostly left intact and is typeset by the pretty printing parser for
\bison\ input. The lexer (\flex) input is reproduced verbatim and is
left mostly unformatted with the exception of spacing and the embedded
\Cee\ code.

The treatment of comments is a bit more invasive. \CWEB\ silently
assumes that the comment refers to the preceding statement or a group
of statements which is reflected in the way the comment is
typeset. The comments in \ld\ source files use the
opposite convention. For the sake of consistency, such comments have
been moved so as to make them fit the \CWEB\ style. The comments meant to refer to a
sizable portion of the program (such as a whole function or a group
of functions) are put at the beginning of a \CWEB\ section containing
the appropriate part of the program.

\CWEB\ treats comments as ordinary \TeX\ so the comments are changed
to take advantage of \TeX\ formatting and introduce some visual
cues. The convention of using {\it italics\/} for the original
comments has been reversed: the italicized comments are the ones
introduced by the author, {\it not\/} the original
creators of \ld.%\checktabletrue\saveparseoutputtrue

@i ldgramo.x
@i ldlexo.x
@q Include the list of index section markers; this is a hack to get around @>
@q the lack of control over the generation of \CWEB's index; the correct order @>
@q of index entries depends on the placement of this inclusion @>
@i alphas.hx

@** Index. \checktablefalse\saveparseoutputtrue
This section lists the variable names and (in some cases)
the keywords used inside the `language sections' of the \CWEB\
source. It takes advantage of the built-in facility of \CWEB\ to supply
references for both definitions (set in {\it
italic}) as well as uses for each \Cee\ identifier in the text. 

Special facilities have been added to extend indexing to
\bison\ grammar terms, \TeX\ control sequences encountered in
\bison\ actions, and file and section names encountered in \ld\
scripts. For a detailed description of the various conventions adhered
to by the index entries the reader is encouraged to consult the
remarks preceding the index of the document describing the core of
the \splint\ suite. We will only mention here that (consistent with
the way \bison\ references are treated) a script example:
$$
\vbox{
\beginldprod
MEMORY
{
  MEMORY1 (xrw) : ORIGIN = 0x20000000, LENGTH = 20K
  MEMORY2 (rx) : ORIGIN = 0x8000000, LENGTH = 128K
}
_var_1 = 0x20005000;
\endprod
}%
$$
\noindent inside the \TeX\ part of a \CWEB\ section will generate several
index entries, as well, mimicking \CWEB's behavior for the
{\it inline \Cee\/} (\.{\yl}$\ldots$\.{\yl}). Such entries are labeled
with $^\circ$, to provide a reminder of their origin.
\unsetfootnotes
\def\next{\expandafter\eatone\string}
\edef\unindexable{{\next\the}{\next\nx}{\next\yy}{\next\yylexnext}{\next\else}{\next\fi}{\next\yyBEGIN}{\next\next}}
\input gindex.sty
\closeout\gindex
\termindexfalse
\let\inx\inxmod
\let\fin\finmod
\let\oldMRL\MRL
\def\MRL#1{\smash{\oldMRL{#1}}} % a more sophisticated way to handle it woud be to add a \smash whenever we are
                                % in the [index] namespace but this is simpler and works as well
\def\topofcontents{\null\vskip-3\baselineskip\centerline{C{\sc ONTENTS} (\sc\uppercase\expandafter{\title})}\medskip}