%{
#include <string>
#include <set>
using namespace std;
#include "fault_tree_textual_parser/fault_tree_textual_parser_includes.h"
#include "basic_types/bijection.h"
extern int fault_tree_textual_parser_lineno;
extern int fault_tree_textual_parser_lex();
extern void fault_tree_textual_parser_error(string s);
extern void fault_tree_textual_parser_scanner_initialize(FILE* in_input_file);
const Event Event_By_Identifier(const string &in_identifier);
const Input_Sequence Identifier_List_To_Input_Sequence(const list<string> &in_identifiers);
const bool Cycle_Exists(searchable_list<Event>& in_path, set<Event> &in_events_to_visit);
const bool Ensure_No_Cycles_In_Inputs();
const bool Ensure_Corresponding_References_And_Definitions();
const bool Ensure_Spare_Gate_Inputs_Are_Basic_Events();
const bool Ensure_Spare_Gate_Inputs_Only_Input_To_Spare_Gates();
const bool Ensure_FDEP_Trigger_Is_Not_Replicated();
const bool Ensure_FDEP_Dependents_Are_Basic_Events();
const string Get_Identifier_For_Event(const Event &in_event);
Fault_Tree parsed_fault_tree;
bijection<string, Event> identifiers_to_events;
extern const bool Ensure_Valid_System_Event();
// This is an additional check to avoid generating lots of unconstrained
// trees. We would need to update the grammar to get this.
const bool Ensure_Connectedness();
const bool Compute_Reachable_Events(const Event& in_event,
const set<Event>& in_seen_events, set<Event>& in_local_seen_events);
// Added for constrained fault tree output
const bool Ensure_Input_Order(const list<string> &in_list);
string NOT_FOUND("<NOT FOUND>");
set<string> declarations;
%}
%union {
string* text;
Natural* natural;
Replication* replication;
char* character;
Event* event;
int token;
list<string>* text_list;
Threshold* threshold;
}
%type <text> system_event
%type <text> node_list
%type <text_list> ands_list_opt
%type <text_list> ors_list_opt
%type <text_list> pands_list_opt
%type <text_list> thresholds_list_opt
%type <text_list> spares_list_opt
%type <text_list> basic_events_list
%type <text_list> fdeps_list_opt
%type <text_list> seqs_list_opt
%type <text> and_gate
%type <text> or_gate
%type <text> pand_gate
%type <text> threshold_gate
%type <text> spare_gate
%type <text> basic_event
%type <text> fdep_constraint
%type <text> seq_constraint
%type <natural> natural_nonterminal
%type <text_list> identifier_list
%token <text> IDENTIFIER
%token <natural> NATURAL
%token <natural> ZERO
%token SYSTEM_EVENT
%token AND
%token OR
%token THRESHOLD
%token PAND
%token SPARE
%token SEQ
%token FDEP
%token BE
%token SEMICOLON
%token MAXIMUM
%token TRIGGER
%token EQUALS
%token REPLICATION
%token END_OF_FILE
%%
fault_tree:
system_event node_list eof {
if (*$1 != *$2)
fault_tree_textual_parser_error("The first defined event " + *$2 + " is not the system event " + *$1);
delete $1;
delete $2;
};
// ---------------------------------------------------------------------------
system_event:
SYSTEM_EVENT EQUALS IDENTIFIER SEMICOLON {
Event system_event = Event_By_Identifier(*$3);
parsed_fault_tree.Set_Event_Description(system_event,*$3);
parsed_fault_tree.Set_System_Event(system_event);
$$ = new string(*$3);
delete $3;
}
{
Event system_event = Event_By_Identifier(*$3);
if (parsed_fault_tree.Event_Not_Referenced(system_event))
parsed_fault_tree.Remove_Event_Description(system_event);
parsed_fault_tree.Unset_System_Event();
delete $3;
};
// ---------------------------------------------------------------------------
eof:
END_OF_FILE {
// This is a check which is specific to the textual language.
if (!Ensure_Corresponding_References_And_Definitions())
return;
// Now do the various checks for consistency as specified in the formal
// definition of fault trees. Other checks (e.g. gates have replication
// of 1) are not necessary because they are handled during creation of
// the fault tree.
if (!Ensure_Valid_System_Event())
return;
if (!Ensure_Spare_Gate_Inputs_Only_Input_To_Spare_Gates())
return;
if (!Ensure_No_Cycles_In_Inputs())
return;
// This is an additional check to avoid generating lots of unconstrained
// trees. We would need to update the grammar to get this.
if (!Ensure_Connectedness())
return;
if (!Ensure_Spare_Gate_Inputs_Are_Basic_Events())
return;
if (!Ensure_FDEP_Dependents_Are_Basic_Events())
return;
if (!Ensure_FDEP_Trigger_Is_Not_Replicated())
return;
};
// ---------------------------------------------------------------------------
node_list:
ands_list_opt ors_list_opt pands_list_opt thresholds_list_opt
spares_list_opt basic_events_list fdeps_list_opt seqs_list_opt
{
list<string> merged_list;
merged_list.insert(merged_list.end(),$1->begin(),$1->end());
merged_list.insert(merged_list.end(),$2->begin(),$2->end());
merged_list.insert(merged_list.end(),$3->begin(),$3->end());
merged_list.insert(merged_list.end(),$4->begin(),$4->end());
merged_list.insert(merged_list.end(),$5->begin(),$5->end());
merged_list.insert(merged_list.end(),$6->begin(),$6->end());
if (merged_list.size() > 0)
*$$ = merged_list.front();
else
fault_tree_textual_parser_error(
"You must be at least one gate or basic event in the fault tree\n");
delete $1;
delete $2;
delete $3;
delete $4;
delete $5;
delete $6;
delete $7;
delete $8;
};
// ---------------------------------------------------------------------------
ands_list_opt :
/* NOTHING */ {
$$ = new list<string>;
} |
ands_list_opt and_gate {
if ($1->size() > 0 && $1->back() > *$2)
{
fault_tree_textual_parser_error(
"Definitions of a given type must be in alphabetical order\n");
delete $1;
}
else
{
$$ = $1;
$$->push_back(*$2);
}
delete $2;
};
and_gate :
IDENTIFIER AND identifier_list SEMICOLON {
if (!Ensure_Input_Order(*$3))
fault_tree_textual_parser_error("Inputs to " + *$1 + " must be sorted");
// Check for duplicate definition
else if (declarations.find(*$1) != declarations.end())
{
string error = "\"" + *$1 +
"\" has already been defined. This definition will be ignored.";
fault_tree_textual_parser_error(error);
}
else
{
declarations.insert(*$1);
Event gate = Event_By_Identifier(*$1);
parsed_fault_tree.Set_Event_Description(gate,*$1);
Input_Sequence inputs = Identifier_List_To_Input_Sequence(*$3);
Input_Sequence::const_iterator an_input_event;
list<string>::const_iterator an_input_identifier;
for (an_input_event = inputs.begin(), an_input_identifier = (*$3).begin();
an_input_event != inputs.end();
an_input_event++, an_input_identifier++)
{
parsed_fault_tree.Set_Event_Description(*an_input_event,*an_input_identifier);
}
parsed_fault_tree.Set_Gate_Inputs(gate,inputs);
parsed_fault_tree.Insert_And_Gate(gate);
}
$$ = $1;
delete $3;
}
{
if (!m_error_occurred)
{
declarations.erase(*$1);
Event gate = Event_By_Identifier(*$1);
Input_Sequence inputs = parsed_fault_tree.Get_Gate_Inputs(gate);
parsed_fault_tree.Remove_Gate_Inputs(gate);
Input_Sequence::const_iterator an_input_event;
for (an_input_event = inputs.begin(); an_input_event != inputs.end(); an_input_event++)
{
if (parsed_fault_tree.Event_Not_Referenced(*an_input_event))
parsed_fault_tree.Remove_Event_Description(*an_input_event);
}
parsed_fault_tree.Remove_And_Gate(gate);
if (parsed_fault_tree.Event_Not_Referenced(gate))
parsed_fault_tree.Remove_Event_Description(gate);
}
delete $1;
};
// ---------------------------------------------------------------------------
ors_list_opt :
/* NOTHING */ {
$$ = new list<string>;
} |
ors_list_opt or_gate {
if ($1->size() > 0 && $1->back() > *$2)
{
fault_tree_textual_parser_error(
"Definitions of a given type must be in alphabetical order\n");
delete $1;
}
else
{
$$ = $1;
$$->push_back(*$2);
}
delete $2;
};
or_gate :
IDENTIFIER OR identifier_list SEMICOLON {
if (!Ensure_Input_Order(*$3))
fault_tree_textual_parser_error("Inputs to " + *$1 + " must be sorted");
// Check for duplicate definition
else if (declarations.find(*$1) != declarations.end())
{
string error = "\"" + *$1 +
"\" has already been defined. This definition will be ignored.";
fault_tree_textual_parser_error(error);
}
else
{
declarations.insert(*$1);
Event gate = Event_By_Identifier(*$1);
parsed_fault_tree.Set_Event_Description(gate,*$1);
Input_Sequence inputs = Identifier_List_To_Input_Sequence(*$3);
Input_Sequence::const_iterator an_input_event;
list<string>::const_iterator an_input_identifier;
for (an_input_event = inputs.begin(), an_input_identifier = (*$3).begin();
an_input_event != inputs.end();
an_input_event++, an_input_identifier++)
{
parsed_fault_tree.Set_Event_Description(*an_input_event,*an_input_identifier);
}
parsed_fault_tree.Set_Gate_Inputs(gate,inputs);
parsed_fault_tree.Insert_Or_Gate(gate);
}
$$ = $1;
delete $3;
}
{
if (!m_error_occurred)
{
declarations.erase(*$1);
Event gate = Event_By_Identifier(*$1);
Input_Sequence inputs = parsed_fault_tree.Get_Gate_Inputs(gate);
parsed_fault_tree.Remove_Gate_Inputs(gate);
Input_Sequence::const_iterator an_input_event;
for (an_input_event = inputs.begin(); an_input_event != inputs.end(); an_input_event++)
{
if (parsed_fault_tree.Event_Not_Referenced(*an_input_event))
parsed_fault_tree.Remove_Event_Description(*an_input_event);
}
parsed_fault_tree.Remove_Or_Gate(gate);
if (parsed_fault_tree.Event_Not_Referenced(gate))
parsed_fault_tree.Remove_Event_Description(gate);
}
delete $1;
};
// ---------------------------------------------------------------------------
pands_list_opt :
/* NOTHING */ {
$$ = new list<string>;
} |
pands_list_opt pand_gate {
if ($1->size() > 0 && $1->back() > *$2)
{
fault_tree_textual_parser_error(
"Definitions of a given type must be in alphabetical order\n");
delete $1;
}
else
{
$$ = $1;
$$->push_back(*$2);
}
delete $2;
};
pand_gate :
IDENTIFIER PAND identifier_list SEMICOLON {
// Check for duplicate definition
if (declarations.find(*$1) != declarations.end())
{
string error = "\"" + *$1 +
"\" has already been defined. This definition will be ignored.";
fault_tree_textual_parser_error(error);
}
else
{
declarations.insert(*$1);
Event gate = Event_By_Identifier(*$1);
parsed_fault_tree.Set_Event_Description(gate,*$1);
Input_Sequence inputs = Identifier_List_To_Input_Sequence(*$3);
Input_Sequence::const_iterator an_input_event;
list<string>::const_iterator an_input_identifier;
for (an_input_event = inputs.begin(), an_input_identifier = (*$3).begin();
an_input_event != inputs.end();
an_input_event++, an_input_identifier++)
{
parsed_fault_tree.Set_Event_Description(*an_input_event,*an_input_identifier);
}
parsed_fault_tree.Set_Gate_Inputs(gate,inputs);
parsed_fault_tree.Insert_Pand_Gate(gate);
}
$$ = $1;
delete $3;
}
{
if (!m_error_occurred)
{
declarations.erase(*$1);
Event gate = Event_By_Identifier(*$1);
Input_Sequence inputs = parsed_fault_tree.Get_Gate_Inputs(gate);
parsed_fault_tree.Remove_Gate_Inputs(gate);
Input_Sequence::const_iterator an_input_event;
for (an_input_event = inputs.begin(); an_input_event != inputs.end(); an_input_event++)
{
if (parsed_fault_tree.Event_Not_Referenced(*an_input_event))
parsed_fault_tree.Remove_Event_Description(*an_input_event);
}
parsed_fault_tree.Remove_Pand_Gate(gate);
if (parsed_fault_tree.Event_Not_Referenced(gate))
parsed_fault_tree.Remove_Event_Description(gate);
}
delete $1;
};
// ---------------------------------------------------------------------------
thresholds_list_opt :
/* NOTHING */ {
$$ = new list<string>;
} |
thresholds_list_opt threshold_gate {
if ($1->size() > 0 && $1->back() > *$2)
{
fault_tree_textual_parser_error(
"Definitions of a given type must be in alphabetical order\n");
delete $1;
}
else
{
$$ = $1;
$$->push_back(*$2);
}
delete $2;
};
threshold_gate :
IDENTIFIER THRESHOLD MAXIMUM EQUALS natural_nonterminal identifier_list SEMICOLON {
if (!Ensure_Input_Order(*$6))
fault_tree_textual_parser_error("Inputs to " + *$1 + " must be sorted");
// Check for duplicate definition
else if (declarations.find(*$1) != declarations.end())
{
string error = "\"" + *$1 +
"\" has already been defined. This definition will be ignored.";
fault_tree_textual_parser_error(error);
}
else
{
declarations.insert(*$1);
Event gate = Event_By_Identifier(*$1);
parsed_fault_tree.Set_Event_Description(gate,*$1);
Input_Sequence inputs = Identifier_List_To_Input_Sequence(*$6);
Input_Sequence::const_iterator an_input_event;
list<string>::const_iterator an_input_identifier;
for (an_input_event = inputs.begin(), an_input_identifier = (*$6).begin();
an_input_event != inputs.end();
an_input_event++, an_input_identifier++)
{
parsed_fault_tree.Set_Event_Description(*an_input_event,*an_input_identifier);
}
parsed_fault_tree.Set_Gate_Inputs(gate,inputs);
parsed_fault_tree.Insert_Threshold_Gate(gate,Threshold(*$5));
}
$$ = $1;
delete $5;
delete $6;
}
{
if (!m_error_occurred)
{
declarations.erase(*$1);
Event gate = Event_By_Identifier(*$1);
Input_Sequence inputs = parsed_fault_tree.Get_Gate_Inputs(gate);
parsed_fault_tree.Remove_Gate_Inputs(gate);
Input_Sequence::const_iterator an_input_event;
for (an_input_event = inputs.begin(); an_input_event != inputs.end(); an_input_event++)
{
if (parsed_fault_tree.Event_Not_Referenced(*an_input_event))
parsed_fault_tree.Remove_Event_Description(*an_input_event);
}
parsed_fault_tree.Remove_Threshold_Gate(gate);
if (parsed_fault_tree.Event_Not_Referenced(gate))
parsed_fault_tree.Remove_Event_Description(gate);
}
delete $1;
};
natural_nonterminal:
ZERO {
$$ = new Natural(*$1);
delete $1;
} |
NATURAL {
$$ = new Natural(*$1);
delete $1;
};
// ---------------------------------------------------------------------------
spares_list_opt :
/* NOTHING */ {
$$ = new list<string>;
} |
spares_list_opt spare_gate {
if ($1->size() > 0 && $1->back() > *$2)
{
fault_tree_textual_parser_error(
"Definitions of a given type must be in alphabetical order\n");
delete $1;
}
else
{
$$ = $1;
$$->push_back(*$2);
}
delete $2;
};
spare_gate :
IDENTIFIER SPARE identifier_list SEMICOLON {
// Check for duplicate definition
if (declarations.find(*$1) != declarations.end())
{
string error = "\"" + *$1 +
"\" has already been defined. This definition will be ignored.";
fault_tree_textual_parser_error(error);
}
else
{
declarations.insert(*$1);
Event gate = Event_By_Identifier(*$1);
parsed_fault_tree.Set_Event_Description(gate,*$1);
Input_Sequence inputs = Identifier_List_To_Input_Sequence(*$3);
Input_Sequence::const_iterator an_input_event;
list<string>::const_iterator an_input_identifier;
for (an_input_event = inputs.begin(), an_input_identifier = (*$3).begin();
an_input_event != inputs.end();
an_input_event++, an_input_identifier++)
{
parsed_fault_tree.Set_Event_Description(*an_input_event,*an_input_identifier);
}
parsed_fault_tree.Set_Gate_Inputs(gate,inputs);
parsed_fault_tree.Insert_Spare_Gate(gate);
}
$$ = $1;
delete $3;
}
{
if (!m_error_occurred)
{
declarations.erase(*$1);
Event gate = Event_By_Identifier(*$1);
Input_Sequence inputs = parsed_fault_tree.Get_Gate_Inputs(gate);
parsed_fault_tree.Remove_Gate_Inputs(gate);
Input_Sequence::const_iterator an_input_event;
for (an_input_event = inputs.begin(); an_input_event != inputs.end(); an_input_event++)
{
if (parsed_fault_tree.Event_Not_Referenced(*an_input_event))
parsed_fault_tree.Remove_Event_Description(*an_input_event);
}
parsed_fault_tree.Remove_Spare_Gate(gate);
if (parsed_fault_tree.Event_Not_Referenced(gate))
parsed_fault_tree.Remove_Event_Description(gate);
}
delete $1;
};
// ---------------------------------------------------------------------------
fdeps_list_opt :
/* NOTHING */ {
$$ = new list<string>;
} |
fdeps_list_opt fdep_constraint {
if ($1->size() > 0 && $1->back() > *$2)
{
fault_tree_textual_parser_error(
"Definitions of a given type must be in alphabetical order\n");
delete $1;
}
else
{
$$ = $1;
$$->push_back(*$2);
}
delete $2;
};
fdep_constraint :
IDENTIFIER FDEP TRIGGER EQUALS IDENTIFIER identifier_list SEMICOLON {
// Check for duplicate definition
if (!Ensure_Input_Order(*$6))
fault_tree_textual_parser_error("Dependents for " + *$1 + " must be sorted");
else if (declarations.find(*$1) != declarations.end())
{
string error = "\"" + *$1 +
"\" has already been defined. This definition will be ignored.";
fault_tree_textual_parser_error(error);
}
else
{
// Using a global this way is really ugly, but I need to pass back
// the threshold value somehow.
Input_Sequence dependents = Identifier_List_To_Input_Sequence(*$6);
Event trigger = Event_By_Identifier(*$5);
Functional_Dependency an_fdep;
an_fdep.Set_Trigger(trigger);
an_fdep.Set_Dependents(dependents);
if (parsed_fault_tree.Get_FDEP_Constraints().find(an_fdep) !=
parsed_fault_tree.Get_FDEP_Constraints().end())
{
string error = "\"" + *$1 +
"\" has already been defined as \"" +
parsed_fault_tree.Get_FDEP_Description(an_fdep) + "\". This definition will be ignored.";
fault_tree_textual_parser_error(error);
}
else
{
declarations.insert(*$1);
Input_Sequence::const_iterator an_input_event;
list<string>::const_iterator an_input_identifier;
for (an_input_event = dependents.begin(), an_input_identifier = (*$6).begin();
an_input_event != dependents.end();
an_input_event++, an_input_identifier++)
{
parsed_fault_tree.Set_Event_Description(*an_input_event,*an_input_identifier);
}
parsed_fault_tree.Set_Event_Description(an_fdep.Get_Trigger(),*$5);
parsed_fault_tree.Insert_FDEP_Constraint(an_fdep);
parsed_fault_tree.Set_FDEP_Description(an_fdep,*$1);
}
}
delete $1;
delete $5;
delete $6;
}
{
if (!m_error_occurred)
{
declarations.erase(*$1);
Input_Sequence dependents = Identifier_List_To_Input_Sequence(*$6);
Functional_Dependency an_fdep;
an_fdep.Set_Trigger(Event_By_Identifier(*$5));
an_fdep.Set_Dependents(dependents);
parsed_fault_tree.Remove_FDEP_Constraint(an_fdep);
parsed_fault_tree.Remove_FDEP_Description(an_fdep);
Input_Sequence::const_iterator an_input_event;
for (an_input_event = dependents.begin(); an_input_event != dependents.end(); an_input_event++)
{
if (parsed_fault_tree.Event_Not_Referenced(*an_input_event))
parsed_fault_tree.Remove_Event_Description(*an_input_event);
}
}
if (parsed_fault_tree.Event_Not_Referenced(Event_By_Identifier(*$5)))
parsed_fault_tree.Remove_Event_Description(Event_By_Identifier(*$5));
delete $1;
delete $5;
delete $6;
};
// ---------------------------------------------------------------------------
seqs_list_opt :
/* NOTHING */ {
$$ = new list<string>;
} |
seqs_list_opt seq_constraint {
if ($1->size() > 0 && $1->back() > *$2)
{
fault_tree_textual_parser_error(
"Definitions of a given type must be in alphabetical order\n");
delete $1;
}
else
{
$$ = $1;
$$->push_back(*$2);
}
delete $2;
};
seq_constraint :
IDENTIFIER SEQ identifier_list SEMICOLON {
// Check for duplicate definition
if (declarations.find(*$1) != declarations.end())
{
string error = "\"" + *$1 +
"\" has already been defined. This definition will be ignored.";
fault_tree_textual_parser_error(error);
}
else
{
Input_Sequence seq = Identifier_List_To_Input_Sequence(*$3);
if (parsed_fault_tree.Get_SEQ_Constraints().find(seq) !=
parsed_fault_tree.Get_SEQ_Constraints().end())
{
string error = "\"" + *$1 +
"\" has already been defined as \"" +
parsed_fault_tree.Get_SEQ_Description(seq) + "\". This definition will be ignored.";
fault_tree_textual_parser_error(error);
}
else
{
declarations.insert(*$1);
Input_Sequence::const_iterator an_input_event;
list<string>::const_iterator an_input_identifier;
for (an_input_event = seq.begin(), an_input_identifier = (*$3).begin();
an_input_event != seq.end();
an_input_event++, an_input_identifier++)
{
parsed_fault_tree.Set_Event_Description(*an_input_event,*an_input_identifier);
}
parsed_fault_tree.Insert_SEQ_Constraint(seq);
parsed_fault_tree.Set_SEQ_Description(seq,*$1);
}
}
delete $1;
delete $3;
}
{
if (!m_error_occurred)
{
declarations.erase(*$1);
Input_Sequence seq = Identifier_List_To_Input_Sequence(*$3);
parsed_fault_tree.Remove_SEQ_Constraint(seq);
parsed_fault_tree.Remove_SEQ_Description(seq);
Input_Sequence::const_iterator an_input_event;
for (an_input_event = seq.begin(); an_input_event != seq.end(); an_input_event++)
{
if (parsed_fault_tree.Event_Not_Referenced(*an_input_event))
parsed_fault_tree.Remove_Event_Description(*an_input_event);
}
}
delete $1;
delete $3;
};
// ---------------------------------------------------------------------------
basic_events_list :
basic_event {
$$ = new list<string>;
$$->push_back(*$1);
delete $1;
} |
basic_events_list basic_event {
$$ = $1;
// Check for out-of-order definition.
if ($1->size() > 0 && *$2 < $1->back())
{
string error = "\"" + *$2 +
"\" is not sorted correctly. This definition will be ignored.";
fault_tree_textual_parser_error(error);
}
else
{
$$->push_back(*$2);
}
delete $2;
};
basic_event:
IDENTIFIER BE SEMICOLON {
// Check for duplicate definition
if (declarations.find(*$1) != declarations.end())
{
string error = "\"" + *$1 +
"\" has already been defined. This definition will be ignored.";
fault_tree_textual_parser_error(error);
}
else
{
declarations.insert(*$1);
Event basic_event = Event_By_Identifier(*$1);
parsed_fault_tree.Insert_Basic_Event(basic_event,1);
parsed_fault_tree.Set_Event_Description(basic_event,*$1);
}
$$ = $1;
}
{
if (!m_error_occurred)
{
declarations.erase(*$1);
Event basic_event = Event_By_Identifier(*$1);
parsed_fault_tree.Remove_Basic_Event(basic_event);
if (parsed_fault_tree.Event_Not_Referenced(basic_event))
parsed_fault_tree.Remove_Event_Description(basic_event);
}
delete $1;
} |
IDENTIFIER BE REPLICATION EQUALS NATURAL SEMICOLON {
// Check for duplicate definition
if (declarations.find(*$1) != declarations.end())
{
string error = "\"" + *$1 +
"\" has already been defined. This definition will be ignored.";
fault_tree_textual_parser_error(error);
}
else
{
declarations.insert(*$1);
Event basic_event = Event_By_Identifier(*$1);
parsed_fault_tree.Insert_Basic_Event(basic_event,Replication(*$5));
parsed_fault_tree.Set_Event_Description(basic_event,*$1);
}
$$ = $1;
delete $5;
}
{
if (!m_error_occurred)
{
declarations.erase(*$1);
Event basic_event = Event_By_Identifier(*$1);
parsed_fault_tree.Remove_Basic_Event(basic_event);
if (parsed_fault_tree.Event_Not_Referenced(basic_event))
parsed_fault_tree.Remove_Event_Description(basic_event);
}
delete $1;
};
// ---------------------------------------------------------------------------
identifier_list:
IDENTIFIER {
$$ = new list<string>;
$$->push_back(*$1);
delete $1;
} |
identifier_list IDENTIFIER {
if ( find($1->begin(),$1->end(),*$2) != $1->end() )
{
string error = '"' + *$2 +
"\" is listed twice in this identifier list." +
" The second definition will be ignored.";
fault_tree_textual_parser_error(error);
delete $1;
}
else
{
$$ = $1;
$$->push_back(*$2);
}
delete $2;
};
// ---------------------------------------------------------------------------
%%
void fault_tree_textual_parser_parser_initialize(FILE* in_input_file)
{
fault_tree_textual_parser_scanner_initialize(in_input_file);
declarations.clear();
parsed_fault_tree.Clear();
identifiers_to_events.clear();
fault_tree_textual_parser_lineno = 1;
}
// ---------------------------------------------------------------------------
/*
* Given a identifier, determines if the identifier has been associated with
* an event. If it has, a copy of the event is returned. If it hasn't, then a
* new event is created.
*/
const Event Event_By_Identifier(const string &in_identifier)
{
bijection<string, Event>::const_iterator the_event =
identifiers_to_events.find(in_identifier);
if (the_event != identifiers_to_events.end())
{
// Already encountered this identifier and created an event for it
return the_event->second;
}
else
{
// Add the new event and identifier
Event new_event;
identifiers_to_events[in_identifier] = new_event;
return new_event;
}
}
// ---------------------------------------------------------------------------
/*
* Converts a list of identifiers into an input sequence by looking up the
* events associated with the identifiers
*/
const Input_Sequence Identifier_List_To_Input_Sequence(const list<string> &in_identifiers)
{
Input_Sequence inputs;
for (list<string>::const_iterator it = in_identifiers.begin();
it != in_identifiers.end();it++)
{
Event event = Event_By_Identifier(*it);
inputs.push_back(event);
}
return inputs;
}
// ---------------------------------------------------------------------------
// If a cycle is found, it is left in in_path
const bool Cycle_Exists(searchable_list<Event>& in_path, set<Event> &in_events_to_visit)
{
in_events_to_visit.erase(in_path.back());
if (parsed_fault_tree.Get_Gates().find(in_path.back()) == parsed_fault_tree.Get_Gates().end())
return false;
Input_Sequence::const_iterator an_input;
for(an_input = parsed_fault_tree.Get_Gate_Inputs(in_path.back()).begin(); an_input != parsed_fault_tree.Get_Gate_Inputs(in_path.back()).end(); an_input++)
{
searchable_list<Event>::iterator location = in_path.find(*an_input);
if (location != in_path.end())
{
in_path.erase(in_path.begin(), location);
return true;
}
in_path.push_back(*an_input);
if (Cycle_Exists(in_path, in_events_to_visit))
return true;
in_path.pop_back();
}
return false;
}
// ---------------------------------------------------------------------------
const bool Ensure_Valid_System_Event()
{
// Check the system level event
if (parsed_fault_tree.Get_Events().find(parsed_fault_tree.Get_System_Event()) ==
parsed_fault_tree.Get_Events().end())
{
string error = "The system level event named " +
parsed_fault_tree.Get_Event_Description(parsed_fault_tree.Get_System_Event()) +
" is not in the fault tree.";
fault_tree_textual_parser_error(error);
return false;
}
return true;
}
// ---------------------------------------------------------------------------
const bool Ensure_No_Cycles_In_Inputs()
{
set<Event> parent_events;
set<Event> events_to_visit = parsed_fault_tree.Get_Events();
set<Event>::const_iterator an_event;
for(an_event = parsed_fault_tree.Get_Events().begin(); an_event != parsed_fault_tree.Get_Events().end(); an_event++)
{
if (parsed_fault_tree.Get_Gates_Event_Is_Input_To(*an_event).size() == 0)
parent_events.insert(*an_event);
}
// First we traverse starting with the parent events. This will hopefully
// visit all the events
// set<Event>::const_iterator an_event;
for(an_event = parent_events.begin(); an_event != parent_events.end(); an_event++)
{
searchable_list<Event> path;
path.push_back(*an_event);
if (Cycle_Exists(path, events_to_visit))
{
string error = "There is a cycle in the fault tree: ";
searchable_list<Event>::const_iterator a_cycle_event;
for(a_cycle_event = path.begin(); a_cycle_event != path.end(); a_cycle_event++)
error += parsed_fault_tree.Get_Event_Description(*a_cycle_event) + " -> ";
error += parsed_fault_tree.Get_Event_Description(path.front());
fault_tree_textual_parser_error(error);
return false;
}
}
// Now visit the remaining nodes
while (!events_to_visit.empty())
{
searchable_list<Event> path;
path.push_back(*(events_to_visit.begin()));
if (Cycle_Exists(path, events_to_visit))
{
string error = "There is a cycle in the fault tree: ";
searchable_list<Event>::const_iterator a_cycle_event;
for(a_cycle_event = path.begin(); a_cycle_event != path.end(); a_cycle_event++)
error += parsed_fault_tree.Get_Event_Description(*a_cycle_event) + " -> ";
error += parsed_fault_tree.Get_Event_Description(path.front());
fault_tree_textual_parser_error(error);
return false;
}
}
// We can get here if there are events that are not inputs to any gates,
// such as triggers for FDEPs or inputs to SEQs.
return true;
}
// ---------------------------------------------------------------------------
const bool Ensure_Corresponding_References_And_Definitions()
{
const set<Event> events = parsed_fault_tree.Get_Events();
const set<Event> gates = parsed_fault_tree.Get_Gates();
set<Event>::const_iterator aGate;
for (aGate = gates.begin(); aGate != gates.end(); aGate++)
{
const Input_Sequence inputs = parsed_fault_tree.Get_Gate_Inputs(*aGate);
Input_Sequence::const_iterator anInput;
for (anInput = inputs.begin();anInput != inputs.end();anInput++)
{
if (events.find(*anInput) == events.end())
{
string error = '"' + Get_Identifier_For_Event(*anInput) +
"\" is an input to gate \"" +
parsed_fault_tree.Get_Event_Description(*aGate) +
"\" but is not defined.";
fault_tree_textual_parser_error(error);
return false;
}
}
}
const set<Input_Sequence> seqs = parsed_fault_tree.Get_SEQ_Constraints();
set<Input_Sequence>::const_iterator aSeq;
for (aSeq = seqs.begin(); aSeq != seqs.end(); aSeq++)
{
const Input_Sequence inputs = *aSeq;
Input_Sequence::const_iterator anInput;
for (anInput = inputs.begin();anInput != inputs.end();anInput++)
{
if (events.find(*anInput) == events.end())
{
string error = '"' + Get_Identifier_For_Event(*anInput) +
"\" is an input to sequence enforcer \"" +
parsed_fault_tree.Get_SEQ_Description(*aSeq) +
"\" but is not defined.";
fault_tree_textual_parser_error(error);
return false;
}
}
}
const set<Functional_Dependency> fdeps = parsed_fault_tree.Get_FDEP_Constraints();
set<Functional_Dependency>::const_iterator an_fdep;
for (an_fdep = fdeps.begin(); an_fdep != fdeps.end(); an_fdep++)
{
const Event trigger = (*an_fdep).Get_Trigger();
const Input_Sequence dependents = (*an_fdep).Get_Dependents();
if (events.find(trigger) == events.end())
{
string error = '"' + Get_Identifier_For_Event(trigger) +
"\" is a trigger for the functional dependency \"" +
parsed_fault_tree.Get_FDEP_Description(*an_fdep) +
"\" but is not defined.";
fault_tree_textual_parser_error(error);
return false;
}
Input_Sequence::const_iterator aDependent;
for (aDependent = dependents.begin();aDependent != dependents.end();aDependent++)
{
if (events.find(*aDependent) == events.end())
{
string error = '"' + Get_Identifier_For_Event(*aDependent) +
"\" is a dependent input to the functional dependency \"" +
parsed_fault_tree.Get_FDEP_Description(*an_fdep) +
"\" but is not defined.";
fault_tree_textual_parser_error(error);
return false;
}
}
}
return true;
}
// ---------------------------------------------------------------------------
const bool Ensure_Spare_Gate_Inputs_Are_Basic_Events()
{
set<Event>::const_iterator a_spare_gate;
for(a_spare_gate = parsed_fault_tree.Get_Spare_Gates().begin(); a_spare_gate != parsed_fault_tree.Get_Spare_Gates().end(); a_spare_gate++)
{
Input_Sequence::const_iterator an_input;
for(an_input = parsed_fault_tree.Get_Gate_Inputs(*a_spare_gate).begin(); an_input != parsed_fault_tree.Get_Gate_Inputs(*a_spare_gate).end(); an_input++)
{
set<Event> gates_basic_event_is_input_to = parsed_fault_tree.Get_Gates_Event_Is_Input_To(*an_input);
set<Event>::const_iterator a_gate_input_to;
for(a_gate_input_to = gates_basic_event_is_input_to.begin(); a_gate_input_to != gates_basic_event_is_input_to.end(); a_gate_input_to++)
{
if(parsed_fault_tree.Get_Spare_Gates().find(*a_gate_input_to) == parsed_fault_tree.Get_Spare_Gates().end())
{
string error = "The input \"" + parsed_fault_tree.Get_Event_Description(*an_input) +
"\" for spare gate \"" + parsed_fault_tree.Get_Event_Description(*a_spare_gate) +
"\" is also input to the gate \"" + parsed_fault_tree.Get_Event_Description(*a_gate_input_to) +
"\" which is not a spare gate.";
fault_tree_textual_parser_error(error);
return false;
}
}
}
}
return true;
}
// ---------------------------------------------------------------------------
const bool Ensure_Spare_Gate_Inputs_Only_Input_To_Spare_Gates()
{
set<Event>::const_iterator a_spare_gate;
for(a_spare_gate = parsed_fault_tree.Get_Spare_Gates().begin(); a_spare_gate != parsed_fault_tree.Get_Spare_Gates().end(); a_spare_gate++)
{
Input_Sequence::const_iterator an_input;
for(an_input = parsed_fault_tree.Get_Gate_Inputs(*a_spare_gate).begin(); an_input != parsed_fault_tree.Get_Gate_Inputs(*a_spare_gate).end(); an_input++)
{
if(parsed_fault_tree.Get_Basic_Events().find(*an_input) == parsed_fault_tree.Get_Basic_Events().end())
{
string error = "The input \"" + parsed_fault_tree.Get_Event_Description(*an_input) +
"\" for spare gate \"" + parsed_fault_tree.Get_Event_Description(*a_spare_gate) +
"\" is not a basic event.";
fault_tree_textual_parser_error(error);
return false;
}
}
}
return true;
}
// ---------------------------------------------------------------------------
const bool Ensure_FDEP_Trigger_Is_Not_Replicated()
{
set<Functional_Dependency>::const_iterator an_fdep;
for(an_fdep = parsed_fault_tree.Get_FDEP_Constraints().begin(); an_fdep != parsed_fault_tree.Get_FDEP_Constraints().end(); an_fdep++)
{
if(parsed_fault_tree.Get_Replication((*an_fdep).Get_Trigger()) > (Natural)1)
{
string error = "The trigger input \"" + parsed_fault_tree.Get_Event_Description((*an_fdep).Get_Trigger()) +
"\" for the functional dependency \"" + parsed_fault_tree.Get_FDEP_Description(*an_fdep) +
"\" has a replication greater than 1.";
fault_tree_textual_parser_error(error);
return false;
}
}
return true;
}
// ---------------------------------------------------------------------------
const bool Ensure_FDEP_Dependents_Are_Basic_Events()
{
set<Functional_Dependency>::const_iterator an_fdep;
for(an_fdep = parsed_fault_tree.Get_FDEP_Constraints().begin(); an_fdep != parsed_fault_tree.Get_FDEP_Constraints().end(); an_fdep++)
{
Input_Sequence::const_iterator a_dependent;
for(a_dependent = (*an_fdep).Get_Dependents().begin(); a_dependent != (*an_fdep).Get_Dependents().end(); a_dependent++)
{
if(parsed_fault_tree.Get_Basic_Events().find(*a_dependent) == parsed_fault_tree.Get_Basic_Events().end())
{
string error = "The depedent input \"" + parsed_fault_tree.Get_Event_Description(*a_dependent) +
"\" for the functional dependency \"" + parsed_fault_tree.Get_FDEP_Description(*an_fdep) +
"\" is not a basic event.";
fault_tree_textual_parser_error(error);
return false;
}
}
}
return true;
}
// ---------------------------------------------------------------------------
const string Get_Identifier_For_Event(const Event &in_event)
{
if (identifiers_to_events.inverse_find(in_event) != identifiers_to_events.end())
return identifiers_to_events.inverse_apply(in_event);
else
return NOT_FOUND;
}
// ---------------------------------------------------------------------------
// This algorithm works by tracking the set of seen events. We initialize the
// seen events set, then we iterate over the remaining unseen events of the
// fault tree. We construct a temporary set of seen events, and merge this set
// with the main set if we encounter an event which is already in the main set.
// If we can't do this, then we know that the temporary set is disjoint, and
// we don't have a connected fault tree.
const bool Ensure_Connectedness()
{
set<Event> parent_events;
set<Event>::const_iterator an_event;
for(an_event = parsed_fault_tree.Get_Events().begin(); an_event != parsed_fault_tree.Get_Events().end(); an_event++)
{
if (parsed_fault_tree.Get_Gates_Event_Is_Input_To(*an_event).size() == 0)
parent_events.insert(*an_event);
}
set< Event > seen_events;
set< Event > local_seen_events;
// set<Event>::const_iterator an_event;
for(an_event = parent_events.begin(); an_event != parent_events.end(); an_event++)
{
if (!Compute_Reachable_Events(*an_event, seen_events, local_seen_events) && !seen_events.empty())
{
fault_tree_textual_parser_error("The fault tree is not fully connected");
return false;
}
set_union(seen_events.begin(), seen_events.end(),
local_seen_events.begin(), local_seen_events.end(),
inserter(seen_events,seen_events.begin()));
local_seen_events.clear();
}
return true;
}
// ---------------------------------------------------------------------------
// Returns true if the local search space connects to the seen events
const bool Compute_Reachable_Events(const Event& in_event,
const set<Event>& in_seen_events, set<Event>& in_local_seen_events)
{
// Avoid cycles
if (in_local_seen_events.find(in_event) != in_local_seen_events.end())
return false;
// Check for connected and avoid extra work
if (in_seen_events.find(in_event) != in_seen_events.end())
return true;
in_local_seen_events.insert(in_event);
bool connected = false;
// If it's a gate, recurse into the inputs
if(parsed_fault_tree.Get_Gates().find(in_event) != parsed_fault_tree.Get_Gates().end())
{
Input_Sequence::const_iterator an_input;
for(an_input = parsed_fault_tree.Get_Gate_Inputs(in_event).begin();
an_input != parsed_fault_tree.Get_Gate_Inputs(in_event).end();
an_input++)
{
if (Compute_Reachable_Events(*an_input, in_seen_events,
in_local_seen_events))
connected = true;
}
}
// Check to see if it's the input to a sequence enforcer
set<Input_Sequence>::const_iterator an_seq;
for(an_seq = parsed_fault_tree.Get_SEQ_Constraints().begin();
an_seq != parsed_fault_tree.Get_SEQ_Constraints().end();
an_seq++)
{
if (an_seq->find(in_event) != an_seq->end())
{
Input_Sequence::const_iterator an_input;
for(an_input = an_seq->begin(); an_input != an_seq->end(); an_input++)
{
if (Compute_Reachable_Events(*an_input,in_seen_events,
in_local_seen_events))
connected = true;
}
}
}
// Check to see if it's a dependent or trigger for a functional dependency
set<Functional_Dependency>::const_iterator a_functional_dependency;
for(a_functional_dependency = parsed_fault_tree.Get_FDEP_Constraints().begin();
a_functional_dependency != parsed_fault_tree.Get_FDEP_Constraints().end();
a_functional_dependency++)
{
if ((a_functional_dependency->Get_Trigger() == in_event) ||
(a_functional_dependency->Get_Dependents().find(in_event) !=
a_functional_dependency->Get_Dependents().end()))
{
if (Compute_Reachable_Events(a_functional_dependency->Get_Trigger(),
in_seen_events, in_local_seen_events))
connected = true;
Input_Sequence::const_iterator an_input;
for(an_input = a_functional_dependency->Get_Dependents().begin();
an_input != a_functional_dependency->Get_Dependents().end();
an_input++)
{
if (Compute_Reachable_Events(*an_input, in_seen_events,
in_local_seen_events))
connected = true;
}
}
}
return connected;
}
// ---------------------------------------------------------------------------
const bool Ensure_Input_Order(const list<string> &in_list)
{
list<string>::const_iterator an_input_identifier;
for(an_input_identifier = in_list.begin();
an_input_identifier != in_list.end();
an_input_identifier++)
{
list<string>::const_iterator next_input_identifier =
an_input_identifier;
next_input_identifier++;
if (next_input_identifier == in_list.end())
break;
if (*an_input_identifier > *next_input_identifier)
{
#ifdef DEBUG_FAULT_TREE_CONSTRAINTS
cerr << "CNSTR: " << Utility::indent << "--> NOT VALID" << endl;
#endif // DEBUG_FAULT_TREE_CONSTRAINTS
fault_tree_textual_parser_error("Inputs must be in order");
return false;
}
}
return true;
}
// ---------------------------------------------------------------------------
/*
Sample main file
#include <string>
#include <cstdio>
#include "fault_tree_textual_parser/fault_tree_textual_parser_includes.h"
#include "y.tab.h"
extern FILE *fault_tree_textual_parser_in;
extern int fault_tree_textual_parser_parse();
extern void fault_tree_textual_parser_parser_initialize(FILE *in_input_file);
int main(int argc, char *argv[]) {
fault_tree_textual_parser_in = fopen(argv[1], "r");
fault_tree_textual_parser_parser_initialize(fault_tree_textual_parser_in);
fault_tree_textual_parser_parse();
// Not freed by yacc
free(fault_tree_textual_parser_ss);
fault_tree_textual_parser_ss = NULL;
free(fault_tree_textual_parser_vs);
fault_tree_textual_parser_vs = NULL;
fclose(fault_tree_textual_parser_in);
if (fault_tree_textual_parser_error_string != "")
printf("ERRORS!\n%s", fault_tree_textual_parser_error_string.c_str());
return 0;
}
*/