7.1 Constructing a Grammar

We are assuming that an ordinary context-free grammar is given for the selected language. Strategies for constructing such a grammar can be found in most textbooks, that deal with compiler construction. In order for the grammar to be useful, it has to fullfill the following requirements:

  1. The grammar must be converted into a structured context-free grammar. Since any context-free grammar can be converted into a structured grammar, this step should not cause major difficulties (except possibly for the restriction that the resulting hierarchy must be tree-structured, as discussed in chapter 2).
  2. The resulting structured context-free grammar has to be LALR(1). This requirement may be ignored, if there is no need for generating a parser for that language (i.e. all programs in that language will be manipulated, using the editor and the meta programming system). Unless otherwise explicitly noted, we will, in the following, always be refering to the structured context-free grammar when we are discussing the grammar.
  3. Along with the grammar, several additional properties of the grammar need to be specified, namely unused predefined nonterminals, the comment symbols of the grammar, the string symbol of the grammar, etc. All these options are described in chapter 6. We will discuss here only the most commonly used options.

The grammar definition is divided into five parts: the fragment part, the naming part, the options part, the rules part, and the attributes part: The naming part specifies the name of the grammar, the options part specifies the valid options of that grammar, the rules part contains the productions of the grammar, and the attributes part specifies for each nonterminal, the number of semantic attributes defined at the semantic level for that nonterminal. The options part and the attributes part are optional parts and may thus be absent from the grammar definition. The meta grammar describing the language for grammar specification is given in appendix 1.

7.1.1 The Fragment Part

In order to make the grammar specification readable for the various grammar tools, it must start with a fragment form specification. The format of a fragment form specification for a grammar is:

-- name: aGrammar: metagrammar --

where name must be the name chosen for this grammar.

7.1.2 The Naming Part

The grammar definition must begin by naming the grammar. This is done in the naming part of the grammar. The naming part consists of one clause:

Grammar name:

where name must be the name chosen for this grammar.

7.1.3 The Options Part

The options part of the grammar contains various settings of variables, that control the way in which the grammar processor treats the productions in the rules part, and other issues.

Each option is specified by the name of the option followed by "=" followed by the value of the option. The valid options are:

7.1.4 The Rules Part

The rules part of the grammar contains the specifications of the productions of the grammar.

The productions must follow the structure of a structured context-free grammar, as described ealier. Terminals have the form 'w', i.e. a string enclosed in single quotes (e.g. 'enter'). Nonterminals has either the form <A> or <t:A>, where t is a tag-name, and A is the syntactical category. If no tag-name is provided, the name of the syntactic category is used as the default tag-name.

The complete grammar must be LALR(1), if a parser needs to be generated by the metaprogramming system.

7.1.5 The Attributes Part

The attributes part of the grammar is a specification of the additional memory, the metaprogramming system needs to allocate in order to be able to handle the semantic attributes defined at the semantic level of the grammar.

The attributes part is a list of

<nonterminalName>: number

where <nonterminalName> is the name of a nonterminal of the grammar, and number is the size of the semantic attributes defined for this nonterminal. These semantic attributes are saved as part of the AST, when it is stored on some file. Please note, that for efficiency reasons, the number of attributes must be even (or zero).

As a side effect of specifying the nonterminal in the attributes part, that the generated context-free level interface pattern for that pattern will contain an attributes slot:

<<SLOT nonterminalNameAttributes: attributes>>

7.1.6 An Example Grammar

The following grammar will be used in the following to illustrate the various tools:

-- mylang: aGrammar: metagrammar --
grammar mylang:
<module>        ::= 'module' <module:id> ';' <importOpt>
                    'begin' <statement> 'end';
<id>            ::= <nameDecl>;
<importOpt>     ::? <import>;
<import>        ::= 'import' <nameList> ';';
<nameList>      ::+ <nameDecl> ',';
<statement>     ::| <if> | <while> | <procCall>;
<if>            ::= 'if' <condition:exp>
                    'then' <thenPart:statement>
                    'else' <elsePart:statement> 'endif';
<while>         ::= 'while' <condition:exp>
                    'do' <statementList> 'end';
<statementList> ::* <statement> ';';
<exp>           ::| <expProcCall> | <text> | <number>;
<text>          ::= <string>;
<number>        ::= <const>;
<expProcCall>   ::= <procCall>;
<procCall>      ::= <nameAppl> '(' ')'

The Metaprogramming System - Reference Manual
© 1991-2004 Mjølner Informatics
[Modified: Wednesday April 4th 2001 at 16:28]