Boost spirit może obsłużyć Postscript/PDF jak języki?

Question

Zauważyłem, że Boost spirit oferuje pewne ograniczenia, w pytaniu tutaj na SO jest użytkownik, który prosi o pomoc na temat ducha boost i inny użytkownik, który podał odpowiedź, że podbicie ducha działa dobrze z oświadczeniami, a nie z "tekstem ogólnym" (Przepraszam, jeśli nie pamiętam tego poprawnie).

Teraz chciałbym myśleć o PostScriptach i PDF pod względem tokenów i uprościć moje podejście do tych formatów w ten sposób, problem polega na tym, że PDF jest mieszanką języka znaczników i języka programowania ze skokami i tabele w nim i nie mogę myśleć o czymś podobnym, biorąc pod uwagę najbardziej popularne formaty plików, takie jak XML, C++ i inne języki i formaty.

Jest jeszcze jeden fakt: nie mogę tak naprawdę znaleźć ludzi, którzy mieli jakieś doświadczenie z boost :: spirytusem parsera lub pisarza pdf, więc pytam, boost :: spirit, że potrafi analizować Plik PDF i wyprowadzić elementy jako tokeny?

Answer 1

Chociaż nie ma to nic wspólnego z Boost, pozwól, że zapewniam, że parsowanie PDF (i PostScript) jest tak trywialne, jak tylko chcesz. Załóżmy, że masz obiekt skanera, który zwraca serię tokenów. Rodzaje Token otrzymasz od skanera to:

• String
• Dict rozpocząć (< <)
• Dict End (>>)
• Nazwa (/ cokolwiek)
• Ilość
• Tablica szesnastkowa
• Lewy kąt (<)
• Kątownik prawy (>)
• Tablica rozpocząć ([)
• koniec tablicy (])
• Procedura rozpoczyna ({)
• zakończeniu procedury (})
• Komentarz (% bla)
• Słowo

Mój skaner jest automatem ze stanem końcowym ze stanami Start, Comment, String, HexArray, Token, DictEnd i Done.

Sposób, w jaki parsujesz PDF, nie polega na analizie składniowej, ale na wykonaniu. Biorąc pod uwagę te tokeny, mój „parser” wygląda następująco (w języku C#):

while (true) { 
    MLPdfToken = scanner.GetToken(); 
    if (token == null) 
     return MachineExit.EndOfFile; 
    PdfObject obj = PdfObject.FromToken(token); 
    PdfProcedure proc = obj as PdfProcedure; 

    if (proc != null) 
    { 
     if (IsExecuting()) 
     { 
      if (token.Type == PdfTokenType.RBrace) 
       proc.Execute(this); 
      else 
       Push(obj); 
     } 
     else { 
      proc.Execute(this); 
     } 
     if (proc.IsTerminal) 
      return Machine.ParseComplete; 
    } 
    else { 
     Push(obj); 
    } 
} 

będę również dodać, że jeśli dać każdy PdfObject Execute() metody takie, że zastosowanie klasa bazowa jest machine.Push(this) i IsTerminal że zwraca false The REPL staje się łatwiejsze:

while (true) { 
    MLPdfToken = scanner.GetToken(); 
    if (token == null) 
     return MachineExit.EndOfFile; 
    PdfObject obj = PdfObject.FromToken(token); 

    if (IsExecuting()) 
    { 
     if (token.Type == PdfTokenType.RBrace) 
      obj.Execute(this); 
     else 
      Push(obj); 
    } 
    else { 
     obj.Execute(this); 
     if (obj.IsTerminal) 
      return Machine.ParseComplete;     
    } 
} 

Istnieje większe wsparcie w - maszyna posiada stos PdfObject i kilka metod dostępu do niego (push, Pop, Mark CountToMark, Index, Dup, swap), jak również ExecProcBegin i ExecProcEnd.

Poza tym jest bardzo lekki. Jedyną rzeczą, która jest nieco dziwna jest to, że PdfObject.FromToken bierze token i jeśli jest to typ pierwotny (liczba, ciąg, nazwa, heks, bool) zwraca odpowiedni obiekt PdfObject.W przeciwnym razie pobiera dany token i wyszukuje w słowniku "proc set" nazw procedur związanych z obiektami PdfProcedure. Więc gdy napotkasz token << że dostaje wyglądał w zestaw PROC i wyjdzie z tego kodu:

void DictBegin(PdfMachine machine) 
{ 
    machine.Push(new PdfMark(PdfMarkType.Dictionary)); 
} 

tak << naprawdę oznacza „oznaczyć stos jako początek słownika >> staje się bardziej interesujące.:

void DictEnd(PdfMachine machine) 
{ 
    PdfDict dict = new PdfDict(); 
    // PopThroughMark pops the entire stack up to the first matching mark, 
    // throws an exception if it fails. 
    PdfObject[] arr = machine.PopThroughMark(PdfMarkType.Dictionary); 
    if ((arr.Length & 1) != 0) 
     throw new PdfException("dictionaries need an even number of objects."); 
    for (int i=0; i < arr.Length; i += 2) 
    { 
     PdfObject key = arr[i], val = arr[i + 1]; 
     if (key.Type != PdfObjectType.Name) 
      throw new PdfException("dictionaries need a /name for the key."); 
     dict.put((PdfName)key, val); 
    } 
    machine.Push(dict); 
} 

Więc >> wyskakuje do najbliższego słowniku znaku w tablicy wykłada każdą parę do słownika. teraz mógł to zrobić bez przypisywania tablicy. I może po prostu pop pary, umieszczając je do słownika dopóki nie trafię na znak, nie otrzymam nazwy ani niedopełnienie stosu.

Ważne jest, że nie ma żadnej składni w pliku PDF, ani nie ma jej w PostScript. Przynajmniej nie tak bardzo, jak byś zauważył. Jedyną prawdziwą składnią (i pętlą read-eval- (push)) jest "}".

Więc jeśli jest to PDF 14 0 obj << /Type /Annot /SubType /Square >> endobj co się naprawdę widząc to seria zabiegów:

1. push 14
2. push 0
3. Execute obj (pop dwa numery i nacisnąć "definicja" obiekt).
4. Execute słowniku rozpocząć
5. push/Typ
6. push/Annot
7. push/Podtyp
8. push/Plac
9. Execute słowniku koniec
10. Execute endobj (pop górny obiekt, a następnie dostać (nie pop), jeśli drugi jest definicją, ustaw jego "wartość" na pierwszym obiekcie, a następnie rzuć).

Ponieważ "endobj" jest terminalem, parsowanie się kończy, a górna część stosu jest wynikiem.

Kiedy więc zostaniesz poproszony o wyszukanie obiektu 14 w pliku PDF, tabela odsyłaczy powie ci, gdzie szukać, tworzymy nową Maszynę ze wskaźnikiem strumienia w tej lokalizacji i uruchamiamy ją. Jeśli szczyt stosu jest obiektem "definicji", to się udało.

O teraz powinno być kiwając głową, ale nie do mnie zaufanie, skoro myślisz o strumieni PDF, który wygląda tak:

<< [/key value]* >> stream ...raw data... endstream endobj 

Ponownie, nie ma składnię. Proc. stream wygląda na górze stosu, który powinien być PdfDict. Jeśli tak, zużywa znaki aż do następnego znaku nowego (skaner to robi), zapisuje bieżącą pozycję pliku w strumieniu jako początek danych, odczytuje długość strumienia z dyktatury (co może spowodować, że inna maszyna zostanie zaktualizowana) i przeskoczy obok końca strumienia i przesuwa nowy obiekt strumienia na stosie. endstream nie jest opcją. Jedyną różnicą między PdfDict i PdfStream jest to, że PdfStream ma pozycję początkową, a bool mówi, że jest to strumień, w przeciwnym razie podwójnie przeznaczę obiekt.

PostScript jest prawie identyczny, z tym że środowisko wykonawcze jest nieco bardziej złożone.Na przykład potrzebujesz kilku stosów w swoim komputerze: stosu parametrów, stosu słownika i stosu wykonawczego. Stamtąd mniej lub bardziej po prostu połącz swój tokenizer z zestawem prymitywnych procedur, a także słowem exec, a następnie większość twojego tłumacza jest napisana w samym PS.

Jeśli mówimy o zwiększeniu, patrzysz na C++, co oznacza, że ​​nie możesz być tak szybki i wolny od pamięci, jak ja, więc będziesz chciał użyć inteligentnych wskaźników lub wymyślić gdzie masz zasięg i bądź ostrożny, aby pozbyć się obiektów zamiast beztrosko je wyrzucać, ale to tylko normalne rzeczy w C++.

Obecnie tworzę narzędzia PDF dla mojej firmy w .NET, ale w poprzednim życiu pracowałem nad wersjami 1-4 programu Acrobat, a większość z tego, co opisałem, jest dokładnie tym, co zrobił Acrobat pod maską (no cóż, więcej mniej - było to C, nie C++, ale to jest to samo podejście).

Jeśli chodzi o tabelę odnośników (lub strumień odnośników), najpierw ją czytasz - specyfikacja mówi, że jeśli przejdziesz do EOF i zeskanujesz ponownie, znajdziesz początek tabeli odnośników. Parsujesz to (co jest przydziałem CS 101), analizujesz zwiastun, poszukujesz do/Prev jeśli takowy i powtarzasz, aż nie będzie żadnych/Prev wpisów. To daje pełny odnośnik do wyszukiwania obiektów.

Co do pisania - istnieje wiele metod, które można zastosować. Najbardziej oczywiste jest to, że gdy obiekt ma być przywoływany, tworzy się nowy obiekt referencyjny, przypisując mu najnowszy dostępny odnośnik xref. Kiedykolwiek obiekty odnoszą się do innych obiektów do pisania, pytają, czy te obiekty są przywoływane. Jeśli tak, piszą referencję (np. 14 0 R). Kiedy przychodzi czas na napisanie obiektu, do którego się odwołujemy, otrzymujemy bieżący wskaźnik strumienia i zapisujemy go w odnośniku, a następnie piszemy <objnum> <generation> obj <object contents> endobj. Na przykład, mój kod napisać słownika wygląda następująco:

public override ToStream(PdfStreamingContext context) 
{ 
    if (context.HasReference(this)) // is object referenced in xref 
    { 
     PdfUtils.WriteObjectDefinitionBegin(this, context); 
    } 
    context.Writer.Indent(); 
    context.Writer.WriteLine("<<"); 
    WriteContents(context); 
    context.Writer.Exdent(); 
    context.Writer.Writeline(">>"); 
    if (context.HasReference(this)) 
    { 
     PdfUtils.WriteObjectDefinitionEnd(this, context); 
    } 
} 

Mam posiekane się trochę plew więc można zobaczyć pod pszenicę. Kontekst jest obiektem, który przechowuje nową tabelę odnośników, a także obiekt do zapisu do strumieni, które automagicznie obsługują odpowiednią nową linię, wcięcie, zawijanie wierszy i tak dalej.

To, co powinieneś zobaczyć, to to, że podstawy tutaj są proste, jeśli nie banalne. A teraz, kiedy powinieneś zadać sobie pytanie: "jeśli to trywialne, to dlaczego nie ma więcej (poważnej) konkurencji dla Acrobata na rynku?" Odpowiedź jest taka, że ​​mimo tego, że jest to banalne, nadal łatwo jest pisać pliki PDF, '' '' '' '' '' '' '' '' '' '' ', a Acrobat obsługuje większość z nich. Prawdziwym wyzwaniem jest być w stanie uszanować specyfikację i upewnić się, że umieściłeś wszystkie wymagane wartości w słowniku i że są one w zakresie i są poprawne semantycznie. format - który jest dość dobrze określony - jest kopcem specjalnego kodu przypadków w mojej bibliotece, który pozwala zarządzać miejscem, w którym inni ludzie je przekręcają, ponieważ generowanie konsekwentnie poprawnego pliku PDF jest trudne i zużywa śmieci w morzu plików PDF na świecie jest trudniejsze

Mogę (i prawdopodobnie powinienem) napisać książkę o tym, jak to zrobić. Podczas gdy wiele kodu jest brudna, ogólna struktura może być bardzo ładna.

tl; dr - Jeśli myślisz o parser rekurencyjny dla pliku PDF, myślisz zbyt mocno. Wszystko czego potrzebujesz to tokenizer i prosty REPL.