/* * Copyright (c) 2007 The Akuma Project * * Permission is hereby granted, free of charge, to any person obtaining a copy * of this software and associated documentation files (the "Software"), to * deal in the Software without restriction, including without limitation the * rights to use, copy, modify, merge, publish, distribute, sublicense, and/or * sell copies of the Software, and to permit persons to whom the Software is * furnished to do so, subject to the following conditions: * * The above copyright notice and this permission notice shall be included in * all copies or substantial portions of the Software. * * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS * IN THE SOFTWARE. * * $Id: grammar.c 133 2007-05-29 14:32:04Z asmodai $ */ /* 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 * *** 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: **/