3. boost::spirit Rekursions-Probleme [gelöst] + [neu] Probleme beim File Handling

boost::spirit Rekursions-Probleme [gelöst] + [neu] Probleme beim File Handling

  • ?

    Hallo miteinander,

    ich habe mit in die Dokumentation von boost eingelesen und will nun meinen selbstentwickelten Compiler für boost umschreiben, habe jedoch Probleme, die ich darauf zurückführe, dass es Probleme bei einer Rekursion gibt. Hier jedoch erstmal ein einfacher Testcode, der folgende Grammatik unterstützen sollte.

    nondigit   ::= ( ALPHA_CHARACTER | '_' ).
digit      ::= DIGIT.
identifier ::= ( nondigit | identifier nondigit | identifier digit ).

    #include <boost\spirit.hpp>
#include <iostream>
#include <iterator>
#include <algorithm>

using namespace boost::spirit;

#define ALPHA_CHARACTER (range<>('a', 'z') | range<>('A', 'Z') | chlit<>('$'))
#define DIGIT (chlit<>('0') | chlit<>('1') | chlit<>('2') | chlit<>('3') | chlit<>('4') | chlit<>('5') | chlit<>('6') | chlit<>('7') | chlit<>('8') | chlit<>('9'))

int main(int argc, char** argv)
{
	rule<> nondigit_p = (ALPHA_CHARACTER | chlit<>('_'));
	rule<> digit_p = DIGIT;
	rule<> identifier_p = (nondigit_p | (identifier_p >> nondigit_p) | (identifier_p >> digit_p));

	std::string str;
	while(getline(std::cin, str)) {
		if(str.empty() || str[0] == 'q' || str[0] == 'Q')
			break;

		if(parse(str.c_str(), identifier_p).full) {
			std::cout << "-------------------------\n";
			std::cout << "Parsing succeeded\n";
			std::cout << str << " Parses OK: " << std::endl;
		}
		else {
			std::cout << "-------------------------\n";
			std::cout << "Parsing failed\n";
			std::cout << "-------------------------\n";
		}
	}

	std::cout << "Bye... :-) \n\n";
    return 0;
}

    Leider funktioniert nur die Eingabe von '_', '$', einem beliebigen char aus A..Za..z, aber wenn ich bloß eine Ziffer eingebe, stürzt das Programm ab und bei einem Text von zwei Zeichen (egal ob char oder mit Ziffer) wird die Eingabe nicht geparsed!

    Eine Ahnung, was das Problem sein könnte und wie es zu beheben ist?

    Gruß,
    Christian

    0
  • W

    Ich weiß nicht, ob boost::spirit rekursive Regeln unterstützt. Warum formulierst du identifier_p nicht als *nondigit_p >> (nondigit_p | digit_p) ?

    0
  • ?

    Ich wollte in meiner EBNF-Notation Kleene-Sterne weglassen, wie es auch in der C++-EBNF-Notation der Fall ist. Aber dein Vorschlag ist ja logisch und klappt. D.h. ich werde wohl oder über, nachher bei komplexen Regeln, die auf sich selber verweisen bisschen tricksen müssen, wenn es dazu kommen sollte 😉

    Mit 2 Promille ist es auch schwer gewesen darauf zu kommen 😛 Aber danke nochmal.

    Gruß,
    Christian

    PS: Wenn ich wieder dieses Problem habe, werde ich diesen Topic einfach pushen und neu nachfragen.

    0
  • O

    Du hast dort eine linksrekursion. Die kann spirit nicht, weil das ein linksrekursiver Parser ist. rechts-rekursionen sind aber kein Problem. DU musst also dafür sorgen, dass du immer mindestens ein echtes Zeichen ließt, bevor du eine Rekursionsebene tiefer gehst.

    Sonst macht Spirit das:

    identifier->nondigit (false)
identifier->identifier
    identifier->nondigit(false)
    identifier->identifier
        identifier->nondigit (false)
        identifier->identifier
//usw

    man kann übrigens jede Linksrekursion entfernen. In diesem Fall mit dem Kleene-Stern, oder direkt mit einer rechtsrekursion.

    identifier ::= ( nondigit | nondigit identifier | digit identifier)
    0
  • ?

    Danke für den Hinweis. Beim Durchsuchen meiner Vorlesungsfolien (Theoretische Informatik) habe ich so einen ähnlichen Zusammenhang/Sachverhalt gefunden. Da sieht man, wie gut es doch ist, vieles aufzuheben 😛

    // EDIT: Ich habe eh etwas aufgeräumt (wenn auch noch nicht ganz gut) und mit Funktoren gespielt. Hier zudem meine (unvollständige) Grammatik, die unten implementiert ist.

    identifier                      ::= ( nondigit | identifier nondigit | identifier digit ).
nondigit                        ::= ( ALPHA_CHARACTER | '_' ).
digit                           ::= DIGIT.
syntax                          ::= [ translation_unit ].
translation_unit                ::= [ declaration_seq ].
declaration_seq                 ::= ( declaration | declaration_seq declaration ).
declaration                     ::= ( explicit_instantiation | explicit_specialization | namespace_definition ).
namespace_definition            ::= ( named_namespace_definition | unnamed_namespace_definition ).
unnamed_namespace_definition    ::= 'namespace' '{' namespace_body '}'.
named_namespace_definition      ::= ( original_namespace_definition | extension_namespace_definition ).
original_namespace_definition   ::= 'namespace' identifier '{' namespace_body '}'.
extension_namespace_definition  ::= 'namespace' original_namespace_name '{' namespace_body '}'.
original_namespace_name         ::= identifier.
namespace_body                  ::= [ declaration_seq ].
explicit_instantiation          ::= 'template' declaration.
explicit_specialization         ::= 'template' '<' '>' declaration.

    #define ALPHA_CHARACTER (alpha_p | chlit<>('$'))
#define DIGIT (range<>('0', '9'))

namespace fpp {
	namespace compiler {
		namespace spirit {
			namespace functors {
				struct __namespace {
					template<typename IteratorT>
					void operator()(IteratorT begin, IteratorT end) const {
						std::cout << "Found a namespace '" << std::string(begin, end) << "'." << std::endl;
					}
				};

				struct __unnamed_namespace {
					template<typename IteratorT>
					void operator()(IteratorT begin, IteratorT end) const {
						std::cout << "Found an unnamed/anonymous namespace." << std::endl;
					}
				};

				struct __explicit_template {
					template<typename IteratorT>
					void operator()(IteratorT begin, IteratorT end) const {
						std::cout << "Explicit template declaration." << std::endl;
					}
				};
			}

			struct fpp_grammar : public grammar<fpp_grammar> {
				template<class ScannerT>
				struct definition {
					rule<ScannerT> nondigit_p;
					rule<ScannerT> digit_p;
					rule<ScannerT> identifier_p;

					rule<ScannerT> explicit_instantiation_p;
					rule<ScannerT> explicit_specialization_p;

					rule<ScannerT> namespace_body_p;
					rule<ScannerT> original_namespace_name_p;
					rule<ScannerT> extension_namespace_definition_p;
					rule<ScannerT> original_namespace_definition_p;
					rule<ScannerT> named_namespace_definition_p;
					rule<ScannerT> unnamed_namespace_definition_p;
					rule<ScannerT> namespace_definition_p;
					rule<ScannerT> declaration_p;
					rule<ScannerT> declaration_seq_p;
					rule<ScannerT> translation_unit_p;
					rule<ScannerT> syntax_p;

					definition(const fpp_grammar &self) {
						nondigit_p = (ALPHA_CHARACTER | chlit<>('_'));
						digit_p = DIGIT;
						identifier_p = nondigit_p >> *(nondigit_p | digit_p);

						explicit_instantiation_p = strlit<>("template") >> declaration_p;
						explicit_specialization_p = strlit<>("template") >> chlit<>('<') >> chlit<>('>') >> declaration_p;

						namespace_body_p = !declaration_seq_p;
						original_namespace_name_p = identifier_p;
						extension_namespace_definition_p = strlit<>("namespace") >> original_namespace_name_p[functors::__namespace()] >> chlit<>('{') >> namespace_body_p >> chlit<>('}');
						original_namespace_definition_p = strlit<>("namespace") >> identifier_p[functors::__namespace()] >> chlit<>('{') >> namespace_body_p >> chlit<>('}');
						named_namespace_definition_p = (original_namespace_definition_p | extension_namespace_definition_p);
						unnamed_namespace_definition_p = strlit<>("namespace") >> chlit<>('{') >> namespace_body_p >> chlit<>('}');
						namespace_definition_p = (named_namespace_definition_p | unnamed_namespace_definition_p[functors::__unnamed_namespace()]);
						declaration_p = (explicit_instantiation_p[functors::__explicit_template()] | explicit_specialization_p[functors::__explicit_template()] | namespace_definition_p);
						declaration_seq_p = declaration_p >> *(declaration_p);
						translation_unit_p = !declaration_seq_p;
						syntax_p = translation_unit_p;
					}

					rule<ScannerT> const &start() {
						return syntax_p;
					}
				};
			};
		}
	}
}
    0
  • O

    lass mal doppelte "_" am Anfang von Namen weg. Diese Namen sind für die Compiler reserviert. Insbesondere bei Namen wie __namespace wäre ich ganz besonders vorsichtig...

    Auch empfinde ich so tief geschachtelte Namensräume hässlich, aber das ist ja jedem selbst überlassen...

    die Makros brauchst du aber auch nicht, stattdessen kannst du eine passende Regel dafür anlegen, kommt am Ende auf das Selbe raus. Ansonsten erinnert mich der Code daran, warum ich spirit als unglaublich hässlich empfand...arrgh.

    0
  • ?

    Das mit den Makros kommt ja noch aus meinem ersten Versuch nachts um wieviel Uhr auch immer mit 2 Promille 🙂
    Spirit ist etwas unschön geworden bei mir, weil ich jetzt zahlreiche Regeln eingebaut habe und alles unleserlich geworden ist, aber immerhin einfacher als mein erster Versuch, wo ich Zeichen für Zeichen geparsed habe! Nun kann man ja auch sprachneutral in alle anderen Sprachen umschreiben 😛

    Diese tiefgeschachtelten Namespaces bin ich aus C# gewohnt und die sind eh nicht öffentlich, weil sie ja eh nur im Scanner/Parser sind 😉

    0
  • ?

    Einen Schritt weiter, mehr Probleme!
    Bisher habe ich meinen Test-Code, der geparsed werden soll, über die Konsole via getline(std::cin, str) eingelesen, nun will ich aber endlich eine Datei normal öffnen. Zunächst einmal eine (zwar syntaktisch korrekte, aber semantisch falsche - ich weiß es!) Datei, die ich nun einlesen will:

    // test source file
namespace NS1 {
    namespace NS2 {
        /* template definition on namespace because i take only care of
           syntactic errors ;) */
        template<typename T>
        namespace {
        }
    }
}

    Nun will ich wissen, wie ich die Datei am besten einlesen soll und wie ich zum Einen die Newlines behandeln soll**[1]**, zum Anderen welche RegEx-Bibliothek ich nutzen soll um die Kommentare beim Preprocessing zu strippen und ob das klappen wird.

    Zum letzten Punkt: Da, in der aktuellen Version, meine Regeln komisch definiert sind und mir bei einem Fehler über parse_info<>.stop einfach das ganze Source ausgeben wird (als ich es via Konsole eingelesen habe) bin ich am Überlegen, wie das dann bei dem File aussehen würde 😉

    Vielen Dank für eure Unterstützung,
    Christian

    Fußnoten:
    [1] Ich habe beim Parsen folgenden Code genutzt, um einige unnötige Whitespaces vom Scanner ignorieren zu lassen, damit ich diese nicht selber in die Regeln schreiben muss (wobei str der eingegebene Code ist und fpp_grammar in meinem vorherigen Post in einer kleineren/abgespeckteren Version definiert ist):

    fpp::compiler::spirit::fpp_grammar g;
parse_info<> info = parse(str.c_str(), g, space_p);
    0
Anmelden zum Antworten