.\"	> do nroff -ms %F | col | sed -f ~pepe/ms/adhoc > l.%P
.\"  ***********************************************
.\"  (C) Copyright 1989-1993; dit/upm
.\"   Distributed under the conditions stated in the
.\"   EPS General Public License (see file LICENSE)
.\"  ***********************************************
.\"  $Log: tutorial.ms,v $
\" Revision 1.3  1993/01/12  16:35:29  eps
\" portability issues
\"
\" Revision 1.2  1990/01/29  14:52:38  eps
\" fixing license details
\"
\" Revision 1.1  90/01/25  18:03:35  eps
\" Initial revision
\" 
.\"  ***********************************************
.\"  $Id: tutorial.ms,v 1.3 1993/01/12 16:35:29 eps Exp $

.pl 12i
.
.nr LL 6.5i
.nr LT 6.5i
.nr FL 6.5i
.nr PO 1i
.
.de LI		\" numbered lists
.if \\n(.$ .nr nL \\$1-1 1
.IP \\*(lL\\n+(nL\\*(rL
..
.de AL
.ie \\n(.$ .af nL \\$1
.el .af nL 1
.ie \\n(.$>1 .ds rL \\$2
.el .ds rL .
.ie \\n(.$>2 .ds lL \\$3
.el .ds lL 
..
.			\" numbered header + TC entry
.de H
.NH \\$1
\\$2
.if \\n(IH-\\$1 \{\
.XS \\n(PN (\\n(NS-1)*4u
\\*(SN \\$2
.XE
.\}
..
.nr IH 3	\" index only for x.x.
.
.DS L
. ...............................................................
				      Ref     : SEDOS/C3/WP/9/M
				      Date    : October, 1986
				      Author  : Jos\*'e A. Ma\*~nas
				                Tom\*'as de Miguel
.DE
.ds LH EL PRADO Tutorial
.ds CH
.ds RH page %
.ds LF SEDOS/C3/WP/9/M
.ds CF
.ds RF (printed: \*(DY)
.TL
A Tutorial on EL PRADO 
.AU
Jos\*'e A. Ma\*~nas
<pepe@etsitm.iris>
Tom\*'as de Miguel
<tomas@etsitm.iris>
.AI
Dpt. Telem\*'atica
E.T.S.I.Telecomunicaci\*'on
Ciudad Universitaria
28040  MADRID
SPAIN
.AB
EL PRADO is a package to manipulate abstract syntax trees.
Here we present the functions provided 
and develop a simple application.
This paper should contain information  enough for most users.
.AE
.H 1 "The Story"
.QP
El Prado is a world famous museum sited at Madrid.
When you come into it,
with a very cheap entrance,
you will find a net of rooms
wisely connected by means of doors, stairs and corridors.
You may navigate through the rooms,
or maybe you prefer an ordered traversing.
You are not allowed to take a picture here
and place it there.
You are not allowed either to bring in your own pictures.
In each room you may find nice pictures
with very nice colouring.
Sadly enough,
you are not allowed to add new colours,
nor to delete the existing ones;
but you can take photographs,
bring them to your place,
and reproduce big pictures at home
(where, at last, you are allowed to do some repainting).
.LP
The software package
.I "EL PRADO"
has some relationship with
.I "El Prado" 
museum.
Let us paraphrase the story:
.QP
EL PRADO is a SEDOS/C3 famous package designed at Madrid.
When you come to use it,
with a very fast introduction,
you will find a tree of nodes
wisely connected by means of brothers, fathers and sons.
You may navigate through the nodes,
or maybe you prefer an ordered traversing.
You are allowed to take a subtree here
and place it there.
You are allowed either to bring in your own nodes.
In each node you may find nice [non]terminals
with very nice colouring.
Happily enough,
you are allowed to add new colours,
or to delete the existing ones;
and you can  write onto files,
bring them to your directory,
and reproduce big AST trees for your application
(where, you are allowed to do some repainting).
.LP
We are sure you will feel better with our package.
.H 1 "Introduction"
.PP
Abstract syntax trees are condensed versions of 
concrete syntax trees.
While the last ones hold as much information as 
a textual representation of a specification,
the AST formalism condenses it
looking for a smaller tree
where it is easy to navigate
and establish semantic properties.
.PP
The tool presented in this paper has been developed at 
The Politechnic University of Madrid.
It is SEDOS background software.
We plan to use it as a coherent representation for
the different groups involved in SEDOS/C3.
That means LOTOS,
but the tool is not restricted to LOTOS,
obviously.
.PP
It provides
standard internal and external formats,
and two C packages with functions for
construction,
destruction,
cut and paste,
navigation,
traversing,
colouring and
input and output
from one format to the other.
.PP
Special effort has been devoted to get
a flexible tool,
where hand editing is possible,
colouring may be defined by the application writer and
error conditions are detected and reported.
.PP
This tool is not a program by itself,
but fixes a methodology,
a common formalism and
provides a set of functions
to help application designers.
.H 1 "Package structure"
.PP
EL PRADO consists of five main files:
.IP astfunc.c
Provides syntax operations on the ast,
everything but colouring.
It is rather independent,
both of the language
(LOTOS, Pascal, ...)
and the concrete application.
.IP astdef.h
This is the standard header for the syntax part.
To be included in user programs.
.IP clrfunc.c
Provides operations on attributes \**.
.FS
We use attribute and colour as synonyms.
.FE
Each application uses different colouring for its treatment of the
AST.
This file does not need to be edited,
but will be recompiled after editing 
.I colours.h .
.IP clrdef.h
This is the standard header for the colour part.
To be refined by the user by means of
.I colours.h .
.IP nodes.h
A collection of defines
for tokens and non terminals that become AST nodes.
It is language dependent,
that is,
a different file is used for LOTOS 
that would be used for Pascal.
.LP
The user must provide, at least, a
.I colours.h
file that parameterizes 
.I clrdef.h ,
which in turn parameterizes 
.I clrfunc.c .
.PP
Besides that,
the user is expected to write an application that uses EL PRADO.
.PP
So, a simplistic relation tree would be
.DS L
<application file(s)>  include   astdef.h clrdef.h nodes.h ...
astfunc.c              includes  astdef.h
clrfunc.c              includes  clrdef.h
astdef.h               untouched
clrdef.h               includes  colours.h
colours.h              user defined
.DE
The real story is a little bit more complex.
See the "makefile" of the second example.
.H 1 "Formats"
.PP
In order for the different pieces to match,
we must agree on a common format,
both for the internal representation of nodes and colours,
and for the textual representation on files.
.PP
In this section we shall use a simple LOTOS specification
to introduce the different formats. 
The textual (source) input is
.DS L
     1	specification simple [ ext-gate ] : noexit
     2	    behaviour
     3		  ext-gate
     4		; stop
     5	endspec
.DE
.H 2 "Internal formats"
.H 3 Syntax
.PP
The syntactic part of the tree uses NODEs.
Each NODE is as follows
.DS L
	+------------+   A
	|  type      |   |
	+------------+   |
	|  father    >----
	+------------+
	|  brothers  >------>
	+------------+
	|  sons      >----
	+------------+   |
    <---<  attrs     |   |
	+------------+   V
.DE
In a proper tree,
every node has a nonNULL father, but the root;
every node has sons, but leafs.
The AST is not magic,
nor trivially designed after the concrete syntax.
The procedure starts with the concrete syntax.
It is edited
refining which information is just punctuation
(and is not needed in the AST),
and which terminals and non terminals are of semantic relevance
(and must be preserved in the AST).
Family relationships must be specified as well.
A coding scheme for types
(usually a short integer)
must be fixed.
These decisions are taken after foreseeing the intended use of the
AST.
Establishing semantic properties may be more or less complex
depending on the family structure.
.PP
For the case of LOTOS that has been already decided,
although it may be easily changed.
In SEDOS/C3/11/M 
the case for LOTOS is presented.
From that specification,
an automatic tool,
currently under development at the E.T.S.I.T.,
generates an AST builder,
something that inputs LOTOS standard text
and outputs a tree.
Since the tool is not yet available for the whole,
we have processed it by hand.
LASTB
(for Lotos Abstract Syntax Tree Builder)
is SEDOS/C3 foreground software.
See SEDOS/C3/12/M.
.PP
Let's go back to EL PRADO.
In C slang, the definition of a NODE is as follows:
.DS L
typedef struct Node {
	int         	type;
	struct	Node	*father;
	struct	Node	*brothers;
	struct	Node	*sons;
	TPATTR		attrs; \**
	} TNODE, *TPNODE;
.DE
.FS
In order to keep "astfunc" and "clrfunc" apart,
actual coding does not include a reference to "TPATTR",
but

	unknown		attrs;

where "unknown" is defined as "(int *)".
Users are expected to access attributes by means of "clrfunc.c"
that performs the required pointer castings.
If you plan to recode that part,
look at actual coding in "clrfunc.c",
but it is strongly discouraged.
.FE
.H 4 "The example specification"
.PP
Let us have in "simple.lot" the example specification.
Its syntax can be checked by "sclotos"

\&...>  sclotos simple

and the AST is build

\&...>  lastb simple

Now we have a file named "simple.ast".
Its format, external format, will be presented later on.
For the time being we shall present the internal representation.
We can use a simple program to draw it \**
.FS
Using EL PRADO libraries,
it is as simple as 1 line of code

	draw_tree (restore (stdin))
.FE
.DS L
node < -1 >
  node < 275 > lexv !simple! line !1!
  node < -28 > class !2!
    node < -59 >
      node < 275 > lexv !ext-gate! line !1!
    node < -29 > class !2! line !1!
  node < -3 >
  node < -38 >
    node < -40 >
      node < -41 >
        node < -43 >
          node < -42 >
            node < -44 >
              node < -45 >
                node < 275 > lexv !ext-gate! line !3!
              node < -44 >
                node < -49 > line !4! class !1!
.DE
There is one line per syntax node.
Vertical alignment stands for brothership relation.
Sons are indented two spaces.
The text after the right angle brackets stands for colours
and is explained below.
The number between angle brackets is the "type".
To find out the coding
you need
.I nodes.h .
Let us filter out that file keeping only those codes used in the
example:
.DS
# define IDENTIFIER                        275

# define tspecification                   -1
# define tdata_type_definitions           -3
# define tformal_parameter_list           -28
# define tfunctionality_list              -29
# define tenable_expression               -38
# define tdisable_expression              -40
# define tparallel_expression             -41
# define tguarded_expression              -42
# define tchoice_expression               -43
# define taction_prefix_expression        -44
# define taction_denotation               -45
# define tatomic_expression               -49
# define tidentifier_list                 -59
.DE
The tree may be drawn as boxes
with vertical links
(for father-son relationships)
and horizontal links
(for inter-brother relationships):
.DS L
+-----+
| -1  |
+--+--+
   |
+--V--+   +-----+   +-----+   +-----+
| 275 +---> -28 +---> -3  +---> -38 |
+-----+   +--+--+   +-----+   +--+--+
             |                   |
          +--V--+   +-----+   +--V--+
          | -59 +---> -29 |   | -40 |
          +--+--+   +-----+   +--+--+
             |                   |
          +--V--+             +--V--+
          | 275 |             | -41 |
          +-----+             +--+--+
                                 |
                              +--V--+
                              | -43 |
                              +--+--+
                                 |
                              +--V--+
                              | -42 |
                              +--+--+
                                 |
                              +--V--+
                              | -44 |
                              +--+--+
                                 |
                              +--V--+   +-----+
                              | -45 +---> -44 |
                              +--+--+   +--+--+
                                 |         |
                              +--V--+   +--V--+
                              | 275 |   | -49 |
                              +-----+   +-----+
.DE
.H 3 Attributes
.PP
For the colouring,
we use a list of colour nodes starting at "attrs":
.DS L
	+------------+
	|  atype     |
	+------------+
	|  next      >------>
	+------------+
	|  ?         |
	+------------+
.DE
Where the "?" field is to be defined by the user
(see
.I colours.h 
below).
In C language:
.DS L
typedef struct Attr {
	colour		atype;
	struct	Attr	*next;
	union {
		COLOURS		/* application dependent */
		} u;
	} TATTR, *TPATTR;
.DE
.H 4 "The example specification"
.PP
In the example we are using three colours
.DS
lexv      lexical value of the source token
line      source line
class     a syntactic refinement of the tree
          (see SEDOS/C3/WP/11/M for details).
.DE
We shall come back to colouring later on.
.H 2 "External formats"
.PP
When a tree is dumped onto a file,
the following format is used,
where there is a line per node:

key  link  { attribute /args(s)/ }

that is:
a <key> that identifies the type;
a <link> to rebuild the tree,
and zero or more pairs including a symbolic name for the colour
and its value between delimiters.
Let us put an example,

  275 C  lexv !Nat14! line !63!

is a node of type 275 
(in the current LOTOS AST,
that is an identifier),
that has a father, some brother(s) and no son.
In the tree that node has two attributes,
the first one, "lexv"
(for lexical value),
has an argument "Nat14".
The second colour, "line"
(for source text line),
has a value "63".
Roughly speaking
that node says that in line 63 there is an identifier named Nat14.
It is placed somewhere in the AST,
but understanding the link
(cryptically coded as "C")
will drive you into problems.
.PP
Standard user is expected to use the
.I astfunc
functions
.I save
and
.I restore
to write and read files.
But for debugging,
it will surely be useful to edit the attributes.
The user is not expected to edit the <type> and <link> fields.
.PP
For the attributes or colours,
the format is simple:
any string of letters and/or digits is a valid colour identifier.
The argument is mandatory and must be enclosed by any character that
does not appear within its value. \**
.FS
As in many editors when you refer to a text string.
.FE
Just plain text is accepted.
A null argument 
(i.e.\ //)
is ok.
Of course,
EL PRADO does not know which attributes are you to have,
so the user has to provide input output procedures.
That is the topic of the next section.
.H 3 "The example specification"
.PP
.I lastb
generates a file named "simple.ast"
that contains as much information as the drawing presented in a
previous section,
using this format:
.DS L
   -1 D 
  275 C  lexv !simple! line !1!
  -28 G  class !2!
   -3 C 
  -38 E 
  -40 E 
  -41 E 
  -43 E 
  -42 E 
  -44 E 
  -45 G 
  -44 E 
  -49 A  line !4! class !1!
  275 A  lexv !ext-gate! line !3!
  -59 G 
  -29 A  class !2! line !1!
  275 A  lexv !ext-gate! line !1!
.DE
Instead of indenting,
the <link> field is used.
.H 2 "I/O Formats"
.PP
When 
.I astfunc
is requested to save (write) a tree
or to restore (read) a tree,
it knows about the syntax part of the tree
(for which there is a fixed format),
but for colouring it calls the
.I clrfunc
functions
.I putattrs
and
.I getattrs .
These functions are table driven.
The table is called
.I iocolours
and the user is expected to fill it up for its application.
.PP
Let us start by presenting its format:
.DS L
typedef struct {
	char		*keyword;
	colour		atype;
	int		printit;
	int		(*get)();
	int		(*put)();
	} TIOCOLOURS;

			/* table to drive io of colours */
extern	TIOCOLOURS	iocolours[];
.DE
The first field holds the symbolic identifier of the attribute.
The second one is the internal coding.
The third one is a boolean flag that tells
.I putattrs
if that attribute is to be printed
or just for internal use.
.I get
is a user defined procedure
that translates the argument from external textual format
to the internal one.
.I put
does the reverse operation.
.PP
Let us present an example.
It is a user handling 3 colours

typedef	enum	colour	{c_line, c_lexv, c_class} colour;

The i/o table may be
.DS L
TIOCOLOURS iocolours [] = {		/* io driver */
	"line",  c_line,  TRUE, getline,  putline,
	"lexv",  c_lexv,  TRUE, getlexv,  putlexv,
	"class", c_class, TRUE, getclass, putclass,
	0
	};
.DE
The actual coding could be as simple as
.DS L
getline (attrp, buf)
	TPATTR	attrp;
	char	*buf;
{
	attrp->u.line= atoi (buf);
}

putline (attrp, buf)
	TPATTR	attrp;
	char	*buf;
{
	sprintf (buf, "%d", attrp->u.line);
}
.DE
The input parameters are always of that type,
a pointer to a colour node
and a pointer to a text buffer.
.PP
The functions for the "lexv" attribute
will surely be much more complex
(they may handle a hash table, for instance),
but the headers are similar:
.DS L
getlexv (attrp, buf)
	TPATTR	attrp;
	char	*buf;
{
	attrp->u.lexval= newid (buf);
}

putlexv (attrp, buf)
	TPATTR	attrp;
	char	*buf;
{
	sprintf (buf, "%s", attrp->u.lexval);
}
.DE
.I putattrs
takes care of choosing a correct delimiter for the argument.
.I getattrs
takes into account most possible input errors
(to cope with manual editing of ast files).
.PP
If you do not want to dump a certain colour,
set the 
.I printit
field to FALSE.
Or just do not put an entry for that colour in
.I iocolours .
If you do not want to load a certain attribute from an AST file,
just do not mention it in
.I iocolours .
.bp
.H 1 "Code libraries"
.PP
We shall present a terse documentation on the available functions
and their intended functionalities.
.H 2 "astfunc"
.LP
.DS l
Abstract syntax tree handling functions

 **********************************************************
	    prints node on stdout  -- debugging

PUBLIC draw_node (nodep)
	TPNODE	nodep;

 **********************************************************
	    prints tree on stdout
	    for debugging

PUBLIC draw_tree (tree)
	TPNODE	tree;
.DE
.DS L
 **********************************************************
	traversing modes : PREORDER
			   POSTORDER
 **********************************************************

 **********************************************************
	selects predecessor node of nodep
	NULL if there is none

PUBLIC TPNODE pred (nodep, tm)
	TPNODE		nodep;
	trav_mode	tm;

 **********************************************************
	selects successor node of nodep
	NULL if there is none

PUBLIC TPNODE succ (nodep, tm)
	TPNODE		nodep;
	trav_mode	tm;

 **********************************************************
	looks for a predecessor in the tree with such a type
	NULL if none

PUBLIC TPNODE look_pred (nodep, type, tm)
	TPNODE		nodep;
	int		type;
	trav_mode	tm;

 **********************************************************
	looks for a successor in the tree with such a type
	NULL if none

PUBLIC TPNODE look_succ (nodep, type, tm)
	TPNODE		nodep;
	int		type;
	trav_mode	tm;

 **********************************************************
	looks for a predecessor according to a predicate
	NULL if none

PUBLIC TPNODE lp_pred (nodep, predicate, tm)
	TPNODE		nodep;
	int		(*predicate) ();
	trav_mode	tm;

 **********************************************************
	looks for a successor according to a predicate
	NULL if none

PUBLIC TPNODE lp_succ (nodep, predicate, tm)
	TPNODE		nodep;
	int		(*predicate) ();
	trav_mode	tm;
.DE
.DS L
 **********************************************************
	goes to the father
	NULL if there is none

PUBLIC TPNODE goto_ft (nodep)
	TPNODE	nodep;

 **********************************************************
	goes to first son
	NULL if there is none

PUBLIC TPNODE goto_fs (nodep)
	TPNODE	nodep;

 **********************************************************
	goes to last son
	NULL if there is none

PUBLIC TPNODE goto_ls (nodep)
	TPNODE	nodep;

 **********************************************************
	goes to right brother
	NULL if there is none

PUBLIC TPNODE goto_rb (nodep)
	TPNODE	nodep;

 **********************************************************
	goes to left brother
	NULL if there is no father or left brother

PUBLIC TPNODE goto_lb (nodep)
	TPNODE	nodep;
.DE
.DS L
 **********************************************************
	creates a new node

PUBLIC TPNODE new_node (type)
	int	type;
.DE
.DS L
 **********************************************************
	adds new sons to a father
	They become the youngest brothers of old sons

PUBLIC ln_sons (pfather, psons)
	TPNODE	pfather;
	TPNODE	psons;

 **********************************************************
	inserts a new son as the n-th one of a father
	or last one if there are not so many

PUBLIC ln_n_son (father, son, n)
	TPNODE	father;
	TPNODE	son;
	int	n;

 **********************************************************
	a new brother is added as the youngest one
	the father of the old brothers
	becomes the father of the new one

PUBLIC ln_r_node (brothers, new)
	TPNODE	brothers;
	TPNODE	new;

 **********************************************************
	a new node becomes the oldest brother
	the father of the old brothers
	becomes the father of the new one

PUBLIC ln_l_node (brothers, new)
	TPNODE	brothers;
	TPNODE	new;

 **********************************************************
	puts a list of brothers to nodep
	the father of nodep
	becomes the father of all the brothers

PUBLIC ln_brothers (nodep, brothers)
	TPNODE	nodep;
	TPNODE	brothers;
.DE
.DS L
 **********************************************************
	checks if it is a root (no father)

PUBLIC int test_root (nodep)
	TPNODE	nodep;

 **********************************************************
	checks if it is a leaf (no son)

PUBLIC int test_leaf (nodep)
	TPNODE	nodep;

 **********************************************************
	checks if it is the first brother (right brother)

PUBLIC int test_first_brother (nodep)
	TPNODE	nodep;

 **********************************************************
	checks if it is a last brother (no right brother)

PUBLIC int test_brother (nodep)
	TPNODE	nodep;
.DE
.DS L
 **********************************************************
	cuts off from father and brothers

PUBLIC cut_tree (nodep)
	TPNODE	nodep;

 **********************************************************
	cuts off from father and brothers
	frees memory

PUBLIC kill_tree (tree)
	TPNODE	tree;
.DE
.DS L
 **********************************************************
	writes a tree on a file pointed by fp

PUBLIC save_tree (fp, tree)
	FILE	*fp;
	TPNODE	tree;

 **********************************************************
	restore a complete tree from a file

PUBLIC TPNODE restore(fp)
	FILE	*fp;

 **********************************************************
	allocs memory
	program aborts if not possible

PUBLIC char *emalloc(n)
	unsigned	n;
.DE
.bp
.H 2 "clrfunc"
.LP
.DS L
Attribute handling functions

 **********************************************************
	    adds colour to node
	    returns a pointer to the new colour node
	    NULL if that colour already exists

PUBLIC TPATTR add_attr (attr, nodep)
	colour attr;
	TPNODE nodep;

 **********************************************************
	    finds colour in node
	    returns a pointer to the colour node
	    NULL if that colour does not exist

PUBLIC TPATTR find_attr (attr, nodep)
	colour attr;
	TPNODE nodep;

 **********************************************************
	    takes off from colour list
	    (memory remains allocated)
	    returns a pointer to the colour node
	    NULL if that colour does not exist

PUBLIC TPATTR take_attr (attr, nodep)
	colour attr;
	TPNODE nodep;

 **********************************************************
	    gets colours from the file into the NODE
	    reads up to a new line
	    driven by table "iocolours"
	    able to cope with most error conditions

PUBLIC getattrs (fp, nodep)
	FILE *fp;
	TPNODE nodep;

 **********************************************************
	    prints the colours attached to that NODE
	    writes up to a new line
	    driven by table "iocolours"

PUBLIC putattrs (fp, nodep)
	FILE *fp;
	TPNODE nodep;
.DE
.bp
.H 1 "Application tailoring"
.PP
Some aspects have been already presented.
Mainly those related to I/O of attributes.
In this section we present how to parameterize the colour nodes.
As we already presented above,
the colouring is application dependent.
Remember,
.DS L
typedef struct Attr {
	colour		atype;
	struct	Attr	*next;
	union {
		COLOURS		/* application dependent */
		} u;
	} TATTR, *TPATTR;
.DE
There is an application dependent field,
.I COLOURS .
The user is expected to provide a
.I colours.h
file with that information.
For instance,
.DS L
/* ---------------------------------------------------- */
				/* colour fields */

# define COLOURS		\e
	int	line;		\e
	char	*lexval;	\e
	int	class;

				/* colour types */

typedef	enum	colour	{c_line, c_lexv, c_class} colour;
/* ---------------------------------------------------- */
.DE
That's all you need.
.LP
Of course,
each application has its own colours.
You will have to edit a similar file.
.H 1 "Directory organization"
.PP
There are many files involved in EL PRADO applications.
Usually there are several applications using EL PRADO,
even for the same language.
Let us present our own organization of files
in order to serve as an example.

In one directory we hold the source files
and a compiled version of 
.I astfunc.c
to be shared
.DS L
\&...> ls -l ~pepe/lotos/elprado
total 33
-rw-r--r--  1 pepe         1597 Oct 31 17:51 astdef.h
-rw-r--r--  1 pepe        16878 Oct 31 17:51 astfunc.c
-rw-r--r--  1 pepe         4497 Oct 31 17:44 astfunc.o
-rw-r--r--  1 pepe         1168 Oct 31 17:51 clrdef.h
-rw-r--r--  1 pepe         6766 Oct 31 17:51 clrfunc.c
.DE
In another directory we hold LOTOS related files
.DS L
\&...> ls -l ~pepe/lotos/last
total 10
-rw-r-----  1 tomas        2569 Oct 24 16:01 colouring.c
-rw-r-----  1 tomas         870 Oct 24 16:01 colours.h
-rw-r-----  1 tomas        3771 Oct 24 16:01 nodes.h
-rw-r-----  1 tomas        1507 Oct 24 16:01 stack.h
.DE
These are the files used by 
.I lastb
that may be useful for other applications.

Now, for an applications we set up symbolic links \**.
.FS
That concept exists in BSD 4.2,
but does not appear in other versions of UNIX.
Each user will look for equivalent mechanisms.
.FE

For instance,
the application presented in appendix 2 has the following files
.DS L
\&...> ls -l ~pepe/lotos/sedos/tools/lxref
total 35
lrwxrwxrwx  1 pepe           33 Oct 24 16:03 astdef.h
			-> ~pepe/lotos/elprado/astdef.h
lrwxrwxrwx  1 pepe           34 Oct 24 16:02 astfunc.o
			-> ~pepe/lotos/elprado/astfunc.o
lrwxrwxrwx  1 pepe           33 Oct 24 16:03 clrdef.h
			-> ~pepe/lotos/elprado/clrdef.h
lrwxrwxrwx  1 pepe           34 Oct 24 16:03 clrfunc.c
			-> ~pepe/lotos/elprado/clrfunc.c
-rw-r-----  1 pepe         1038 Oct 10 11:44 colouring.c
-rw-r-----  1 pepe          338 Oct 10 11:13 colours.h
-rw-r-----  1 pepe         1203 Oct 10 14:36 lxref.c
-rw-r-----  1 pepe          742 Oct 10 11:13 lxref.h
-rw-r-----  1 pepe          784 Oct 24 15:18 lxref.make
lrwxrwxrwx  1 pepe           29 Oct 24 15:21 nodes.h
			-> ~pepe/lotos/last/nodes.h
-rw-r-----  1 pepe         2170 Oct 10 11:58 symtab.c
.DE
This organization minimizes the amount of identical files
around the system,
and allow for immediate actualization of versions.
Even more, this saves recompiling "astfunc.c" now and then,
which is a slow task.
.bp
.H 1 "Example 1: stacks"
.PP
.I astfunc
and
.I clrfunc
may be seen as kernel libraries.
It is extremely easy to enhance its functionality
by introducing a new level of abstraction
that puts the functions closer to the user application.
.PP
In this section we present a set of definitions
to work on a stack of trees.
The case is taken from actual coding of
.I lastb .
It must be self explanatory.
.DS L
/*-------------------------------------------------------
	basic elements
---------------------------------------------------------
*/

# define STACKT 30

TPNODE stack[STACKT];		/* THE stack */
int stack_pos= -1;
TPNODE cursor;
.DE
.DS L
/*-------------------------------------------------------
	basic functions
---------------------------------------------------------
*/

# define top       stack[stack_pos]

# define push(n)   stack[++stack_pos] = n
# define pop()     stack_pos--
# define popn(n)   stack_pos -= n
# define pick(n)   stack[stack_pos-n]

# define swap() 				\e
	{ TPNODE auxt = top;			\e
	  top = pick (1);			\e
	  stack[stack_pos-1] = auxt;		\e
	}

# define full_stack      stack_pos == STACKT ? TRUE : FALSE
# define empty_stack     stack_pos == -1 ? TRUE : FALSE

# define create_nodep(t) cursor = push ((TPNODE)new_node (t))

# define stack_type(n)   pick(n)->type

# define add_brother()   { ln_l_node(top, pick(1)); pop(); }
# define put_brothers()  { ln_r_node(pick(1), top); pop(); }
# define put_son()       { ln_sons(top, pick(1)); swap(); pop(); }
.DE
.DS L
/*-------------------------------------------------------
	for debugging
---------------------------------------------------------
*/

draw_stack()
{
	int i;

  for (i = stack_pos; i >= 0; i--)
  {
    printf("(%3d ) ",i);
    draw_node (stack[i]);
  }
}
.DE
.DS L
/*-------------------------------------------------------
	Ad-hoc colour functions to add attributes to ast nodes
---------------------------------------------------------
*/

#define add_line(arg)	add_attr (c_line,  top)->u.line   = arg
#define add_lexv(arg)	add_attr (c_lexv,  top)->u.lexval = arg
#define add_class(arg)	add_attr (c_class, top)->u.class  = arg
.DE
.bp
.H 1 "Example 2: cross references"
.PP
Now, let us try a full application:
a cross reference generator.
Not a very sophisticated one including semantic analysis,
but a direct,
even trivial one.
It includes the following files:
.DS L
lxref.h		common header
colours.h	to parameterize EL PRADO
symtab.c	the symbol table manager
colouring.c	the input/output functions
lxref.c		the main loops
.DE
The files are directly included from a working version,
thus they can be stripped off from this text
to get the utility.
The text must be self explanatory.
Nevertheless,
let us show the structural dependencies between modules
.DS L
  Application           Attribution             Syntax Tree
    Section       :       Section       :         Section
                  :                     :
                  :                     :
  -----------     :                     :   ----------
 ( colours.h ) ---:------        -------:- ! astdef.h !
  -----------     :      !      !       :   ----------
                  :      !      !       :    !
                  :      V      V       :    !
                  :     ----------      :    !    ---------
                  :    ! clrdef.h !     :    !   ! nodes.h !
                  :     ----------      :    !    ---------
                  :         !           :    !          !
                  :         !           :    !          !
        ----------:---------!           :    !          !
       !          :         !           :    !          !
       !          :         !           :    !          !
       V          :         V           :    V          !
  -----------     :     ---------       :   ---------   !
 ( colouring ) ---:--> ! clrfunc !      :  ! astfunc !  !
  -----------     :     ---------       :   ---------   !
       ^          :         !           :     !         !
       !          :         !           :     !         !
\&.. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. ..
       !                    !                 !         !
       !                    !                 !         !
       !                    V                 V         V
   --------         ------------------------------------------
  ( symtab ) ----> (                 lxref                    )
   --------         ------------------------------------------
.DE
The picture above shows the modular structure of the "lxref" application.
There are two types of modules.
The rectangular ones
(boxed with "!")
are standard libraries
and definitions to work with abstract syntax tree and its attributes.
The rest of modules
(boxed with "()")
are application dependent.
.PP
The picture is divided in four sections.
The first vertical one,
"application section",
contains code related to specific attributes defined "lxref".
"Attribution section" shows standard modules associated with attribute
management.
The last section,
"syntax tree",
stores library functions and
definitions of the abstract syntax tree.
.PP
There exist two additional modules in the lower part of the picture.
They are specific application code.
In "lxref",
it is necessary to manage an identifier table to store names and line numbers.
"Symtab" performs that role.
.PP
The main program is in module "lxref".
.PP
Next follows the complete listing of those modules specific of the
application
and the "makefile" to build it.
.bp
.H 2 "lxref.h"
.LP
.DS L
/******  application dependant types  ******/

typedef struct Linelist {
	int		line;
	struct Linelist	*next;
	} LNODE, *TLNODE;

typedef struct Symbol {
	char		*name;
	TLNODE		lines;
	struct Symbol	*left,
			*right;
	} SNODE, *TSNODE;

/*****  external functions  *****/

TSNODE	putid ();	/* insert identifier in symbol table */
.DE
.H 2 "colours.h"
.LP
We need to define the colours we plan to use.
.DS L
# include "lxref.h"

				/* colour fields */

# define COLOURS		\
	int	line;		\
	TSNODE	lexval;

				/* colour types */

typedef	enum	colour	{c_line, c_lexv} colour;
.DE
.bp
.H 2 "symtab.c"
.LP
Symbol table manager.
Creates, maintains and dumps a binary tree
where nodes are lexicographically ordered identifiers
with an ordered list of source text lines.
.DS L
# include <stdio.h>
# include <strings.h>
# include "astdef.h"
# include "lxref.h"

PRIVATE TSNODE tsroot;

PRIVATE TSNODE new_tsnode (name) 
	char	*name;
{
	TSNODE s= (TSNODE) emalloc (sizeof (SNODE));

	s->name= emalloc (strlen (name) + 1);
	strcpy (s->name, name);
	s->lines= NULL;
	s->left= NULL;
	s->right= NULL;
	return s;
}

PUBLIC init_ts ()
{
	tsroot= new_tsnode ("ROOT");
}
.DE
.DS L
/*
	inserts in lexicographical order
	duplicates are not inserted
*/

PUBLIC TSNODE putid (id)
	char	*id;
{
	TSNODE	p= tsroot;
	TSNODE	q= tsroot->right;
	TSNODE	n;
	int	test= 1;
	
	while (q != NULL) {
	  p= q;
	  test= strcmp (id, q->name);
	  if (test == 0)
	    return q;
	  if (test < 0)
	    q= p->left;
	  else
	    q= p->right;
	  }

	/* comes to this point if id does not yet exist */

	n= new_tsnode (id);
	if (test > 0)
	  p->right= n;
	else
	  p->left= n;
	return n;
}
.DE
.DS L
/*
	Given a symbol entry,
	add a new line occurrence
	lines are introduced in normal order
*/

PUBLIC addline (s, line)
	TSNODE	s;
	int	line;
{
	TLNODE l= s->lines;
	TLNODE n= (TLNODE) emalloc (sizeof (LNODE));

	n->line= line;
	n->next= NULL;

	if (l == NULL || line <= l->line) {
	  s->lines= n;
	  n->next= l;
	  return;
	  }
	while (l->next != NULL && line > l->next->line)
	  l= l->next;
	n->next= l->next;
	l->next= n;
}
.DE
.DS L
/*
	Prints one or more lines per symbol
*/

PRIVATE print_item (t)
	TSNODE t;
{
	int	length= strlen (t->name);
	int	i;
	TLNODE	l;

	printf ("%s", t->name);
	if (length > 8)
	  printf ("\n          ");
	else
	  for (i= length; i < 10; i++)
	    putchar (' ');
	i= 10;			/* numbers per line */
	for (l= t->lines; l != NULL; l= l->next) {
	  if (i-- == 0)
	    printf ("\n          "),
	    i= 9;
	  printf ("%6d", l->line);
	  }
	putchar ('\n');
}
.DE
.DS L
/*
	traverses the symbol table
	while printing each item
*/

PRIVATE traverse (t)
	TSNODE t;
{
	while (t != NULL) {
	  traverse (t->left);
	  print_item (t);
	  t= t->right;
	  }
}

PUBLIC print_ts ()
{
	traverse (tsroot->right);
}
.DE
.bp
.H 2 "colouring.c"
.LP
.DS L
# include <stdio.h>
# include "clrdef.h"

/*****   definition of intended colours   *****/

				/* handling functions */
PRIVATE	int	getline (), putline ();
PRIVATE	int	getlexv (), putlexv ();

PUBLIC	TIOCOLOURS iocolours [] = {		/* io driver */
	"line", c_line, TRUE, getline, putline,
	"lexv", c_lexv, TRUE, getlexv, putlexv,
	0
	};

/*****   functions to handle colour  LINE   *****/

PRIVATE	getline (attrp, buf)
	TPATTR	attrp;
	char	*buf;
{
	attrp->u.line= atoi (buf);
}

PRIVATE	putline (attrp, buf)
	TPATTR	attrp;
	char	*buf;
{
	sprintf (buf, "%d", attrp->u.line);
}

/*****   functions to handle colour  LEXVAL   *****/

PRIVATE	getlexv (attrp, buf)
	TPATTR	attrp;
	char	*buf;
{
	attrp->u.lexval= putid (buf);
}

PRIVATE	putlexv (attrp, buf)	/* is it required at all? */
	TPATTR	attrp;
	char	*buf;
{
	sprintf (buf, "%s", attrp->u.lexval->name);
}
.DE
.bp
.H 2 "lxref.c"
.LP
.DS L
# include <stdio.h>
# include "clrdef.h"
# include "nodes.h"

main () 
{
	TPNODE	astroot;		/* root of AST */

	init_ts ();			/* create */
	astroot= restore (stdin);	/* load the symbol table */
	setup (astroot);		/* add lines to symbols */
	print_ts ();			/* print the table */
}

/*
	traverses the AST
	looking for nodes of type IDENTIFIER or IDENTIFIER2
	that should have the lexv and line attributes,
	and actualizes the symbol table

	uses a preorder traversing
*/

PRIVATE int predicate (nodep)
	TPNODE	nodep;
{
	return nodep->type == IDENTIFIER  ||
	       nodep->type == IDENTIFIER2   ;
}

# define next(node) lp_succ (node, predicate, PREORDER)

PRIVATE	setup (ast)
	TPNODE ast;
{
	TPATTR alexv, aline;

	while ((ast= next (ast)) != NULL) {
	  alexv= find_attr (c_lexv, ast);
	  aline= find_attr (c_line, ast);
	  if (alexv != NULL && aline != NULL)
	    addline (alexv->u.lexval, aline->u.line);
	  else
	    fprintf (stderr, "lxref: strange ast!!\n");
	  }
}
.DE
.bp
.H 2 "lxref.make"
.LP
.DS L
#
# LXREF:  makefile
#
# notice:    anything file that contains
#		# include "clrdef.h"
#
#	    depends on
#		file:	astdef.h clrdef.h colours.h
#
LIBOBJS = astfunc.o clrfunc.o

#--------------------------------------------------------

APPOBJS = lxref.o symtab.o colouring.o

lxref:	$(APPOBJS) $(LIBOBJS)
	cc $(CFLAGS) -o $@ $(APPOBJS) $(LIBOBJS)

lxref.o:	nodes.h astdef.h clrdef.h colours.h

symtab.o:	astdef.h lxref.h

#..........................  application colouring

colouring.o:	astdef.h clrdef.h colours.h

colours.h:	lxref.h
		@touch $@

#--------------------------------------------------------
#	this part is application independent
#	leave it as it is
#--------------------------------------------------------

astfunc.o:	astdef.h

clrfunc.o:	astdef.h clrdef.h colours.h
.DE
.bp
.H 2 "Using lxref"
.PP
The previous code is complete.
You may strip it off the text,
and run the "make".
You get a program able to get a LOTOS AST from the standard input,
dumping a nice cross reference listing on the standard output.
.PP
Typically,
you have a LOTOS specification wonderfully edited

\&...>  vi simple.lot

you check it for syntactic errors

\&...>  sclotos simple

then you may run the AST builder

\&...>  lastb simple > simple.ast

that builds a file named "simple.ast", on which you may run "lxref"
.DS L
\&...>  lxref < simple.ast
ext-gate       1     3
simple         1
.DE
Maybe you are surprised with some of the identifiers you are using.
.H 1 "Final words"
.PP
.I "EL PRADO"
is a tool under development.
.I asrfunc
and 
.I clrfunc
provide a set of functions that have proven valuable so far.
But be sure your application will discover nice functions
you would like to have.
We are sure some of those functions would be widely useful.
Thus,
let us know of your experience
and supply as many extensions as you think are worth.
Next release of the system will reflect your contribution.
Thank you for your uninterested (?) collaboration.
.TC
