misc/lemon.c
author Ryan C. Gordon <icculus@icculus.org>
Sat, 13 Feb 2010 01:04:55 -0500
changeset 830 b15b3c3b5c4a
parent 829 7b3c3ae9e5a9
child 831 80e47b096ecd
permissions -rw-r--r--
Lemon now writes errors to stderr instead of stdout, and uses full output. The previous way truncated the filename, so my editor couldn't jump to the problem line in the source code.
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
710
cbcba3ea6a05 Hacks to lemon parser generator to fit my needs.
Ryan C. Gordon <icculus@icculus.org>
parents: 708
diff changeset
     1
/*
cbcba3ea6a05 Hacks to lemon parser generator to fit my needs.
Ryan C. Gordon <icculus@icculus.org>
parents: 708
diff changeset
     2
 * My changes over the original lemon.c from SQLite are encased in
cbcba3ea6a05 Hacks to lemon parser generator to fit my needs.
Ryan C. Gordon <icculus@icculus.org>
parents: 708
diff changeset
     3
 *  #if __MOJOSHADER__ blocks.  --ryan.
cbcba3ea6a05 Hacks to lemon parser generator to fit my needs.
Ryan C. Gordon <icculus@icculus.org>
parents: 708
diff changeset
     4
 */
cbcba3ea6a05 Hacks to lemon parser generator to fit my needs.
Ryan C. Gordon <icculus@icculus.org>
parents: 708
diff changeset
     5
#define __MOJOSHADER__ 1
cbcba3ea6a05 Hacks to lemon parser generator to fit my needs.
Ryan C. Gordon <icculus@icculus.org>
parents: 708
diff changeset
     6
708
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
     7
/*
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
     8
** This file contains all sources (including headers) to the LEMON
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
     9
** LALR(1) parser generator.  The sources have been combined into a
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
    10
** single file to make it easy to include LEMON in the source tree
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
    11
** and Makefile of another program.
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
    12
**
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
    13
** The author of this program disclaims copyright.
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
    14
*/
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
    15
#include <stdio.h>
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
    16
#include <stdarg.h>
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
    17
#include <string.h>
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
    18
#include <ctype.h>
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
    19
#include <stdlib.h>
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
    20
#include <assert.h>
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
    21
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
    22
#ifndef __WIN32__
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
    23
#   if defined(_WIN32) || defined(WIN32)
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
    24
#	define __WIN32__
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
    25
#   endif
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
    26
#endif
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
    27
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
    28
#ifdef __WIN32__
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
    29
extern int access();
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
    30
#else
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
    31
#include <unistd.h>
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
    32
#endif
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
    33
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
    34
/* #define PRIVATE static */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
    35
#define PRIVATE
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
    36
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
    37
#ifdef TEST
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
    38
#define MAXRHS 5       /* Set low to exercise exception code */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
    39
#else
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
    40
#define MAXRHS 1000
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
    41
#endif
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
    42
829
7b3c3ae9e5a9 Lemon now deletes its output on failure.
Ryan C. Gordon <icculus@icculus.org>
parents: 809
diff changeset
    43
#if __MOJOSHADER__
7b3c3ae9e5a9 Lemon now deletes its output on failure.
Ryan C. Gordon <icculus@icculus.org>
parents: 809
diff changeset
    44
static const char **made_files = NULL;
7b3c3ae9e5a9 Lemon now deletes its output on failure.
Ryan C. Gordon <icculus@icculus.org>
parents: 809
diff changeset
    45
static int made_files_count = 0;
7b3c3ae9e5a9 Lemon now deletes its output on failure.
Ryan C. Gordon <icculus@icculus.org>
parents: 809
diff changeset
    46
static void lemon_exit(const int status)
7b3c3ae9e5a9 Lemon now deletes its output on failure.
Ryan C. Gordon <icculus@icculus.org>
parents: 809
diff changeset
    47
{
7b3c3ae9e5a9 Lemon now deletes its output on failure.
Ryan C. Gordon <icculus@icculus.org>
parents: 809
diff changeset
    48
    /* if we failed, delete (most) files we made, to unconfuse build tools. */
7b3c3ae9e5a9 Lemon now deletes its output on failure.
Ryan C. Gordon <icculus@icculus.org>
parents: 809
diff changeset
    49
    int i;
7b3c3ae9e5a9 Lemon now deletes its output on failure.
Ryan C. Gordon <icculus@icculus.org>
parents: 809
diff changeset
    50
    for (i = 0; i < made_files_count; i++) {
7b3c3ae9e5a9 Lemon now deletes its output on failure.
Ryan C. Gordon <icculus@icculus.org>
parents: 809
diff changeset
    51
        if (status != 0) {
7b3c3ae9e5a9 Lemon now deletes its output on failure.
Ryan C. Gordon <icculus@icculus.org>
parents: 809
diff changeset
    52
            remove(made_files[i]);
7b3c3ae9e5a9 Lemon now deletes its output on failure.
Ryan C. Gordon <icculus@icculus.org>
parents: 809
diff changeset
    53
        }
7b3c3ae9e5a9 Lemon now deletes its output on failure.
Ryan C. Gordon <icculus@icculus.org>
parents: 809
diff changeset
    54
        free((void *) made_files[i]);
7b3c3ae9e5a9 Lemon now deletes its output on failure.
Ryan C. Gordon <icculus@icculus.org>
parents: 809
diff changeset
    55
    }
7b3c3ae9e5a9 Lemon now deletes its output on failure.
Ryan C. Gordon <icculus@icculus.org>
parents: 809
diff changeset
    56
    free(made_files);
7b3c3ae9e5a9 Lemon now deletes its output on failure.
Ryan C. Gordon <icculus@icculus.org>
parents: 809
diff changeset
    57
    made_files_count = 0;
7b3c3ae9e5a9 Lemon now deletes its output on failure.
Ryan C. Gordon <icculus@icculus.org>
parents: 809
diff changeset
    58
    made_files = NULL;
7b3c3ae9e5a9 Lemon now deletes its output on failure.
Ryan C. Gordon <icculus@icculus.org>
parents: 809
diff changeset
    59
    exit(status);
7b3c3ae9e5a9 Lemon now deletes its output on failure.
Ryan C. Gordon <icculus@icculus.org>
parents: 809
diff changeset
    60
}
7b3c3ae9e5a9 Lemon now deletes its output on failure.
Ryan C. Gordon <icculus@icculus.org>
parents: 809
diff changeset
    61
#define exit(x) lemon_exit(x)
7b3c3ae9e5a9 Lemon now deletes its output on failure.
Ryan C. Gordon <icculus@icculus.org>
parents: 809
diff changeset
    62
#endif
7b3c3ae9e5a9 Lemon now deletes its output on failure.
Ryan C. Gordon <icculus@icculus.org>
parents: 809
diff changeset
    63
708
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
    64
static char *msort(char*,char**,int(*)(const char*,const char*));
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
    65
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
    66
/*
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
    67
** Compilers are getting increasingly pedantic about type conversions
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
    68
** as C evolves ever closer to Ada....  To work around the latest problems
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
    69
** we have to define the following variant of strlen().
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
    70
*/
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
    71
#define lemonStrlen(X)   ((int)strlen(X))
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
    72
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
    73
static struct action *Action_new(void);
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
    74
static struct action *Action_sort(struct action *);
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
    75
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
    76
/********** From the file "build.h" ************************************/
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
    77
void FindRulePrecedences();
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
    78
void FindFirstSets();
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
    79
void FindStates();
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
    80
void FindLinks();
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
    81
void FindFollowSets();
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
    82
void FindActions();
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
    83
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
    84
/********* From the file "configlist.h" *********************************/
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
    85
void Configlist_init(/* void */);
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
    86
struct config *Configlist_add(/* struct rule *, int */);
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
    87
struct config *Configlist_addbasis(/* struct rule *, int */);
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
    88
void Configlist_closure(/* void */);
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
    89
void Configlist_sort(/* void */);
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
    90
void Configlist_sortbasis(/* void */);
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
    91
struct config *Configlist_return(/* void */);
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
    92
struct config *Configlist_basis(/* void */);
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
    93
void Configlist_eat(/* struct config * */);
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
    94
void Configlist_reset(/* void */);
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
    95
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
    96
/********* From the file "error.h" ***************************************/
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
    97
void ErrorMsg(const char *, int,const char *, ...);
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
    98
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
    99
/****** From the file "option.h" ******************************************/
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   100
struct s_options {
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   101
  enum { OPT_FLAG=1,  OPT_INT,  OPT_DBL,  OPT_STR,
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   102
         OPT_FFLAG, OPT_FINT, OPT_FDBL, OPT_FSTR} type;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   103
  char *label;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   104
  char *arg;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   105
  char *message;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   106
};
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   107
int    OptInit(/* char**,struct s_options*,FILE* */);
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   108
int    OptNArgs(/* void */);
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   109
char  *OptArg(/* int */);
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   110
void   OptErr(/* int */);
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   111
void   OptPrint(/* void */);
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   112
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   113
/******** From the file "parse.h" *****************************************/
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   114
void Parse(/* struct lemon *lemp */);
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   115
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   116
/********* From the file "plink.h" ***************************************/
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   117
struct plink *Plink_new(/* void */);
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   118
void Plink_add(/* struct plink **, struct config * */);
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   119
void Plink_copy(/* struct plink **, struct plink * */);
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   120
void Plink_delete(/* struct plink * */);
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   121
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   122
/********** From the file "report.h" *************************************/
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   123
void Reprint(/* struct lemon * */);
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   124
void ReportOutput(/* struct lemon * */);
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   125
void ReportTable(/* struct lemon * */);
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   126
void ReportHeader(/* struct lemon * */);
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   127
void CompressTables(/* struct lemon * */);
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   128
void ResortStates(/* struct lemon * */);
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   129
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   130
/********** From the file "set.h" ****************************************/
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   131
void  SetSize(/* int N */);             /* All sets will be of size N */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   132
char *SetNew(/* void */);               /* A new set for element 0..N */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   133
void  SetFree(/* char* */);             /* Deallocate a set */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   134
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   135
int SetAdd(/* char*,int */);            /* Add element to a set */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   136
int SetUnion(/* char *A,char *B */);    /* A <- A U B, thru element N */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   137
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   138
#define SetFind(X,Y) (X[Y])       /* True if Y is in set X */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   139
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   140
/********** From the file "struct.h" *************************************/
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   141
/*
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   142
** Principal data structures for the LEMON parser generator.
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   143
*/
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   144
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   145
typedef enum {LEMON_FALSE=0, LEMON_TRUE} Boolean;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   146
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   147
/* Symbols (terminals and nonterminals) of the grammar are stored
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   148
** in the following: */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   149
struct symbol {
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   150
  char *name;              /* Name of the symbol */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   151
  int index;               /* Index number for this symbol */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   152
  enum {
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   153
    TERMINAL,
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   154
    NONTERMINAL,
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   155
    MULTITERMINAL
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   156
  } type;                  /* Symbols are all either TERMINALS or NTs */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   157
  struct rule *rule;       /* Linked list of rules of this (if an NT) */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   158
  struct symbol *fallback; /* fallback token in case this token doesn't parse */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   159
  int prec;                /* Precedence if defined (-1 otherwise) */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   160
  enum e_assoc {
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   161
    LEFT,
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   162
    RIGHT,
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   163
    NONE,
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   164
    UNK
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   165
  } assoc;                 /* Associativity if precedence is defined */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   166
  char *firstset;          /* First-set for all rules of this symbol */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   167
  Boolean lambda;          /* True if NT and can generate an empty string */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   168
  int useCnt;              /* Number of times used */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   169
  char *destructor;        /* Code which executes whenever this symbol is
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   170
                           ** popped from the stack during error processing */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   171
  int destLineno;          /* Line number for start of destructor */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   172
  char *datatype;          /* The data type of information held by this
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   173
                           ** object. Only used if type==NONTERMINAL */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   174
  int dtnum;               /* The data type number.  In the parser, the value
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   175
                           ** stack is a union.  The .yy%d element of this
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   176
                           ** union is the correct data type for this object */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   177
  /* The following fields are used by MULTITERMINALs only */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   178
  int nsubsym;             /* Number of constituent symbols in the MULTI */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   179
  struct symbol **subsym;  /* Array of constituent symbols */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   180
};
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   181
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   182
/* Each production rule in the grammar is stored in the following
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   183
** structure.  */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   184
struct rule {
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   185
  struct symbol *lhs;      /* Left-hand side of the rule */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   186
  char *lhsalias;          /* Alias for the LHS (NULL if none) */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   187
  int lhsStart;            /* True if left-hand side is the start symbol */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   188
  int ruleline;            /* Line number for the rule */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   189
  int nrhs;                /* Number of RHS symbols */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   190
  struct symbol **rhs;     /* The RHS symbols */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   191
  char **rhsalias;         /* An alias for each RHS symbol (NULL if none) */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   192
  int line;                /* Line number at which code begins */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   193
  char *code;              /* The code executed when this rule is reduced */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   194
  struct symbol *precsym;  /* Precedence symbol for this rule */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   195
  int index;               /* An index number for this rule */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   196
  Boolean canReduce;       /* True if this rule is ever reduced */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   197
  struct rule *nextlhs;    /* Next rule with the same LHS */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   198
  struct rule *next;       /* Next rule in the global list */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   199
};
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   200
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   201
/* A configuration is a production rule of the grammar together with
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   202
** a mark (dot) showing how much of that rule has been processed so far.
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   203
** Configurations also contain a follow-set which is a list of terminal
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   204
** symbols which are allowed to immediately follow the end of the rule.
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   205
** Every configuration is recorded as an instance of the following: */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   206
struct config {
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   207
  struct rule *rp;         /* The rule upon which the configuration is based */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   208
  int dot;                 /* The parse point */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   209
  char *fws;               /* Follow-set for this configuration only */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   210
  struct plink *fplp;      /* Follow-set forward propagation links */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   211
  struct plink *bplp;      /* Follow-set backwards propagation links */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   212
  struct state *stp;       /* Pointer to state which contains this */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   213
  enum {
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   214
    COMPLETE,              /* The status is used during followset and */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   215
    INCOMPLETE             /*    shift computations */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   216
  } status;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   217
  struct config *next;     /* Next configuration in the state */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   218
  struct config *bp;       /* The next basis configuration */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   219
};
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   220
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   221
/* Every shift or reduce operation is stored as one of the following */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   222
struct action {
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   223
  struct symbol *sp;       /* The look-ahead symbol */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   224
  enum e_action {
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   225
    SHIFT,
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   226
    ACCEPT,
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   227
    REDUCE,
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   228
    ERROR,
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   229
    SSCONFLICT,              /* A shift/shift conflict */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   230
    SRCONFLICT,              /* Was a reduce, but part of a conflict */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   231
    RRCONFLICT,              /* Was a reduce, but part of a conflict */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   232
    SH_RESOLVED,             /* Was a shift.  Precedence resolved conflict */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   233
    RD_RESOLVED,             /* Was reduce.  Precedence resolved conflict */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   234
    NOT_USED                 /* Deleted by compression */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   235
  } type;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   236
  union {
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   237
    struct state *stp;     /* The new state, if a shift */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   238
    struct rule *rp;       /* The rule, if a reduce */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   239
  } x;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   240
  struct action *next;     /* Next action for this state */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   241
  struct action *collide;  /* Next action with the same hash */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   242
};
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   243
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   244
/* Each state of the generated parser's finite state machine
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   245
** is encoded as an instance of the following structure. */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   246
struct state {
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   247
  struct config *bp;       /* The basis configurations for this state */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   248
  struct config *cfp;      /* All configurations in this set */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   249
  int statenum;            /* Sequential number for this state */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   250
  struct action *ap;       /* Array of actions for this state */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   251
  int nTknAct, nNtAct;     /* Number of actions on terminals and nonterminals */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   252
  int iTknOfst, iNtOfst;   /* yy_action[] offset for terminals and nonterms */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   253
  int iDflt;               /* Default action */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   254
};
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   255
#define NO_OFFSET (-2147483647)
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   256
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   257
/* A followset propagation link indicates that the contents of one
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   258
** configuration followset should be propagated to another whenever
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   259
** the first changes. */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   260
struct plink {
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   261
  struct config *cfp;      /* The configuration to which linked */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   262
  struct plink *next;      /* The next propagate link */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   263
};
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   264
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   265
/* The state vector for the entire parser generator is recorded as
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   266
** follows.  (LEMON uses no global variables and makes little use of
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   267
** static variables.  Fields in the following structure can be thought
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   268
** of as begin global variables in the program.) */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   269
struct lemon {
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   270
  struct state **sorted;   /* Table of states sorted by state number */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   271
  struct rule *rule;       /* List of all rules */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   272
  int nstate;              /* Number of states */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   273
  int nrule;               /* Number of rules */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   274
  int nsymbol;             /* Number of terminal and nonterminal symbols */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   275
  int nterminal;           /* Number of terminal symbols */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   276
  struct symbol **symbols; /* Sorted array of pointers to symbols */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   277
  int errorcnt;            /* Number of errors */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   278
  struct symbol *errsym;   /* The error symbol */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   279
  struct symbol *wildcard; /* Token that matches anything */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   280
  char *name;              /* Name of the generated parser */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   281
  char *arg;               /* Declaration of the 3th argument to parser */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   282
  char *tokentype;         /* Type of terminal symbols in the parser stack */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   283
  char *vartype;           /* The default type of non-terminal symbols */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   284
  char *start;             /* Name of the start symbol for the grammar */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   285
  char *stacksize;         /* Size of the parser stack */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   286
  char *include;           /* Code to put at the start of the C file */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   287
  char *error;             /* Code to execute when an error is seen */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   288
  char *overflow;          /* Code to execute on a stack overflow */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   289
  char *failure;           /* Code to execute on parser failure */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   290
  char *accept;            /* Code to execute when the parser excepts */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   291
  char *extracode;         /* Code appended to the generated file */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   292
  char *tokendest;         /* Code to execute to destroy token data */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   293
  char *vardest;           /* Code for the default non-terminal destructor */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   294
  char *filename;          /* Name of the input file */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   295
  char *outname;           /* Name of the current output file */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   296
  char *tokenprefix;       /* A prefix added to token names in the .h file */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   297
  int nconflict;           /* Number of parsing conflicts */
809
d0fcadcc93b4 Forgot to wrap this in a #if __MOJOSHADER__.
Ryan C. Gordon <icculus@icculus.org>
parents: 786
diff changeset
   298
#if __MOJOSHADER__
786
795e7762da7f Modified Lemon to accept a specific amount of conflicts.
Ryan C. Gordon <icculus@icculus.org>
parents: 714
diff changeset
   299
  int nexpected;           /* Number of expected parsing conflicts */
809
d0fcadcc93b4 Forgot to wrap this in a #if __MOJOSHADER__.
Ryan C. Gordon <icculus@icculus.org>
parents: 786
diff changeset
   300
#endif
708
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   301
  int tablesize;           /* Size of the parse tables */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   302
  int basisflag;           /* Print only basis configurations */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   303
  int has_fallback;        /* True if any %fallback is seen in the grammar */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   304
  int nolinenosflag;       /* True if #line statements should not be printed */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   305
  char *argv0;             /* Name of the program */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   306
};
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   307
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   308
#define MemoryCheck(X) if((X)==0){ \
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   309
  extern void memory_error(); \
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   310
  memory_error(); \
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   311
}
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   312
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   313
/**************** From the file "table.h" *********************************/
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   314
/*
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   315
** All code in this file has been automatically generated
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   316
** from a specification in the file
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   317
**              "table.q"
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   318
** by the associative array code building program "aagen".
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   319
** Do not edit this file!  Instead, edit the specification
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   320
** file, then rerun aagen.
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   321
*/
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   322
/*
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   323
** Code for processing tables in the LEMON parser generator.
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   324
*/
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   325
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   326
/* Routines for handling a strings */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   327
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   328
char *Strsafe();
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   329
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   330
void Strsafe_init(/* void */);
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   331
int Strsafe_insert(/* char * */);
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   332
char *Strsafe_find(/* char * */);
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   333
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   334
/* Routines for handling symbols of the grammar */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   335
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   336
struct symbol *Symbol_new();
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   337
int Symbolcmpp(/* struct symbol **, struct symbol ** */);
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   338
void Symbol_init(/* void */);
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   339
int Symbol_insert(/* struct symbol *, char * */);
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   340
struct symbol *Symbol_find(/* char * */);
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   341
struct symbol *Symbol_Nth(/* int */);
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   342
int Symbol_count(/*  */);
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   343
struct symbol **Symbol_arrayof(/*  */);
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   344
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   345
/* Routines to manage the state table */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   346
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   347
int Configcmp(/* struct config *, struct config * */);
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   348
struct state *State_new();
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   349
void State_init(/* void */);
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   350
int State_insert(/* struct state *, struct config * */);
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   351
struct state *State_find(/* struct config * */);
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   352
struct state **State_arrayof(/*  */);
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   353
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   354
/* Routines used for efficiency in Configlist_add */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   355
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   356
void Configtable_init(/* void */);
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   357
int Configtable_insert(/* struct config * */);
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   358
struct config *Configtable_find(/* struct config * */);
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   359
void Configtable_clear(/* int(*)(struct config *) */);
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   360
/****************** From the file "action.c" *******************************/
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   361
/*
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   362
** Routines processing parser actions in the LEMON parser generator.
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   363
*/
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   364
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   365
/* Allocate a new parser action */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   366
static struct action *Action_new(void){
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   367
  static struct action *freelist = 0;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   368
  struct action *new;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   369
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   370
  if( freelist==0 ){
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   371
    int i;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   372
    int amt = 100;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   373
    freelist = (struct action *)calloc(amt, sizeof(struct action));
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   374
    if( freelist==0 ){
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   375
      fprintf(stderr,"Unable to allocate memory for a new parser action.");
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   376
      exit(1);
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   377
    }
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   378
    for(i=0; i<amt-1; i++) freelist[i].next = &freelist[i+1];
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   379
    freelist[amt-1].next = 0;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   380
  }
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   381
  new = freelist;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   382
  freelist = freelist->next;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   383
  return new;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   384
}
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   385
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   386
/* Compare two actions for sorting purposes.  Return negative, zero, or
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   387
** positive if the first action is less than, equal to, or greater than
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   388
** the first
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   389
*/
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   390
static int actioncmp(
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   391
  struct action *ap1,
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   392
  struct action *ap2
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   393
){
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   394
  int rc;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   395
  rc = ap1->sp->index - ap2->sp->index;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   396
  if( rc==0 ){
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   397
    rc = (int)ap1->type - (int)ap2->type;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   398
  }
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   399
  if( rc==0 && ap1->type==REDUCE ){
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   400
    rc = ap1->x.rp->index - ap2->x.rp->index;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   401
  }
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   402
  return rc;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   403
}
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   404
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   405
/* Sort parser actions */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   406
static struct action *Action_sort(
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   407
  struct action *ap
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   408
){
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   409
  ap = (struct action *)msort((char *)ap,(char **)&ap->next,
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   410
                              (int(*)(const char*,const char*))actioncmp);
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   411
  return ap;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   412
}
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   413
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   414
void Action_add(app,type,sp,arg)
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   415
struct action **app;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   416
enum e_action type;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   417
struct symbol *sp;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   418
char *arg;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   419
{
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   420
  struct action *new;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   421
  new = Action_new();
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   422
  new->next = *app;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   423
  *app = new;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   424
  new->type = type;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   425
  new->sp = sp;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   426
  if( type==SHIFT ){
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   427
    new->x.stp = (struct state *)arg;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   428
  }else{
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   429
    new->x.rp = (struct rule *)arg;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   430
  }
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   431
}
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   432
/********************** New code to implement the "acttab" module ***********/
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   433
/*
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   434
** This module implements routines use to construct the yy_action[] table.
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   435
*/
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   436
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   437
/*
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   438
** The state of the yy_action table under construction is an instance of
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   439
** the following structure
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   440
*/
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   441
typedef struct acttab acttab;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   442
struct acttab {
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   443
  int nAction;                 /* Number of used slots in aAction[] */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   444
  int nActionAlloc;            /* Slots allocated for aAction[] */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   445
  struct {
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   446
    int lookahead;             /* Value of the lookahead token */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   447
    int action;                /* Action to take on the given lookahead */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   448
  } *aAction,                  /* The yy_action[] table under construction */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   449
    *aLookahead;               /* A single new transaction set */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   450
  int mnLookahead;             /* Minimum aLookahead[].lookahead */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   451
  int mnAction;                /* Action associated with mnLookahead */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   452
  int mxLookahead;             /* Maximum aLookahead[].lookahead */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   453
  int nLookahead;              /* Used slots in aLookahead[] */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   454
  int nLookaheadAlloc;         /* Slots allocated in aLookahead[] */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   455
};
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   456
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   457
/* Return the number of entries in the yy_action table */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   458
#define acttab_size(X) ((X)->nAction)
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   459
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   460
/* The value for the N-th entry in yy_action */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   461
#define acttab_yyaction(X,N)  ((X)->aAction[N].action)
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   462
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   463
/* The value for the N-th entry in yy_lookahead */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   464
#define acttab_yylookahead(X,N)  ((X)->aAction[N].lookahead)
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   465
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   466
/* Free all memory associated with the given acttab */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   467
void acttab_free(acttab *p){
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   468
  free( p->aAction );
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   469
  free( p->aLookahead );
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   470
  free( p );
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   471
}
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   472
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   473
/* Allocate a new acttab structure */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   474
acttab *acttab_alloc(void){
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   475
  acttab *p = calloc( 1, sizeof(*p) );
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   476
  if( p==0 ){
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   477
    fprintf(stderr,"Unable to allocate memory for a new acttab.");
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   478
    exit(1);
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   479
  }
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   480
  memset(p, 0, sizeof(*p));
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   481
  return p;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   482
}
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   483
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   484
/* Add a new action to the current transaction set
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   485
*/
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   486
void acttab_action(acttab *p, int lookahead, int action){
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   487
  if( p->nLookahead>=p->nLookaheadAlloc ){
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   488
    p->nLookaheadAlloc += 25;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   489
    p->aLookahead = realloc( p->aLookahead,
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   490
                             sizeof(p->aLookahead[0])*p->nLookaheadAlloc );
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   491
    if( p->aLookahead==0 ){
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   492
      fprintf(stderr,"malloc failed\n");
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   493
      exit(1);
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   494
    }
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   495
  }
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   496
  if( p->nLookahead==0 ){
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   497
    p->mxLookahead = lookahead;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   498
    p->mnLookahead = lookahead;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   499
    p->mnAction = action;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   500
  }else{
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   501
    if( p->mxLookahead<lookahead ) p->mxLookahead = lookahead;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   502
    if( p->mnLookahead>lookahead ){
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   503
      p->mnLookahead = lookahead;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   504
      p->mnAction = action;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   505
    }
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   506
  }
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   507
  p->aLookahead[p->nLookahead].lookahead = lookahead;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   508
  p->aLookahead[p->nLookahead].action = action;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   509
  p->nLookahead++;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   510
}
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   511
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   512
/*
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   513
** Add the transaction set built up with prior calls to acttab_action()
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   514
** into the current action table.  Then reset the transaction set back
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   515
** to an empty set in preparation for a new round of acttab_action() calls.
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   516
**
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   517
** Return the offset into the action table of the new transaction.
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   518
*/
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   519
int acttab_insert(acttab *p){
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   520
  int i, j, k, n;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   521
  assert( p->nLookahead>0 );
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   522
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   523
  /* Make sure we have enough space to hold the expanded action table
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   524
  ** in the worst case.  The worst case occurs if the transaction set
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   525
  ** must be appended to the current action table
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   526
  */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   527
  n = p->mxLookahead + 1;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   528
  if( p->nAction + n >= p->nActionAlloc ){
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   529
    int oldAlloc = p->nActionAlloc;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   530
    p->nActionAlloc = p->nAction + n + p->nActionAlloc + 20;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   531
    p->aAction = realloc( p->aAction,
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   532
                          sizeof(p->aAction[0])*p->nActionAlloc);
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   533
    if( p->aAction==0 ){
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   534
      fprintf(stderr,"malloc failed\n");
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   535
      exit(1);
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   536
    }
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   537
    for(i=oldAlloc; i<p->nActionAlloc; i++){
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   538
      p->aAction[i].lookahead = -1;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   539
      p->aAction[i].action = -1;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   540
    }
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   541
  }
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   542
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   543
  /* Scan the existing action table looking for an offset where we can
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   544
  ** insert the current transaction set.  Fall out of the loop when that
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   545
  ** offset is found.  In the worst case, we fall out of the loop when
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   546
  ** i reaches p->nAction, which means we append the new transaction set.
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   547
  **
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   548
  ** i is the index in p->aAction[] where p->mnLookahead is inserted.
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   549
  */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   550
  for(i=0; i<p->nAction+p->mnLookahead; i++){
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   551
    if( p->aAction[i].lookahead<0 ){
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   552
      for(j=0; j<p->nLookahead; j++){
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   553
        k = p->aLookahead[j].lookahead - p->mnLookahead + i;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   554
        if( k<0 ) break;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   555
        if( p->aAction[k].lookahead>=0 ) break;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   556
      }
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   557
      if( j<p->nLookahead ) continue;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   558
      for(j=0; j<p->nAction; j++){
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   559
        if( p->aAction[j].lookahead==j+p->mnLookahead-i ) break;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   560
      }
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   561
      if( j==p->nAction ){
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   562
        break;  /* Fits in empty slots */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   563
      }
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   564
    }else if( p->aAction[i].lookahead==p->mnLookahead ){
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   565
      if( p->aAction[i].action!=p->mnAction ) continue;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   566
      for(j=0; j<p->nLookahead; j++){
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   567
        k = p->aLookahead[j].lookahead - p->mnLookahead + i;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   568
        if( k<0 || k>=p->nAction ) break;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   569
        if( p->aLookahead[j].lookahead!=p->aAction[k].lookahead ) break;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   570
        if( p->aLookahead[j].action!=p->aAction[k].action ) break;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   571
      }
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   572
      if( j<p->nLookahead ) continue;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   573
      n = 0;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   574
      for(j=0; j<p->nAction; j++){
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   575
        if( p->aAction[j].lookahead<0 ) continue;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   576
        if( p->aAction[j].lookahead==j+p->mnLookahead-i ) n++;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   577
      }
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   578
      if( n==p->nLookahead ){
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   579
        break;  /* Same as a prior transaction set */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   580
      }
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   581
    }
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   582
  }
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   583
  /* Insert transaction set at index i. */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   584
  for(j=0; j<p->nLookahead; j++){
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   585
    k = p->aLookahead[j].lookahead - p->mnLookahead + i;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   586
    p->aAction[k] = p->aLookahead[j];
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   587
    if( k>=p->nAction ) p->nAction = k+1;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   588
  }
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   589
  p->nLookahead = 0;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   590
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   591
  /* Return the offset that is added to the lookahead in order to get the
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   592
  ** index into yy_action of the action */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   593
  return i - p->mnLookahead;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   594
}
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   595
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   596
/********************** From the file "build.c" *****************************/
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   597
/*
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   598
** Routines to construction the finite state machine for the LEMON
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   599
** parser generator.
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   600
*/
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   601
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   602
/* Find a precedence symbol of every rule in the grammar.
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   603
** 
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   604
** Those rules which have a precedence symbol coded in the input
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   605
** grammar using the "[symbol]" construct will already have the
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   606
** rp->precsym field filled.  Other rules take as their precedence
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   607
** symbol the first RHS symbol with a defined precedence.  If there
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   608
** are not RHS symbols with a defined precedence, the precedence
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   609
** symbol field is left blank.
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   610
*/
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   611
void FindRulePrecedences(xp)
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   612
struct lemon *xp;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   613
{
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   614
  struct rule *rp;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   615
  for(rp=xp->rule; rp; rp=rp->next){
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   616
    if( rp->precsym==0 ){
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   617
      int i, j;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   618
      for(i=0; i<rp->nrhs && rp->precsym==0; i++){
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   619
        struct symbol *sp = rp->rhs[i];
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   620
        if( sp->type==MULTITERMINAL ){
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   621
          for(j=0; j<sp->nsubsym; j++){
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   622
            if( sp->subsym[j]->prec>=0 ){
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   623
              rp->precsym = sp->subsym[j];
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   624
              break;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   625
            }
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   626
          }
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   627
        }else if( sp->prec>=0 ){
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   628
          rp->precsym = rp->rhs[i];
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   629
	}
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   630
      }
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   631
    }
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   632
  }
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   633
  return;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   634
}
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   635
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   636
/* Find all nonterminals which will generate the empty string.
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   637
** Then go back and compute the first sets of every nonterminal.
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   638
** The first set is the set of all terminal symbols which can begin
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   639
** a string generated by that nonterminal.
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   640
*/
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   641
void FindFirstSets(lemp)
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   642
struct lemon *lemp;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   643
{
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   644
  int i, j;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   645
  struct rule *rp;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   646
  int progress;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   647
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   648
  for(i=0; i<lemp->nsymbol; i++){
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   649
    lemp->symbols[i]->lambda = LEMON_FALSE;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   650
  }
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   651
  for(i=lemp->nterminal; i<lemp->nsymbol; i++){
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   652
    lemp->symbols[i]->firstset = SetNew();
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   653
  }
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   654
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   655
  /* First compute all lambdas */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   656
  do{
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   657
    progress = 0;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   658
    for(rp=lemp->rule; rp; rp=rp->next){
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   659
      if( rp->lhs->lambda ) continue;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   660
      for(i=0; i<rp->nrhs; i++){
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   661
         struct symbol *sp = rp->rhs[i];
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   662
         if( sp->type!=TERMINAL || sp->lambda==LEMON_FALSE ) break;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   663
      }
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   664
      if( i==rp->nrhs ){
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   665
        rp->lhs->lambda = LEMON_TRUE;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   666
        progress = 1;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   667
      }
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   668
    }
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   669
  }while( progress );
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   670
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   671
  /* Now compute all first sets */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   672
  do{
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   673
    struct symbol *s1, *s2;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   674
    progress = 0;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   675
    for(rp=lemp->rule; rp; rp=rp->next){
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   676
      s1 = rp->lhs;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   677
      for(i=0; i<rp->nrhs; i++){
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   678
        s2 = rp->rhs[i];
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   679
        if( s2->type==TERMINAL ){
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   680
          progress += SetAdd(s1->firstset,s2->index);
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   681
          break;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   682
        }else if( s2->type==MULTITERMINAL ){
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   683
          for(j=0; j<s2->nsubsym; j++){
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   684
            progress += SetAdd(s1->firstset,s2->subsym[j]->index);
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   685
          }
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   686
          break;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   687
	}else if( s1==s2 ){
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   688
          if( s1->lambda==LEMON_FALSE ) break;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   689
	}else{
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   690
          progress += SetUnion(s1->firstset,s2->firstset);
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   691
          if( s2->lambda==LEMON_FALSE ) break;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   692
	}
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   693
      }
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   694
    }
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   695
  }while( progress );
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   696
  return;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   697
}
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   698
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   699
/* Compute all LR(0) states for the grammar.  Links
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   700
** are added to between some states so that the LR(1) follow sets
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   701
** can be computed later.
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   702
*/
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   703
PRIVATE struct state *getstate(/* struct lemon * */);  /* forward reference */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   704
void FindStates(lemp)
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   705
struct lemon *lemp;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   706
{
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   707
  struct symbol *sp;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   708
  struct rule *rp;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   709
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   710
  Configlist_init();
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   711
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   712
  /* Find the start symbol */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   713
  if( lemp->start ){
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   714
    sp = Symbol_find(lemp->start);
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   715
    if( sp==0 ){
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   716
      ErrorMsg(lemp->filename,0,
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   717
"The specified start symbol \"%s\" is not \
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   718
in a nonterminal of the grammar.  \"%s\" will be used as the start \
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   719
symbol instead.",lemp->start,lemp->rule->lhs->name);
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   720
      lemp->errorcnt++;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   721
      sp = lemp->rule->lhs;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   722
    }
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   723
  }else{
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   724
    sp = lemp->rule->lhs;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   725
  }
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   726
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   727
  /* Make sure the start symbol doesn't occur on the right-hand side of
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   728
  ** any rule.  Report an error if it does.  (YACC would generate a new
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   729
  ** start symbol in this case.) */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   730
  for(rp=lemp->rule; rp; rp=rp->next){
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   731
    int i;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   732
    for(i=0; i<rp->nrhs; i++){
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   733
      if( rp->rhs[i]==sp ){   /* FIX ME:  Deal with multiterminals */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   734
        ErrorMsg(lemp->filename,0,
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   735
"The start symbol \"%s\" occurs on the \
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   736
right-hand side of a rule. This will result in a parser which \
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   737
does not work properly.",sp->name);
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   738
        lemp->errorcnt++;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   739
      }
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   740
    }
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   741
  }
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   742
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   743
  /* The basis configuration set for the first state
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   744
  ** is all rules which have the start symbol as their
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   745
  ** left-hand side */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   746
  for(rp=sp->rule; rp; rp=rp->nextlhs){
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   747
    struct config *newcfp;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   748
    rp->lhsStart = 1;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   749
    newcfp = Configlist_addbasis(rp,0);
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   750
    SetAdd(newcfp->fws,0);
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   751
  }
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   752
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   753
  /* Compute the first state.  All other states will be
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   754
  ** computed automatically during the computation of the first one.
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   755
  ** The returned pointer to the first state is not used. */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   756
  (void)getstate(lemp);
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   757
  return;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   758
}
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   759
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   760
/* Return a pointer to a state which is described by the configuration
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   761
** list which has been built from calls to Configlist_add.
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   762
*/
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   763
PRIVATE void buildshifts(/* struct lemon *, struct state * */); /* Forwd ref */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   764
PRIVATE struct state *getstate(lemp)
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   765
struct lemon *lemp;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   766
{
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   767
  struct config *cfp, *bp;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   768
  struct state *stp;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   769
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   770
  /* Extract the sorted basis of the new state.  The basis was constructed
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   771
  ** by prior calls to "Configlist_addbasis()". */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   772
  Configlist_sortbasis();
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   773
  bp = Configlist_basis();
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   774
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   775
  /* Get a state with the same basis */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   776
  stp = State_find(bp);
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   777
  if( stp ){
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   778
    /* A state with the same basis already exists!  Copy all the follow-set
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   779
    ** propagation links from the state under construction into the
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   780
    ** preexisting state, then return a pointer to the preexisting state */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   781
    struct config *x, *y;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   782
    for(x=bp, y=stp->bp; x && y; x=x->bp, y=y->bp){
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   783
      Plink_copy(&y->bplp,x->bplp);
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   784
      Plink_delete(x->fplp);
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   785
      x->fplp = x->bplp = 0;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   786
    }
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   787
    cfp = Configlist_return();
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   788
    Configlist_eat(cfp);
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   789
  }else{
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   790
    /* This really is a new state.  Construct all the details */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   791
    Configlist_closure(lemp);    /* Compute the configuration closure */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   792
    Configlist_sort();           /* Sort the configuration closure */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   793
    cfp = Configlist_return();   /* Get a pointer to the config list */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   794
    stp = State_new();           /* A new state structure */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   795
    MemoryCheck(stp);
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   796
    stp->bp = bp;                /* Remember the configuration basis */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   797
    stp->cfp = cfp;              /* Remember the configuration closure */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   798
    stp->statenum = lemp->nstate++; /* Every state gets a sequence number */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   799
    stp->ap = 0;                 /* No actions, yet. */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   800
    State_insert(stp,stp->bp);   /* Add to the state table */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   801
    buildshifts(lemp,stp);       /* Recursively compute successor states */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   802
  }
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   803
  return stp;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   804
}
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   805
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   806
/*
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   807
** Return true if two symbols are the same.
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   808
*/
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   809
int same_symbol(a,b)
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   810
struct symbol *a;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   811
struct symbol *b;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   812
{
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   813
  int i;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   814
  if( a==b ) return 1;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   815
  if( a->type!=MULTITERMINAL ) return 0;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   816
  if( b->type!=MULTITERMINAL ) return 0;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   817
  if( a->nsubsym!=b->nsubsym ) return 0;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   818
  for(i=0; i<a->nsubsym; i++){
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   819
    if( a->subsym[i]!=b->subsym[i] ) return 0;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   820
  }
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   821
  return 1;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   822
}
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   823
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   824
/* Construct all successor states to the given state.  A "successor"
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   825
** state is any state which can be reached by a shift action.
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   826
*/
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   827
PRIVATE void buildshifts(lemp,stp)
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   828
struct lemon *lemp;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   829
struct state *stp;     /* The state from which successors are computed */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   830
{
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   831
  struct config *cfp;  /* For looping thru the config closure of "stp" */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   832
  struct config *bcfp; /* For the inner loop on config closure of "stp" */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   833
  struct config *new;  /* */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   834
  struct symbol *sp;   /* Symbol following the dot in configuration "cfp" */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   835
  struct symbol *bsp;  /* Symbol following the dot in configuration "bcfp" */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   836
  struct state *newstp; /* A pointer to a successor state */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   837
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   838
  /* Each configuration becomes complete after it contibutes to a successor
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   839
  ** state.  Initially, all configurations are incomplete */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   840
  for(cfp=stp->cfp; cfp; cfp=cfp->next) cfp->status = INCOMPLETE;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   841
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   842
  /* Loop through all configurations of the state "stp" */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   843
  for(cfp=stp->cfp; cfp; cfp=cfp->next){
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   844
    if( cfp->status==COMPLETE ) continue;    /* Already used by inner loop */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   845
    if( cfp->dot>=cfp->rp->nrhs ) continue;  /* Can't shift this config */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   846
    Configlist_reset();                      /* Reset the new config set */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   847
    sp = cfp->rp->rhs[cfp->dot];             /* Symbol after the dot */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   848
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   849
    /* For every configuration in the state "stp" which has the symbol "sp"
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   850
    ** following its dot, add the same configuration to the basis set under
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   851
    ** construction but with the dot shifted one symbol to the right. */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   852
    for(bcfp=cfp; bcfp; bcfp=bcfp->next){
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   853
      if( bcfp->status==COMPLETE ) continue;    /* Already used */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   854
      if( bcfp->dot>=bcfp->rp->nrhs ) continue; /* Can't shift this one */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   855
      bsp = bcfp->rp->rhs[bcfp->dot];           /* Get symbol after dot */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   856
      if( !same_symbol(bsp,sp) ) continue;      /* Must be same as for "cfp" */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   857
      bcfp->status = COMPLETE;                  /* Mark this config as used */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   858
      new = Configlist_addbasis(bcfp->rp,bcfp->dot+1);
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   859
      Plink_add(&new->bplp,bcfp);
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   860
    }
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   861
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   862
    /* Get a pointer to the state described by the basis configuration set
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   863
    ** constructed in the preceding loop */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   864
    newstp = getstate(lemp);
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   865
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   866
    /* The state "newstp" is reached from the state "stp" by a shift action
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   867
    ** on the symbol "sp" */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   868
    if( sp->type==MULTITERMINAL ){
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   869
      int i;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   870
      for(i=0; i<sp->nsubsym; i++){
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   871
        Action_add(&stp->ap,SHIFT,sp->subsym[i],(char*)newstp);
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   872
      }
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   873
    }else{
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   874
      Action_add(&stp->ap,SHIFT,sp,(char *)newstp);
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   875
    }
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   876
  }
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   877
}
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   878
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   879
/*
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   880
** Construct the propagation links
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   881
*/
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   882
void FindLinks(lemp)
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   883
struct lemon *lemp;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   884
{
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   885
  int i;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   886
  struct config *cfp, *other;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   887
  struct state *stp;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   888
  struct plink *plp;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   889
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   890
  /* Housekeeping detail:
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   891
  ** Add to every propagate link a pointer back to the state to
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   892
  ** which the link is attached. */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   893
  for(i=0; i<lemp->nstate; i++){
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   894
    stp = lemp->sorted[i];
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   895
    for(cfp=stp->cfp; cfp; cfp=cfp->next){
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   896
      cfp->stp = stp;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   897
    }
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   898
  }
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   899
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   900
  /* Convert all backlinks into forward links.  Only the forward
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   901
  ** links are used in the follow-set computation. */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   902
  for(i=0; i<lemp->nstate; i++){
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   903
    stp = lemp->sorted[i];
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   904
    for(cfp=stp->cfp; cfp; cfp=cfp->next){
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   905
      for(plp=cfp->bplp; plp; plp=plp->next){
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   906
        other = plp->cfp;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   907
        Plink_add(&other->fplp,cfp);
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   908
      }
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   909
    }
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   910
  }
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   911
}
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   912
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   913
/* Compute all followsets.
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   914
**
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   915
** A followset is the set of all symbols which can come immediately
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   916
** after a configuration.
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   917
*/
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   918
void FindFollowSets(lemp)
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   919
struct lemon *lemp;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   920
{
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   921
  int i;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   922
  struct config *cfp;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   923
  struct plink *plp;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   924
  int progress;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   925
  int change;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   926
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   927
  for(i=0; i<lemp->nstate; i++){
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   928
    for(cfp=lemp->sorted[i]->cfp; cfp; cfp=cfp->next){
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   929
      cfp->status = INCOMPLETE;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   930
    }
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   931
  }
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   932
  
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   933
  do{
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   934
    progress = 0;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   935
    for(i=0; i<lemp->nstate; i++){
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   936
      for(cfp=lemp->sorted[i]->cfp; cfp; cfp=cfp->next){
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   937
        if( cfp->status==COMPLETE ) continue;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   938
        for(plp=cfp->fplp; plp; plp=plp->next){
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   939
          change = SetUnion(plp->cfp->fws,cfp->fws);
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   940
          if( change ){
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   941
            plp->cfp->status = INCOMPLETE;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   942
            progress = 1;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   943
	  }
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   944
	}
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   945
        cfp->status = COMPLETE;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   946
      }
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   947
    }
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   948
  }while( progress );
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   949
}
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   950
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   951
static int resolve_conflict();
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   952
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   953
/* Compute the reduce actions, and resolve conflicts.
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   954
*/
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   955
void FindActions(lemp)
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   956
struct lemon *lemp;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   957
{
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   958
  int i,j;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   959
  struct config *cfp;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   960
  struct state *stp;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   961
  struct symbol *sp;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   962
  struct rule *rp;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   963
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   964
  /* Add all of the reduce actions 
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   965
  ** A reduce action is added for each element of the followset of
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   966
  ** a configuration which has its dot at the extreme right.
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   967
  */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   968
  for(i=0; i<lemp->nstate; i++){   /* Loop over all states */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   969
    stp = lemp->sorted[i];
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   970
    for(cfp=stp->cfp; cfp; cfp=cfp->next){  /* Loop over all configurations */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   971
      if( cfp->rp->nrhs==cfp->dot ){        /* Is dot at extreme right? */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   972
        for(j=0; j<lemp->nterminal; j++){
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   973
          if( SetFind(cfp->fws,j) ){
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   974
            /* Add a reduce action to the state "stp" which will reduce by the
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   975
            ** rule "cfp->rp" if the lookahead symbol is "lemp->symbols[j]" */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   976
            Action_add(&stp->ap,REDUCE,lemp->symbols[j],(char *)cfp->rp);
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   977
          }
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   978
	}
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   979
      }
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   980
    }
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   981
  }
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   982
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   983
  /* Add the accepting token */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   984
  if( lemp->start ){
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   985
    sp = Symbol_find(lemp->start);
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   986
    if( sp==0 ) sp = lemp->rule->lhs;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   987
  }else{
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   988
    sp = lemp->rule->lhs;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   989
  }
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   990
  /* Add to the first state (which is always the starting state of the
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   991
  ** finite state machine) an action to ACCEPT if the lookahead is the
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   992
  ** start nonterminal.  */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   993
  Action_add(&lemp->sorted[0]->ap,ACCEPT,sp,0);
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   994
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   995
  /* Resolve conflicts */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   996
  for(i=0; i<lemp->nstate; i++){
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   997
    struct action *ap, *nap;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   998
    struct state *stp;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
   999
    stp = lemp->sorted[i];
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1000
    /* assert( stp->ap ); */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1001
    stp->ap = Action_sort(stp->ap);
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1002
    for(ap=stp->ap; ap && ap->next; ap=ap->next){
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1003
      for(nap=ap->next; nap && nap->sp==ap->sp; nap=nap->next){
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1004
         /* The two actions "ap" and "nap" have the same lookahead.
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1005
         ** Figure out which one should be used */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1006
         lemp->nconflict += resolve_conflict(ap,nap,lemp->errsym);
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1007
      }
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1008
    }
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1009
  }
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1010
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1011
  /* Report an error for each rule that can never be reduced. */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1012
  for(rp=lemp->rule; rp; rp=rp->next) rp->canReduce = LEMON_FALSE;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1013
  for(i=0; i<lemp->nstate; i++){
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1014
    struct action *ap;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1015
    for(ap=lemp->sorted[i]->ap; ap; ap=ap->next){
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1016
      if( ap->type==REDUCE ) ap->x.rp->canReduce = LEMON_TRUE;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1017
    }
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1018
  }
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1019
  for(rp=lemp->rule; rp; rp=rp->next){
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1020
    if( rp->canReduce ) continue;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1021
    ErrorMsg(lemp->filename,rp->ruleline,"This rule can not be reduced.\n");
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1022
    lemp->errorcnt++;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1023
  }
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1024
}
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1025
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1026
/* Resolve a conflict between the two given actions.  If the
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1027
** conflict can't be resolved, return non-zero.
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1028
**
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1029
** NO LONGER TRUE:
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1030
**   To resolve a conflict, first look to see if either action
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1031
**   is on an error rule.  In that case, take the action which
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1032
**   is not associated with the error rule.  If neither or both
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1033
**   actions are associated with an error rule, then try to
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1034
**   use precedence to resolve the conflict.
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1035
**
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1036
** If either action is a SHIFT, then it must be apx.  This
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1037
** function won't work if apx->type==REDUCE and apy->type==SHIFT.
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1038
*/
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1039
static int resolve_conflict(apx,apy,errsym)
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1040
struct action *apx;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1041
struct action *apy;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1042
struct symbol *errsym;   /* The error symbol (if defined.  NULL otherwise) */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1043
{
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1044
  struct symbol *spx, *spy;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1045
  int errcnt = 0;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1046
  assert( apx->sp==apy->sp );  /* Otherwise there would be no conflict */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1047
  if( apx->type==SHIFT && apy->type==SHIFT ){
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1048
    apy->type = SSCONFLICT;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1049
    errcnt++;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1050
  }
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1051
  if( apx->type==SHIFT && apy->type==REDUCE ){
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1052
    spx = apx->sp;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1053
    spy = apy->x.rp->precsym;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1054
    if( spy==0 || spx->prec<0 || spy->prec<0 ){
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1055
      /* Not enough precedence information. */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1056
      apy->type = SRCONFLICT;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1057
      errcnt++;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1058
    }else if( spx->prec>spy->prec ){    /* Lower precedence wins */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1059
      apy->type = RD_RESOLVED;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1060
    }else if( spx->prec<spy->prec ){
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1061
      apx->type = SH_RESOLVED;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1062
    }else if( spx->prec==spy->prec && spx->assoc==RIGHT ){ /* Use operator */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1063
      apy->type = RD_RESOLVED;                             /* associativity */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1064
    }else if( spx->prec==spy->prec && spx->assoc==LEFT ){  /* to break tie */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1065
      apx->type = SH_RESOLVED;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1066
    }else{
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1067
      assert( spx->prec==spy->prec && spx->assoc==NONE );
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1068
      apy->type = SRCONFLICT;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1069
      errcnt++;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1070
    }
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1071
  }else if( apx->type==REDUCE && apy->type==REDUCE ){
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1072
    spx = apx->x.rp->precsym;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1073
    spy = apy->x.rp->precsym;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1074
    if( spx==0 || spy==0 || spx->prec<0 ||
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1075
    spy->prec<0 || spx->prec==spy->prec ){
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1076
      apy->type = RRCONFLICT;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1077
      errcnt++;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1078
    }else if( spx->prec>spy->prec ){
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1079
      apy->type = RD_RESOLVED;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1080
    }else if( spx->prec<spy->prec ){
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1081
      apx->type = RD_RESOLVED;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1082
    }
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1083
  }else{
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1084
    assert( 
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1085
      apx->type==SH_RESOLVED ||
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1086
      apx->type==RD_RESOLVED ||
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1087
      apx->type==SSCONFLICT ||
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1088
      apx->type==SRCONFLICT ||
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1089
      apx->type==RRCONFLICT ||
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1090
      apy->type==SH_RESOLVED ||
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1091
      apy->type==RD_RESOLVED ||
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1092
      apy->type==SSCONFLICT ||
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1093
      apy->type==SRCONFLICT ||
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1094
      apy->type==RRCONFLICT
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1095
    );
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1096
    /* The REDUCE/SHIFT case cannot happen because SHIFTs come before
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1097
    ** REDUCEs on the list.  If we reach this point it must be because
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1098
    ** the parser conflict had already been resolved. */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1099
  }
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1100
  return errcnt;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1101
}
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1102
/********************* From the file "configlist.c" *************************/
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1103
/*
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1104
** Routines to processing a configuration list and building a state
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1105
** in the LEMON parser generator.
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1106
*/
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1107
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1108
static struct config *freelist = 0;      /* List of free configurations */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1109
static struct config *current = 0;       /* Top of list of configurations */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1110
static struct config **currentend = 0;   /* Last on list of configs */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1111
static struct config *basis = 0;         /* Top of list of basis configs */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1112
static struct config **basisend = 0;     /* End of list of basis configs */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1113
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1114
/* Return a pointer to a new configuration */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1115
PRIVATE struct config *newconfig(){
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1116
  struct config *new;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1117
  if( freelist==0 ){
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1118
    int i;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1119
    int amt = 3;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1120
    freelist = (struct config *)calloc( amt, sizeof(struct config) );
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1121
    if( freelist==0 ){
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1122
      fprintf(stderr,"Unable to allocate memory for a new configuration.");
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1123
      exit(1);
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1124
    }
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1125
    for(i=0; i<amt-1; i++) freelist[i].next = &freelist[i+1];
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1126
    freelist[amt-1].next = 0;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1127
  }
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1128
  new = freelist;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1129
  freelist = freelist->next;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1130
  return new;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1131
}
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1132
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1133
/* The configuration "old" is no longer used */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1134
PRIVATE void deleteconfig(old)
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1135
struct config *old;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1136
{
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1137
  old->next = freelist;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1138
  freelist = old;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1139
}
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1140
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1141
/* Initialized the configuration list builder */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1142
void Configlist_init(){
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1143
  current = 0;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1144
  currentend = &current;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1145
  basis = 0;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1146
  basisend = &basis;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1147
  Configtable_init();
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1148
  return;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1149
}
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1150
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1151
/* Initialized the configuration list builder */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1152
void Configlist_reset(){
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1153
  current = 0;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1154
  currentend = &current;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1155
  basis = 0;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1156
  basisend = &basis;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1157
  Configtable_clear(0);
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1158
  return;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1159
}
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1160
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1161
/* Add another configuration to the configuration list */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1162
struct config *Configlist_add(rp,dot)
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1163
struct rule *rp;    /* The rule */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1164
int dot;            /* Index into the RHS of the rule where the dot goes */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1165
{
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1166
  struct config *cfp, model;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1167
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1168
  assert( currentend!=0 );
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1169
  model.rp = rp;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1170
  model.dot = dot;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1171
  cfp = Configtable_find(&model);
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1172
  if( cfp==0 ){
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1173
    cfp = newconfig();
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1174
    cfp->rp = rp;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1175
    cfp->dot = dot;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1176
    cfp->fws = SetNew();
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1177
    cfp->stp = 0;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1178
    cfp->fplp = cfp->bplp = 0;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1179
    cfp->next = 0;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1180
    cfp->bp = 0;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1181
    *currentend = cfp;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1182
    currentend = &cfp->next;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1183
    Configtable_insert(cfp);
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1184
  }
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1185
  return cfp;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1186
}
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1187
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1188
/* Add a basis configuration to the configuration list */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1189
struct config *Configlist_addbasis(rp,dot)
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1190
struct rule *rp;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1191
int dot;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1192
{
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1193
  struct config *cfp, model;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1194
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1195
  assert( basisend!=0 );
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1196
  assert( currentend!=0 );
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1197
  model.rp = rp;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1198
  model.dot = dot;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1199
  cfp = Configtable_find(&model);
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1200
  if( cfp==0 ){
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1201
    cfp = newconfig();
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1202
    cfp->rp = rp;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1203
    cfp->dot = dot;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1204
    cfp->fws = SetNew();
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1205
    cfp->stp = 0;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1206
    cfp->fplp = cfp->bplp = 0;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1207
    cfp->next = 0;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1208
    cfp->bp = 0;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1209
    *currentend = cfp;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1210
    currentend = &cfp->next;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1211
    *basisend = cfp;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1212
    basisend = &cfp->bp;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1213
    Configtable_insert(cfp);
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1214
  }
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1215
  return cfp;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1216
}
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1217
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1218
/* Compute the closure of the configuration list */
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1219
void Configlist_closure(lemp)
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1220
struct lemon *lemp;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1221
{
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1222
  struct config *cfp, *newcfp;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1223
  struct rule *rp, *newrp;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1224
  struct symbol *sp, *xsp;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1225
  int i, dot;
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1226
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1227
  assert( currentend!=0 );
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordon <icculus@icculus.org>
parents:
diff changeset
  1228
  for(cfp=current; cfp; cfp=cfp->next){
d29c193900b0 Added lemon and lempar sources to revision control.
Ryan C. Gordo