home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD1.mdf / magazine / drdobbs / 1991 / 02 / expert.asc < prev    next >
Text File  |  1990-12-26  |  11KB  |  521 lines
  1. _YACC FOR EXPERT SYSTEMS_
  2. by Todd King
  3.  
  4.  
  5. [LISTING ONE]
  6.  
  7. /*---------------------------------------------------------------------------
  8.   FILE: lfx.y -- Rules and actions for a land form expert system -- Todd King
  9. ----------------------------------------------------------------------------*/
  10. %{
  11. #include <string.h>
  12. #include "lfclass.h"
  13. %}
  14.  
  15. %union {
  16.    LOCATION location;
  17. }
  18.  
  19. %token <location> UP_SLOPE DOWN_SLOPE HORIZONTAL DONE
  20.  
  21. %start terrain
  22. %%
  23. terrain: land_form
  24.      {
  25.         YYACCEPT;
  26.      }
  27.      ;
  28. land_form : peak
  29.           | valley
  30.           | plateau
  31.           | basin
  32.           | shelf
  33.           | DONE
  34.      ;
  35. peak : UP_SLOPE DOWN_SLOPE
  36.      {
  37.         label("peak", $1.start_x, $2.end_x);
  38.      }
  39.      ;
  40. valley : DOWN_SLOPE UP_SLOPE
  41.      {
  42.         label("valley", $1.start_x, $2.end_x);
  43.      }
  44.      ;
  45. plateau : UP_SLOPE HORIZONTAL DOWN_SLOPE
  46.      {
  47.         label("plateau", $1.start_x, $3.end_x);
  48.      }
  49.      ;
  50. basin : DOWN_SLOPE HORIZONTAL UP_SLOPE
  51.      {
  52.        label("basin", $1.start_x, $3.end_x);
  53.      }
  54.      ;
  55. shelf : DOWN_SLOPE HORIZONTAL DOWN_SLOPE
  56.      {
  57.        label("shelf", $1.start_x, $3.end_x);
  58.      }
  59.       | UP_SLOPE HORIZONTAL UP_SLOPE
  60.      {
  61.        label("shelf", $1.start_x, $3.end_x);
  62.      }
  63.      ;
  64. %%
  65.  
  66.  
  67.  
  68.  
  69.  
  70. [LISTING TWO]
  71.  
  72. /*-------------------------------------------------------------------------
  73.    FILE: error.c -- Error reporting and recover function called by the YACC 
  74.    state engine whenever an impossible combination of states is encountered.
  75.    Todd King
  76. ---------------------------------------------------------------------------*/
  77. #include "lfclass.h"  /* Must precede "ytab.h" */
  78. #include "ytab.h"
  79.  
  80. yyerror(c)
  81. {
  82.   extern SOURCE Map_source;
  83.  
  84.   TOKEN *token;
  85.  
  86.   label("?!", Map_source.last_token.location.start_x, 
  87.               Map_source.last_token.location.start_x);
  88.   token = pop_token(&Map_source);
  89.   while(token->value != DONE) {  /* Clear stack */
  90.     token = pop_token(&Map_source);
  91.   }
  92.   Map_source.last_token.value = UNDEF_TOKEN;
  93.   return(0);
  94. }
  95.  
  96.  
  97.  
  98. [LISTING THREE]
  99.  
  100. /*--------------------------------------------------------------------------
  101.    FILE: lfclass.c -- All functions used to identify indivisable features of 
  102.    the land form. This is just the slope of the terrain. -- Todd King
  103. --------------------------------------------------------------------------*/
  104. #include "lfclass.h"    /* Must precede "ytab.h" */
  105. #include "ytab.h"
  106.  
  107. yylex() {
  108.   extern SOURCE Map_source;
  109.  
  110.   TOKEN last_token;
  111.   TOKEN *tptr;
  112.   int x;
  113.   char buffer[10];
  114.  
  115.   token_copy(&last_token, get_token(&Map_source));
  116.   token_copy(&Map_source.last_token, &last_token);
  117.   if(last_token.value == DONE) return(last_token.value);
  118.  
  119.   tptr = get_token(&Map_source);
  120.   while(tptr->value == last_token.value) {
  121.      tptr = get_token(&Map_source);
  122.   }
  123.   push_token(&Map_source, tptr);
  124.   location_copy(&yylval, &last_token.location);
  125.   return(last_token.value);
  126. }
  127.  
  128. TOKEN *get_token(source)
  129. SOURCE *source;
  130. {
  131.   if(source->in_buffer > 0) {
  132.     return(pop_token(source));
  133.   } else {
  134.     return(trend(source));
  135.   }
  136. }
  137.  
  138. token_copy(t1, t2)
  139. TOKEN *t1;
  140. TOKEN *t2;
  141. {
  142.   t1->value = t2->value;
  143.   location_copy(&t1->location, &t2->location);
  144. }
  145.  
  146. location_copy(l1, l2)
  147. LOCATION *l1;
  148. LOCATION *l2;
  149. {
  150.   l1->start_x = l2->start_x;
  151.   l1->start_y = l2->start_y;
  152.   l1->end_x = l2->end_x;
  153.   l1->end_y = l2->end_y;
  154. }
  155.  
  156. TOKEN *trend(source)
  157. SOURCE *source;
  158. {
  159.   static TOKEN _Trend_token;
  160.  
  161.   int delta;
  162.   int x, y;
  163.  
  164.   _Trend_token.value = DONE;
  165.   if(source->last_y == NOT_DEF) {
  166.      if(fscanf(source->fptr, "%d, %d", &source->last_x, &source->last_y) < 2) {
  167.     return(&_Trend_token);
  168.      }
  169.   }
  170.   if(fscanf(source->fptr, "%d, %d", &x, &y) < 1) {
  171.      return(&_Trend_token);
  172.   }
  173.  
  174.   _Trend_token.location.start_x = source->last_x;
  175.   _Trend_token.location.start_y = source->last_y;
  176.   _Trend_token.location.end_x = x;
  177.   _Trend_token.location.end_y = y;
  178.  
  179.   delta = y - source->last_y;
  180.   source->last_y = y;
  181.   source->last_x = x;
  182.  
  183.   if(delta < 0) {
  184.      _Trend_token.value = DOWN_SLOPE;
  185.   } else if(delta > 0) {
  186.      _Trend_token.value = UP_SLOPE;
  187.   } else {
  188.      _Trend_token.value = HORIZONTAL;
  189.   }
  190.   return(&_Trend_token);
  191. }
  192.  
  193. TOKEN *pop_token(source)
  194. SOURCE *source;
  195. {
  196.   static TOKEN _Pop_token;
  197.  
  198.   _Pop_token.value = DONE;
  199.   if(source->in_buffer <= 0) return(&_Pop_token);
  200.   source->in_buffer--;
  201.   return(&source->token_buffer[source->in_buffer]);
  202. }
  203.  
  204. push_token(source, token)
  205. SOURCE *source;
  206. TOKEN *token;
  207. {
  208.    if(source->in_buffer >= MAX_TOKEN_BUFFER) {
  209.       return(-1);
  210.    }
  211.    if(token->value == UNDEF_TOKEN) {
  212.       return(-1);
  213.    }
  214.  
  215.    token_copy(&source->token_buffer[source->in_buffer], token);
  216.    source->in_buffer++;
  217.    return(source->in_buffer);
  218. }
  219.  
  220. init_source(source)
  221. SOURCE *source;
  222. {
  223.   source->in_buffer = 0;
  224.   source->fptr = NULL;
  225.   source->last_y = NOT_DEF;
  226.   source->last_token.value = UNDEF_TOKEN;
  227. }
  228.  
  229.  
  230.  
  231.  
  232. [LISTING FOUR]
  233.  
  234. /*----------------------------------------------------------------------
  235.   FILE: lfclass.h -- Type and misc. definitions for land form classifier.
  236.    Todd King
  237. ------------------------------------------------------------------------*/
  238. #ifndef _LFCLASS.H_
  239. #define _LFCLASS.H_ 
  240.  
  241. #define GRAPHICS    1    /* If defined graphics output is used */
  242. #include <stdio.h>
  243.  
  244. /* Defines for use with the scaled() function */
  245. #define X_AXIS    1
  246. #define Y_AXIS    2
  247.  
  248. /* Definitions for token and token source items */
  249. #define NOT_DEF    -1
  250. #define UNDEF_TOKEN    0    /* Must less than 255 for YACC's sake */
  251. #define MAX_TOKEN_BUFFER    8
  252. #define LABEL_AT_Y    12
  253.  
  254. typedef struct {
  255.   int start_x;
  256.   int start_y;
  257.   int end_x;
  258.   int end_y;
  259. } LOCATION;
  260.  
  261. typedef struct {
  262.   LOCATION location;
  263.   int value;
  264. } TOKEN;
  265.  
  266. typedef struct {
  267.   FILE *fptr;
  268.   int last_y;
  269.   int last_x;
  270.   TOKEN last_token;
  271.   int in_buffer;
  272.   TOKEN token_buffer[MAX_TOKEN_BUFFER];
  273. } SOURCE;
  274.  
  275. /* Function Definitions */
  276. TOKEN *pop_token();
  277. TOKEN *get_token();
  278. TOKEN *trend();
  279.  
  280. #endif _LFCLASS.H_
  281.  
  282.  
  283.  
  284.  
  285. [LISTING FIVE]
  286.  
  287. /*---------------------------------------------------------
  288.    FILE: render.c -- All rendering functions -- Todd King
  289. ----------------------------------------------------------*/
  290. #include <graphics.h>
  291. #include "lfclass.h"    /* Must Precede "ytab.h" */
  292. #include "ytab.h"
  293.  
  294. /* Variables for graphics output */
  295. int View_max_x;
  296. int View_max_y;
  297. int Screen_max_x;
  298. int Screen_max_y;
  299.  
  300. set_screen_max(x, y)
  301. int x;
  302. int y;
  303. {
  304.    Screen_max_x = x;
  305.    Screen_max_y = y;
  306. }
  307.  
  308. set_view_max(fptr)
  309. FILE *fptr;
  310. {
  311.    int x, y;
  312.  
  313.    View_max_x = 0;
  314.    View_max_y = 0;
  315.  
  316.    while(fscanf(fptr, "%d, %d", &x, &y) > 0) {
  317.       if(x > View_max_x) View_max_x = x;
  318.       if(y > View_max_y) View_max_y = y;
  319.    }
  320.    rewind(fptr);
  321. }
  322.  
  323. init_graphics()
  324. {
  325. #ifdef GRAPHICS
  326.   int gdriver;
  327.   int gmode;
  328.  
  329. /* Initialize graphics */
  330.   detectgraph(&gdriver, &gmode);
  331.   if(gdriver < 0) {
  332.      fprintf(stderr, "Unable to determine graphics device.\n");
  333.      return(0);
  334.   }
  335.   initgraph(&gdriver, &gmode, "c:\\turboc");
  336.   if(gdriver < 0) {
  337.      fprintf(stderr, "Unable to determine graphics device.\n");
  338.      return(0);
  339.   }
  340.  
  341. /* A few initializations. */
  342.   set_screen_max(getmaxx(), getmaxy());
  343. #endif GRAPHICS
  344.  
  345.   return(1);    /* Success */
  346. }
  347.  
  348. deinit_graphics()
  349. {
  350.   closegraph();
  351. }
  352.  
  353. display_message(msg)
  354. char msg[];
  355. {
  356. #ifdef GRAPHICS
  357.   moveto(0, getmaxy() - 12);
  358.   outtext(msg);
  359.   getch();
  360. #else
  361.   printf(msg);
  362.   getch();
  363. #endif GRAPHICS
  364. }
  365.  
  366. draw_trace(fptr)
  367. FILE *fptr;
  368. {
  369. #ifdef GRAPHICS
  370.    int x, y;
  371.    int first = 1;
  372.  
  373. /* Draw surface */
  374.    while(fscanf(fptr, "%d, %d", &x, &y) > 0) {
  375.       if(first) {
  376.          moveto(scaled(x, X_AXIS), scaled(y, Y_AXIS));
  377.          first = 0;
  378.       }
  379.       lineto(scaled(x, X_AXIS), scaled(y, Y_AXIS));
  380.    }
  381.    rewind(fptr);
  382. #endif GRAPHICS
  383. }
  384.  
  385. label(text, start_x, end_x)
  386. char text[];
  387. int start_x;
  388. int end_x;
  389. {
  390. #ifdef GRAPHICS
  391.    settextjustify(CENTER_TEXT, BOTTOM_TEXT);
  392.    moveto(scaled(start_x + (end_x - start_x) / 2, X_AXIS),
  393.       LABEL_AT_Y);
  394.    outtext(text);
  395.    settextjustify(LEFT_TEXT, BOTTOM_TEXT);
  396. #else
  397.    printf("%s @ %d\n", text, start_x + (end_x - start_x) / 2);
  398. #endif GRAPHICS
  399. }
  400.  
  401. scaled(xy, axis)
  402. int xy;
  403. int axis;
  404. {
  405.   int new_xy;
  406.  
  407.   switch(axis) {
  408.     case X_AXIS:
  409.       new_xy = ((float)xy / View_max_x) * Screen_max_x;
  410.       break;
  411.     case Y_AXIS:
  412.       new_xy = Screen_max_y - ((float)xy / View_max_y) * Screen_max_y;
  413.       break;
  414.    }
  415.  
  416.    return(new_xy);
  417. }
  418.  
  419.  
  420.  
  421. [LISTING SIX]
  422.  
  423. /*----------------------------------------------------------------------
  424.    FILE: example.c -- An example integration of all the land form expert
  425.    system code -- Todd King
  426. -----------------------------------------------------------------------*/
  427. #include <stdio.h>
  428. #include "mclass.h"    /* Must precede "ytab.h" */
  429. #include "ytab.h"
  430.  
  431. #define MAX_WIDTH    79
  432. #define MAX_HEIGHT    10
  433. SOURCE Map_source;
  434.  
  435. main(argc, argv)
  436. int argc;
  437. char *argv[];
  438. {
  439.   FILE *fptr;
  440.   int temp[2];
  441.  
  442. /* Check arguments, if OK open file */
  443.   if(argc < 2) {
  444.      printf("Proper usage: example {terrain hieght file}\n");
  445.      exit(0);
  446.   }
  447.  
  448.   init_source(&Map_source);
  449.   if((Map_source.fptr = fopen(argv[1], "r")) == NULL) {
  450.      perror(argv[1]);
  451.      exit(0);
  452.   }
  453.  
  454.   init_graphics();
  455.  
  456. /* A few initializations. */
  457.   set_view_max(Map_source.fptr);
  458.  
  459.   draw_trace(Map_source.fptr);
  460.  
  461. /* Now classify all features. */
  462.   while(Map_source.last_token.value != DONE) {
  463.     yyparse();
  464.     push_token(&Map_source, &Map_source.last_token);
  465.   }
  466.  
  467. /* All done, wait before cleaning up. */
  468.   display_message("Press any key to exit ...");
  469.   deinit_graphics();
  470.   exit(0);
  471. }
  472.  
  473.  
  474.  
  475.  
  476. [FIGURE 1]
  477.  
  478. #-------------------------------------------------------------------------
  479. #   Makefile for the generation of a land form expert system -- Todd King
  480. #--------------------------------------------------------------------------
  481. CFLAGS = -mc
  482. LDFLAGS = $(CFLAGS)
  483. YFLAGS = -d
  484.  
  485. OBJ = example.obj lfx.obj lfclass.obj render.obj error.obj
  486. example.exe : $(OBJ)
  487.     $(LD) $(LDFLAGS) $(OBJ) graphics.lib
  488.  
  489. lfx.c : lfx.y lfclass.h
  490.  
  491. lfclass.obj : lfclass.c lfclass.h ytab.h
  492.  
  493. render.obj : render.c lfclass.h
  494.  
  495. error.obj : error.c ytab.h
  496.  
  497. clean :
  498.     del *.obj
  499.     del lfx.c
  500.  
  501.  
  502. [FIGURE 2]
  503.  
  504. 0, 50
  505. 10, 60
  506. 20, 40
  507. 30, 30
  508. 40, 30
  509. 55, 50
  510. 60, 50
  511. 70, 80
  512. 80, 20
  513. 90, 80
  514. 100, 50
  515. 105, 50
  516. 110, 20
  517. 120, 20
  518.  
  519.  
  520.  
  521.