Subversion Repositories tendra.SVN

/*

 * Copyright (c) 2002-2005 The TenDRA Project <http://www.tendra.org/>.

 * All rights reserved.

 *

 * Redistribution and use in source and binary forms, with or without

 * modification, are permitted provided that the following conditions are met:

 *

 * 1. Redistributions of source code must retain the above copyright notice,

 *    this list of conditions and the following disclaimer.

 * 2. Redistributions in binary form must reproduce the above copyright notice,

 *    this list of conditions and the following disclaimer in the documentation

 *    and/or other materials provided with the distribution.

 * 3. Neither the name of The TenDRA Project nor the names of its contributors

 *    may be used to endorse or promote products derived from this software

 *    without specific, prior written permission.

 *

 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS ``AS

 * IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,

 * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR

 * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT HOLDERS OR

 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,

 * EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,

 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;

 * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,

 * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR

 * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF

 * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

 *

 * $Id$

 */

/*

    		 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(EntryP entry, 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(*)(EntryP, GenericP)), NIL(GenericP));

	}

    }

}

static void

grammar_check_1(EntryP entry, 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(GrammarP grammar, 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(EntryP entry, GenericP gclosure)

{

    OStreamP ostream = (OStreamP)gclosure;

    if (entry_is_rule(entry)) {

	write_rule(ostream, entry_get_rule(entry));

	write_newline(ostream);

    }

}

/*--------------------------------------------------------------------------*/

void

grammar_init(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(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(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(GrammarP grammar)

{

    return(grammar->terminal);

}

#ifdef FS_FAST

#define grammar_max_terminal(g)	((g)->terminal)

#endif /* defined (FS_FAST) */

unsigned

grammar_next_terminal(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(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(GrammarP grammar, 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(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(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(*)(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(GrammarP grammar)

{

    grammar_find_cycles(grammar, CT_LEFT);

}

void

grammar_compute_first_sets(GrammarP grammar)

{

    TableP table = grammar_table(grammar);

    table_iter(table, rule_compute_first_set, NIL(GenericP));

}

void

grammar_factor(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(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(*)(EntryP, GenericP)),

			  NIL(GenericP));

    table_unlink_untraced_rules(table);

}

void

grammar_compute_inlining(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(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(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(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(OStreamP ostream, 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:

**/