_YACC FOR EXPERT SYSTEMS_
by Todd King


[LISTING ONE]

/*---------------------------------------------------------------------------
  FILE: lfx.y -- Rules and actions for a land form expert system -- Todd King
----------------------------------------------------------------------------*/
%{
#include <string.h>
#include "lfclass.h"
%}

%union {
   LOCATION location;
}

%token <location> UP_SLOPE DOWN_SLOPE HORIZONTAL DONE

%start terrain
%%
terrain: land_form
     {
        YYACCEPT;
     }
     ;
land_form : peak
          | valley
          | plateau
          | basin
          | shelf
          | DONE
     ;
peak : UP_SLOPE DOWN_SLOPE
     {
        label("peak", $1.start_x, $2.end_x);
     }
     ;
valley : DOWN_SLOPE UP_SLOPE
     {
        label("valley", $1.start_x, $2.end_x);
     }
     ;
plateau : UP_SLOPE HORIZONTAL DOWN_SLOPE
     {
        label("plateau", $1.start_x, $3.end_x);
     }
     ;
basin : DOWN_SLOPE HORIZONTAL UP_SLOPE
     {
       label("basin", $1.start_x, $3.end_x);
     }
     ;
shelf : DOWN_SLOPE HORIZONTAL DOWN_SLOPE
     {
       label("shelf", $1.start_x, $3.end_x);
     }
      | UP_SLOPE HORIZONTAL UP_SLOPE
     {
       label("shelf", $1.start_x, $3.end_x);
     }
     ;
%%





[LISTING TWO]

/*-------------------------------------------------------------------------
   FILE: error.c -- Error reporting and recover function called by the YACC 
   state engine whenever an impossible combination of states is encountered.
   Todd King
---------------------------------------------------------------------------*/
#include "lfclass.h"  /* Must precede "ytab.h" */
#include "ytab.h"

yyerror(c)
{
  extern SOURCE Map_source;

  TOKEN *token;

  label("?!", Map_source.last_token.location.start_x, 
              Map_source.last_token.location.start_x);
  token = pop_token(&Map_source);
  while(token->value != DONE) {  /* Clear stack */
    token = pop_token(&Map_source);
  }
  Map_source.last_token.value = UNDEF_TOKEN;
  return(0);
}



[LISTING THREE]

/*--------------------------------------------------------------------------
   FILE: lfclass.c -- All functions used to identify indivisable features of 
   the land form. This is just the slope of the terrain. -- Todd King
--------------------------------------------------------------------------*/
#include "lfclass.h"	/* Must precede "ytab.h" */
#include "ytab.h"

yylex() {
  extern SOURCE Map_source;

  TOKEN last_token;
  TOKEN *tptr;
  int x;
  char buffer[10];

  token_copy(&last_token, get_token(&Map_source));
  token_copy(&Map_source.last_token, &last_token);
  if(last_token.value == DONE) return(last_token.value);

  tptr = get_token(&Map_source);
  while(tptr->value == last_token.value) {
     tptr = get_token(&Map_source);
  }
  push_token(&Map_source, tptr);
  location_copy(&yylval, &last_token.location);
  return(last_token.value);
}

TOKEN *get_token(source)
SOURCE *source;
{
  if(source->in_buffer > 0) {
    return(pop_token(source));
  } else {
    return(trend(source));
  }
}

token_copy(t1, t2)
TOKEN *t1;
TOKEN *t2;
{
  t1->value = t2->value;
  location_copy(&t1->location, &t2->location);
}

location_copy(l1, l2)
LOCATION *l1;
LOCATION *l2;
{
  l1->start_x = l2->start_x;
  l1->start_y = l2->start_y;
  l1->end_x = l2->end_x;
  l1->end_y = l2->end_y;
}

TOKEN *trend(source)
SOURCE *source;
{
  static TOKEN _Trend_token;

  int delta;
  int x, y;

  _Trend_token.value = DONE;
  if(source->last_y == NOT_DEF) {
     if(fscanf(source->fptr, "%d, %d", &source->last_x, &source->last_y) < 2) {
	return(&_Trend_token);
     }
  }
  if(fscanf(source->fptr, "%d, %d", &x, &y) < 1) {
     return(&_Trend_token);
  }

  _Trend_token.location.start_x = source->last_x;
  _Trend_token.location.start_y = source->last_y;
  _Trend_token.location.end_x = x;
  _Trend_token.location.end_y = y;

  delta = y - source->last_y;
  source->last_y = y;
  source->last_x = x;

  if(delta < 0) {
     _Trend_token.value = DOWN_SLOPE;
  } else if(delta > 0) {
     _Trend_token.value = UP_SLOPE;
  } else {
     _Trend_token.value = HORIZONTAL;
  }
  return(&_Trend_token);
}

TOKEN *pop_token(source)
SOURCE *source;
{
  static TOKEN _Pop_token;

  _Pop_token.value = DONE;
  if(source->in_buffer <= 0) return(&_Pop_token);
  source->in_buffer--;
  return(&source->token_buffer[source->in_buffer]);
}

push_token(source, token)
SOURCE *source;
TOKEN *token;
{
   if(source->in_buffer >= MAX_TOKEN_BUFFER) {
      return(-1);
   }
   if(token->value == UNDEF_TOKEN) {
      return(-1);
   }

   token_copy(&source->token_buffer[source->in_buffer], token);
   source->in_buffer++;
   return(source->in_buffer);
}

init_source(source)
SOURCE *source;
{
  source->in_buffer = 0;
  source->fptr = NULL;
  source->last_y = NOT_DEF;
  source->last_token.value = UNDEF_TOKEN;
}




[LISTING FOUR]

/*----------------------------------------------------------------------
  FILE: lfclass.h -- Type and misc. definitions for land form classifier.
   Todd King
------------------------------------------------------------------------*/
#ifndef _LFCLASS.H_
#define _LFCLASS.H_ 

#define GRAPHICS	1	/* If defined graphics output is used */
#include <stdio.h>

/* Defines for use with the scaled() function */
#define X_AXIS	1
#define Y_AXIS	2

/* Definitions for token and token source items */
#define NOT_DEF	-1
#define UNDEF_TOKEN	0	/* Must less than 255 for YACC's sake */
#define MAX_TOKEN_BUFFER	8
#define LABEL_AT_Y	12

typedef struct {
  int start_x;
  int start_y;
  int end_x;
  int end_y;
} LOCATION;

typedef struct {
  LOCATION location;
  int value;
} TOKEN;

typedef struct {
  FILE *fptr;
  int last_y;
  int last_x;
  TOKEN last_token;
  int in_buffer;
  TOKEN token_buffer[MAX_TOKEN_BUFFER];
} SOURCE;

/* Function Definitions */
TOKEN *pop_token();
TOKEN *get_token();
TOKEN *trend();

#endif _LFCLASS.H_




[LISTING FIVE]

/*---------------------------------------------------------
   FILE: render.c -- All rendering functions -- Todd King
----------------------------------------------------------*/
#include <graphics.h>
#include "lfclass.h"	/* Must Precede "ytab.h" */
#include "ytab.h"

/* Variables for graphics output */
int View_max_x;
int View_max_y;
int Screen_max_x;
int Screen_max_y;

set_screen_max(x, y)
int x;
int y;
{
   Screen_max_x = x;
   Screen_max_y = y;
}

set_view_max(fptr)
FILE *fptr;
{
   int x, y;

   View_max_x = 0;
   View_max_y = 0;

   while(fscanf(fptr, "%d, %d", &x, &y) > 0) {
      if(x > View_max_x) View_max_x = x;
      if(y > View_max_y) View_max_y = y;
   }
   rewind(fptr);
}

init_graphics()
{
#ifdef GRAPHICS
  int gdriver;
  int gmode;

/* Initialize graphics */
  detectgraph(&gdriver, &gmode);
  if(gdriver < 0) {
     fprintf(stderr, "Unable to determine graphics device.\n");
     return(0);
  }
  initgraph(&gdriver, &gmode, "c:\\turboc");
  if(gdriver < 0) {
     fprintf(stderr, "Unable to determine graphics device.\n");
     return(0);
  }

/* A few initializations. */
  set_screen_max(getmaxx(), getmaxy());
#endif GRAPHICS

  return(1);	/* Success */
}

deinit_graphics()
{
  closegraph();
}

display_message(msg)
char msg[];
{
#ifdef GRAPHICS
  moveto(0, getmaxy() - 12);
  outtext(msg);
  getch();
#else
  printf(msg);
  getch();
#endif GRAPHICS
}

draw_trace(fptr)
FILE *fptr;
{
#ifdef GRAPHICS
   int x, y;
   int first = 1;

/* Draw surface */
   while(fscanf(fptr, "%d, %d", &x, &y) > 0) {
      if(first) {
         moveto(scaled(x, X_AXIS), scaled(y, Y_AXIS));
         first = 0;
      }
      lineto(scaled(x, X_AXIS), scaled(y, Y_AXIS));
   }
   rewind(fptr);
#endif GRAPHICS
}

label(text, start_x, end_x)
char text[];
int start_x;
int end_x;
{
#ifdef GRAPHICS
   settextjustify(CENTER_TEXT, BOTTOM_TEXT);
   moveto(scaled(start_x + (end_x - start_x) / 2, X_AXIS),
	  LABEL_AT_Y);
   outtext(text);
   settextjustify(LEFT_TEXT, BOTTOM_TEXT);
#else
   printf("%s @ %d\n", text, start_x + (end_x - start_x) / 2);
#endif GRAPHICS
}

scaled(xy, axis)
int xy;
int axis;
{
  int new_xy;

  switch(axis) {
    case X_AXIS:
      new_xy = ((float)xy / View_max_x) * Screen_max_x;
      break;
    case Y_AXIS:
      new_xy = Screen_max_y - ((float)xy / View_max_y) * Screen_max_y;
      break;
   }

   return(new_xy);
}



[LISTING SIX]

/*----------------------------------------------------------------------
   FILE: example.c -- An example integration of all the land form expert
   system code -- Todd King
-----------------------------------------------------------------------*/
#include <stdio.h>
#include "mclass.h"	/* Must precede "ytab.h" */
#include "ytab.h"

#define MAX_WIDTH	79
#define MAX_HEIGHT	10
SOURCE Map_source;

main(argc, argv)
int argc;
char *argv[];
{
  FILE *fptr;
  int temp[2];

/* Check arguments, if OK open file */
  if(argc < 2) {
     printf("Proper usage: example {terrain hieght file}\n");
     exit(0);
  }

  init_source(&Map_source);
  if((Map_source.fptr = fopen(argv[1], "r")) == NULL) {
     perror(argv[1]);
     exit(0);
  }

  init_graphics();

/* A few initializations. */
  set_view_max(Map_source.fptr);

  draw_trace(Map_source.fptr);

/* Now classify all features. */
  while(Map_source.last_token.value != DONE) {
    yyparse();
    push_token(&Map_source, &Map_source.last_token);
  }

/* All done, wait before cleaning up. */
  display_message("Press any key to exit ...");
  deinit_graphics();
  exit(0);
}




[FIGURE 1]

#-------------------------------------------------------------------------
#   Makefile for the generation of a land form expert system -- Todd King
#--------------------------------------------------------------------------
CFLAGS = -mc
LDFLAGS = $(CFLAGS)
YFLAGS = -d

OBJ = example.obj lfx.obj lfclass.obj render.obj error.obj
example.exe : $(OBJ)
	$(LD) $(LDFLAGS) $(OBJ) graphics.lib

lfx.c : lfx.y lfclass.h

lfclass.obj : lfclass.c lfclass.h ytab.h

render.obj : render.c lfclass.h

error.obj : error.c ytab.h

clean :
	del *.obj
	del lfx.c


[FIGURE 2]

0, 50
10, 60
20, 40
30, 30
40, 30
55, 50
60, 50
70, 80
80, 20
90, 80
100, 50
105, 50
110, 20
120, 20