1 /* $Id: lalr.c,v 1.14 2021/05/20 23:57:23 tom Exp $ */
12 static Value_t
map_goto(int state
, int symbol
);
13 static Value_t
**transpose(Value_t
**R
, int n
);
14 static void add_lookback_edge(int stateno
, int ruleno
, int gotono
);
15 static void build_relations(void);
16 static void compute_FOLLOWS(void);
17 static void compute_lookaheads(void);
18 static void digraph(Value_t
**relation
);
19 static void initialize_F(void);
20 static void initialize_LA(void);
21 static void set_accessing_symbol(void);
22 static void set_goto_map(void);
23 static void set_maxrhs(void);
24 static void set_reduction_table(void);
25 static void set_shift_table(void);
26 static void set_state_table(void);
27 static void traverse(int i
);
29 static int tokensetsize
;
33 Value_t
*accessing_symbol
;
36 reductions
**reduction_table
;
42 static Value_t infinity
;
44 static Value_t ngotos
;
46 static Value_t
**includes
;
47 static shorts
**lookback
;
49 static Value_t
*INDEX
;
50 static Value_t
*VERTICES
;
56 tokensetsize
= WORDSIZE(ntokens
);
59 set_accessing_symbol();
61 set_reduction_table();
76 state_table
= NEW2(nstates
, core
*);
77 for (sp
= first_state
; sp
; sp
= sp
->next
)
78 state_table
[sp
->number
] = sp
;
82 set_accessing_symbol(void)
86 accessing_symbol
= NEW2(nstates
, Value_t
);
87 for (sp
= first_state
; sp
; sp
= sp
->next
)
88 accessing_symbol
[sp
->number
] = sp
->accessing_symbol
;
96 shift_table
= NEW2(nstates
, shifts
*);
97 for (sp
= first_shift
; sp
; sp
= sp
->next
)
98 shift_table
[sp
->number
] = sp
;
102 set_reduction_table(void)
106 reduction_table
= NEW2(nstates
, reductions
*);
107 for (rp
= first_reduction
; rp
; rp
= rp
->next
)
108 reduction_table
[rp
->number
] = rp
;
121 item_end
= ritem
+ nitems
;
122 for (itemp
= ritem
; itemp
< item_end
; itemp
++)
145 lookaheads
= NEW2(nstates
+ 1, Value_t
);
148 for (i
= 0; i
< nstates
; i
++)
150 lookaheads
[i
] = (Value_t
)k
;
151 rp
= reduction_table
[i
];
155 lookaheads
[nstates
] = (Value_t
)k
;
157 LA
= NEW2(k
* tokensetsize
, unsigned);
158 LAruleno
= NEW2(k
, Value_t
);
159 lookback
= NEW2(k
, shorts
*);
162 for (i
= 0; i
< nstates
; i
++)
164 rp
= reduction_table
[i
];
167 for (j
= 0; j
< rp
->nreds
; j
++)
169 LAruleno
[k
] = rp
->rules
[j
];
187 goto_base
= NEW2(nvars
+ 1, Value_t
);
188 temp_base
= NEW2(nvars
+ 1, Value_t
);
190 goto_map
= goto_base
- ntokens
;
191 temp_map
= temp_base
- ntokens
;
194 for (sp
= first_shift
; sp
; sp
= sp
->next
)
196 for (i
= sp
->nshifts
- 1; i
>= 0; i
--)
198 symbol
= accessing_symbol
[sp
->shift
[i
]];
203 if (ngotos
== MAXYYINT
)
204 fatal("too many gotos");
212 for (i
= ntokens
; i
< nsyms
; i
++)
214 temp_map
[i
] = (Value_t
)k
;
218 for (i
= ntokens
; i
< nsyms
; i
++)
219 goto_map
[i
] = temp_map
[i
];
221 goto_map
[nsyms
] = (Value_t
)ngotos
;
222 temp_map
[nsyms
] = (Value_t
)ngotos
;
224 from_state
= NEW2(ngotos
, Value_t
);
225 to_state
= NEW2(ngotos
, Value_t
);
227 for (sp
= first_shift
; sp
; sp
= sp
->next
)
229 Value_t state1
= sp
->number
;
231 for (i
= sp
->nshifts
- 1; i
>= 0; i
--)
233 state2
= sp
->shift
[i
];
234 symbol
= accessing_symbol
[state2
];
239 k
= temp_map
[symbol
]++;
240 from_state
[k
] = state1
;
241 to_state
[k
] = state2
;
248 /* Map_goto maps a state/symbol pair into its numeric representation. */
251 map_goto(int state
, int symbol
)
253 int low
= goto_map
[symbol
];
254 int high
= goto_map
[symbol
+ 1];
262 middle
= (low
+ high
) >> 1;
263 s
= from_state
[middle
];
265 return (Value_t
)(middle
);
288 nwords
= ngotos
* tokensetsize
;
289 F
= NEW2(nwords
, unsigned);
291 reads
= NEW2(ngotos
, Value_t
*);
292 edge
= NEW2(ngotos
+ 1, Value_t
);
296 for (i
= 0; i
< ngotos
; i
++)
298 int stateno
= to_state
[i
];
300 sp
= shift_table
[stateno
];
306 for (j
= 0; j
< k
; j
++)
308 symbol
= accessing_symbol
[sp
->shift
[j
]];
311 SETBIT(rowp
, symbol
);
316 symbol
= accessing_symbol
[sp
->shift
[j
]];
317 if (nullable
[symbol
])
318 edge
[nedges
++] = map_goto(stateno
, symbol
);
323 reads
[i
] = rp
= NEW2(nedges
+ 1, Value_t
);
325 for (j
= 0; j
< nedges
; j
++)
333 rowp
+= tokensetsize
;
339 for (i
= 0; i
< ngotos
; i
++)
350 build_relations(void)
365 Value_t
**new_includes
;
367 includes
= NEW2(ngotos
, Value_t
*);
368 edge
= NEW2(ngotos
+ 1, Value_t
);
369 states
= NEW2(maxrhs
+ 1, Value_t
);
371 for (i
= 0; i
< ngotos
; i
++)
374 int symbol1
= accessing_symbol
[to_state
[i
]];
375 Value_t state1
= from_state
[i
];
377 for (rulep
= derives
[symbol1
]; *rulep
>= 0; rulep
++)
383 for (rp
= ritem
+ rrhs
[*rulep
]; *rp
>= 0; rp
++)
386 sp
= shift_table
[stateno
];
389 for (j
= 0; j
< k
; j
++)
391 stateno
= sp
->shift
[j
];
392 if (accessing_symbol
[stateno
] == symbol2
)
396 states
[length
++] = stateno
;
399 add_lookback_edge(stateno
, *rulep
, i
);
409 stateno
= states
[--length
];
410 edge
[nedges
++] = map_goto(stateno
, *rp
);
411 if (nullable
[*rp
] && length
> 0)
419 includes
[i
] = shortp
= NEW2(nedges
+ 1, Value_t
);
420 for (j
= 0; j
< nedges
; j
++)
426 new_includes
= transpose(includes
, ngotos
);
428 for (i
= 0; i
< ngotos
; i
++)
434 includes
= new_includes
;
441 add_lookback_edge(int stateno
, int ruleno
, int gotono
)
447 i
= lookaheads
[stateno
];
448 k
= lookaheads
[stateno
+ 1];
450 while (!found
&& i
< k
)
452 if (LAruleno
[i
] == ruleno
)
460 sp
->next
= lookback
[i
];
461 sp
->value
= (Value_t
)gotono
;
466 transpose(Value_t
**R2
, int n
)
474 nedges
= NEW2(n
, Value_t
);
476 for (i
= 0; i
< n
; i
++)
486 new_R
= NEW2(n
, Value_t
*);
487 temp_R
= NEW2(n
, Value_t
*);
489 for (i
= 0; i
< n
; i
++)
495 sp
= NEW2(k
+ 1, Value_t
);
504 for (i
= 0; i
< n
; i
++)
510 *temp_R
[*sp
++]++ = (Value_t
)i
;
520 compute_FOLLOWS(void)
526 compute_lookaheads(void)
529 unsigned *fp1
, *fp2
, *fp3
;
534 n
= lookaheads
[nstates
];
535 for (i
= 0; i
< n
; i
++)
537 fp3
= rowp
+ tokensetsize
;
538 for (sp
= lookback
[i
]; sp
; sp
= sp
->next
)
541 fp2
= F
+ tokensetsize
* sp
->value
;
548 for (i
= 0; i
< n
; i
++)
549 for (sp
= lookback
[i
]; sp
; sp
= next
)
560 digraph(Value_t
**relation
)
564 infinity
= (Value_t
)(ngotos
+ 2);
565 INDEX
= NEW2(ngotos
+ 1, Value_t
);
566 VERTICES
= NEW2(ngotos
+ 1, Value_t
);
571 for (i
= 0; i
< ngotos
; i
++)
574 for (i
= 0; i
< ngotos
; i
++)
576 if (INDEX
[i
] == 0 && R
[i
])
596 VERTICES
[++top
] = (Value_t
)i
;
597 INDEX
[i
] = height
= top
;
599 base
= F
+ i
* tokensetsize
;
600 fp3
= base
+ tokensetsize
;
605 while ((j
= *rp
++) >= 0)
610 if (INDEX
[i
] > INDEX
[j
])
614 fp2
= F
+ j
* tokensetsize
;
621 if (INDEX
[i
] == height
)
632 fp2
= F
+ j
* tokensetsize
;
648 for (i
= 0; i
< ngotos
; i
++)