C With Structs

Introduction

The title here is a play on the earliest version of C++. It was called "C With Classes." As the name suggests, it was a modest extension of the C programming language. The model presented here is not an extension of C, but rather just another way to use it. This model provides some of the benefits of object oriented programming (OOP), while retaining the elegant simplicity of the C language.

"Instance Model Programming" is also a simplified OOP model that could be even simpler if code reentrancy is not a requirement. This is often the case in simple environments. Also, in some cases the operating system provides the instance data that enables the code to be reentrant. This model uses file level static data and methods to implement privacy and modularity. C structs that contain only function pointers provide namespace support.

An example of a parser

The header file is presented in figure 1. It contains what would have been called global data in pre-OOP times. Each section of the parser revolves around a typedef that contains the pointers to the public methods that provide functionality to the other parts of the program. A drawback of inheritance is avoided because these units are all on the same level and have mutual access. Their internal workings are private in a black box fashion.


/*************************************************************************

    parser.h

    Version 6.42

    This module contains the public declarations.

    Copyright (c) 2002-2014  SLK Systems, all rights reserved.
    
*************************************************************************/

#ifndef _PARSER_H
#define _PARSER_H

#include "SlkParse.h"
#include "SlkString.h"

// ----------------------------------------------------------------------- 
// general constants
// -----------------------------------------------------------------------

typedef unsigned int    bool;
typedef unsigned int    uint;
typedef unsigned long   ulong;
typedef unsigned char   uchar;
typedef unsigned short  ushort;

#define TRUE        1
#define FALSE       0
#ifndef  NULL
    #define NULL    ( (void *) 0 )
#endif
#define PUBLIC
#define PRIVATE     static

// ----------------------------------------------------------------------- 
// namespace for the public constructors
//
// The extra Parser prefix should avoid any name conflicts with external
// code. In the very unlikely event that an external say MakeMemorySet()
// needs to be used in the program it can be invoked as (MakeMemorySet)(),
// preventing the preprocessor from changing it to ParserMakeMemorySet().
//
// -----------------------------------------------------------------------

#define MakeMemorySet   ParserMakeMemorySet
#define MakeSymbol      ParserMakeSymbol
#define MakeTree        ParserMakeTree
#define MakeAction      ParserMakeAction
#define MakeError       ParserMakeError
#define MakeScanner     ParserMakeScanner
#define MakeToken       ParserMakeToken
#define MakeOptions     ParserMakeOptions
#define MakeParser      ParserMakeParser

// ------------------------------------------------------------------------
// memory_set_t
// ------------------------------------------------------------------------

typedef struct _memory_set 
{
    void * (*allocate) ( void   *memory_set_handle, uint    length );
    char * (*save_string) ( void *memory_set_handle, char *string, uint length );
    char * (*resave_string) ( void *memory_set_handle, char *old_string, 
                                                       char *new_string );
    uint (*get_size) ( void   *memory_set_handle );
    void (*release) ( void  *memory_set_handle );
    void  *handle;

} memory_set_t;

PUBLIC
memory_set_t
MakeMemorySet ( int  chunk_size );

// ----------------------------------------------------------------------- 
// symbol_t
//
// symbol table entry node
// -----------------------------------------------------------------------

typedef struct _symbol {
    struct 
    _symbol    *next;
    char       *name;
    slk_size_t  token;
    uchar       scope;
    uchar       deleted;
} symbol_t;

// ------------------------------------------------------------------------
// Symbols_t
// ------------------------------------------------------------------------

typedef struct _Symbols
{
    symbol_t* (*lookup) ( char   *name );
    symbol_t* (*insert) ( slk_size_t   token, char   *name );
    void      (*release_table_scope) ( void );
    void      (*set_new_table_scope) ( void );
    uchar     (*get_table_scope) ( void );
    void      (*print_table) ( void );
    void      (*release) ( void );

} Symbols_t;

PUBLIC
Symbols_t
MakeSymbol ( uint  table_size );

// ------------------------------------------------------------------------
// Tree_t
// ------------------------------------------------------------------------

typedef struct _Tree
{
    void (*predict) ( slk_size_t production_number );
    void (*reduce) ( slk_size_t production_number );
    void (*show_tree) ( void );
    void (*show_parse_derivation) ( void );
    void (*finish_tree) ( void );
    void (*release) ( void );

} Tree_t;

PUBLIC
Tree_t
MakeTree ( void );   

// ------------------------------------------------------------------
// Action_t
// ------------------------------------------------------------------ 

typedef struct _Action
{
    void (*show_tree) ( void );
    void (*show_parse_derivation) ( void );
    void (*release) ( void );
    SlkAction  slk;

} Action_t;

PUBLIC
Action_t
MakeAction ( void );

// -----------------------------------------------------------------------
// Error_t
// -----------------------------------------------------------------------

typedef struct _Error
{
    uint  (*get_total_errors) ( void );
    uint  (*get_total_warnings) ( void );
    void  (*set_max_errors) ( int number );
    void  (*set_max_warnings) ( int number );
    SlkError  slk;

} Error_t;

PUBLIC
Error_t
MakeError ( void ); 

// ------------------------------------------------------------------------
// Scanner_t
// ------------------------------------------------------------------------

typedef struct _Scanner
{
    int       (*get_line_number) ( void );
    symbol_t* (*get) ( void );

} Scanner_t;

PUBLIC
Scanner_t
MakeScanner ( char  *input );

// ------------------------------------------------------------------------
// Tokens_t
// ------------------------------------------------------------------------

typedef struct _Tokens
{
    int  (*get_line_number) ( void );
    void (*repeat_last) ( void );
    void (*release) ( void );
    struct {
        symbol_t* (*get_current) ( void );
        symbol_t* (*get_last_identifier) ( void );
        void      (*set_last_identifier) ( symbol_t *symbol );
        struct {
            symbol_t* (*get_next) ( void );
            void      (*show_all) ( void );
            void      (*reset) ( void );
        } list;
    } symbols;
    SlkToken   slk;
    
} Tokens_t;

PUBLIC
Tokens_t
MakeToken ( char     *input );

// ------------------------------------------------------------------------
// Options_t
// A struct containing the command line arg results 
// ------------------------------------------------------------------------

typedef struct _Options
{
    char *file_name;
    uint  max_errors,
          max_warnings;
    bool  DISPLAY             : 1;
    bool  JUMP_EDITOR         : 1;
    bool  NAMETABLE           : 1;
    bool  PRUNE_TREE          : 1;
    bool  SHOW_DERIVATION     : 1;
    bool  SHOW_PARSE_TREE     : 1;
    bool  SHOW_SYMBOLS_LIST   : 1;
    bool  TRACE_ERRORS        : 1;
    bool  TRACE_ACTIONS       : 1;
    bool  TRACE_NAMES         : 1;
    bool  TRACE_PEEKER        : 1;
    bool  TRACE_SYMBOLS       : 1;
    bool  TRACE_STATES        : 1;
    bool  TRACE_TYPEDEF       : 1;

} Options_t;

PUBLIC
Options_t
MakeOptions ( int    argc,
              char  *argv[] );

// ------------------------------------------------------------------------
// Parser_t
// Constructs a global Parser for the program
// ------------------------------------------------------------------------

typedef struct _Parser
{
    void (*parse) ( void );
    void (*release) ( void );

} Parser_t;

PUBLIC
Parser_t 
MakeParser ( int    argc,
             char  *argv [] );

// ------------------------------------------------------------------------
// Global Parser for the program namespaced with prefix "Parser"
// ------------------------------------------------------------------------

#define Options    ParserOptions
#define Symbols    ParserSymbols
#define Tokens     ParserTokens
#define Error      ParserError
#define Action     ParserAction
#define Parser     ParserParser

PUBLIC
Options_t  Options;
PUBLIC
Symbols_t  Symbols;
PUBLIC
Tokens_t   Tokens;
PUBLIC
Error_t    Error;
PUBLIC
Action_t   Action;
PUBLIC
Parser_t   Parser;               
                                 
#endif

Figure 1. Header file for a parser


Note that the header uses the much maligned and much abused C preprocessor directives. Defining the typedef instances as being "Parser" is a handy way to reduce redundancy and length in the method usage. This is a C version of "using" in newer languages. Another option would be to have instances of each of the structs inside of the Parser_t. Then the define would refer to them as "Parser." instead of just "Parser" as is done here. The drawback to this is that these public names would not be visible to the debugger.

A careful observer would notice that the Scanner_t does not appear in the Parser. This is because the Scanner is inherited by the Tokens_t. It adds extra lookahead and buffering capability to the lower level Scanner functionality. Inheritance is achieved by simply creating and saving an instance of the Scanner in Tokens. No other code inside or outside of the Parser needs to know anything about the Scanner.

The implementation file in C is shown in figure 2. Note that everything in this file is private except for the constructors. In C, file level privacy is provided by the "static" keyword. Any structs here would be private by virtue of not being included in any header file.


/*************************************************************************

    parser.c

    Version 6.41

    Main entry point for the recognizer.

    Copyright (c) 2001-2014  SLK Systems, all rights reserved.

    09-06-14    Added symbol name tracing
    09-08-14    Just make a full array of all the scanned symbols
    09-09-14    Combine everything into Parser
    09-22-14    Use Parser_t with parse(), release()
    
*************************************************************************/

#include "stdio.h"
#include "stdlib.h"
#include "parser.h"

#define HASH_SIZE    1013           // prime number:  211 503 1013 10007 40013

PRIVATE
char  *Input;

PRIVATE
char Banner [] =
    "scc  V6.41 (c) 2001-2014  SLK Systems";

PRIVATE
char UsageMessage [] =
    "C language recognizer\n"
    "Usage:  scc [ options ] file_name\n\n"

    "  -a     turn on all options that have no argument \n"
    "  -d     display parse derivation \n"
    "  -db    debug options set: d Tp Te \n"
    "  -j     jump to the editor on an error, then exit \n"
    "  -p     print symbol table \n"
    "  -Dp    do not prune/decorate the tree \n"
    "  -Men   set maximum allowed errors to n \n"
    "  -Mwn   set maximum allowed warnings to n \n"
    "  -Sd    show parse derivation from parse tree \n"
    "  -Ss    show all symbols list \n"
    "  -St    show parse tree \n"
    "  -Tc    trace names in actions \n"
    "  -Te    trace error handling \n"
    "  -Tn    trace symbol names in scanner \n"
    "  -Tp    trace peeking/scanning of tokens \n"
    "  -Ts    trace symbol lookup/installation \n"
    "  -Tt    trace states in actions \n"
    "  -Ty    trace typedef \n"
    "  -Ta    trace all \n";

// ------------------------------------------------------------------------
// get_file
// 
// returns the file in a malloc buffer. 
// file is null terminated 
// ------------------------------------------------------------------------

PRIVATE
char *
get_file ( char    *file_name )
{
    size_t  file_size,
            size;
    FILE   *fp;
    char   *file = NULL;

    fp = fopen ( file_name, "rb" );
    if ( fp ) {
        fseek ( fp, 0L, 2 );
        file_size = ftell ( fp );
        rewind ( fp );
        file = (char *)  malloc ( file_size + 4 );
        if ( file ) {
            size = fread ( file, 1, file_size, fp );
            if ( size == file_size ) {
                file [ file_size ] = '\0';
                file [ file_size + 1 ] = '\0';
            } else {
                free ( file );
                file = NULL;
            }
        }
        fclose ( fp );
    }
    return  file;
}

// ------------------------------------------------------------------------
// MakeOptions
// 
// A struct containing the command line arg results 
// ------------------------------------------------------------------------

PUBLIC
Options_t
MakeOptions ( int   argc,
              char *argv[] )
{
    register 
    char     *p; 
    Options_t options = { NULL, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0 };

    while ( --argc > 0 ) {                  // process command line options
        p = *++argv;
        switch (*p){
            case '-':
                if ( *++p ) {
                    switch ( *p ) {
                        case 'a':
                            options.DISPLAY = TRUE;
                            options.JUMP_EDITOR = TRUE;
                            options.NAMETABLE = TRUE;
                            options.SHOW_DERIVATION = TRUE;
                            options.SHOW_SYMBOLS_LIST = TRUE;
                            options.SHOW_PARSE_TREE = TRUE;
                            goto TRACE_ALL; 
                            break;
                        case 'd':
                            options.DISPLAY = TRUE;
                            if ( *++p == 'b' ) {
                                options.TRACE_ERRORS = TRUE;
                                options.TRACE_PEEKER = TRUE;
                            } else {
                                --p;
                            } 
                            break;
                        case 'j':
                            options.JUMP_EDITOR = TRUE;
                            break;
                        case 'p':
                            options.NAMETABLE = TRUE;
                            break;
                        case 'D':
                            if ( *++p ) {
                                switch ( *p ) {
                                case 'p':
                                    options.PRUNE_TREE = FALSE;
                                    break;
                                default:
                                    fputc ('D', stderr);
                                    fputc (*p, stderr);
                                    fputs (", invalid option\n", stderr);
                                }
                            }
                            break;
                        case 'M':
                            if ( *++p ) {
                                switch ( *p ) {
                                case 'e':
                                    options.max_errors = atoi ( ++p );
                                    break;
                                case 'w':
                                    options.max_warnings = atoi ( ++p );
                                    break;
                                default:
                                    fputc ('M', stderr);
                                    fputc (*p, stderr);
                                    fputs (", invalid option\n", stderr);
                                }
                            }
                            break;
                        case 'S':
                            while ( *++p ) {
                                switch ( *p ) {
                                    case 'd':
                                        options.SHOW_DERIVATION = TRUE;
                                        break;
                                    case 's':
                                        options.SHOW_SYMBOLS_LIST = TRUE;
                                        break;
                                    case 't':
                                        options.SHOW_PARSE_TREE = TRUE;
                                        break;
                                    default:
                                        fputc ('S', stderr);
                                        fputc (*p, stderr);
                                        fputs (", invalid option\n", stderr);
                                } 
                            }
                            --p;
                            break;
                        case 'T':
                            while ( *++p ) {
                                switch ( *p ) {
                                    case 'a':                       TRACE_ALL:
                                        options.TRACE_ACTIONS = TRUE;
                                        options.TRACE_ERRORS = TRUE;
                                        options.TRACE_NAMES = TRUE;
                                        options.TRACE_PEEKER = TRUE;
                                        options.TRACE_SYMBOLS = TRUE;
                                        options.TRACE_TYPEDEF = TRUE;
                                        break;
                                    case 'c':
                                        options.TRACE_ACTIONS = TRUE;
                                        break;
                                    case 'e':
                                        options.TRACE_ERRORS = TRUE;
                                        break;
                                    case 'n':
                                        options.TRACE_NAMES = TRUE;
                                        break;
                                    case 'p':
                                        options.TRACE_PEEKER = TRUE;
                                        break;
                                    case 's':
                                        options.TRACE_SYMBOLS = TRUE;
                                        break;
                                    case 't':
                                        options.TRACE_STATES = TRUE;
                                        break;
                                    case 'y':
                                        options.TRACE_TYPEDEF = TRUE;
                                        break;
                                    default:
                                        fputc ('T', stderr);
                                        fputc (*p, stderr);
                                        fputs (", invalid option\n", stderr);
                                } 
                            }
                            --p;
                            break;
                        default:
                            fputc (*p, stderr);
                            fputs (", invalid option\n", stderr);
		    }
                }
                break;
	    default:
                options.file_name = *argv;
	}
    }
    return  options;
}

// ----------------------------------------------------------------------- 
// parse 
// -----------------------------------------------------------------------

PRIVATE
void
parse ( void )
{
    SlkParse  ( Action.slk, Tokens.slk, Error.slk, 0 );
}

// ----------------------------------------------------------------------- 
// release
// -----------------------------------------------------------------------

PRIVATE
void
release ( void )
{
    Symbols.release();
    Tokens.release(); 
    Action.release();
    free ( Input );
}

// ------------------------------------------------------------------------
// MakeParser
//
// Constructs a global Parser for the program
// ------------------------------------------------------------------------

PUBLIC
Parser_t
MakeParser ( int   argc,
             char *argv [] )
{
    char  *file_name;

    puts ( Banner );
    Options = MakeOptions ( argc, argv );       // process command line options
    file_name = Options.file_name;
    if ( ! file_name ) {
        puts ( UsageMessage );
        return  Parser;
    }
    Input = get_file ( file_name );
    if ( ! Input ) {
        perror ( file_name );
        return  Parser;
    }
    Symbols = MakeSymbol ( HASH_SIZE );
    Tokens = MakeToken ( Input );
    Error = MakeError();
    if ( Options.max_errors ) {
        Error.set_max_errors ( Options.max_errors );
    }
    if ( Options.max_warnings ) {
        Error.set_max_warnings ( Options.max_warnings );
    }                                           
    Action = MakeAction();

    Parser.parse = parse;                       // NULL if error return
    Parser.release = release;

    return  Parser;
}

// ------------------------------------------------------------------------
// main
// This logic can be in another file and made a unit test here
// Must include parser.h
// ------------------------------------------------------------------------

PUBLIC
int 
main ( int    argc,
       char  *argv [] )
{
    uint      errors,
              warnings;

    MakeParser ( argc, argv );
    if ( ! Parser.parse ) {                 // construction failed
        return  3;
    }
    Parser.parse();
    warnings = Error.get_total_warnings ();
    if ( warnings ) {
        printf ( "%5u warnings \n", warnings );
    }
    errors = Error.get_total_errors ();
    if ( errors ) {
        if ( errors > 1 ) {
            --errors;                      // extra one from the first no_entry
        }
        printf ( "%5u errors \n", errors );
    }
    if ( Options.NAMETABLE ) {
        Symbols.print_table();
    }
    if ( Options.SHOW_SYMBOLS_LIST ) {
        Tokens.symbols.list.show_all();
    }
    if ( Options.SHOW_DERIVATION ) {
        Action.show_parse_derivation ();
    }
    if ( Options.SHOW_PARSE_TREE ) {
        Action.show_tree ();
    }
    Parser.release();

    return  0;
}
Figure 2. C code file for a parser

The other components of the Parser are not shown here both for brevity and to illustrate that it is not necessary to wade through every line of code in a system in order to be able to use it. This is the advantage of a black box design over the more common OOP white box approach. Clearly a compiler using this parser would want to add functionality to the Tree_t parse tree construction to for example convert the parse tree into an abstract syntax tree. But it is quite unlikely that the compiler would need to know anything more about the memory_set_t than the information present in the header file.


Home

Copyright © 2001-2014 SLK Systems