next up previous contents index
Next: B. Glossary Up: V. Fifth Part: Appendix Previous: V. Fifth Part: Appendix   Contents   Index

Subsections


A. How to add new Keywords, Pragmas and Attributes

This appendix describes how to modify the GNAT front-end to experiment with Ada extensions. As an example we use Drago, an experimental extension of Ada 83 designed to support the implementation of fault-tolerant distributed applications. It was the result of an effort to impose discipline and give linguistic support to the group communication paradigm. In the following sections we briefly introduce Drago (Section A.1), and describe the modifications made to the GNAT scanner, parser, and semantic analyzer. A previous version of this work was publised in [MGMG99].


A.1 Drago

Drago [MAAG96,MAGA00] is an experimental language developed as an extension of Ada for the construction of fault-tolerant distributed applications. The hardware assumptions are: a distributed system with no memory shared among the different nodes, a reliable communication network with no partitions, and fail-silent nodes (that is, nodes which once failed are never heard from again by the rest of the system.) The language is the result of an effort to impose discipline and give linguistic support to the main concepts of Isis [BCJ$^+$90], as well as to experiment with the group communication paradigm. To help build fault-tolerant distributed applications, Drago explicitly supports two process group paradigms, replicated process groups and cooperative process groups. Replicated process groups allow the programming of fault-tolerant applications according to the active replication model, while cooperative process groups permit programmers to express parallelism and therefore increase throughput.

A process group in Drago is actually a collection of agents, which is the way processes are identified in the language. Agents are rather similar in appearance to Ada tasks (they have an internal state not directly accessible from outside the agent, an independent flow of control, and public operations called entries). Furthermore, they are the unit of distribution in Drago and in this sense they perform a role similar to Ada 95 active partitions and Ada 83 programs. Each agent resides in a single node of the network, although several agents can reside in the same node. A Drago program is composed of a number of agents residing at a number of nodes.

A.2 First Step: Addition of new Keywords

Drago adds four reserved keywords (agent, group, intragroup, and replicated). In the following sections we describe the main steps required to introduce them into the GNAT environment. GNAT list of predefined identifiers contains all the supported pragmas, attributes and keywords. This list is declared in the specification of package Snames. For each predefined identifier there is a constant declaration which records its position in the Names Table. This hash table stores all the names, predefined or not. Keywords are classified in two main groups: keywords shared by Ada 83 and Ada 95, and exclusive Ada 95 keywords. Each group is delimited by means of a subtype declaration. Depending on the GNAT compilation mode, Ada 83 or Ada 95, this subtype allows the scanner to properly distinguish user identifiers from Ada keywords.

In order to introduce Drago keywords we added a third GNAT mode, Drago mode, and one new group with Drago exclusive keywords. The result was as follows:

\begin{figure}\begin{lstlisting}{}
First_Drago_Reserved_Word : constant Name_Id ...
...t_Drago_Reserved_Word
.. Last_Drago_Reserved_Word;
\end{lstlisting}\end{figure}

We also updated the value of the constant Preset_Names, declared in the body of Snames, keeping the order specified in the previous declarations. This constant contains the literals of all the predefined identifiers.

A.3 Second step: Addition of new tokens

The list of tokens is declared in the package Scans. It is an enumerated type whose elements are grouped into classes used for source tests by the parser. For example, Eterm class contains all the expression terminators; Sterm class contains the simple expressions terminatorsA.1; After_SM is the class of tokens that can appear after a semicolon; Declk is the class of keywords which start a declaration; Deckn is the class of keywords which start a declaration but can not start a compilation unit; and Cunit is the class of tokens which can begin a compilation unit. Members of each class are alphabetically ordered. We have introduced the new tokens in the following way:

\begin{figure}\begin{lstlisting}{}
type Token_Type is (
-- Token name Class(es)...
..., -- Eterm, Sterm, Cunit, After_SM
...
No_Token);
\end{lstlisting}\end{figure}

Classes associated with tokens are specified in the third column. Our choices were based on the following guidelines:

According to the alphabetic ordering, Tok_Agent is new first token of Cunit class. Therefore we updated the declaration of the corresponding subtype Tok_Class_Unit to start the class with Tok_Agent. Finally we modified the declaration of the table Is_Reserved_Keyword, which records which tokens are reserved keywords of the language.

A.4 Third Step: Update the Scanner Initialization

The scanner initialization (subprogram Scn.Initialization) is responsible for stamping all the keywords stored in the Names Table with the byte code of their corresponding token (0 otherwise). This allows the scanner to determine if a word is an identifier of a reserved keyword. This work is done by means of repeated calls to the procedure Set_Name_Table_Byte passing the keyword and its corresponding token byte as parameters. Therefore we added the following sentences to the scanner initialization:

\begin{figure}\begin{lstlisting}{}
...
Set_Name_Table_Byte (Name_Agent,
Token_T...
...Name_Replicated,
Token_Type'Pos (Tok_Replicated));
\end{lstlisting}\end{figure}

We also modified the scanner (subprogram Scn.Scan) in order to recognize the new keywords only when compiling a Drago program. This allows us to preserve its original behaviour when analyzing Ada source code. This was the last modification required to integrate the new keywords into GNAT. In the following section we describe the modifications made to add one new pragma and one attribute into the GNAT scanner.

A.5 Addition of Pragmas an Attributes

Drago provides one new attribute Member_Identifier and one new pragma (Drago). When Member_Identifier is applied to a group identifier it returns the identifier of the current agent in the specified group. When pragma Drago is applied the compiler is notified about the existence of Drago code (similar to GNAT pragmas Ada83 and Ada95). For integrating them into GNAT we had to modify the package Snames in the following way:

  1. Add their declaration to the list of predefined identifiers keeping the alphabetic order. GNAT classifies all pragmas in two groups: configuration pragmas, those used to select a partition-wide or system-wide option, and non-configuration pragmas. The pragma Drago was placed in the group of non-configuration pragmas.

    GNAT classifies all attributes in four groups: attributes that designate procedures (output, read and write), attributes that return entities (elab_body and elab_spec), attributes that return types (base and class), and the rest of the attributes. Member_Identifier was placed in this fourth group.

  2. Insert their declarations in the enumerated Pragma_Id and Attribute_Id keeping the order specified in the previous step. Similar to tokens associated with keywords, these types facilitate the handling of pragmas and attributes in later stages of the frontend.

  3. Add their literals in Preset_Names. Similar to the introduction of the keywords, we must keep the order specified in the list of predefined identifiers.

  4. Update the C file a-snames.h. This file associates a C macro to each element of the types Attribute_Id and Pragma_Id. This work can be automatically done by means of the GNAT utility xsnames.


A.6 Addition of New Syntax Rules

In this section we describe, by means of an example, the modifications made in the parser in order to support Drago syntax. The example is the specification of a Drago group, whose syntax is similar to the one of an Ada package specification:

\begin{figure}\begin{lstlisting}{}
GROUP_DECLARATION ::= GROUP_SPECIFICATION
GRO...
...{basic_declarative_item ]
end [ group_identifier];
\end{lstlisting}\end{figure}

Replicated groups are denoted by the reserved keyword replicated at the heading of the group specification. Cooperative groups do not require any reserved word because they are considered the default group specification. The first list of declarative items of a group specification (the intergroup section) contains all the information that clients are able to know about this group. The optional list of declarative items after the keyword intragroup is called the intragroup section. It contains information that only members of the group are able to know, and it can be declared only in a cooperative group specificationA.2. The optional list of declarative items after the reserved word private is called the private section and provides groups with the same functionality as the private part of Ada packages. The following sections describe the steps made in order to add this syntax to the GNAT parser.

A.6.1 First step: Addition of New Node Kinds

GNAT node kinds are declared in the enumerated Sinfo.Node_Kind. Similar to Token_Type elements, all its elements are grouped into classes (i.e. nodes that correspond to sentences, nodes which correspond to operators, ...), and elements of each class are alphabetically ordered.

The addition of the rules of a Drago group required two additional kinds of nodes: N_Group_Declaration and N_Group_Specification. Due to the similarity of a Drago group specification and an Ada package specification we placed the N_Group_Declaration node in the class associated with N_Package_Declaration node, and N_Group_Specification in the class associated with N_Package_Specification.

A.6.2 Second Step: High-level specification of the new nodes

The specification of package Sinfo contains the high level specification of the AST nodes (cf. Section 2.2.1). When we define a new node we have two possibilities: to reuse the AST field-names used in the current high-level specification of Ada, or to define new names. In the first case we must keep all its features: field-number and associated data. In the second case we must carefully analyze the field to which we associate the new names because once it is stated it must be kept fixed for all nodes; in addition, for each new name we must declare two subprograms in Sinfo: one procedure (used to set the value of the field), and one function (to get the stored value). Following with out example, the templates associated with N_Group_Declaration and N_Group_Specification are:

\begin{figure}\begin{lstlisting}{}
-- N_Group_Declaration
-- Sloc points to GROU...
...t4) (set to No\_List if
-- no private part present)
\end{lstlisting}\end{figure}

This means that the value of Sloc in a N_Group_Declaration node points to the source code word group, and the first field of the node (Field1) points to a specification node. On the other hand, the value of Sloc in a N_Group_Specification node also points to the same word group (because the reason for the creation of both nodes was the same word), its first field (Field1) points to a defining identifier node, and its second, third and fourth fields (Field2..Field4) point to lists which contain respectively its visible, intragroup and private declarations.

Similar to GNAT handling of private packages, the handling of replicated groups only requires the addition of one new flag in the AST root node (Flag15 for a private package, and we chose Flag16 for a replicated group).

A.6.3 Third Step: Automatic modification of the frontend

The templates specified in the previous step are used by three GNAT utility programs (xsinfo, xtreeprs and xnmake) to automatically generate four frontend source files involved in the handling of nodes: a-sinfo.h, treeprs.ads, nmake.ads and nmake.adb (cf. Figure A.1).

Figure A.1: GNAT utility programs.
\begin{figure}\centerline{\psfig{figure=figures/frontend_extension/xprosint.eps,width=9 cm }}\end{figure}

A.6.4 Fourth Step: Update of the Parser

The GNAT parser is implemented by means of the well known recursive descent technique. All its code is inside the function Par which is composed of several subunits (one subunit for each Ada Reference Manual Chapter [AAR95]). According to this philosophy we decided to add the subunit Par.Drag to group all the parser code that syntactically analyzes Drago rules (figure A.2). We gave the name P_Group to the function associated with the parsing of a group specification. We used the fragment of the parser that analyzes a package specification as a reference for its development. Finally we modified the parsing of a compilation unit to include a call to this function when analyzing Drago source code and it detects a group token.

Figure A.2: New parser structure.
\begin{figure}\centerline{\psfig{figure=figures/frontend_extension/subsindr.eps,width=10 cm }}\end{figure}

A.7 Verification of the Semantics

When the parser finishes its work, the semantic analizer makes a top-down traversal of the AST and, according to the kind of each visited node, it calls one subprogram that semantically verifies it. These subprograms are structured as a set of packages. Each package contains all the subprograms required to verify the semantic rules of each ARM chapter (packages Sem_Ch2..Sem_Ch13). There is one subprogram for each node type created by the parser and the main package that derivates the calls is called Sem.

For the semantic verification of a Drago group specification we made the following modifications to the GNAT sources:

  1. Add one new package: Sem_Drag. This package contains all the Drago subprograms that make the semantic verifications.

  2. Add one new semantic entity. A GNAT entity is an internal representation of the identifiers, operators and character literals found in the source program declarations. Therefore, the identifier of a group specification must have its corresponding entity. We added the element E_Group to the enumerated Entity_Info (inside the Einfo package) to represent the new group name entity.

  3. Update the C file a-einfo.h. This work is automatically done by means of the GNAT utility program names xeinfo (figure A.3).

    Figure A.3: GNAT semantic utility program
    \begin{figure}\centerline{\psfig{figure=figures/frontend_extension/xprosem.eps,width=10 cm }}\end{figure}

  4. Write one subprogram for each new kind of node declared in the parser. We wrote the subprogram associated with the group specification node, and the subprogram for the group declaration node, and placed them inside the new package Sem_Drag. We used the subprograms performing semantic analysis of a package specification as a model for our new subprograms.

Finally we modified the Sem package to include calls to these subprograms when analyzing a group specification (or declaration) node.

A.8 Tree expansion

In the general case, to generate code there is no need to access the GIGI level, and our work finishes at the expansion phase. Following with our example, we expanded the Drago nodes into Ada 95 nodes which called several added Run-Time subprograms. Again, we recommend to use the expansion subprograms available in the GNAT sources as a reference.

A.9 Summary

This appendix has described the integration of Drago into the GNAT frontend. Drago is a language designed as an Ada extension to experiment with the active replication model of fault-tolerant distributed programming. We have focused our attention on the lexical, syntactic and semantic aspects of the integration. The abstract syntax tree expansion and code generation have not been discussed here.



Footnotes

... terminatorsA.1
All the reserved keywords, except mod, rem, new, abs, others, null, delta, digits, range, and, or xor, in and not, are always members of these two classes (Eterm, Sterm).
... specificationA.2
Replicated groups do not have this facility because their members are assumed to be replicas of a deterministic automaton and thus they do not need to exchange their state --all the replicas have the same state.

next up previous contents index
Next: B. Glossary Up: V. Fifth Part: Appendix Previous: V. Fifth Part: Appendix   Contents   Index
(C) Javier Miranda and Edmond Schonberg, 2004