• Table of Contents
• Previous Chapter
• Next Chapter

Chapter 5: Bisonc++ grammar files

In this chapter the organization and specification of such a grammar file is discussed in detail.

Having read this chapter you should be able to define a grammar for which Bisonc++ can generate a class, containing a member that will recognize correctly formulated (in terms of your grammar) input, using all the features and facilities offered by bisonc++ to specify a grammar. In principle this grammar will be in the class of LALR(1) grammars (see, e.g., Aho, Sethi & Ullman, 2003 (Addison-Wesley)).

5.1: Outline of a Bisonc++ Grammar File

    Bisonc++ directives
    %%
    Grammar rules
        

The `%%' is a punctuation that appears in every bisonc++ grammar file to separate the two sections.

The bisonc++ directives section is used to declare the names of the terminal and nonterminal symbols, and may also describe operator precedence and the data types of semantic values of various symbols. Furthermore, this section is also used to specify bisonc++ directives. These bisonc++ directives are used to define, e.g., the name of the generated parser class and a namespace in which the parser class is defined. All bisonc++ directives are covered in section 5.5.

The grammar rules define how to construct nonterminal symbols from their parts. The grammar rules section contains one or more bisonc++ grammar rules, and nothing else. See section 5.3, covering the syntax of grammar rules.

There must always be at least one grammar rule, and the first `%%' (which precedes the grammar rules) may never be omitted even if it is the first thing in the file.

Bisonc++'s grammar file may be split into several files. Each file may be given a suggestive name. This allows quick identification of where a particular section or rule is found, and improves readability of the designed grammar. The %include-directive (see section 5.5.7) can be used to include a partial grammar specification file into another specification file.

5.2: Symbols, Terminal and Nonterminal Symbols

A terminal symbol (also known as a token type) represents a class of syntacticly equivalent tokens. You use the symbol in grammar rules to mean that a token in that class is allowed. The symbol is represented in the Bisonc++ parser by a numeric code, and the parser's lex() member function returns a token type code to indicate what kind of token has been read. You don't need to know what the code value is; you can use the symbol to stand for it.

A nonterminal symbol stands for a class of syntactically equivalent groupings. The symbol name is used in writing grammar rules. By convention, it should be all lower case.

Symbol names can contain letters, digits (not at the beginning), and underscores. Bisonc++ currently does not support periods in symbol names (Users familiar with Bison may observe that Bison does support periods in symbol names, but the Bison user guide remarks that `Periods make sense only in nonterminals'. Even so, it appears that periods in symbols are hardly ever used).

There are two ways to write terminal symbols in the grammar:

• A named token type is written with an identifier, like an identifier in C++. By convention, it should be all upper case. Each such name must be defined with a bisonc++ directive such as %token. See section 5.5.24.
• A character token type (or literal character token) is written in the grammar using the same syntax used in C++ for character constants; for example, '+' is a character token type. A character token type doesn't need to be declared unless you need to specify its semantic value data type (see section 5.6.1), associativity, or precedence (see section 5.5.8).

By convention, a character token type is used only to represent a token that consists of that particular character. Thus, the token type '+' is used to represent the character `+' as a token. Nothing enforces this convention, but if you depart from it, your program will likely confuse other readers.

All the usual escape sequences used in character literals in C++ can be used in bisonc++ as well, but you must not use the 0 character as a character literal because its ASCII code, zero, is the code lex() must return for end-of-input (see section 6.3.1). If your program must be able to return 0-byte characters, define a special token (e.g., ZERO_BYTE) and return that token instead.

Note that literal string tokens, formally supported in Bison, is not supported by bisonc++. Again, such tokens are hardly ever encountered, and the dominant lexical scanner generators (like flex(1)) do not support them. Common practice is to define a symbolic name for a literal string token. So, a token like EQ may be defined in the grammar file, with the lexical scanner returning EQ when it matches ==.

How you choose to write a terminal symbol has no effect on its grammatical meaning. That depends only on where it appears in rules and on when the parser function returns that symbol.

The value returned by the lex() member is always one of the terminal symbols (or 0 for end-of-input). Whichever way you write the token type in the grammar rules, you write it the same way in the definition of yylex. The numeric code for a character token type is simply the ASCII code for the character, so lex() can use the identical character constant to generate the requisite code. Each named token type becomes a C++ enumeration value in the parser base-class header file, so lex() can use the corresponding enumeration identifiers. When using an externally (to the parser) defined lexical scanner, the lexical scanner should include the parser's base class header file, returning the required enumeration identifiers as defined in the parser class. So, if (%token NUM) is defined in the parser class Parser, then the externally defined lexical scanner may return Parser::NUM.

The symbol `error' is a terminal symbol reserved for error recovery (see chapter 8). The error symbol should not be used for any other purpose. In particular, the parser's member function lex() should never return this value. Several other identifiers should not be used as terminal symbols. See section 5.5.24.1 for a description.

5.3: Syntax of Grammar Rules

 
    result: 
        components
        ...
    ;
        

• The construction:

      exp:    
          exp '+' exp
      ;
          
  

  means that two groupings of type exp, with a `+' token in between, can be combined into a larger grouping of type exp.

• Whitespace in rules is significant only to separate symbols. You can add extra whitespace as you wish.

• Scattered among the components can be actions that determine the semantics of the rule. An action looks like this:

      {
          C++ statements
      }
          
  

  Usually there is only one action and it follows the components. See section 5.6.4.

• Multiple rules for the same result can be written separately or can be joined with the vertical-bar character `|' as follows:

      result: 
          rule1-components
          ...
      | 
          rule2-components...
          ...
      ;
          
  

  They are still considered distinct rules even when joined in this way.

• Alternatively, multiple rules of the same nonterminal can be defined. E.g., the previous definition of result: could also have been defined as:

      result: 
          rule1-components
          ...
      ;
  
      result:
          rule2-components...
          ...
      ;
          
  

  However, this is a potentially dangerous practice, since one of the two result rules could also have used a misspelled rule-name (e.g., the second result) should have been results. Therefore, bisonc++ generates a warning if the same nonterminal is used repeatedly when defining production rules.

• If components in a rule is empty, it means that result can match the empty string. Such a alternative is called an empty production rule. For example, here is how to define a comma-separated sequence of zero or more exp groupings:

      expseq:   
          expseq1
      | 
          // empty 
      ;
  
      expseq1:  
          expseq1 ',' exp
      | 
          exp
      ;
          
  

  Convention calls for a comment `// empty' in each empty production rule.

5.4: Writing recursive rules

    expseq1:  
            expseq1 ',' exp
    | 
            exp
    ;
        

    expseq1:  
            exp ',' expseq1
    | 
            exp
    ;
        

Indirect or mutual recursion occurs when the result of the rule does not appear directly on its right hand side, but does appear in rules for other nonterminals which do appear on its right hand side. For example:

    expr:     
        primary '+' primary
    |
        primary
        ;

    primary:  
        constant
    | 
        '(' expr ')'
    ;
        

5.5: Bisonc++ Directives

All token type names (but not single-character literal tokens such as '+' and '*') must be declared. If you need to specify which data type to use for the semantic value (see section 5.6.2) of nonterminal symbols, these symbols must be declared as well.

The first rule in the file by default specifies the start symbol. If you want some other symbol to be the start symbol, you must use an explicit %start directive (see section 3.1).

In this section all of bisonc++'s declarations are discussed. Some of the declarations have already been mentioned, but several more are available. Some declarations define how the grammar parses its input (like %left, %right); other declarations are available, defining, e.g., the name of the parsing function (by default parse()), or the name(s) of the files generated by bisonc++.

In particular readers familiar with Bison (or Bison++) should read this section thoroughly, since bisonc++'s directives are more extensive and different from the `declarations' offered by Bison, and the macros offered by Bison++.

Several directives expect file- or path-name arguments. File- or path-names must be specified on the same line as the directive itself, and they start at the first non-blank character following the directive. File- or path-names may contain escape sequences (e.g., if you must: use `\ ' to include a blank in a filename) and continue until the first blank character thereafter. Alternatively, file- or path-names may be surrounded by double quotes ("...") or pointed brackets (<...>). Pointed brackets surrounding file- or path-names merely function to delimit filenames. They do not refer to, e.g., C++'s include path. No escape sequences are required for blanks within delimited file- or path-names.

Directives accepting a `filename' do not accept path names, i.e., they cannot contain directory separators (/); options accepting a 'pathname' may contain directory separators.

Sometimes directives have analogous command-line options. In those cases command-line options take priority over directives.

Some directives may generate errors. This happens when an directive conflicts with the contents of a file which bisonc++ cannot modify (e.g., a parser class header file exists, but doesn't define a name space, but a %namespace directive was provided).

To solve such errore the offending directive could be omitted, the existing file could be removed, or the existing file could be hand-edited according to the directive's specification.

5.5.1: %baseclass-preinclude: specifying a header included by the baseclass

5.5.2: %class-name: defining the name of the parser class

If you're familiar with the Bison++ program, please note:

• This directive replaces the %name directive previously used by Bison++.
• Contrary to Bison++'s %name directive, %class-name may appear anywhere in the directive section of the grammar specification file.

It is an error if this directive is used and an already existing parser-class header file does not define class `className' and/or if an already existing implementation header file does not define members of the class `className'.

5.5.3: %debug: adding debugging code to the `parse()' member

5.5.4: %error-verbose: dumping the parser's state stack

5.5.5: %expect: suppressing conflict warnings

The argument number is a decimal integer. The declaration says there should be no warning if there are number shift/reduce conflicts and no reduce/reduce conflicts. The usual warning is given if there are either more or fewer conflicts, or if there are any reduce/reduce conflicts.

In general, using %expect involves these steps:

• Compile your grammar without %expect. Use the `-V' option to get a verbose list of where the conflicts occur. Bisonc++ will also print the number of conflicts.
• Check each of the conflicts to make sure that bisonc++'s default resolution is what you really want. If not, rewrite the grammar and go back to the beginning.
• Add an %expect declaration, copying the number of (shift-reduce) conflict printed by bisonc++.

5.5.6: %flex: using the traditional `flex++' interface

5.5.7: %include: splitting the input file

Bisonc++'s main grammar specification file could be:

    %include spec/declarations.gr
    %%
    %include spec/rules.gr
        

%include directives should be specified on a line of their own.

5.5.8: %left, %right, %nonassoc: defining operator precedence

%left [ <type> ] terminal(s)
%nonassoc [ <type> ] terminal(s)
%right [ <type> ] terminal(s)

The %left, %right or %nonassoc directive are used to declare tokens and to specify their precedence and associativity, all at once.

• The associativity of an operator op determines how repeated uses of the operator nest: whether `x op y op z' is parsed by grouping x with y first or by grouping y with z first. %left specifies left-associativity (grouping x with y first) and %right specifies right-associativity (grouping y with z first). %nonassoc specifies no associativity, which means that `x op y op z' is not a defined operation, and could be considered an error.
• The precedence of an operator determines how it nests with other operators. All the tokens declared in a single precedence directive have equal precedence and nest together according to their associativity. When two tokens declared in different precedence directives associate, the one declared later has the higher precedence and is grouped first.

When multiple tokens are listed they must be separated by whitespace or by commas. Note that the precedence directives also serve to define token names: symbolic tokens mentioned with these directives should not be defined using %token directives.

5.5.9: %locationstruct: specifying a dedicated location struct

5.5.10: %lsp-needed: using the default location type

    struct LTYPE__
    {
        int timestamp;
        int first_line;
        int first_column;
        int last_line;
        int last_column;
        char *text;
    };
           

5.5.11: %ltype: using an existing location type

Any text following %ltype up to the end of the line, up to the first of a series of trailing blanks or tabs or up to a comment-token (// or /*) becomes part of the type definition. Be sure not to end a %ltype definition in a semicolon.

5.5.12: %namespace: using a namespace

If this options is used the implementation header will contain a commented out using namespace directive for the requested namespace.

In addition, the parser and parser base class header files also use the specified namespace to define their include guard directives.

It is an error if this directive is used and an already existing parser-class header file and/or implementation header file does not define namespace identifier.

5.5.13: %negative-dollar-indices: using constructions like $-1

In combination with the %polymorphic directive (see below) only the $-i format can be used (see also section 5.6.3).

5.5.14: %no-lines: suppressing `#line' directives

The #line directives allow compilers and debuggers to associate errors with lines in your grammar specification file, rather than with the source file containing the parse function itself.

5.5.15: %prec: overruling default precedences

    expression:
        '-' expression %prec UMINUS
        {
            ...
        }
                

    %right UMINUS
                

    %left '+' '-'
    %left '*' '/' '%'
    %right UMINUS
        

In the above production rule the operator order would cause the construction

    '-' expression
        

5.5.16: %polymorphic: using polymorphism to define multiple semantic values

The %polymorphic directive results in defining and using a polymorphic semantic value class, which can be used as a (preferred) alternative to the (traditional) a union specification.

Refer to section 5.6.3 for a detailed description of the specification, characteristics, and use of polymorphic semantic values as defined by bisonc++.

As a quick reference: to define multiple semantic values using a polymorphic semantic value class offering either an int, a std::string or a std::vector<double> specify:

    %polymorphic INT: int; STRING: std::string; 
                 VECT: std::vector<double>
                

5.5.17: %print-tokens: displaying tokens and matched text

The %print-tokens directive provides an implementation of the Parser class's print__ function displaying the current token value and the text matched by the lexical scanner as received by the generated parse function.

The print__ function is also implemented if the --print command-line option is provided.

5.5.18: %required-tokens: defining the minimum number of tokens between error reports

The directive %required-tokens can be used to specify this number. E.g., the specification %required-tokens 10 requires the parsing function to process successfully a series of 10 tokens before another syntactic error is reported (and counted). If a syntactic error is encountered before processing 10 tokens then the counter counting the number of successfully processed tokens is reset to zero, no error is reported, but the error recoery procedure continues as usual. The number of required tokens can also be set using the option --required-tokens. By default the number of required tokens is initialized to 0.

5.5.19: %scanner: using a standard scanner interface

By specifying the %flex directive the function d_scanner.YYText() is called.

The specfied header file will be surrounded by double quotes if no delimiters were provided. If pointed brackets (<...>) are used, they are kept.

It is an error if this directive is used and an already existing parser-class header file does not include `header'.

5.5.20: %scanner-matched-text-function: define the name of the scanner's member returning the matched texttoken

The %scanner-matched-text-function directive defines the scanner function returning the text matching the previously returned token. By default this is d_scanner.matched().

A complete function call expression should be provided (including a scanner object, if used). This option overrules the d_scanner.matched() call used by default when the %scanner directive is specified. Example:

    %scanner-matched-text-function myScanner.matchedText()
                

5.5.21: %scanner-token-function: define the name of the scanner's token function

The scanner function returning the next token, called from the generated parser's lex function. A complete function call expression should be provided (including a scanner object, if used). Example:

    %scanner-token-function d_scanner.lex()
                

It is an error if this directive is used and the specified scanner token function is not called from the code in an already existing implementation header.

5.5.22: %start: defining the start rule

By default bisonc++ uses the the LHS of the first rule in a grammar specification file as the start symbol. I.e., the parser tries to recognize that nonterminal when parsing input.

This default behavior may be overriden using the %start directive. The nonterminal symbol specifies a LHS that may be defined anywhere in the rules section of the grammar specification file. This LHS becomes the grammar's start symbol.

5.5.23: %stype: specifying the semantic stack type

Any text following %stype up to the end of the line, up to the first of a series of trailing blanks or tabs or up to a comment-token (// or /*) becomes part of the type definition. Be sure not to end a %stype definition in a semicolon.

5.5.24: %token: defining token names

%token terminal token(s)
%token [ <type> ] terminal token(s)

The %token directive is used to define one or more symbolic terminal tokens. When multiple tokens are listed they must be separated by whitespace or by commas.

The <type> specification is optional, and specifies the type of the semantic value when a token specified to the right of a <type> specification is received. The pointed arrows are part of the type specification; the type itself must be a field of a %union specification (see section 5.5.26).

bisonc++ converts symbolic tokens (including those defined by the precedence directives (cf. section 5.5.8)) into Parser::Tokens enumeration values (where `Parser' is the name of the generated parser class, see section 5.5.2). This allows the lexical scanner member function lex() to return these token values by name directly, and it allows externally defined lexical scanners (called by lex()) to return token values as Parser::name.

When an externally defined lexical scanner is used, it should include Parserbase.h, the parser's base class header file, in order to be able to use the Parser::Tokens enumeration type.

Although it is possible to specify explicitly the numeric code for a token type by appending an integer value in the field immediately following the token name (as in %token NUM 300) this practice is deprecated. It is generally best to let bisonc++ choose the numeric values for all token types. Bisonc++ automatically selects values that don't conflict with each other or with ASCII character values.

5.5.24.1: Improper token names

In particular,

• no token should end in two underscores (__).
• some identifiers are reserved and cannot be used as tokens. They are:

      ABORT, ACCEPT, ERROR, clearin, debug, error, setDebug
          
  

  Except for error, which is a predefined terminal token, these identifiers are the names of functions traditionally defined by bisonc++. The restriction on the above identifers could be lifted, but then the resulting generated parser would no longer be backward compatible with versions before Bisonc++ 2.0.0. It appears that imposing minimal restrictions on the names of tokens is a small penalty to pay for keeping backward compatibility.

5.5.25: %type: associating semantic values to (non)terminals

When %union is used to specify multiple semantic value types, (non-)terminals can be associated with one of the union fields specified with the %union directive.

To associate (non-)terminals with specific semantic value types the %type directive is used.

With this directive, symbol(s) represents of one or more blank or comma delimited grammatical symbols (i.e., terminal and/or nonterminal symbols); type is either a polymorphic type-identifier or a field name defined in the %union specification. The specified nonterminal(s) are automatically associated with the indicate semantic type. The pointed arrows are part of the type specification.

When the semantic value type of a terminal symbol is defined the lexical scanner rather than the parser's actions must assign the appropriate semantic value to d_val__ just prior to returning the token. To associate terminal symbols with semantic values, terminal symbols can also be specified in a %type directive.

5.5.26: %union: using a 'union' to define multiple semantic values

    %union {
      double u_val;
      symrec *u_tptr;
    };
        

Notes:

• The semicolon following the closing brace is optional.
• C++-11 does allow class types to be used in union definitions, so they can also be used in %union directives. When a class type variant is required, all required constructors, the destructor and other members (like overloaded assignment operators) must be able to handle the actual class type data fields properly. A discussion of how to use unrestricted unions is beyon this manual's scope, but can be found, e.g., in the C++ Annotations. See also section 5.6.2.

5.5.27: %weak-tags: %polymorphic declaring 'enum Tag__'

If tags are explicitly used, then they must be prefixed with the Tag__ scope. Before the arrival of the C++-11 standard strongly typed enumerations didn't exist, and explicit enum-type scope prefixes were usually omitted. This works fine, as long as there are no name-conflicts: parser-tokens, other enumerations or variables could use identifiers also used by enum Tag__. This results in compilation errors that can simply be prevented using strongly typed enumerations.

The %weak-tags directive can be specified when the Tag__ enum should not be declared as a strongly typed enum. When in doubt, don't use this directive and stick to using the strongly typed Tag__ enum. When using %weak-tags be prepared for compilation errors caused by name collisions.

5.5.28: Directives controlling the names of generated files

• The parser's base class header: <Class>base.h, configurable using %baseclass-header (see section 5.5.28.1) or %filenames (see section 5.5.28.3);
• The parser's class header: <Class>.h, configurable using %class-header (see section 5.5.28.2) or %filenames (see section 5.5.28.3);
• The parser's implementation header file: <Class>.ih, configurable using %implementation-header (see section 5.5.28.4) or %filenames (see section 5.5.28.3);

5.5.28.1: %baseclass-header: defining the parser's base class header

It is an error if this directive is used and an already existing parser class header file does not contain #include "filename".

5.5.28.2: %class-header: defining the parser's class header

It is an error if this directive is used and an already existing parser-class header file does not define class `className' and/or if an already existing implementation header file does not define members of the class `className'.

5.5.28.3: %filenames: specifying a generic filename

5.5.28.4: %implementation-header: defining the implementation header

5.5.28.5: %parsefun-source: defining the parse() function's sourcefile

5.5.28.6: %target-directory: defining the directory where files must be written

5.6: Defining Language Semantics

For example, the calculator calculates properly because the value associated with each expression is the proper number; it adds properly because the action for the grouping `x + y' is to add the numbers associated with x and y.

In this section defining the semantics of a language is addressed, covering the following topics:

• Specifying one data type for all semantic values;
• Specifying several alternative data types;
• Using Polymorphism to specify several data types;
• Specifying Actions (an action is the semantic definition of a grammar rule);
• Specifying data types for actions to operate on;
• Specifying when and how to put actions in the middle of a rule (most actions go at the end of a rule. In some situations it may be desirable to put an action in in the middle of a rule).

5.6.1: Data Types of Semantic Values

Bisonc++'s default is to use type int for all semantic values. To specify some other type, the directive %stype must be used, like this:

    %stype double
        

This directive must go in the directives section of the grammar file (see section 5.1). As a result of this, the parser class defines a private type STYPE__ as double: Semantic values of language constructs always have the type STYPE__, and (assuming the parser class is named Parser) an internally used data member d_val that could be used by the lexical scanner to associate a semantic value with a returned token is defined as:

    Parser::STYPE__ d_val;
        

5.6.2: More Than One Value Type

To use more than one data type for semantic values in one parser, bisonc++ offers the following feature:

• Define polymorphic semantic values, associating (non)terminals with their proper semantic types (cf section 5.6.3), and associate (non-)terminal tokens with their appropriate semantic values;
• Specify the entire collection of possible data types, using a %union directive (see section 5.5.26), and associate (non-)terminal tokens with their appropriate semantic values;
• Define your own class handling the various semantic values, and associate that class with the parser's semantic value type using the %stype directive. The association of (non-)terminal tokens and specific value types is handled by your own class.

5.6.3: Polymorphism and multiple semantic values: `%polymorphic'

One may wonder why a union is still used by bisonc++ as C++ offers inherently superior approaches to combine multiple types in one type. The C++ way to do so is by defining a polymorphic base class and a series of derived classes implementing the various exclusive data types. The union approach is still supported by bisonc++ since it is supported by bison(1) and bison++; dropping the union would needlessly impede backward compatibility.

The (preferred) alternative to using a union, however, is using a polymorphic base class. Although it is possible to define your own polymorphic semantic value classes, bisonc++ makes life easy by offering the %polymorphic directive.

The example program (cf. poly) implements a polymorphic base class, and derived classes containing either an int or a std::string semantic value. These types are asociated with tags (resp. INT and TEXT using the %polymorphic directive, which is discussed next.

5.6.3.1: The %polymorphic directive

Tags and type definitions are separated from each other by a colon, and multiple semantic values specifications are separated by semicolons. The semicolon trailing the final semantic value specification is optional.

A grammar specification file may contain only one %polymorphic directive, and the %polymorphic, %stype and %union directives are mutually exclusive.

Here is an example, defining three semantic values types: an int, a std::string and a std::vector<double>:

    %polymorphic INT: int; STRING: std::string; 
                 VECT: std::vector<double>
        

If type declarations refer to types declared in header files that were not already included by the parser's base class header, then these header s must be inserted using the %baseclass-preinclude directive as these types are referred to in the generated parserbase.h header file.

5.6.3.2: The %polymorphic and %type: associating semantic values with (non-)terminals

Semantic values may also be associated with terminal tokens. In that case it is the lexical scanner's responsibility to assign a properly typed value to the parser's STYPE__ d_val__ data member.

Non-terminals may automatically be associated with polymorphic semantic values using %type directives. E.g., after:

    %polymorphic INT: int; TEXT: std::string
    %type <INT> expr
        

    expr:
        expr '+' expr
        {
            $$ = $1 + $3;
        }
        

When negative dollar indices (like $-1) are used, pre-defined associations between non-terminals and semantic types are ignored. With positive indices or in combination with the production rule's return value $$, however, semantic value types can explicitly be specified using the common `$<type>$' or `$<type>1' syntax. (In this and following examples index number 1 represents any valid positive index; -1 represents any valid negative index).

The type-overruling syntax does not allow blanks to be used (so $<INT>$ is OK, $< INT >$ isn't).

Various combinations of type-associations and type specifications may be encountered:

• $-1: %type associations are ignored, and the semantic value type STYPE__ is used instead. A warning is issued unless the %negative-dollar-indices directive was specified.
• $<tag>-1: error: <tag> specifications are not allowed for negative dollar indices.

When using `$$.' or `$1.' default tags are ignored. A warning is issued that the default tag is ignored. This syntax allows members of the semantic value type (STYPE__) to be called explicitly. The default tag is only ignored if there are no additional characters (e.g., blanks, closing parentheses) between the dollar-expressions and the member selector operator (e.g., no tags are used with $1.member(), but tags are used with ($1).member()). The opposite, overriding default tag associations, is accomplished using constructions like $<STYPE__>$ and $<STYPE__>1.

When negative dollar indices are used, the appropriate tag must explicitly be specified. The next example shows how this is realized in the grammar specification file itself:

    %polymorphic INT: int
    %type <INT> ident
    %%
    
    type:
        ident arg
    ;
    
    arg:
        {
            call($-1->get<Tag__::INT>());
        }
    ;
        

It is also possible to delegate specification of the semantic value to the function call itself, as shown next:

    %polymorphic INT: int
    %type <INT> ident
    %%
    
    type:
        ident arg
    ;
    
    arg:
        {
            call($-1);
        }
    ;
        

    void call(STYPE__ &st)
    {
        st->get<Tag__::INT>() = 5;
    }
        

5.6.3.3: Code generated by %polymorphic

To minimize namespace pollution most of the additional code is contained in a namespace of its own: Meta__. If the %namespace directive was used then Meta__ is nested under the namespace declared by that directive. The name Meta__ hints at the fact that much of the code implementing polymorphic semantic values uses template meta programming.

The enumeration 'enum class Tag__'

One notable exception is the enumeration Tag__. It is declared outside of Meta__ (but inside the %namespace namespace, if provided) to simplify its use. Its identifiers are the tags declared by the %polymorphic directive. This is a strongly typed enumeration. The %weak-tags directive can be used to declare a pre C++-11 standard enum Tag__.

The namespace Meta__

Below, DataType refers to the semantic value's data type that is associated with a Tag__ identifier; ReturnType equals DataType if DataType is a built-in type (like int, double, etc.), while it is equal to DataType const & otherwise (for, e.g., class-type data types).

The important elements of the namespace Meta__ are:

• The polymorphic semantic value's base class Base.
  Its public interface offers the following members:
  
  • Tag__ tag() const: returns the semantic value type's tag.
  • ReturnType get<Tag__>() const: accesses the (non-modifiable) data element of the type matching the tag. the data element of the type matching the tag (also see below at the description of the class SType).
  • DataType &get<Tag__>() const: accesses the (modifiable) data element of the type matching the tag.

• The semantic value classes Semantic<Tag__::ID>: public Base.
  Semantic<Tag__::ID> classes are derived for each of the tag identifiers ID declared at the %polymorphic directive. Semantic<Tag__::ID> classes contain a mutable DataType data member. Their public interfaces offer the following members:
  • A default constructor;
  • A Semantic(DataType const &) constructor;
  • A Semantic(DataType &&) constructor;
  • An operator ReturnType() const conversion operator;
  • An operator DataType &()t conversion operator.
  Semantic<Tag__::ID> objects are usually not explicitly used. Rather, their use is implied by the actual semantic value class SType and by several support functions (see below).

• De semantic value class SType: public std::shared_ptr<Base> provides access to the various semantic value types. The SType__ class becomes the parser's STYPE__ type, and explicitly accessing Semantic<Tag__::ID> should never be necessary.
  SType's public interface offers the following members:
  • Constructors: default, copy and move constructors.
    Since the parser's semantic value and semantic value stack is completely controlled by the parser, and since the actual semantic data values are unknown at construction time of the semantic value (d_val__) and of the semantic value stack, no constructors expecting DataType values are provided.
  • Assignment operators.
    The standard overloaded assignment operator (copy and move variants) as well as copy and move assignment operators for the types declared at the %polymorphic directive are provided. Assigning a value using operator= allocates a Semantic<Tag__::tag> object for the tag matching the right-hand side's data type, and resets the SType's shared_pointer to this new Semantic<Tag__::tag> object. Be aware that this may break the default association of the semantic value as declared by a %type directive. When breaking the default association make sure that explicit tags are used (as in $<Tag__::tag>1), overriding the default association with the currently active association. In most cases, however, the assignment is not used to break the default association but simply to assign a value to $$. By default the SType's shared pointer is zero, and the assignment initializes the semantic value to a value of the proper type. Assuming a lexical scanner may return a NR token, offering an int number() const accessor, then part of expr rule could be:

            expr:
                NR
                {
                    $$ = d_scanner.number();
                }
            ...
                
    

    after which expr's semantic value has been initialized to a Semantic<Tag__::INT>.
  • returns the semantic value stored inside Semantic<Tag__>. If the type-name is a built-in type a copy of the value is returned, otherwise a reference to a constant object is returned;
    This member checks for 0-pointers and for Tag__ mismatches between the requested and actual Tag__, throwing a std::logic_error if found.
  • returns a reference to the (modifiable) semantic value stored inside Semantic<Tag__>.
    This member checks for 0-pointers and for Tag__ mismatches between the requested and actual Tag__, in that case replacing the current Semantic object pointed to by a new Semantic<Tag__> object of the requested Tag__.
  • refers to the semantic value stored inside Semantic<Tag__>. If the type-name is a built-in type a copy of the value is returned, otherwise a reference to a constant object is returned;
    This is a (partially) unchecking variant of the corresponing get member, resulting in a Segfault if used when the shared_ptr holds a 0-pointer, and throwing a std::bad_cast in case of a mismatch between the requested and actual Tag__.
  • returns a reference to the (modifiable) semantic value stored inside Semantic<Tag__>.
    This is a (partially) unchecking variant of the corresponing get member, resulting in a Segfault if used when the shared_ptr holds a 0-pointer, and throwing a std::bad_cast in case of a mismatch between the requested and actual Tag__.

Additional Headers

When using %polymorphic three additional header files are included by parserbase.h:

• memory, required for std::shared_ptr;
• stdexcept, required for std::logic_error;
• type_traits, required for the implementation of one of SType's overloaded assignment operators.

5.6.3.4: A parser using a polymorphic semantic value type

    %polymorphic INT: int; TEXT: std::string;
        

    %type <TEXT>    identifier
    %type <INT>     int
    %type <STYPE__> combi
        

    rule:
        identifier '(' identifier ')' '\n'
    |
        identifier '=' int '\n'
    |
        combi '\n'
    ;
        

The rules for identifier and int assign, respectively, text and an int value to the parser's semantic value stack:

    identifier:
        IDENTIFIER
        {
            $$ = d_scanner.matched();
        }
    ;
    int:
        INT
        {
            $$ = d_scanner.intValue();
        }
    ;
        

These simple assignments can be used as int is pre-associated with the INT tag and identifier is asociated with the TEXT tag.

As the combi rule is not associated with a specific semantic value, its semantic value could be either INT or TEXT. Irrespective of what is actually returned by combi, its semantic value can be passed on to a function (process(STYPE__ const &), responsible for the semantic value's further processing. Here are the definition of the combi non-terminal and action blocks for the rule non-terminal:

    combi:
        int
    |
        identifier;
    ;
        
    rule:
        identifier '(' identifier ')' '\n'
        {
            cout << $1 << " " << $3 << '\n';
        }
    |
        identifier '=' int '\n'
        {
            cout << $1 << " " << $3 << '\n';
        }
    |
        combi '\n'
        {
            process($1);
        }
    ;
        

Since identifier has been associated with TEXT and int with INT, the $-references to these elements in the production rules already return, respectively, a std::string const & and an int.

For combi the situation is slightly more complex, as combi could either return an int (via its int production rule) or a std::string const & (via its identifier production rule).

Fortunately, process can find out by inspecting the semantic value's Tag__:

    void process(SSTYPE__ const &semVal)
    {
        if (semVal.tag() == Tag__::INT)
            cout << "Saw an int-value: " << semVal.get<Tag__::INT>() << '\n';
        else
            cout << "Saw text: " << semVal.get<Tag__::TEXT>() << '\n';
    }
        

5.6.3.5: A scanner using a polymorphic semantic value type

It is easily created by flexc++(1) processing the following simple specification file.

%interactive
%filenames scanner

%%

[ \t]+                  // skip white space

[0-9]+                  return Parser::NR;

[a-zA-Z_][a-zA-Z0-9_]*  return Parser::IDENTIFIER;

.|\n                    return matched()[0];

The reader may refer to flexc++(1) documentation for details about flexc++(1) specification files.

5.6.4: Actions

An action consists of C++ statements surrounded by braces, much like a compound statement in C++. It can be placed at any position in the rule; it is executed at that position. Most rules have just one action at the end of the rule, following all the components. Actions in the middle of a rule are tricky and should be used only for special purposes (see section 5.6.6).

The C++ code in an action can refer to the semantic values of the components matched by the rule with the construct $n, which stands for the value of the nth component. The semantic value for the grouping being constructed is $$. (Bisonc++ translates both of these constructs into array element references when it copies the actions into the parser file.)

Here is a typical example:

    exp:
        ...
    |
        exp '+' exp
        { 
            $$ = $1 + $3; 
        }
    |
        ...    
        

If you don't specify an action for a rule, bisonc++ supplies a default: $$ = $1. Thus, the value of the first symbol in the rule becomes the value of the whole rule. Of course, the default rule is valid only if the two data types match. There is no meaningful default action for an empty rule; every empty rule must have an explicit action unless the rule's value does not matter. Note that the default $$ value is assigned at the beginning of an action block. Any changes to $1 are therefore not automatically propagated to $$. E.g., assuming that $1 == 3 at the beginning of the following action block, then $$ will still be equal to 3 after executing the statement in the action block:

    {               // assume: $1 == 3
        $1 += 12;   // $1 now is 15, $$ remains 3
    }
        

    {               // assume: $1 == 3
        $1 += 12;   // $1 now is 15, $$ remains 3
        $$ = $1;    // now $$ == 15 as well.
    }
        

Using $n with n equal to zero or a negative value is allowed for reference to tokens and groupings on the stack before those that match the current rule. This is a very risky practice, and to use it reliably you must be certain of the context in which the rule is applied. Here is a case in which you can use this reliably:

    foo:      
        expr bar '+' expr  
        { ... }
    | 
        expr bar '-' expr  
        { ... }
    ;

    bar:
        // empty
    |
        { 
            previous_expr = $0; 
        }
    ;
        

All $-type variables used in action blocks can be modified. All numbered $-variables are deleted when a production rule has been recognized. Unless an action explicitly assigns a value to $$, the (possibly modified) $1 value is assigned to $$ when a production rule has been recognized.

5.6.5: Data Types of Values in Actions

If you have used a %union directive to specify a variety of data types, then you must declare a choice among these types for each terminal or nonterminal symbol that can have a semantic value. Then each time you use $$ or $n, its data type is determined by which symbol it refers to in the rule. In this example,

    exp:    
        ...
    | 
        exp '+' exp
        { 
            $$ = $1 + $3; 
        }
        

Alternatively, you can specify the data type when you refer to the value, by inserting `<type>' after the `$' at the beginning of the reference. For example, if you have defined types as shown here:

    %union 
    {
        int u_int;
        double u_double;
    };
        

5.6.6: Actions in Mid-Rule

A mid-rule action may refer to the components preceding it using $n, but it may not (cannot) refer to subsequent components because it is executed before they are parsed.

The mid-rule action itself counts as one of the components of the rule. This makes a difference when there is another action later in the same rule (and usually there is another at the end): you have to count the actions along with the symbols when working out which number n to use in $n.

The mid-rule action can also have a semantic value. The action can set its value with an assignment to $$, and actions later in the rule can refer to the value using $n. Since there is no symbol to name the action, there is no way to declare a data type for the value in advance, so you must use the `$<...>' construct to specify a data type each time you refer to this value.

There is no way to set the value of the entire rule with a mid-rule action, because assignments to $$ do not have that effect. The only way to set the value for the entire rule is with an ordinary action at the end of the rule.

Here is an example from a hypothetical compiler, handling a let statement that looks like ``let (variable) statement' and serves to create a variable named variable temporarily for the duration of statement. To parse this construct, we must put variable into the symbol table while statement is parsed, then remove it afterward. Here is how it is done:

    stmt:   
        LET '(' var ')'
        {
            $<u_context>$ = pushSymtab();
            temporaryVariable($3); 
        }
        stmt    
        { 
            $$ = $6;
            popSymtab($<u_context>5); 
        }
        

Once the embedded statement is parsed, its semantic value becomes the value of the entire let-statement. Then the semantic value from the earlier action is used to restore the former symbol table. This removes the temporary let-variable from the list so that it won't appear to exist while the rest of the program is parsed.

Taking action before a rule is completely recognized often leads to conflicts since the parser must commit to a parse in order to execute the action. For example, the following two rules, without mid-rule actions, can coexist in a working parser because the parser can shift the open-brace token and look at what follows before deciding whether there is a declaration or not:

    compound: 
        '{' declarations statements '}'
    | 
        '{' statements '}'
    ;
        

    compound: 
        { 
            prepareForLocalVariables(); 
        }
        '{' declarations statements '}'
    | 
        '{' statements '}'
    ;
        

You might think that the problem can be solved by putting identical actions into the two rules, like this:

        { 
            prepareForLocalVariables(); 
        }
        '{' declarations statements '}'
    | 
        { 
            prepareForLocalVariables(); 
        }
        '{' statements '}'
    ;
        

If the grammar is such that a declaration can be distinguished from a statement by the first token (which is true in C, but not in C++, which allows statements and declarations to be mixed)), then one solution is to put the action after the open-brace, like this:

    compound: 
        '{'
        { 
            prepareForLocalVariables(); 
        }
        declarations statements '}'
    | 
        '{' statements '}'
    ;
        

Another (much used) solution is to bury the action inside a support non-terminal symbol which recognizes the first block-open brace and performs the required preparations:

    openblock:
        '{'
        { 
            prepareForLocalVariables(); 
        }
    ;

    compound: 
            openblock declarations statements '}'
    | 
            openblock statements '}'
    ;
        

By the way, note that in a language like C++ the above construction is obsolete anyway, since C++ allows mid-block variable- and object declarations. In C++ a compound statement could be defined, e.g., as follows:

    stmnt_or_decl:
        declarations
    |
        pure_stmnt      // among which: compound_stmnt
    ;

    statements:
        // empty
    |
        statements stmnt_or_decl
    ;

    compound_stmnt:                 
        open_block statements '}'
    ;
        

5.7: Basic Grammatical Constructions

5.7.1: Plain Alternatives

    // Example 1:  plain terminal distinguishing tokens
    expr:
        ID        
    |
        NUMBER
    ;

    // Example 2:  nested terminal distinguishing tokens
    expr:
        id
    |
        number
    ;

    id:
        ID
    ;

    number:
        NUMBER
    ;

    // Example 3:  eventually diverting routes
    expr:
        ID
        id
    |
        ID
        number
    ;

    id:
        ID
    ;

    number:
        NUMBER
    ;
        

5.7.2: One Or More Alternatives, No Separators

    "hello"         // multiple ws-delimited strings
    " " 
    "world"

    "hello world"   // same thing
        

    string:
        STRING
    |
        string STRING
        

    series:
        unit
    |
        series unit
        

5.7.3: Zero Or More Alternatives, No Separators

    opt_statements:
        // empty
    |
        opt_statements statements
        

    opt_series:
        // empty
    |
        opt_series unit
        

5.7.4: One Or More Alternatives, Using Separators

    variables:
        IDENTIFIER
    |
        variables ',' IDENTIFIER
        

    series:
        unit
    |
        series delimiter unit
        

5.7.5: Zero Or More Alternatives, Using Separators

    opt_parlist:
        // empty
    |
        opt_parlist ',' parameter
        

    opt_parlist:
        // empty
    |
        parlist
    ;

    parlist:
        parameter
    |
        parlist ',' parameter
    ;
        

    opt_series:
        // empty
    |
        series
    ;

    series:
        element
    |
        series delimiter element
        

5.7.6: Nested Blocks

    expr:
        NUMBER
    |
        ID
    |
        expr '+' expr
    |
        ...
    |
        '(' expr ')'
    ;
        

The definition of opt_statements, however, is a bit more complex. But acknowledging the fact that a statement contains among other elements a compound statement, and that a compound statement, in turn, contains opt_statements an opt_statements construction can be formulated accordingly:

    opt_statements:         // define an optional series
        // empty
    |
        opt_statements statement
    ;
        
    statement:              // define alternatives for `statement'
        expr_statement
    |
        if_statement
    |
        ...
    |
        compound_statement
    ;

    compound_statement:     // define the compound statement itself
        '{' opt_statements '}'
    ;
        

5.8: Multiple Parsers in the Same Program

• Table of Contents
• Previous Chapter
• Next Chapter