Biblioteka Boost Spirit

Bartłomiej Wojcieszek G1SST

Parser, zwany także analizatorem składniowym, pozwala na analize danych wejściowych i określenie czy są zgodne z daną gramatyką. Zazwyczaj parsery są wykorzystywane przy przetwarzaniu danych zrozumialych dla czlowieka w dane najbardziej wygodne dla komputera.

Biblioteka Spirit pozwala tworzyć własne złożone parsery lub wykorzytywać te najprostsze wbudowane w bibliotekę. Szablony wyrażeń zastosowanych w bibliotece pozwalają na zapis w notacji bardzo podobnej do EBNF (Extended Backus-Normal Form):
Gramatyka EBNF:

    group       ::= '(' expression ')'
    factor      ::= integer | group
    term        ::= factor (('*' factor) | ('/' factor))*
    expression  ::= term (('+' term) | ('-' term))*

I ten sam parser zapisany w C++ z pomocą biblioteki Spirit:

    group       = '(' >> expression >> ')';
    factor      = integer | group;
    term        = factor >> *(('*' >> factor) | ('/' >> factor));
    expression  = term >> *(('+' >> term) | ('-' >> term));

Aby wykorzystywać w swoich programach bibliotekę spirit, należy dołączyć odpowiednie nagłówki do naszego pliku:

#include <boost/spirit/core.hpp>
#include <boost/spirit/actor/push_back_actor.hpp>

Załóżmy,że chcemy aby nasz program akceptował tylko takie dane wejsciowe, że pierwszym elementem jest liczba rzeczywista, a następnym znak alfabetyczny. Tworzymy parser:

   real_p>>alpha_p

Aby go wykorzystać, należy skorzystać z funkcji parse:

bool parseInput(String str){
    return parse(str,real_p>>alpha_p,space_p);
}

Funkcja parse zwraca true jeżeli parsowanie przebiegło pomyślnie. Przyjmuje trzy argumenty:

1. Zakończone nullem const char* dane do sparsowania
2. Obiekt parsujący
3. Parser pomijania (mówi na co nie zwracać uwagi w danych wejściowych, w tym przypadku na spacje)

Wyrażenia parsujące tworzy się za pomocą wbudowanych w bibliotekę prymitywów oraz operatorów. Kilka podstawowych prymitywów (więcej można znaleźć w dokumentacji):

ch_p('X')         //parsuje char podany jako argument
range_p('a','z')  //parsuje pojedynczy char z podanego zakresu
str_p("Hello")    //parsuje podany string
anychar_p         //dowolny znak
alnum_p           //znak alfanumeryczny
alpha_p           //znak alfabetu
blank_p           //spacje i tabulacje
lower_p           //male litery
print_p           //znaki drukowane
punct_p           //znaki punktuacyjne
space_p           //spacja tab,nowa linia
upper_p           //duze litery
digit_p           //cyfra
int_p             //int
real_p            //liczba rzeczywista

I operatory:

a | b        //a lub b
a & b        //a i b
a - b        //a ale nie b
a ^ b        //a lub b ale nie oba (XOR)
a>>b         //a i b w sekwencji
a&&b         //jw
a||b         //a lub b w sekwencji
*a           //a zero lub wiecej razy
+a           //a raz lub wiecej razy
!a           //a zero lub jeden raz
a%b          //lista a oddzielonych przez b

Dodatkowo parsery numeryczna możemy bardziej sprecyzować. Oto szablon takiego parsera:

template <
        typename T = unsigned,     //bazowy typ parsera, default jest unsigned
        int Radix = 10,            //podstawa systemu, czyli dziesiętny szesnastkowy itp.
        unsigned MinDigits = 1,    //minimalna liczba cyfr
        int MaxDigits = -1>        //maksymalna liczba cyfr (-1 oznacza niograniczona)
    struct uint_parser { /*...*/ };
 
 
//zatem jeżeli chcemy sparsować liczbę szesnastkową, nasz parser będzie wyglądał następująco:
uint_parser<unsigned, 16, 1, -1> const
 
//lub to samo osiągniemy korzystając z wbudowanego parsera hex_p
 
//chcielibyśmy sparsować liczbe odzdzieloną przecinkami, taką jak: 1,234,567,891
 
    uint_parser<unsigned, 10, 1, 3> uint3_p;        //  parsuje od 1 do 3 cyfr,czyli pierwsza część
    uint_parser<unsigned, 10, 3, 3> uint3_3_p;      //  dokładnie 3 cyfry
    ts_num_p = (uint3_p >> *(',' >> uint3_3_p));    //  dowolna liczba oddzielana co 3 cyfry przecinkami

Załóżmy, że chcemy wczytać ze standardowego wyjscia do wektora ciąg liczb oddzielonych przecinkami (oczywiście przecinki nas nie interesują, tylko liczby). Czyli n a wejsciu ma się pojawić liczba, nastepnie dowolna ilość razy przecinek i kolejna liczba. Zatem w kodzie c++ wygląda to następująco:

bool
    parse_numbers(char const* str, vector<double>& v)
    {
        return parse(str,
            (
                real_p[push_back_a(v)] >> *(',' >> real_p[push_back_a(v)])
            )
            ,
            space_p).full;
    }

Wywołana metoda full zwraca true jeżeli wszystkie dane zostały poprawnie sparsowane.

A co to za dziwne nawiasy kwadratowe za wyrażeniem? Jest to akcja semantyczna (ang. Semantic Action). Dzięki niej sparsowane liczby są przekazywane do wektora. Sam parser sprawdza tylko czy dane wyrażenie pasuje do wzorca, ale nic więcej z nim nie robi. Z pomocą przychodzą akcje semantyczne. Mogą być one dodane w dowolnym miejscu. Funkcja jest wywoływana w momencie, gdy parsowanie przebiegło pomyślnie. Jak to się robi?:

//jeżeli P to nasz parser a F to funkcja w c++ to aby "podłączyć" funkcję do parsera, należy to zrobić w następujący sposób:
P[&F]
//jeżeli natomiast F  jest funktorem:
P[F]
//dodatkowo argument fukncji musi się zgadzać z elementem parsowanym:
void Foo(double d);
real_p[&Foo]

Reguła czyli rule pozwala przechowywać skonstruowany przez nas parser. Kilka przykładów:

rule<> a_rule = *(ch_p('a') | ch_p('b')) & +(ch_p('c') | ch_p('d') | range_p('k','z'));
 
//można też odwołać się do innej reguły:
 
rule<> another_rule = int_p >> ch_p('a') >> str_p('bla') >> second_rule;
//należy tylko pamiętać,że jest to odwołanie przez referencję, do programisty więc należy pilnowanie
//aby dana reguła była w zasięgu i ciągle istniała

Dzięki regułom możemy tworzyć dynamiczne parsery w naszym programie, zalęznie od jego przebiegu:

rule<> my_rule=digit_p;
 
if(some condition)
   my_rule=str_p("blaBla");

Dyrektywy zmieniają zachowanie parsera. Jest kilka wbudowanych w bibliotekę dyrektyw, użytkownik ma także możliwość tworzenia własnych.

Przykłady:

//Dyrektywa as_lower_d konwertuje wszystkie znaki z wejścia na małe znaki
 rule = as_lower_d["hello"]; 
//zaakceptuje "HeLlO" jak i "HELLO" oraz "hello"
 
//Dyrektywa lexeme_d wyłącza ignorowanie białych znaków, przydatna gdy chcemy wczytywać znaki oddzielone spacją np 1 2 345 bez tej dyrektywy może byc 
//przyjęte jako 12345 a nie jako 3 liczby:
 
integer = lexeme_d[ !(ch_p('+') | '-') >> +digit ];
 
//Dyrektywa limit_d ogranicza min i max w jakim może się znajdować parsowane wyrażenie
//Stwórzmy np. parser przyjmujący date w formacie:  dd.mm.yyyy i zakładamy że interesują nas tylko daty z lat 2000 do 2010:
 
uint_parser<int, 10, 2, 2> uint2_p;
uint_parser<int, 10, 4, 4> year;
 
lexeme_d
 [
    limit_d(1, 31)[uint2_p] >> '.'      //  dni od 1 do 31
>>  limit_d(1, 12)[uint2_p] >> '.'      //  miesiace od 1 do 12
>>  limit_d(2000,2010)[year]            //  rok ograniczony latami 2000 do 2010
]

Jak już wcześniej wspomniałem możemy użyć funkcji które będą wyzwalane w momencie pozytywnego sparsowania. Dzięki temu można łatwo tworzyć program w którym po sparsowaniu analizujemy to co było no wejściu. Za pomocą funkcji możemy także generować osrtrzeżenia o niepoprawnych argumentach itp. Prosty przykład:

 void
    action(char const* first, char const* last)
    {
        std::string str(first, last);
        std::cout << str << std::endl;
    }
 
    rule<> myrule = (ch_p(a) | int_p >> *(int_p >> ch_p('x')))[&action];
//w momencie poprawnego sparsowania, funkca wypisze w postaci stringa wszystkie sparsowane elementy

Po tych podstawach, przydałoby się napisać krótki program ilustrujący faktyczne działanie biblioteki Spirit. Podany program zamienia formatowanie w stylu wiki na dokument html. Aby rozpocząc wprowadzanie należy otworzyć klamrę { a po zakończonym wprowadzaniu zamknąć klamrą }. Podobnie jak w wiki nagłówki oznacza się za pomocą symboli „=” linki tak jak w wiki, kod za pomocą tagów <coding> </coding>. Program jest bardzo uproszczony, ale latwo mozna dodac więcej rozpoznawanych przez niego tagów.

 
#include <boost/spirit/core.hpp>
#include <iostream>
#include <string>
 
 
using namespace std;
using namespace boost::spirit;
 
////////////////////////////////////////////////////////////////////////////
//TUTAJ PODAJEMY AKCJE JAKIE BEDA WYKONYWANE W ZALEZNOSCI OD WEJSCIA
////////////////////////////////////////////////////////////////////////////
 
void
    h1Action(char const* first,char const* last)
    {
		std::string str(first, last);
        std::cout << "<h1>"<<str.substr(4,str.length()-8)<<"</h1>" << std::endl;
    }
void	h2Action(char const* first,char const* last)
   {
		std::string str(first, last);
       std::cout << "<h2>"<<str.substr(3,str.length()-6)<<"</h2>" << std::endl;
   }
void	h3Action(char const* first,char const* last)
   {
		std::string str(first, last);
       std::cout << "<h3>"<<str.substr(2,str.length()-4)<<"</h3>" << std::endl;
   }
void	h4Action(char const* first,char const* last)
   {
		std::string str(first, last);
       std::cout << "<h4>"<<str.substr(1,str.length()-2)<<"</h4>" << std::endl;
   }
void	href(char const* first,char const* last)
   {
		std::string str(first, last);
        std::cout << "<a href="+str.substr(2,str.find("|",2)-2)+">"+str.substr(str.find("|",2)+1,str.length()-5-(str.substr(2,str.find("|",2)-2)).length())+"</a>" << std::endl;
   }
 
void	code(char const* first,char const* last)
   {
 
		std::string str(first, last);
        std::cout << "<div style=\"border-width: 1px; border-style: dashed; border-color: blue; \">"+str.substr(6,str.length()-13)+"</div>" << std::endl;
   }
 
void	tail(char const* first,char const* last)
    {
		std::string str(first, last);
        std::cout << "</body>" << std::endl << "</html>" << std::endl;
    }
void	head(char const first)
    {
        std::cout <<"<!DOCTYPE html PUBLIC \"-//W3C//DTD XHTML 1.0 Strict//EN\""<<std::endl;
        std::cout <<"\"http://www.w3.org/TR/xhtml1/DTD/xhtml1i-strict.dtd\">"<<std::endl;
        std::cout<<"<html xmlns=\"http://www.w3.org/1999/xhtml\" xml:lang=\"pl\">"<<std::endl;
        std::cout<<"<head>"<<std::endl<< "<link rel=\"stylesheet\" type=\"text/css\" href=\"main.css\" />"<<std::endl;
        std::cout<<"</head>"<<std::endl<<"<body>"<<std::endl;     
    }
 
///////////////////////////////////////////////////////////////////////////////
//TUTAJ DEFINIUJEMY REGULY PARSOWANIA
///////////////////////////////////////////////////////////////////////////////
 
struct html : public grammar<html>
{
    template <typename ScannerT>
    struct definition
    {
        definition(html const& )
        {
            //reguly parsowania i wywolywane przez nie akcje:
 
            header
        	=	ch_p('{')[&head];
            tag
                =       (str_p("====")>>(*(~ch_p('=')))>>str_p("===="))[&h1Action]
                |	(str_p("===")>>(*(~ch_p('=')))>>str_p("==="))[&h2Action]
            	|	(str_p("==")>>(*(~ch_p('=')))>>str_p("=="))[&h3Action]
            	|	(str_p("=")>>(*(~ch_p('=')))>>str_p("="))[&h4Action]
            	| 	(str_p("<coding>")>>*(anychar_p-str_p("</coding>"))>>str_p("</coding>"))[&code]           	
            	|	(str_p("[[")>>(*((~ch_p(']'))-ch_p('|')))>>ch_p('|')>>(*(~ch_p(']')))>>str_p("]]"))[&href];
            document
                =   header>>(*tag>>ch_p('}'))[&tail];
 
 
 
        }
 
        rule<ScannerT> tag, document, header;
 
        rule<ScannerT> const&
        start() const { return document; }
    };
};
 
 
int
main()
{
	cout << "Simple parsing example\n";
	cout << "Type \"quit\" to exit program\n";
 
    html htmlParser;    //  Our parser
 
    string str,tmp;
        while (getline(cin, str))
        {
            if (str=="quit")
                break;
            if(str[str.length()-1]=='}')
            {
            	tmp+=str;
            	parse_info<> info = parse(tmp.c_str(), htmlParser, space_p);
    	        if (info.full)
    	        {
    	            cout << "Parsing succeeded\n";
    	        }
    	        else
    	        {
    	            cout << "Parsing failed at:\n"<<info.stop;
    	        }
 
    	        tmp="";
            }
            else
            {
            	tmp+=str;
            }
        }
        return 0;
    }

• Witryna biblioteki