Rev 5 | Go to most recent revision | Blame | Compare with Previous | Last modification | View Log | RSS feed
/*
Crown Copyright (c) 1997
This TenDRA(r) Computer Program is subject to Copyright
owned by the United Kingdom Secretary of State for Defence
acting through the Defence Evaluation and Research Agency
(DERA). It is made available to Recipients with a
royalty-free licence for its use, reproduction, transfer
to other parties and amendment for any purpose not excluding
product development provided that any such use et cetera
shall be deemed to be acceptance of the following conditions:-
(1) Its Recipients shall ensure that this Notice is
reproduced upon any copies or amended versions of it;
(2) Any amended version of it shall be clearly marked to
show both the nature of and the organisation responsible
for the relevant amendment or amendments;
(3) Its onward transfer from a recipient to another
party shall be deemed to be that party's acceptance of
these conditions;
(4) DERA gives no warranty or assurance as to its
quality or suitability for any purpose and DERA accepts
no liability whatsoever in relation to any use to which
it may be put.
*/
/*** grammar.c --- Grammar transforms frontend.
*
** Author: Steve Folkes <smf@hermes.mod.uk>
*
*** Commentary:
*
* This file implements the SID transformation front-end routines.
*
* Before any of these routines are called, the grammar should have been read
* in by the parser. The functions should be called in the following order.
*
* ``grammar_check_complete''
*
* This function traces the grammar that is accessible from the entry points,
* and ensures that there are no unused rules, basics, actions or types, and
* that all of the rules are defined.
*
* ``grammar_remove_left_recursion''
*
* This function applies several functions from the file "rule.c" to the rules
* in the grammar, to detect left cycles (this is done by the
* "grammar_find_cycles" function). When such a cycle is found, it calls
* ``rule_remove_left_cycle'' (defined in the file "rule-lre.c") to remove the
* cycle. The function removes any left recursion from the rules, replacing
* it with a right recursive equivalent. See the file "rule-lre.c" for more
* details.
*
* The cycle detection algorithm works as follows: firstly a list of rules is
* built by the function ``rule_build_root_list''; this list acts as the root
* node of the graph. The remainder of the graph is built up from the
* leftmost rule invocations (if any) in each alternative of each production.
* This graph is depth first searched by the function ``rule_compute_dfs'', to
* produce an ordered list of productions. The reverse graph (which is
* computed by applying the function ``rule_compute_reverse_list'' to each
* production, at the same time as the dfs is being performed) is then depth
* first searched in the order specified by the list, using the function
* ``rule_compute_reverse_dfs''. The result of this is the set of left
* cycles. The algorithm is explained fully in {"Data Structures and
* Algorithms"; Aho, Hopcroft, Ullman; Addison Wesley; ISBN 0-201-00023-7;
* page 222}.
*
* ``grammar_compute_first_sets''
*
* This function applies the ``rule_compute_first_set'' function to all rules
* in the grammar. The function computes the first set for each rule. It
* also computes a priority for the rule, and whether the rule is see through
* or not. See the file "rule-first.c" for more details.
*
* ``grammar_factor''
*
* This function applies the ``rule_factor'' function to all of the rules in
* the grammar. The function does a number of transformations on the rules to
* make them more likely to be LL(1). See the file "rule-factor.c" for more
* details.
*
* ``grammar_simplify''
*
* This function calls the ``rule_remove_duplicates'' function on the grammar,
* to remove any rules that have identical form. See the file "rule-simp.c"
* for more details.
*
* ``grammar_compute_inlining''
*
* This function applies a number of functions to the rules in the grammar in
* order to indicate which rules should be inlined during the output phase.
* See the file "rule-tail.c" for more details.
*
* ``grammar_check_collisions''
*
* This function applies a number of functions to the rules in the grammar in
* order to check that the grammar is valid. It also causes the first sets
* for all of the alternatives within a rule to be calculated, and if there is
* a see through alternative. See the file "rule-check.c" for more details.
*
* ``grammar_recompute_alt_names''
*
* This function applies the ``rule_recompute_alt_names'' function to all
* rules in the grammar. The function recomputes the identifier names that
* are used within each alternative of the rule. See the file "rule-names.c"
* for more details.
*
* ``grammar_compute_mutations''
*
* This function applies the ``rule_compute_mutations'' function to all rules
* in the grammar. The function computes the mutation effects from actions
* that mutate their parameters. See the file "rule-mutate.c" for more
* details.
*
*** Change Log:
* $Log: grammar.c,v $
* Revision 1.1.1.1 1998/01/17 15:57:46 release
* First version to be checked into rolling release.
*
* Revision 1.2 1994/12/15 09:58:13 smf
* Brought into line with OSSG C Coding Standards Document, as per
* "CR94_178.sid+tld-update".
*
* Revision 1.1.1.1 1994/07/25 16:04:34 smf
* Initial import of SID 1.8 non shared files.
*
**/
/****************************************************************************/
#include "grammar.h"
#include "action.h"
#include "basic.h"
#include "gen-errors.h"
#include "name.h"
#include "rule.h"
#include "type.h"
/*--------------------------------------------------------------------------*/
static void
grammar_trace_ignored PROTO_N ((entry, gclosure))
PROTO_T (EntryP entry X
GenericP gclosure)
{
UNUSED (gclosure);
if (entry_is_basic (entry)) {
BasicP basic = entry_get_basic (entry);
if (basic_get_ignored (basic)) {
entry_iter (entry, TRUE,
NIL (void (*) PROTO_S ((EntryP, GenericP))),
NIL (GenericP));
}
}
}
static void
grammar_check_1 PROTO_N ((entry, gclosure))
PROTO_T (EntryP entry X
GenericP gclosure)
{
UNUSED (gclosure);
switch (entry_type (entry)) EXHAUSTIVE {
case ET_RULE:
if (!rule_is_defined (entry_get_rule (entry))) {
E_rule_not_defined (entry_key (entry));
}
if (!entry_is_traced (entry)) {
E_rule_not_used (entry_key (entry));
}
break;
case ET_BASIC:
if (!entry_is_traced (entry)) {
E_basic_not_used (entry_key (entry));
}
break;
case ET_ACTION:
if (!entry_is_traced (entry)) {
E_action_not_used (entry_key (entry));
}
break;
case ET_TYPE:
if (!entry_is_traced (entry)) {
E_type_not_used (entry_key (entry));
}
break;
case ET_NON_LOCAL:
if (!entry_is_traced (entry)) {
E_non_local_not_used (entry_key (entry));
}
break;
case ET_NAME:
case ET_RENAME:
break;
case ET_PREDICATE:
UNREACHED;
}
}
static void
grammar_find_cycles PROTO_N ((grammar, type))
PROTO_T (GrammarP grammar X
CycleTypeT type)
{
TableP table = grammar_table (grammar);
EntryP predicate_id = grammar_get_predicate_id (grammar);
RuleP dfs_list_head = NIL (RuleP);
RuleListT root_list;
RuleP rule;
rule_list_init (&root_list);
table_iter (table, rule_build_root_list, (GenericP) &root_list);
rule_list_terminate (&root_list);
for (rule = rule_list_head (&root_list); rule;
rule = rule_next_in_root_list (rule)) {
rule_compute_reverse_list (rule, type);
rule_compute_dfs (rule, type, &dfs_list_head);
}
for (rule = rule_list_head (&root_list); rule;
rule = rule_next_in_root_list (rule)) {
rule_set_dfs_state (rule, DFS_UNTRACED);
}
for (rule = dfs_list_head; rule; rule = rule_get_next_in_dfs (rule)) {
if (!rule_has_no_cycles (rule)) {
RuleP reverse_dfs_list_head = NIL (RuleP);
rule_compute_reverse_dfs (rule, rule, &reverse_dfs_list_head);
if (reverse_dfs_list_head) {
switch (type) EXHAUSTIVE {
case CT_LEFT:
rule_remove_left_cycle (reverse_dfs_list_head,
predicate_id, table);
break;
case CT_TAIL:
rule_handle_tails (reverse_dfs_list_head);
break;
case CT_ALL:
rule_handle_need_functions (reverse_dfs_list_head);
break;
case CT_MUTATE:
UNREACHED;
}
}
}
}
for (rule = rule_list_head (&root_list); rule;
rule = rule_next_in_root_list (rule)) {
rule_reinit_reverse_list (rule);
}
}
static void
write_grammar_1 PROTO_N ((entry, gclosure))
PROTO_T (EntryP entry X
GenericP gclosure)
{
OStreamP ostream = (OStreamP) gclosure;
if (entry_is_rule (entry)) {
write_rule (ostream, entry_get_rule (entry));
write_newline (ostream);
}
}
/*--------------------------------------------------------------------------*/
void
grammar_init PROTO_N ((grammar))
PROTO_T (GrammarP grammar)
{
TableP table = grammar_table (grammar);
table_init (table);
entry_list_init (grammar_entry_list (grammar));
grammar->terminal = 0;
grammar->predicate_type = NIL (EntryP);
grammar->predicate_id = table_add_generated_name (table);
}
#ifdef FS_FAST
#undef grammar_table
#endif /* defined (FS_FAST) */
TableP
grammar_table PROTO_N ((grammar))
PROTO_T (GrammarP grammar)
{
return (&(grammar->table));
}
#ifdef FS_FAST
#define grammar_table(g) (&((g)->table))
#endif /* defined (FS_FAST) */
#ifdef FS_FAST
#undef grammar_entry_list
#endif /* defined (FS_FAST) */
EntryListP
grammar_entry_list PROTO_N ((grammar))
PROTO_T (GrammarP grammar)
{
return (&(grammar->entry_list));
}
#ifdef FS_FAST
#define grammar_entry_list(g) (&((g)->entry_list))
#endif /* defined (FS_FAST) */
#ifdef FS_FAST
#undef grammar_max_terminal
#endif /* defined (FS_FAST) */
unsigned
grammar_max_terminal PROTO_N ((grammar))
PROTO_T (GrammarP grammar)
{
return (grammar->terminal);
}
#ifdef FS_FAST
#define grammar_max_terminal(g) ((g)->terminal)
#endif /* defined (FS_FAST) */
unsigned
grammar_next_terminal PROTO_N ((grammar))
PROTO_T (GrammarP grammar)
{
if (grammar->terminal == UINT_MAX) {
E_too_many_terminals ();
UNREACHED;
}
return (grammar->terminal ++);
}
#ifdef FS_FAST
#undef grammar_get_predicate_type
#endif /* defined (FS_FAST) */
EntryP
grammar_get_predicate_type PROTO_N ((grammar))
PROTO_T (GrammarP grammar)
{
return (grammar->predicate_type);
}
#ifdef FS_FAST
#define grammar_get_predicate_type(g) ((g)->predicate_type)
#endif /* defined (FS_FAST) */
#ifdef FS_FAST
#undef grammar_set_predicate_type
#endif /* defined (FS_FAST) */
void
grammar_set_predicate_type PROTO_N ((grammar, type))
PROTO_T (GrammarP grammar X
EntryP type)
{
grammar->predicate_type = type;
}
#ifdef FS_FAST
#define grammar_set_predicate_type(g, t) ((g)->predicate_type = (t))
#endif /* defined (FS_FAST) */
#ifdef FS_FAST
#undef grammar_get_predicate_id
#endif /* defined (FS_FAST) */
EntryP
grammar_get_predicate_id PROTO_N ((grammar))
PROTO_T (GrammarP grammar)
{
return (grammar->predicate_id);
}
#ifdef FS_FAST
#define grammar_get_predicate_id(g) ((g)->predicate_id)
#endif /* defined (FS_FAST) */
void
grammar_check_complete PROTO_N ((grammar))
PROTO_T (GrammarP grammar)
{
TableP table = grammar_table (grammar);
EntryListP entry_list = grammar_entry_list (grammar);
table_untrace (table);
entry_list_iter_table (entry_list, TRUE,
NIL (void (*) PROTO_S ((EntryP, GenericP))),
NIL (GenericP));
table_iter (table, grammar_trace_ignored, NIL (GenericP));
table_iter (table, grammar_check_1, NIL (GenericP));
}
void
grammar_remove_left_recursion PROTO_N ((grammar))
PROTO_T (GrammarP grammar)
{
grammar_find_cycles (grammar, CT_LEFT);
}
void
grammar_compute_first_sets PROTO_N ((grammar))
PROTO_T (GrammarP grammar)
{
TableP table = grammar_table (grammar);
table_iter (table, rule_compute_first_set, NIL (GenericP));
}
void
grammar_factor PROTO_N ((grammar))
PROTO_T (GrammarP grammar)
{
TableP table = grammar_table (grammar);
EntryListP entry_list = grammar_entry_list (grammar);
FactorClosureT closure;
bitvec_init (&(closure.bitvec1));
bitvec_init (&(closure.bitvec2));
closure.table = table;
closure.predicate_id = grammar_get_predicate_id (grammar);
table_untrace (table);
entry_list_iter_table (entry_list, FALSE, rule_factor,
(GenericP) &closure);
table_unlink_untraced_rules (table);
bitvec_destroy (&(closure.bitvec1));
bitvec_destroy (&(closure.bitvec2));
}
void
grammar_simplify PROTO_N ((grammar))
PROTO_T (GrammarP grammar)
{
TableP table = grammar_table (grammar);
EntryListP entry_list = grammar_entry_list (grammar);
EntryP predicate_id = grammar_get_predicate_id (grammar);
rule_remove_duplicates (table, predicate_id);
table_untrace (table);
entry_list_iter_table (entry_list, FALSE,
NIL (void (*) PROTO_S ((EntryP, GenericP))),
NIL (GenericP));
table_unlink_untraced_rules (table);
}
void
grammar_compute_inlining PROTO_N ((grammar))
PROTO_T (GrammarP grammar)
{
TableP table = grammar_table (grammar);
if (rule_get_inline_tail_calls ()) {
grammar_find_cycles (grammar, CT_TAIL);
}
table_iter (table, rule_compute_all_basics, NIL (GenericP));
table_iter (table, rule_compute_inlining, NIL (GenericP));
table_iter (table, rule_compute_needed_functions, NIL (GenericP));
grammar_find_cycles (grammar, CT_ALL);
}
void
grammar_check_collisions PROTO_N ((grammar))
PROTO_T (GrammarP grammar)
{
TableP table = grammar_table (grammar);
table_iter (table, rule_check_first_set, (GenericP) grammar);
table_iter (table, rule_compute_follow_set, (GenericP) grammar);
table_iter (table, rule_compute_see_through_alt, NIL (GenericP));
table_iter (table, rule_compute_alt_first_sets, NIL (GenericP));
}
void
grammar_recompute_alt_names PROTO_N ((grammar))
PROTO_T (GrammarP grammar)
{
TableP table = grammar_table (grammar);
EntryP predicate_id = grammar_get_predicate_id (grammar);
table_iter (table, rule_recompute_alt_names, (GenericP) predicate_id);
}
void
grammar_compute_mutations PROTO_N ((grammar))
PROTO_T (GrammarP grammar)
{
TableP table = grammar_table (grammar);
RuleListT root_list;
RuleP rule;
rule_list_init (&root_list);
table_iter (table, rule_build_root_list, (GenericP) &root_list);
rule_list_terminate (&root_list);
for (rule = rule_list_head (&root_list); rule;
rule = rule_next_in_root_list (rule)) {
rule_compute_reverse_list (rule, CT_MUTATE);
}
table_iter (table, rule_compute_mutations, NIL (GenericP));
for (rule = rule_list_head (&root_list); rule;
rule = rule_next_in_root_list (rule)) {
rule_reinit_reverse_list (rule);
}
}
void
write_grammar PROTO_N ((ostream, grammar))
PROTO_T (OStreamP ostream X
GrammarP grammar)
{
TableP table = grammar_table (grammar);
EntryListP entry_list = grammar_entry_list (grammar);
table_untrace (table);
entry_list_iter_table (entry_list, FALSE, write_grammar_1,
(GenericP) ostream);
}
/*
* Local variables(smf):
* eval: (include::add-path-entry "../os-interface" "../library")
* eval: (include::add-path-entry "../generated")
* end:
**/