-
Notifications
You must be signed in to change notification settings - Fork 2
/
Po_prod_bst.cpp
182 lines (169 loc) · 8.26 KB
/
Po_prod_bst.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
/*******************************************************************/
/*** FILE : Po_prod_bst.c ***/
/*** AUTHORS: Jagdish Thurimella ***/
/*** Sekhar Muddana ***/
/*** PUBLIC ROUTINES: ***/
/*** PROD_TREEPTR Prod_insert() ***/
/*** PROD_TREEPTR Prod_member() ***/
/*** void Prt_prod_inorder() ***/
/*** PRIVATE ROUTINES: ***/
/*** static int EQUAL() ***/
/*** static int LT() ***/
/*** static int GT() ***/
/*** MODULE DESCRIPTION: ***/
/*** These routines are used by Po_parse_poly.c to set up ***/
/*** search tree of productions. ***/
/*******************************************************************/
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include "Po_prod_bst.h"
#include "Memory_routines.h"
#if 0
static void Prt_prod_inorder(PROD_TREEPTR Node);
#endif
static int LT(const char *X, const char *Y);
static int GT(const char *X, const char *Y);
static int EQUAL(const char *X, const char *Y);
/*******************************************************************/
/* MODIFIES: */
/* *Node_ptr -- insert a new node into the tree. */
/* REQUIRES: */
/* X -- string, is copied into a field in the new node. */
/* The string equivalent of Handle of the production, */
/* obtained by gluing integers together as a string. */
/* Left -- Non terminal of the production */
/* Pnum -- Production number. */
/* RETURNS: */
/* *Node_ptr -- Pointer to the tree of productions. */
/* FUNCTION: */
/* Insert the production at the right place in the binary */
/* tree, after allocating space. Key is the string. */
/* NOTE: */
/* This routine is called to store all the production as a */
/* part of initialization. Called from Init_prod_tree() in */
/* the module Po_parse_poly.c */
/*******************************************************************/
PROD_TREEPTR Prod_insert(const char X[], int Left, int Pnum, PROD_TREEPTR *Node_ptr)
{
if (*Node_ptr == NULL) {
(*Node_ptr) = prod_talloc();
strcpy((*Node_ptr)->rhs_str, X) ;
(*Node_ptr)->lhs = Left;
(*Node_ptr)->prodnum = Pnum;
(*Node_ptr)->left = NULL ;
(*Node_ptr)->right = NULL ;
return (*Node_ptr) ;
}
else if (LT(X, (*Node_ptr)->rhs_str))
return (Prod_insert(X, Left, Pnum, &((*Node_ptr)->left))) ;
else if (GT(X, (*Node_ptr)->rhs_str))
return (Prod_insert(X, Left, Pnum, &((*Node_ptr)->right))) ;
else if (EQUAL(X, (*Node_ptr)->rhs_str))
return (*Node_ptr) ;
return NULL;
}
/*******************************************************************/
/* MODIFIES: None. */
/* REQUIRES: */
/* X -- a Handle of a reduction. */
/* Node_ptr -- Pointer to the tree of productions. */
/* RETURNS: */
/* If X is a valid handle, return pointer to the node where */
/* the Handle is present. */
/* NULL otherwise. */
/* FUNCTION: */
/* Search the binary tree of productions to see if the Handle */
/* is a valid right hand of side of a production. */
/* NOTE: */
/* This routine is called from Reduce() in the file */
/* Po_parse_poly.c, while doing the parsing of identity. */
/*******************************************************************/
PROD_TREEPTR Prod_member(const char X[], PROD_TREEPTR Node_ptr)
{
if (Node_ptr == NULL)
return(NULL) ;
else if (EQUAL(X, (Node_ptr)->rhs_str))
return (Node_ptr) ;
else if (LT(X, Node_ptr->rhs_str))
return (Prod_member(X, Node_ptr->left)) ;
else if (GT(X, Node_ptr->rhs_str))
return (Prod_member(X, Node_ptr->right)) ;
return NULL;
}
#if 0
/*******************************************************************/
/* MODIFIES: None. */
/* REQUIRES: */
/* Node -- Pointer to the tree of productions. */
/* RETURNS: None. */
/* FUNCTION: */
/* Print productions in ascending order. */
/* NOTE: */
/* called only when flag to Debug Parsing is ON. */
/*******************************************************************/
void Prt_prod_inorder(PROD_TREEPTR Node)
{
if (Node != NULL) {
if (Node->left == NULL) {
printf(" %30s %d %d \n", Node->rhs_str, Node->lhs, Node->prodnum);
if (Node->right != NULL)
Prt_prod_inorder(Node->right) ;
}
else {
Prt_prod_inorder(Node->left) ;
printf(" %30s %d %d \n", Node->rhs_str, Node->lhs, Node->prodnum);
if (Node->right != NULL)
Prt_prod_inorder(Node->right) ;
}
}
}
#endif
/*******************************************************************/
/* MODIFIES: None. */
/* REQUIRES: */
/* X */
/* Y */
/* RETURNS: */
/* 1 if string X is less than string Y. */
/* 0 otherwise. */
/*******************************************************************/
int LT(const char *X, const char *Y)
{
if (strcmp(X, Y) < 0)
return(1) ;
else
return(0) ;
}
/*******************************************************************/
/* MODIFIES: None. */
/* REQUIRES: */
/* X */
/* Y */
/* RETURNS: */
/* 1 if string X is greater than string Y. */
/* 0 otherwise. */
/*******************************************************************/
int GT(const char *X, const char *Y)
{
if (strcmp(X, Y) > 0)
return(1) ;
else
return(0) ;
}
/*******************************************************************/
/* MODIFIES: None. */
/* REQUIRES: */
/* X */
/* Y */
/* RETURNS: */
/* 1 if string X is equal to string Y. */
/* 0 otherwise. */
/*******************************************************************/
int EQUAL(const char *X, const char *Y)
{
if (strcmp(X, Y) == 0)
return(1) ;
else
return(0) ;
}