Zine.net online

Intro

W poprzednim odcinku tej małej serii przedstawiłem w paru przykładach mplex - generator skanerów w C#, dedykowany do współpracy z Visual Studio. Dziś skupimy się na kolejnym z 'narzędzi językowych' dostępnych w SDK dla Visual Studio 2005, czyli MPPG.
MPPG, czyli Managed Package Parser Generator, to odpowiednik unixowego YACC’a , czyli 'Yet Another Compiler Compiler' - kompilatora kompilatorów. Podstawą MPPG jest projekt GPPG, który jest wspierany przez Microsoft w ramach prac nad Ruby.NET (GPPG stanowi jego część). MPPG generuje kod w C# i współpracuje z MPLexem przy tworzeniu analizatorów składni.
O tym, gdzie można znaleźć narzędzia językowe oraz jak przygotować sobie podstawowe środowisko pracy można przeczytać w poprzednim odcinku, więc przechodzimy od razu do przykładów.

Przykłady

Zacznijmy od skanera.

A. ex4.lex. Wracamy do naszego przykładu z poprzedniego odcinka i nieco go modyfikujemy na potrzeby parsera.

/* SEKCJA 1: DEFINICJE */
%using System.Collections;
%using Babel;
%using Babel.Parser;
%namespace Babel.Lexer
%{
const int LOOKUP = 0;
int stan;
Hashtable words = new Hashtable();
internal void add_word(int s, string text) {
if(!words.Contains(text))
 words.Add(text, s);
}
internal int lookup_word(string text) {
 if(words.Contains(text)) return (int) words[text];
 else return LOOKUP;
}
%}
%%
 /* SEKCJA 2: REGULY */
\n           { stan = LOOKUP;}
\.          {stan = LOOKUP; return (int)Tokens.KROPKA;}
^rzeczownik   {stan = (int)Tokens.RZECZOWNIK;}
^czasownik    {stan = (int)Tokens.CZASOWNIK;}
^przymiotnik  {stan = (int)Tokens.PRZYMIOTNIK;}
[a-zA-Z]+   {
  if(stan != LOOKUP) { add_word((int)stan, yytext);}
  else {
   switch(lookup_word(yytext)) {
    case (int)Tokens.RZECZOWNIK: return((int)Tokens.RZECZOWNIK);
    case (int)Tokens.CZASOWNIK: return((int)Tokens.CZASOWNIK);
    case (int)Tokens.PRZYMIOTNIK: return((int)Tokens.PRZYMIOTNIK);
    default: {return (int)Tokens.LEX_ERROR;}
   }
  }
 }
%%
 /* SEKCJA 3: KOD UZYTKOWNIKA */

Typ wyliczeniowy Locals z ex3.lex zastępujemy nieznanym nam jeszcze typem Tokens. Rezygnujemy z wypisywania informacji o zdefiniowanych częściach mowy, zamiast tego zwracamy liczbę określającą token powiązany z daną częścią mowy. Z sekcji kodu użytkownika, w której uprzednio mieliśmy zdefiniowany Main, nie pozostało już nic. W sekcji reguł z przyzwoitości zdefiniowaliśmy kropkę :). Reszta właściwie bez zmian.

Czas na wprowadzenie parsera.

1. ex41.y

/* SEKCJA 1: DEFINICJE */
%namespace Babel.Parser
%partial
%token RZECZOWNIK CZASOWNIK PRZYMIOTNIK
%token KROPKA
%token LEX_ERROR
%token maxParseToken
%%
 /* SEKCJA 2: REGULY */
zdanie: RZECZOWNIK CZASOWNIK KROPKA {Console.WriteLine("Zdanie prawidlowe!");}
      ;
%%
 /* SEKCJA 3: KOD UZYTKOWNIKA */
public static void Main(string[] args) {
 Babel.Lexer.Scanner scnr = new Babel.Lexer.Scanner();
 Parser p = new Parser();
 p.scanner = scnr;
 //p.Trace = true;
 string line = Console.ReadLine();
 do {
  scnr.SetSource(line, 0);
  p.Parse();
 } while((line = Console.ReadLine()) != null);
}

O co w tym chodzi???

Sprawa jest prostsza, niż się wydaje :). Po pierwsze, widać gołym okiem, że pliki mppg, podobnie jak pliki mplex, składają się z 3 części: Definicji, Reguł składniowych i Kodu użytkownika. I tak:

• W sekcji Definicji, korzystając ze specjalnego symbolu %namespace, ustalamy przestrzeń, w jakiej znajdzie się klasa Parser wygenerowanego analizatora składniowego. Dzięki symbolowi %partial ustalamy, że klasa Parser będzie klasą częściową, dzięki czemu możemy podzielić definicję klasy pomiędzy pliki (my jednak z tego nie korzystamy). Kolejny symbol specjalny to %token, dzięki któremu definiujemy symbole, których oczekujemy od leksera. Tak zdefiniowane symbole trafią do typu wyliczeniowego Tokens, który widzieliśmy już w naszym pliku leksera.
• W sekcji Reguł ustalamy reguły gramatyczne, dzięki którym określamy, czy dana konstrukcja jest prawidłowa składniowo, czy też nie. W naszym przypadku definiujemy regułę, która mówi, że zdanie jest prawidłowe, jeśli składa się z rzeczownika, czasownika i zakończone jest kropką. Dla przykładu, oczekujemy, że zdanie:
  Ala je.
  jest prawidłowe, o ile 'Ala' to rzeczownik, a 'je' to czasownik, natomiast spodziewamy się, że zdanie:
  Ala je obiad.
  jest nieprawidłowe, bez względu na definicję poszczególnych słów, ponieważ nasze zdanie pozwala tylko na konstrukcje składające się z dwóch słów, w ustalonej kolejności, po których jest kropka. A zatem komunikat 'Zdanie prawidłowe!' powinien pojawić się wyłącznie w przypadku zdań takich, jak to z pierwszego przykładu.
• W sekcji kodu użytkownika dołączamy metodę Main, dzięki której możemy sprawdzić działanie naszego analizatora. Tworzymy obiekty klasy Scanner i Parser, wiążemy je ze sobą i przechodzimy w pętli do parsowania. Dla ciekawskich, którzy chcieliby zobaczyć jak odbywają się poszczególne redukcje oraz przesunięcia w toku działania parsera, wystarczy odkomentować linijkę 'p.Trace = true;'.
  

Wszystko w porządku, ale jak to teraz skompilować?

Jak już wcześniej pisałem, oba narzędzia - mplex oraz mppg wykorzystywane są przez usługi językowe Visual Studio, przez co wygenerowane klasy muszą implementować określone interfejsy oraz dziedziczyć po określonych klasach. W przypadku samego lexera wystarczyło dodać plik dummy.cs z odpowiednimi definicjami i sprawa była załatwiona. Tym razem jednak jest nieco trudniej. A zatem - krok po kroku:

1. Lexer. Tak, jak poprzednio, uruchamiamy:

2. Parser. W wierszu poleceń wykonujemy:

mppg wyrzuca wygenerowaną zawartość na wyjście standardowe, więc musimy przekierować wyjście do pliku, żeby móc z tego później skorzystać.

3. Z katalogu "%VS2K5SDK%\2007.02\VisualStudioIntegration\Common\Source\CSharp\" kopiujemy katalog Babel do katalogu, w którym znajdują się nasze pliki .lex i .y. Ponadto modyfikujemy nieco nasz plik dummy.cs:

//dummy.cs
using System;
namespace Babel.Parser
{
    public interface IColorScan
    {
        void SetSource(string source, int offset);
        int GetNext(ref int state, out int start, out int end);
    }
    public interface IErrorHandler
    {
        int ErrNum { get; }
        int WrnNum { get; }
        void AddError(string msg, int lin, int col, int len, int severity);
    }
}

4. Podczas kompilacji musimy dołączyć kilka referencji do bibliotek z katalogu "%VS2K5SDK%\2007.02\VisualStudioIntegration\Common\Assemblies\", a mianowicie:

• Microsoft.VisualStudio.TextManager.Interop.dll;
• Microsoft.VisualStudio.OLE.Interop.dll;
• Microsoft.VisualStudio.Package.LanguageService.dll;
• Microsoft.VisualStudio.Shell.dll;
• Microsoft.VisualStudio.Shell.Interop.dll;
• Microsoft.VisualStudio.Shell.Interop.8.0.dll;
• Microsoft.VisualStudio.TextManager.Interop.8.0.dll.

Mając tę wiedzę, możemy wreszcie skompilować nasz projekt (przy standardowej instalacji SDK tak to wygląda):

UFF!!!

Oczywiście, nie życzę nikomu takiej zabawy na dłuższą metę i sugeruję przygotowanie sobie czy to pliku .bat, czy też odpowiedniego pliku dla msbuild. W tym drugim przypadku można skorzystać z przygotowanych tasków MPLexCompile oraz MPPGCompile, do których jeszcze wrócimy przy omawianiu usług językowych.

Po wykonaniu tych kroków mamy wreszcie nasz program, który wreszcie możemy uruchomić i potestować:

Tak, "mgrzeg je." i jest to zgodne z naszą gramatyką :)

Pobawmy się przez chwilę specjalnym symbolem 'error', dzięki któremu możemy powiedzieć, że coś jest nie do końca tak, jak powinno być. Zmodyfikujmy w tym celu sekcję reguł, pozostawiając resztę kodu niezmienną.

2. ex42.y

/* SEKCJA 2: REGULY */
zdanie: RZECZOWNIK CZASOWNIK KROPKA {Console.WriteLine("Zdanie prawidlowe!");}
      | RZECZOWNIK CZASOWNIK error {Console.WriteLine("Brakuje kropki!");}
      | RZECZOWNIK error {Console.WriteLine("Brakuje czasownika!");}
      | error CZASOWNIK {Console.WriteLine("Brakuje rzeczownika!");}
      ;
%%

Teraz po uruchomieniu programu nasza sesja może wyglądać następująco:

A zatem potrafimy już wychodzić (a przynajmniej informować użytkownika o tym) z sytuacji błędnych, czas na nieco bardziej złożoną gramatykę. Zmodyfikujmy zatem nieco naszą definicję zdania, dodajmy części zdania. Zmieńmy zatem po raz kolejny sekcję Reguł, resztę kodu pozostawiając bez zmian.

3. ex43.y

zdanie: podmiot orzeczenie dopelnienie KROPKA {Console.WriteLine("Zdanie prawidlowe!");}
      | podmiot orzeczenie dopelnienie error {Console.WriteLine("Brakuje kropki");}
      | podmiot error {Console.WriteLine("Brakuje orzeczenia");}
      | error orzeczenie {Console.WriteLine("Brakuje podmiotu");}
      ;
     
podmiot:    RZECZOWNIK
      ;
orzeczenie: CZASOWNIK
      ;
     
dopelnienie:  /* pusto! */
      |       PRZYMIOTNIK RZECZOWNIK
      |       PRZYMIOTNIK error {Console.WriteLine("Brakuje rzeczownika w dopelnieniu!");}
      |       RZECZOWNIK
      ;

Teraz przykładowa sesja z programem może wyglądać następująco:

Teraz nasza definicja zdania zakłada, że składa się ono z podmiotu, orzeczenia, dopełnienia i zakończone jest kropką. Reszta definicji jest oczywista, może dodatkowego komentarza wymaga dopełnienie, które może być puste, lub składać się z przymiotnika i rzeczownika, lub samego rzeczownika. Wszystkie trzy przypadki zostały przez nas sprawdzone w przykładowej sesji.

W ostatniej zabawie ze zdaniami możemy pokusić się o regułę rekurencyjną

4. ex44.y

zdanie        : zdanie_proste KROPKA {Console.WriteLine("Zdanie proste!");}
      |         zdanie_zlozone KROPKA {Console.WriteLine("Zdanie zlozone!");}
      ;
zdanie_proste : podmiot orzeczenie dopelnienie
      | podmiot error {Console.WriteLine("Brakuje orzeczenia");}
      | error orzeczenie {Console.WriteLine("Brakuje podmiotu");}
      ;
zdanie_zlozone :  zdanie_proste SPOJNIK zdanie_proste
      |           zdanie_proste error zdanie_proste {Console.WriteLine("Brak spojnika");}
      |           zdanie_zlozone SPOJNIK zdanie_proste
      ;
...reszta reguł,

Zdefiniowanie dodatkowego tokena oraz pozostałą zabawę pozostawiam jako samodzielne ćwiczenie.

Na sam koniec przykładów baaardzo prosty przykład kalkulatora (w końcu Gutek też pisał kalkulator :P), który potrafi tylko dodawać i odejmować liczby całkowite :D.

B. ex6.lex

/* SEKCJA 1: DEFINICJE */
%using Babel;
%using Babel.Parser;
%namespace Babel.Lexer
%%
 /* SEKCJA 2: REGULY */
[0-9]+  { yylval.value = int.Parse(yytext); return (int)Tokens.NUMBER;}
[ \t] ;
\n|\r\n  return 0;
.   return yytext[0];
%%
 /* SEKCJA 3: KOD UZYTKOWNIKA */

Do tego dorzucamy plik parsera.

1. ex61.y

/* SEKCJA 1: DEFINICJE */
%namespace Babel.Parser
%partial
%union {
  public int value;
}
%start statement
%token NAME NUMBER
%token maxParseToken
%%
 /* SEKCJA 2: REGULY */
statement:    expression '.' {Console.WriteLine("={0}", $1.value);}
          ;
         
expression:   expression '+' NUMBER {$$.value = $1.value + $3.value;}
          |   expression '-' NUMBER {$$.value = $1.value - $3.value;}
          |   NUMBER {$$.value = $1.value;}
          ;
         
%%
 /* SEKCJA 3: KOD UZYTKOWNIKA */
public static void Main(string[] args) {
 Babel.Lexer.Scanner scnr = new Babel.Lexer.Scanner();
 Parser p = new Parser();
 p.Initialize();
 p.scanner = scnr;
 //p.Trace = true;
 string line = Console.ReadLine();
 do {
  scnr.SetSource(line, 0);
  p.Parse();
 } while((line = Console.ReadLine()) != null);
}

Warto zwrócić uwagę na wykorzystanie symbolu specjalnego %union, który definiuje nam strukturę, obiekt której widoczny jest od strony scannera jako yylval, a od strony parsera możemy operować na nim wykorzystując symbole $$ oraz $i, gdzie i oznacza pozycję terminala w danej regule, dla przykładu:
expression:   expression '+' NUMBER {$$.value = $1.value + $3.value;}
$$.value - wartość pola value symbolu nieterminalnego $$;
$1.value - wartość terminala expression z prawej strony reguły
'+' - odpowiada $2,
$3.value - wartość terminala NUMBER.

Przykładowe działanie programu:

Ostatki

Na koniec pare informacji o debuggowaniu. Jakkolwiek MPLex nie pomaga nam w tym za bardzo, to MPPG emituje do wygenerowanego pliku z klasą Parsera informację o numerach wierszy pliku źródłowego. Tym samym wystarczy podpiąć się z debuggerem gdziekolwiek w kodzie i możemy na bieżąco śledzić bieżące wartości pól skanera i parsera. Dla przykładu, żeby wskoczyć z debuggerem do pliku .y i sprawdzić jakie mamy bieżące wartości odpowiednich terminali w regule dodawania, wystarczy zapisać ją:

expression:   expression '+' NUMBER {
System.Diagnostics.Debugger.Break();
$$.value = $1.value + $3.value;
}

Sugeruję umieszczanie kolejnych instrukcji w osobnych wierszach - debugger na podstawie wygenerowanego pliku ma tylko informację o numerze linii, nie wie nic o kolumnie :(.
Oczywiście, należy też pamiętać o zmuszeniu kompilatora do wygenerowania informacji dla debuggera, czyli dodaniu opcji /debug+ w wywołaniu csc.