Hallo,
nachdem ich im letzten Posting zu diesem Thema einige grundlegende Überlegungen zum Einsatz der boost::spirit C++ parser library beschrieben habe möchte ich heute den konkreten Einsatz in dem bereits beschriebenen Beispiel zeigen.
Für den beschriebenen Ansatz werden folgende Include-Direktiven benötigt:
//lint -save -elib(*)
#include <boost/spirit/core.hpp>
#include <boost/spirit/tree/tree_to_xml.hpp>
#include <boost/spirit/tree/parse_tree.hpp>
//lint -restore
Die spirit header files sind nicht “PC-Lint clean”, weshalb entsprechende warnings unterdrückt werden sollten. Da boost::spirit eine “header only” library ist, sind keine weiteren Eingabedaten für den linker erforderlich.
Hier sind einige typedefs, die die Nutzung der boost-Klassen erleichtern. Ich habe sie in einem “anonymous namespace” innerhalb des entsprechenden cpp-files definiert:
typedef char const* iterator_t;
typedef tree_match<iterator_t> parse_tree_match_t;
typedef parse_tree_match_t::const_tree_iterator iter_t;
typedef pt_match_policy<iterator_t> match_policy_t;
typedef scanner_policies<skip_parser_iteration_policy<space_parser>, match_policy_t, action_policy> scanner_policy_t;
typedef scanner<iterator_t, scanner_policy_t> scanner_t;
typedef rule<scanner_t> rule_t;
Nun kann man den Parser selbst definieren. Dies ist z.B. bei kleineren Grammatiken die nicht oft aufgerufen werden direkt in der Methode die das parsen übernimmt, möglich.
Fangen wir mit den Regeln (nonterminals) an:
InstantiatedTypeParser::parse(char marker, const std::string& instantiatedType)
{
rule_t path_sep;
rule_t identifier;
rule_t path;
rule_t single_type;
rule_t instantiated_type_list;iund hier die eigentliche Grammatik, der EBNF-Form nicht unähnlich:
path_sep = token_node_d[(ch_p(':') >> ch_p(':'))]
;
identifier = token_node_d[((alpha_p | ch_p('_')) >> *(alnum_p | ch_p('_')))]
;
path = identifier >> *(path_sep >> identifier)
;
single_type = path >> ch_p(m_startMarker)
>> path
>> ch_p(m_endMarker)
;
instantiated_type_list = single_type
|
path >> ch_p(m_startMarker)
>> instantiated_type_list
>> ch_p(m_endMarker)
;Hier der eigentliche Aufruf des parser:
const char* first = instantiatedType.c_str();
tree_parse_info<> info = pt_parse(first, instantiated_type_list, space_p);
Das zurückgegebene Objekt vom Type tree_parse_info gibt nun Auskunft darüber, ob die Eingabe komplett gelesen wurde (was bedeutet, dass sie syntaktisch korrekt ist) oder ob ein Fehler aufgetreten ist. Eine Fehlerbehandlung könnte z.B. so aussehen:
if (info.full)
{
evaluate(path.id(), identifier.id(), result, info.trees.begin());
}
else
{
std::ostringstream msg;
msg << "Invalid syntax in instantiated type '" << instantiatedType
<< "' at character position " << (info.stop - first) + 1
<<". Invalid character: '" << *info.stop
<< "'.";
throw std::runtime_error(msg.str());
}Falls das parsen erfolgreich war, kann dem zurückgegeben tree_parse_info-Objekt der komplette parse tree entnommen und verarbeitet werden. Die Struktur und Beschreibung des parse trees ist ziemlich kompliziert und ich fand es hilfreich, mir von spirit ein xml-Dokument aus dem parse tree erzeugen zu lassen um ihn besser zu verstehen:
std::map
rule_names;
rule_names[path_sep.id()] = "pathsep";
rule_names[path.id()] = "path";
rule_names[identifier.id()] = "identifier";
rule_names[single_type.id()] = "single_type";
rule_names[instantiated_type_list.id()] = "instantiated_type_list";
tree_to_xml(std::cout, info.trees, first, rule_names);
Dies macht es leichter eine Methode zu schreiben, die den parse tree auswertet. In unserem Beispiel sieht diese Methode so aus:
/**
* Processes the parse tree returned by the spirit tree parser.
* The parse tree is not intuitively to understand.
*
* We use a tree parser instead of semantic actions because the grammar is
* ambiguous and semantic actions cannot easily be undone during
* backtracking.
*/
void evaluate(const parser_id& parentId,
const parser_id& childId,
et::ocl::InstantiatedTypeParser::TypeList& result,
const iter_t& node)
{
if (node->value.id() == parentId)
{
std::ostringstream path;
/*
* Collect all child nodes of type childId.
* These are the actual identifiers.
*/
for (iter_t child = node->children.begin();
child != node->children.end();
++child)
{
if (child->value.id() == childId)
{
/*
* Look at the xml parse tree to understand the
* following code.
* For unknown reasons, the parse tree contains
* always two nested nodes for an identifier rule
* and only the child node contains the actual
* identifier.
*/
assert(child->children[0].value.id() == childId);
std::string value(child->children[0].value.begin(),
child->children[0].value.end());
if (path.str().size() > 0)
{
path << "::";
}
path << value;
}
}
std::string p = path.str();
et::base::trim(p);
result.push_back(p);
}
for (iter_t child = node->children.begin();
child != node->children.end();
++child)
{
evaluate(parentId, childId, result, child);
}
}Insgesamt würde ich sagen dass boost::spirit eine echte Alternative ist wenn man einen kleinen Parser in eine C++ Anwendung integrieren möchte. Bei komplexeren Grammatiken würde ich einem richtigen parser generator wie ANTLR den Vorzug geben.
Noch eine Anmerkung: wenn man das warning level in Visual Studio sinnvollerweise auf 4 setzt und ebenso sinnvollerweise die Option “Warnings as errors” aktiviert, verursacht die Spirit header files warnings die zu einem Abbruch des builds führen. Abhilfe schafft es, für die Dateien die diese header files einbinden, die Warnungen 4512, 4127 und 4996 zu deaktivieren.
Technorati Tags: C++, parser, boost, spirit
Viele Grüße,
Andreas
