parsing with haskell parser combinators
1.0.0
Müssen Sie etwas analysieren? Noch nie von einem "Parser -Kombinator" gehört? Möchten Sie etwas Haskell lernen? Eindrucksvoll! Unten finden Sie alles, was Sie brauchen, um aufzustehen und mit Haskell -Parser -Kombinators zu analysieren. Von hier aus können Sie versuchen, esoterische Datenserialisierungsformate, Compiler -Frontenden, domänenspezifische Sprachen anzugehen - Sie nennen es!
In diesem Leitfaden sind zwei Demo -Programme enthalten.
version-number-parser analysiert eine Datei für eine Versionsnummer. srt-file-parser analysiert eine Datei für SRT-Untertitel. Probieren Sie sie gerne mit den Dateien aus, die im test-input/ gefunden wurden.
Laden Sie den Haskell -Tool -Stack herunter und führen Sie dann Folgendes aus.
git clone https://github.com/lettier/parsing-with-haskell-parser-combinators
cd parsing-with-haskell-parser-combinators
stack buildWenn Sie Cabal verwenden, können Sie Folgendes ausführen.
git clone https://github.com/lettier/parsing-with-haskell-parser-combinators
cd parsing-with-haskell-parser-combinators
cabal sandbox init
cabal --require-sandbox build
cabal --require-sandbox installNach dem Bau der beiden Demo -Programme können Sie sie so ausführen.
Führen Sie Folgendes aus.
cd parsing-with-haskell-parser-combinators
stack exec -- version-number-parser
What is the version output file path ?
test-input/gifcurry-version-output.txtFühren Sie Folgendes aus, um den Parser SRT -Datei zu probieren.
cd parsing-with-haskell-parser-combinators
stack exec -- srt-file-parser
What is the SRT file path ?
test-input/subtitles.srtFühren Sie Folgendes aus.
cd parsing-with-haskell-parser-combinators
.cabal-sandbox/bin/version-number-parser
What is the version output file path ?
test-input/gifcurry-version-output.txtFühren Sie Folgendes aus, um den Parser SRT -Datei zu probieren.
cd parsing-with-haskell-parser-combinators
.cabal-sandbox/bin/srt-file-parser
What is the SRT file path ?
test-input/subtitles.srtEine der besseren Möglichkeiten, um die Parsen -Strategie, der Parser -Kombinator, zu lernen, besteht darin, eine Implementierung von einem zu betrachten.
Parser, die mit Kombinatoren gebaut wurden, sind unkompliziert zu konstruieren, lesbar, modular, gut strukturiert und leicht zu warten.
- Parser -Kombinator - Wikipedia
Werfen wir einen Blick unter die Motorhaube von Readp, einer Parser -Kombinatorbibliothek, die in der Basis zu finden ist. Da es in der Basis ist, sollten Sie es bereits haben.
Beachten Sie, dass Sie Parsec ausprobieren möchten, nachdem Sie sich mit ReadP vertraut gemacht haben. Es ist auch eine Parser -Kombinatorbibliothek, die andere bevorzugen. Als zusätzlichen Bonus ist es in GHC -Bibliotheken von GHC Version 8.4.1 enthalten.
-- (c) The University of Glasgow 2002
data P a
= Get ( Char -> P a )
| Look ( String -> P a )
| Fail
| Result a ( P a )
| Final [( a , String )]
deriving Functor Wir beginnen mit dem P -Datentyp. Das a in P a liegt bei Ihnen (dem Bibliotheksbenutzer) und kann alles sein, was Sie möchten. Der Compiler erstellt automatisch eine Functor-Instanz und es gibt handgeschriebene Instanzen für Anwendung, Monad, MonadFail und Alternative.
Beachten Sie, dass weitere Informationen zu Funkern, Bewerbern und Monaden finden Sie in Ihrem einfachen Leitfaden für Monades, Bewerber und Funkern.
P ist ein Sumentyp mit fünf Fällen.
Get ein einzelnes Zeichen aus der Eingabezeichenfolge und gibt einen neuen P zurück.Look akzeptiert ein Duplikat der Eingangszeichenfolge und gibt einen neuen P zurück.Fail zeigt den Parser ohne Ergebnis an.Result hält eine mögliche Parsen und einen weiteren P -Fall.Final ist eine Liste von zwei Tupeln. Das erste Tupelelement ist eine mögliche Parsen des Eingangs und das zweite Tupelelement ist der Rest der Eingangszeichenfolge, die nicht von Get verzehrt wurde. -- (c) The University of Glasgow 2002
run :: P a -> ReadS a
run ( Get f) (c : s) = run (f c) s
run ( Look f) s = run (f s) s
run ( Result x p) s = (x,s) : run p s
run ( Final r) _ = r
run _ _ = [] run ist das Herz des Readp -Parsers. Es macht das ganze schwere Heben, da es rekursiv durch alle Parserstaaten geht, die wir oben aufgesehen haben. Sie können sehen, dass es ein P benötigt und ein ReadS zurückgibt.
-- (c) The University of Glasgow 2002
type ReadS a = String -> [( a , String )] ReadS a ist ein Typ Alias für String -> [(a,String)] . Wenn Sie also sehen, wie Sie ReadS a , denken Sie String -> [(a,String)] .
-- (c) The University of Glasgow 2002
run :: P a -> String -> [( a , String )]
run ( Get f) (c : s) = run (f c) s
run ( Look f) s = run (f s) s
run ( Result x p) s = (x,s) : run p s
run ( Final r) _ = r
run _ _ = [] run entspricht den verschiedenen Fällen von P .
Get , ruft es sich mit einem neuen P (zurückgegeben durch Übergeben der Funktion f , in Get f , dem nächsten Zeichen c in der Eingangszeichenfolge) und dem Rest der Eingabezeichenfolge s .Look , ruft sich selbst mit einem neuen P (zurückgegeben durch Übergeben der Funktion f , in Look f , der Eingangszeichenfolge s ) und der Eingabezeichenfolge auf. Beachten Sie, wie Look keine Zeichen aus der Eingabezeichenfolge konsumiert wie Get .Result ist, setzt es ein Zwei-Tupel zusammen, das das analysierte Ergebnis und das, was von der Eingangszeichenfolge übrig ist, auf das Ergebnis eines rekursiven Aufrufs vorbereitet, der mit einem anderen P Fall und der Eingabezeichenfolge ausgeführt wird.Final ist, gibt run eine Liste von zwei Tupeln mit analysierten Ergebnissen und Eingabe-String-Resten zurück.run eine leere Liste zurück. Wenn der Fall beispielsweise Fail , gibt run eine leere Liste zurück. > run ( Get ( a -> Get ( b -> Result [a,b] Fail ))) " 12345 "
[( " 12 " , " 345 " )] ReadP enthüllt keinen run , aber wenn dies der Fall wäre, können Sie es so nennen. Die beiden Get S die '1' und '2' und lassen die "345" zurück.
> run ( Get ( a -> Get ( b -> Result [a,b] Fail ))) " 12345 "
> run ( Get ( b -> Result [ ' 1 ' ,b] Fail )) " 2345 "
> run ( Result [ ' 1 ' , ' 2 ' ] Fail ) " 345 "
> ([ ' 1 ' , ' 2 ' ], " 345 " ) : run ( Fail ) " 345 "
> ([ ' 1 ' , ' 2 ' ], " 345 " ) : []
[( " 12 " , " 345 " )]Wenn Sie jeden rekursiven Anruf durchlaufen, können Sie sehen, wie wir zum Endergebnis angekommen sind.
> run ( Get ( a -> Get ( b -> Result [a,b] ( Final [([ ' a ' , ' b ' ], " c " )])))) " 12345 "
[( " 12 " , " 345 " ),( " ab " , " c " )] Mit Final können Sie ein analysiertes Ergebnis in der endgültigen Liste der Zwei-Tupel einfügen.
-- (c) The University of Glasgow 2002
readP_to_S :: ReadP a -> ReadS a
-- readP_to_S :: ReadP a -> String -> [(a,String)]
readP_to_S ( R f) = run (f return ) Während ReadP run nicht direkt freilegt, enthält es ihn über readP_to_S . readP_to_S führt einen newtype namens ReadP vor. readP_to_S akzeptiert eine ReadP a , eine Zeichenfolge, und gibt eine Liste von zwei Tupeln zurück.
-- (c) The University of Glasgow 2002
newtype ReadP a = R ( forall b . ( a -> P b ) -> P b ) Hier ist die Definition von ReadP a . Es gibt Fälle für Functor, Applicativ, Monad, MonadFail , Alternative und MonadPlus . Der R -Konstruktor übernimmt eine Funktion, die eine andere Funktion übernimmt und eine P zurückgibt. Die akzeptierte Funktion nimmt alles, was Sie für a ausgewählt haben, und gibt a P zurück.
-- (c) The University of Glasgow 2002
readP_to_S ( R f) = run (f return ) Erinnern Sie sich daran, dass P ein Monad ist und der Typ von return ist a -> ma . Also ist f die (a -> P b) -> Pb -Funktion und return ist die (a -> P b) Funktion. Letztendlich bekommt run das P b das es erwartet.
-- (c) The University of Glasgow 2002
readP_to_S ( R f) inputString = run (f return ) inputString
-- ^ ^^^^^^^^^^ ^^^^^^^^^^^ Es ist im Quellcode aufgehört, aber denken Sie daran, dass readP_to_S und run eine Eingabezeichenfolge erwarten.
-- (c) The University of Glasgow 2002
instance Functor ReadP where
fmap h ( R f) = R ( k -> f (k . h)) Hier ist die Definition der Functor -Instanz für ReadP .
> readP_to_S ( fmap toLower get) " ABC "
[( ' a ' , " BC " )]
> readP_to_S (toLower <$> get) " ABC "
[( ' a ' , " BC " )] Dies ermöglicht es uns, so etwas zu tun. fmap -FUNKTOR MAPS toLower OVER DEN FUNKTOR get DIE GEHEN R Get . Erinnern Sie sich daran, dass die Art des Get (Char -> P a) -> P a den der ReadP -Konstruktor ( R ) akzeptiert.
-- (c) The University of Glasgow 2002
fmap h ( R f ) = R ( k -> f (k . h ))
fmap toLower ( R Get ) = R ( k -> Get (k . toLower)) Hier sehen Sie, wie die Functor Definition für den fmap toLower get Beispiel umgeschrieben wird.
Wie gab es zurück, wie readP_to_S [('a',"BC")] zurückgegeben hat, wenn wir nur verwendeten, was nicht Get , was run nicht beendet? Die Antwort liegt in der anwendbaren Definition für P .
-- (c) The University of Glasgow 2002
instance Applicative P where
pure x = Result x Fail
(<*>) = ap return EqualS Gon pure , damit wir readP_to_S (R f) = run (f return) neu schreiben konnten, um readP_to_S (R f) = run (f pure) zu sein. Durch die Verwendung von return oder eher pure ist readP_to_S Result x Fail , wenn der endgültige run auftritt. Wenn er erreicht wird, wird run enden und wir erhalten unsere Liste der Parsen.
> readP_to_S ( fmap toLower get) " ABC "
-- Use the functor instance to transform fmap toLower get.
> readP_to_S ( R ( k -> Get (k . toLower))) " ABC "
-- Call run which removes R.
> run (( k -> Get (k . toLower)) pure ) " ABC "
-- Call function with pure to get rid of k.
> run ( Get ( pure . toLower)) " ABC "
-- Call run for Get case to get rid of Get.
> run (( pure . toLower) ' A ' ) " BC "
-- Call toLower with 'A' to get rid of toLower.
> run ( pure ' a ' ) " BC "
-- Use the applicative instance to transform pure 'a'.
> run ( Result ' a ' Fail ) " BC "
-- Call run for the Result case to get rid of Result.
> ( ' a ' , " BC " ) : run ( Fail ) " BC "
-- Call run for the Fail case to get rid of Fail.
> ( ' a ' , " BC " ) : []
-- Prepend.
[( ' a ' , " BC " )] Hier sehen Sie den Fluss von readP_to_S zum analysierten Ergebnis.
-- (c) The University of Glasgow 2002
instance Alternative P where
-- ...
-- most common case: two gets are combined
Get f1 <|> Get f2 = Get ( c -> f1 c <|> f2 c)
-- results are delivered as soon as possible
Result x p <|> q = Result x (p <|> q)
p <|> Result x q = Result x (p <|> q)
-- ... Die Alternative Instanz für P ermöglicht es uns, den Fluss des Parsers in einen linken und rechten Weg aufzuteilen. Dies ist praktisch, wenn die Eingabe keine, einen oder (seltener) zwei von zwei Arten verlaufen kann.
> readP_to_S ((get >>= a -> return a) <|> (get >> get >>= b -> return b)) " ABC "
[( ' A ' , " BC " ),( ' B ' , " C " )] Der <|> Operator oder Funktion führt eine Gabel im Parserfluss ein. Der Parser fährt sowohl die linken als auch die rechten Wege. Das Endergebnis enthält alle möglichen Paruren, die links gingen, und alle möglichen Paruren, die nach rechts gingen. Wenn beide Pfade fehlschlagen, schlägt der gesamte Parser fehl.
Beachten Sie, dass der Parser in anderen Implementierungen des Parser -Kombinators bei Verwendung des <|> -Operators nach links oder rechts, aber nicht beides geht. Wenn der linke Erfolg hat, wird das rechte ignoriert. Die rechte wird nur verarbeitet, wenn die linke Seite fehlschlägt.
> readP_to_S ((get >>= a -> return [a]) <|> look <|> (get >> get >>= a -> return [a])) " ABC "
[( " ABC " , " ABC " ),( " A " , " BC " ),( " B " , " C " )] Sie können den <|> Bediener für so viele Optionen oder Alternativen ketten. Der Parser wird eine mögliche Parsen zurückgeben, die jeweils beteiligt.
-- (c) The University of Glasgow 2002
instance Monad ReadP where
fail _ = R ( _ -> Fail )
R m >>= f = R ( k -> m ( a -> let R m' = f a in m' k)) Hier ist die ReadP -Monad -Instanz. Beachten Sie die Definition für fail .
> readP_to_S (( a b c -> [a,b,c]) <$> get <*> get <*> get) " ABC "
[( " ABC " , " " )]
> readP_to_S (( a b c -> [a,b,c]) <$> get <*> fail " " <*> get) " ABC "
[]
> readP_to_S (get >>= a -> get >>= b -> get >>= c -> return [a,b,c]) " ABC "
[( " ABC " , " " )]
> readP_to_S (get >>= a -> get >>= b -> fail " " >>= c -> return [a,b,c]) " ABC "
[] Sie können einen gesamten Parser -Pfad bewirken, indem Sie fail . Da ReadP keine direkte Möglichkeit bietet, ein Result oder Final Fall zu generieren, ist der Rückgabewert eine leere Liste. Wenn der fehlgeschlagene Pfad der einzige Pfad ist, ist das gesamte Ergebnis eine leere Liste. Erinnern Sie sich daran, dass bei Fail run -Übereinstimmungen eine leere Liste zurückgegeben wird.
-- (c) The University of Glasgow 2002
instance Alternative P where
-- ...
-- fail disappears
Fail <|> p = p
p <|> Fail = p
-- ... Wenn Sie zur alternativen P -Instanz zurückkehren, können Sie sehen, wie ein Fehler auf beiden Seiten (aber nicht beides) den gesamten Parser nicht ausfällt.
> readP_to_S (get >>= a -> get >>= b -> pfail >>= c -> return [a,b,c]) " ABC "
[] Anstatt fail zu verwenden, bietet ReadP pfail , mit dem Sie direkt einen Fail -Fall generieren können.
GIFCURRY, der von Haskell gebaute Video-Editor für GIF-Macher, wird in verschiedenen Programmen ausgeschaltet. Um die Kompatibilität zu gewährleisten, benötigt sie die Versionsnummer für jedes der Programme, an die es ausgeschaltet ist. Eines dieser Programme ist Imagemagick.
Version: ImageMagick 6.9.10-14 Q16 x86_64 2018-10-24 https://imagemagick.org
Copyright: © 1999-2018 ImageMagick Studio LLC
License: https://imagemagick.org/script/license.php
Features: Cipher DPC HDRI Modules OpenCL OpenMP Hier sehen Sie die Ausgabe von convert --version . Wie können Sie dies analysieren, um die 6, 9, 10 und 14 zu erfassen?
Wenn wir uns die Ausgabe ansehen, wissen wir, dass die Versionsnummer eine Sammlung von Zahlen ist, die entweder durch einen Zeitraum oder einen Armaturenbrett getrennt sind. Diese Definition deckt auch die Daten ab, daher werden wir sicherstellen, dass die ersten beiden Zahlen durch einen Zeitraum getrennt sind. Auf diese Weise erhalten wir nicht das falsche Ergebnis, wenn sie ein Datum vor der Versionsnummer einstellen.
1. Consume zero or more characters that are not 0 through 9 and go to 2.
2. Consume zero or more characters that are 0 through 9, save this number, and go to 3.
3. Look at the rest of the input and go to 4.
4. If the input
- is empty, go to 6.
- starts with a period, go to 1.
- starts with a dash
- and you have exactly one number, go to 5.
- and you have more than one number, go to 1.
- doesn't start with a period or dash
- and you have exactly one number, go to 5.
- you have more than one number, go to 6.
5. Delete any saved numbers and go to 1.
6. Return the numbers found.Bevor wir in den Code eintauchen, ist hier der Algorithmus, den wir folgen werden.
parseVersionNumber
:: [ String ]
-> ReadP [ String ]
parseVersionNumber
nums
= do
_ <- parseNotNumber
num <- parseNumber
let nums' = nums ++ [num]
parseSeparator nums' parseVersionNumber parseVersionNumber ist der Hauptparser -Kombinator, der eine Eingangszeichenfolge für eine Versionsnummer analysiert. Es akzeptiert eine Liste von Zeichenfolgen und gibt eine Liste von Zeichenfolgen im Kontext des ReadP -Datentyps zurück. Die akzeptierte Liste der Zeichenfolgen ist nicht die Eingabe, die analysiert wird, sondern die Liste der bisher gefundenen Zahlen. Für den ersten Funktionsaufruf ist die Liste leer, da sie noch nichts analysiert hat.
parseVersionNumber
nums An der Spitze stellt parseVersionNumber eine Liste von Zeichenfolgen auf, die die aktuelle Liste der bisher gefundenen Zahlen sind.
_ <- parseNotNumber parseNotNumber verbraucht alles, was keine Zahl aus der Eingabezeichenfolge ist. Da wir uns nicht für das Ergebnis interessieren, verwerfen wir es ( _ <- ).
num <- parseNumber
let nums' = nums ++ [num]Als nächstes verbrauchen wir alles, was eine Zahl ist, und fügen dies dann der bisher gefundenen Liste der Zahlen hinzu.
parseSeparator nums' parseVersionNumber Nachdem parseVersionNumber die nächste Nummer verarbeitet hat, gibt sie die Liste der gefundenen Zahlen und sich selbst an parseSeparator weiter.
parseSeparator
:: [ String ]
-> ([ String ] -> ReadP [ String ])
-> ReadP [ String ]
parseSeparator
nums
f
= do
next <- look
case next of
" " -> return nums
(c : _) ->
case c of
' . ' -> f nums
' - ' -> if length nums == 1 then f [] else f nums
_ -> if length nums == 1 then f [] else return nums Hier sehen Sie parseSeparator .
next <- look
case next of
" " -> return nums
(c : _) -> look Sie es uns, das zu erhalten, was von der Eingangszeichenfolge übrig ist, ohne sie zu konsumieren. Wenn nichts mehr übrig ist, gibt es die gefundenen Zahlen zurück. Wenn jedoch noch etwas übrig ist, analysiert es den ersten Charakter.
case c of
' . ' -> f nums
' - ' -> if length nums == 1 then f [] else f nums
_ -> if length nums == 1 then f [] else return nums Wenn der nächste Charakter ein Zeitraum ist, rufen Sie parseVersionNumber erneut mit der aktuellen Liste der gefundenen Zahlen auf. Wenn es sich um einen Armaturenbrett handelt und wir genau eine Nummer haben, rufen Sie parseVersionNumber mit einer leeren Liste von Zahlen an, da es sich um ein Datum handelt. Wenn es sich um einen Armaturenbrett handelt und wir nicht genau eine Nummer haben, rufen Sie parseVersionNumber mit der Liste der bisher gefundenen Zahlen an. Andernfalls rufen Sie parseVersionNumber mit einer leeren Liste an, wenn wir genau eine Nummer haben, oder geben Sie die gefundenen Zahlen zurück, wenn wir nicht genau eine Nummer haben.
parseNotNumber
:: ReadP String
parseNotNumber
=
munch ( not . isNumber) parseNotNumber verwendet munch , den ReadP bietet. munch erhält das Prädikat (not . isNumber) , das für jeden Charakter, der nicht 0 bis 9 ist, wahr zurückgibt.
munch :: ( Char -> Bool ) -> ReadP String munch Continuous Calls get wenn das nächste Zeichen in der Eingabezeichenfolge das Prädikat erfüllt. Wenn dies nicht der Fall ist, gibt munch die Charaktere zurück, die gegebenenfalls getan werden. Da es nur get verwendet, gelingt Munch immer.
Beachten Sie, dass parseNumber in parseNotNumber ähnelt. Statt not . isNumber , das Prädikat ist nur isNumber .
parseNotNumber'
:: ReadP String
parseNotNumber'
=
many (satisfy ( not . isNumber)) Anstatt munch zu verwenden, können Sie parseNotNumber so schreiben, wobei many und satisfy - sowohl die ReadP bietet. Betrachtet man die Typ Signatur für many und akzeptiert einen einzelnen Parser -Kombinator ( ReadP a ). In diesem Fall wird der Parser -Kombinator satisfy .
> readP_to_S (satisfy ( not . isNumber)) " a "
[( ' a ' , " " )]
> readP_to_S (satisfy ( not . isNumber)) " 1 "
[] satisfy nimmt ein Prädikat und get den nächsten Charakter. Wenn das anerkannte Prädikat den wahren Renditen zurückgibt, satisfy das Charakter zurück. Ansonsten satisfy Anrufe pfail und scheitern.
> readP_to_S (munch ( not . isNumber)) " abc123 "
[( " abc " , " 123 " )]
> readP_to_S (many (satisfy ( not . isNumber))) " abc123 "
[( " " , " abc123 " ),( " a " , " bc123 " ),( " ab " , " c123 " ),( " abc " , " 123 " )] Mit many können Sie unerwünschte Ergebnisse erzielen. Letztendlich führen many ein oder mehrere Result ein. Aus diesem Grund gelingt es many immer.
> readP_to_S (many look) " abc123 "
-- Runs forever. many werden Ihren Parser ausführen, bis er fehlschlägt oder die Eingabe ausgeht. Wenn Ihr Parser nie versagt oder nie die Eingaben ausgeht, werden many niemals zurückkehren.
> readP_to_S (many (get >>= a -> return ( read (a : " " ) :: Int ))) " 12345 "
[( [] , " 12345 " ),([ 1 ], " 2345 " ),([ 1 , 2 ], " 345 " ),([ 1 , 2 , 3 ], " 45 " ),([ 1 , 2 , 3 , 4 ], " 5 " ),([ 1 , 2 , 3 , 4 , 5 ], " " )]Für jeden Index im Ergebnis wird das analysierte Ergebnis das Ergebnis sein, die Parser -Indexzeiten für die gesamte Eingabe ausgeführt zu haben.
> let parser = get >>= a -> return ( read (a : " " ) :: Int )
> let many' results = return results <|> (parser >>= result -> many' (results ++ [result]))
> readP_to_S (many' [] ) " 12345 "
[( [] , " 12345 " ),([ 1 ], " 2345 " ),([ 1 , 2 ], " 345 " ),([ 1 , 2 , 3 ], " 45 " ),([ 1 , 2 , 3 , 4 ], " 5 " ),([ 1 , 2 , 3 , 4 , 5 ], " " )] Hier ist eine alternative Definition für many . Auf der linken Seite von <|> gibt es die aktuellen Parserergebnisse zurück. Auf der rechten Seite von <|> wird der Parser ausgeführt, fügt das Ergebnis zu den aktuellen Parser -Ergebnissen hinzu und ruft sich mit den aktualisierten Ergebnissen auf. Dies hat einen kumulativen Sumentypeffekt, bei dem Index i das Parser -Ergebnis ist, das dem Parser -Ergebnis bei i - 1 , i - 2 , ... und 1 angehängt ist.
Jetzt, wo wir den Parser gebaut haben, lass uns ihn laufen.
> let inputString =
> " Some Program (C) 1234-56-78 All rights reserved. n
> Version: 12.345.6-7 n
> License: Some open source license. "
> readP_to_S (parseVersionNumber [] ) inputString
[([ " 12 " , " 345 " , " 6 " , " 7 " ], " n License: Some open source license. " )]Sie können sehen, dass die Versionsnummer auch dann korrekt extrahiert wurde, wenn das Datum vor dem vorliegende Datum ist.
Lassen Sie uns nun etwas komplizierteres analysieren - SRT -Dateien.
Für die Veröffentlichung von Gifcurry Six musste ich SRT -Dateien (Subrip Text) analysieren. SRT -Dateien enthalten Untertitel, mit denen Videoverarbeitungsprogramme Text oben in einem Video anzeigen. Normalerweise ist dieser Text der Dialog eines in verschiedenen Sprachen übersetzten Films. Indem der Text vom Video getrennt bleibt, muss es nur ein Video geben, das Zeit, Speicherplatz und Bandbreite spart. Die Video -Software kann den Text austauschen, ohne das Video auszutauschen müssen. Vergleichen Sie dies mit dem Einbrennen oder hartem Kodieren der Untertitel, in denen der Text zu einem Teil der Bilddaten wird, aus denen das Video besteht. In diesem Fall benötigen Sie ein Video für jede Sammlung von Untertiteln.
Inneres Video © Blender Foundation | www.sintel.org
Gifcurry kann eine SRT-Datei aufnehmen und die Untertitel für das Video-Slice Your Select einbrennen.
7
00:02:09,400 --> 00:02:13,800
What brings you to
the land of the gatekeepers?
8
00:02:15,000 --> 00:02:17,500
I'm searching for someone.
9
00:02:18,000 --> 00:02:22,200
Someone very dear?
A kindred spirit?Hier sehen Sie die englischen Untertitel für SINTEL (© Blender Foundation | www.sintel.org).
SRT ist vielleicht die grundlegendste aller Untertitelformate.
- Srt Untertitel | Matrosk
Das SRT -Dateiformat besteht aus Blöcken, einer für jeden Untertitel, der durch eine leere Linie getrennt ist.
2Am oberen Rand des Blocks befindet sich der Index. Dies bestimmt die Reihenfolge der Untertitel. Hoffentlich sind die Untertitel bereits in Ordnung und alle haben einzigartige Indizes, aber dies ist möglicherweise nicht der Fall.
01:04:13,000 --> 02:01:01,640 X1:167 X2:267 Y1:33 Y2:63Nach dem Index ist die Startzeit, die Endzeit und ein optionaler Satz von Punkten, die das Rechteck angeben, in dem der Untertiteltext eingeführt werden sollte.
01:04:13,000 Das Zeitstempelformat dauert hours:minutes:seconds,milliseconds .
Beachten Sie das Komma anstelle der Periode, die die Sekunden von den Millisekunden trennt.
This is the actual subtitle
text. It can span multiple lines.
It may include formating
like <b>bold</b>, <i>italic</i>,
<u>underline</u>,
and <font color="#010101">font color</font>.Der dritte und letzte Teil eines Blocks ist der Untertiteltext. Es kann mehrere Zeilen umfassen und endet, wenn eine leere Linie vorhanden ist. Der Text kann Formatierungs -Tags enthalten, die an HTML erinnern.
parseSrt
:: ReadP [ SrtSubtitle ]
parseSrt
=
manyTill parseBlock (skipSpaces >> eof) parseSrt ist der Hauptparser -Kombinator, der alles umgeht. Es analysiert jeden Block, bis es das Ende der Datei ( eof ) oder die Eingabe erreicht. Um auf der sicheren Seite zu sein, könnte zwischen dem letzten Block und dem Ende der Datei eine Blätterei nachfolgen. Um dies zu bewältigen, analysiert es null oder mehr Zeichen von Whitespace ( skipSpaces ), bevor es das Ende der Datei analysiert ( skipSpaces >> eof ). Wenn bis zum Erreichen eof noch eingegeben wird, wird eof fehlschlagen und dies gibt nichts zurück. Daher ist es wichtig, dass parseBlock nichts anderes als Whitespace hinter sich lässt.
parseBlock
:: ReadP SrtSubtitle
parseBlock
= do
i <- parseIndex
(s, e) <- parseTimestamps
c <- parseCoordinates
t <- parseTextLines
return
SrtSubtitle
{ index = i
, start = s
, end = e
, coordinates = c
, taggedText = t
} Als wir früher übergingen, besteht ein Block aus einem Index, Zeitstempeln, möglicherweise einigen Koordinaten und einigen Textzeilen. In dieser Version von parseBlock sehen Sie den Notationstil mit der Plattensyntax.
parseBlock'
:: ReadP SrtSubtitle
parseBlock'
=
SrtSubtitle
<$> parseIndex
<*> parseStartTimestamp
<*> parseEndTimestamp
<*> parseCoordinates
<*> parseTextLines Hier ist eine andere Möglichkeit, parseBlock zu schreiben. Dies ist der angelegte Stil. Achten Sie nur darauf, dass Sie die Bestellung richtig machen. Zum Beispiel hätte ich versehentlich den Start- und Endzeitstempel durcheinander bringen können.
parseIndex
:: ReadP Int
parseIndex
=
skipSpaces
>> readInt <$> parseNumber Am oberen Rand des Blocks befindet sich der Index. Hier sehen Sie wieder skipSpaces . Nach dem Überspringen von Whitespace analysiert es die Eingabe für Zahlen und konvertiert sie in eine tatsächliche Ganzzahl.
readInt
:: String
-> Int
readInt
=
read readInt sieht so aus.
> read " 123 " :: Int
123
> read " 1abc " :: Int
*** Exception : Prelude. read : no parse Normalerweise kann die direkte Verwendung read gefährlich sein. read kann möglicherweise nicht in der Lage sein, die Eingabe in den angegebenen Typ umzuwandeln. parseNumber gibt jedoch nur die 10 numerischen Ziffernzeichen zurück ( ['0'..'9'] ). Die Verwendung von read wird also direkt sicher.
Das Parsen der Zeitstempel ist etwas mehr involviert als das Parsen des Index.
parseTimestamps
:: ReadP ( Timestamp , Timestamp )
parseTimestamps
= do
_ <- char ' n '
s <- parseTimestamp
_ <- skipSpaces
_ <- string " --> "
_ <- skipSpaces
e <- parseTimestamp
return (s, e)Dies ist der Hauptkombinator für die Parsen der Zeitstempel.
char analysiert den Charakter, den Sie ihm geben oder es scheitert. Wenn es fehlschlägt, schlägt parseTimestamps fehl und führt letztendlich dazu, dass parseSrt fehlschlägt, so
string ist wie char , außer anstelle von nur einem Zeichen, es analysiert die Zeichenfolge, die Sie ihm geben, oder es scheitert.
parseStartTimestamp
:: ReadP Timestamp
parseStartTimestamp
=
char ' n '
>> parseTimestamp parseTimestamps analysiert beide Zeitstempel, aber für den Anwendungsstil ( parseSrt' ) brauchen wir einen Parser nur für den Start -Timestamp.
parseEndTimestamp
:: ReadP Timestamp
parseEndTimestamp
=
skipSpaces
>> string " --> "
>> skipSpaces
>> parseTimestampDies analysiert alles zwischen den Zeitstempeln und gibt den Endstempel zurück.
parseTimestamp
:: ReadP Timestamp
parseTimestamp
= do
h <- parseNumber
_ <- char ' : '
m <- parseNumber
_ <- char ' : '
s <- parseNumber
_ <- char ' , ' <|> char ' . '
m' <- parseNumber
return
Timestamp
{ hours = readInt h
, minutes = readInt m
, seconds = readInt s
, milliseconds = readInt m'
}Dies analysiert die vier Zahlen, aus denen der Zeitstempel besteht. Die ersten drei Zahlen werden durch einen Dickdarm getrennt und der letzte wird durch ein Komma getrennt. Um jedoch verzeihender zu sein, erlauben wir die Möglichkeit, dass es eine Zeit anstelle eines Kommas gibt.
> readP_to_S (char ' . ' <|> char ' , ' ) " ... "
[( ' . ' , " .. " )]
> readP_to_S (char ' . ' <|> char ' , ' ) " ,.. "
[( ' , ' , " .. " )] Beachten Sie, dass bei Verwendung von char mit <|> nur eine Seite erfolgreich sein kann (zwei char eingeben, ein char -Urlaub), da char ein einzelnes Zeichen konsumiert und zwei Zeichen nicht den gleichen Raum einnehmen können.
Die Koordinaten sind ein optionaler Bestandteil des Blocks, sind jedoch auf derselben Zeile wie die Zeitstempel.
parseCoordinates
:: ReadP ( Maybe SrtSubtitleCoordinates )
parseCoordinates
=
option Nothing $ do
_ <- skipSpaces1
x1 <- parseCoordinate ' x ' 1
_ <- skipSpaces1
x2 <- parseCoordinate ' x ' 2
_ <- skipSpaces1
y1 <- parseCoordinate ' y ' 1
_ <- skipSpaces1
y2 <- parseCoordinate ' y ' 2
return
$ Just
SrtSubtitleCoordinates
{ x1 = readInt x1
, x2 = readInt x2
, y1 = readInt y1
, y2 = readInt y2
} option nimmt zwei Argumente ein. Das erste Argument wird zurückgegeben, wenn das zweite Argument, ein Parser, fehlschlägt. Wenn der Koordinaten -Parser fehlschlägt, gibt parseCoordinates Nothing zurück. Anders ausgedrückt, der Koordinaten -Parser -Fehlschlag führt nicht dazu, dass der gesamte Parser fehlschlägt. Dieser Block wird einfach Nothing für seine coordinates "Feld" haben.
parseCoordinate
:: Char
-> Int
-> ReadP String
parseCoordinate
c
n
= do
_ <- char ( Data.Char. toUpper c) <|> char ( Data.Char. toLower c)
_ <- string $ show n ++ " : "
parseNumber Mit diesem Parser können sich die Koordinatenetiketten entweder in Großbuchstaben oder in Kleinbuchstaben befinden. Zum Beispiel würde x1:1 X2:2 Y1:3 y2:4 erfolgreich sein.
Das Analysieren des Textes ist aufgrund der HTML-ähnlichen Tag-Formatierung am meisten beteiligt.
Tag -Parsen kann eine Herausforderung sein - fragen Sie einfach jeden, der ihn mit einem regelmäßigen Ausdruck analysiert. Um dies zu erleichtern - und für den Benutzer - werden wir einen Ansatz der Tag -Suppe verwenden. Der Parser erlaubt nicht lehnte und/oder fälschlicherweise verschachtelte Tags. Es wird auch ein Tag und nicht nur b , u , i und font zulassen.
parseTextLines
:: ReadP [ TaggedText ]
parseTextLines
=
char ' n '
>> (getTaggedText <$> manyTill parseAny parseEndOfTextLines) Wir beginnen mit einem neuen Charakter. Danach Functor Map oder FMAP ( <$> ) getTaggedText über die Untertiteltextzeichen, bis wir das Ende der Textzeilen erreichen.
parseEndOfTextLines
:: ReadP ()
parseEndOfTextLines
=
void (string " nn " ) <|> eof Wir hören auf, Charaktere ( parseAny ) zu sammeln, wenn wir zwei Newline -Zeichen oder das Ende der Datei erreichen. Dies signalisiert das Ende des Blocks.
getTaggedText
:: String
-> [ TaggedText ]
getTaggedText
s
=
fst
$ foldl
folder
( [] , [] )
parsed
where getTaggedText faltet den analysierten Text von links nach rechts durch und gibt den akkumulierten markierten Text zurück.
parsed
:: [ String ]
parsed
=
case readP_to_S (parseTaggedText [] ) s of
[] -> [s]
r @ (_ : _) -> ( fst . last ) r parsed gibt eine Liste von einem oder mehreren Zeichenfolgen zurück. Es wird versucht, den Eingabtext für Tags zu analysieren. Wenn dies fehlschlägt, gibt parsed die Eingangszeichenfolge in einer Liste zurück. Andernfalls gibt parse , wenn parseTaggedText erfolgreich ist, das letzte mögliche Parsing ( (fst . last) r ) zurückgibt.
folder
:: ([ TaggedText ], [ Tag ])
-> String
-> ([ TaggedText ], [ Tag ])
folder
(tt, t)
x
| isTag x = (tt, updateTags t x)
| otherwise = (tt ++ [ TaggedText { text = x, tags = t}], t) Wenn sich folder von links nach rechts über die analysierten Saiten bewegt, überprüft er, ob die aktuelle Zeichenfolge ein Tag ist. Wenn es sich um ein Tag handelt, aktualisiert es den aktuellen Satz aktiver Tags ( t ). Andernfalls fügt es ein weiteres markiertes Textstück hinzu, das dem Satz aktiver Tags zugeordnet ist.
updateTags
:: [ Tag ]
-> String
-> [ Tag ]
updateTags
tags
x
| isClosingTag x = remove compare' tags (makeTag x)
| isOpeningTag x = add compare' tags (makeTag x)
| otherwise = tags
where
compare'
:: Tag
-> Tag
-> Bool
compare'
a
b
=
name a /= name b updateTags aktualisiert die tags , indem das angegebene Tag ( x ) entfernen oder hinzugefügt wird, je nachdem, ob es sich um ein Schließ- oder Öffnungs -Tag handelt. Wenn es auch nicht ist, gibt es nur die übergabes Set von Tags zurück. add überschreibt ein vorhandenes Tag, wenn tags bereits ein Tag zum gleichen Namen enthalten. Sie können dies in der gegebenen compare' sehen.
Um den Parser einfach zu halten, wird T, wenn ein Öffnungs -Tag T gefunden wird, T der Liste der Tags hinzugefügt oder überschreibt ein Ausgang T wenn er bereits vorhanden ist. Wenn ein entsprechendes Schließen /T gefunden wird, wird T aus der Liste der Tags entfernt, falls vorhanden. Es spielt keine Rolle, ob es zwei oder mehr T in einer Reihe gibt, ein oder mehrere T ohne Schließung /T und /oder es gibt ein Schluss /T ohne Öffnen T .
makeTag
:: String
-> Tag
makeTag
s
=
Tag
{ name = getTagName s
, attributes = getTagAttributes s
} makeTag stellt ein Tag aus den angegebenen s zusammen. Jedes Tag hat einen Namen und null oder mehr Attribute.
parseTaggedText
:: [ String ]
-> ReadP [ String ]
parseTaggedText
strings
= do
s <- look
case s of
" " -> return strings
_ -> do
r <- munch1 ( /= ' < ' ) <++ parseClosingTag <++ parseOpeningTag
parseTaggedText $ strings ++ [r] parseTaggedText gibt die Eingangszeichenfolge in Stücke zurück. Jedes Stück ist entweder der von Tags eingeschlossene Text, ein Schlussetikett oder ein Öffnungs -Tag. Nachdem es ein Stück abgebrochen hat, fügt es es den anderen Teilen hinzu und ruft sich wieder an. Wenn die verbleibende Eingangszeichenfolge leer ist, wird die Liste der gefundenen Zeichenfolgen zurückgegeben.
> readP_to_S (string " ab " <++ string " abc " ) " abcd "
[( " ab " , " cd " )]
> readP_to_S (string " ab " +++ string " abc " ) " abcd "
[( " ab " , " cd " ),( " abc " , " d " )]
> readP_to_S (string " ab " <|> string " abc " ) " abcd "
[( " ab " , " cd " ),( " abc " , " d " )] Der <++ Operator ist links vorgespannt, was bedeutet, dass sich die linke Seite nicht einmal mit dem Recht kümmert. Denken Sie daran, dass wir beim Ausführen des Parsers eine Liste aller möglichen Paruren erhalten. Alle diese möglichen Paruren sind das Ergebnis des Parsers, der durch alle möglichen Wege gereist ist. Durch die Verwendung <++ erhalten wir die möglichen Paruren vom linken Pfad und vom rechten Pfad nur, wenn die linke Seite fehlgeschlagen ist. Wenn Sie alle möglichen Paruren über die linke und rechte Seite möchten, können Sie den von ReadP bereitgestellten +++ -Operator verwenden. +++ ist nur <|> , was wir oben aufgesehen haben.
parseOpeningTag
:: ReadP String
parseOpeningTag
= do
_ <- char ' < '
t <- munch1 ( c -> c /= ' / ' && c /= ' > ' )
_ <- char ' > '
return $ " < " ++ t ++ " > "Ein Eröffnungs -Tag ist eine Öffnungswinkelhalterung, ein Text, der keinen Vorwärtsschrägstrich und die nächste unmittelbare Schließwinkelhalterung enthält.
parseClosingTag
:: ReadP String
parseClosingTag
= do
_ <- char ' < '
_ <- char ' / '
t <- munch1 ( /= ' > ' )
_ <- char ' > '
return $ " </ " ++ t ++ " > "Ein Schlussetikett ist eine Öffnungswinkelhalterung, ein Vorwärts -Schrägstrich, ein Text und die nächste unmittelbare Schließwinkelhalterung.
getTagAttributes
:: String
-> [ TagAttribute ]
getTagAttributes
s
=
if isOpeningTag s
then
case readP_to_S (parseTagAttributes [] ) s of
[] -> []
(x : _) -> fst x
else
[] Öffnen von Tags können Attribute haben. Zum Beispiel <font color="#101010"> . Jedes Attribut ist ein zwei-Tupel-Schlüssel-Wert-Paar. Im obigen Beispiel wäre color der Schlüssel und #101010 wäre der Wert.
getTagName
:: String
-> String
getTagName
s
=
case readP_to_S parseTagName s of
[] -> " "
(x : _) -> toLower' $ fst xDies gibt den Tag -Namen in Kleinbuchstaben zurück.
parseTagName
:: ReadP String
parseTagName
= do
_ <- char ' < '
_ <- munch ( == ' / ' )
_ <- skipSpaces
n <- munch1 ( c -> c /= ' ' && c /= ' > ' )
_ <- munch ( /= ' > ' )
_ <- char ' > '
return nDer Tag-Name ist die erste Zeichenfolge von Nicht-Whitespace-Zeichen nach der Eröffnungswinkelhalterung, einem möglichen Vorwärtsschrägstrich und einer möglichen Whitespace und vor einer weiteren Whitespace und/oder der Schließwinkelhalterung.
parseTagAttributes
:: [ TagAttribute ]
-> ReadP [ TagAttribute ]
parseTagAttributes
tagAttributes
= do
s <- look
case s of
" " -> return tagAttributes
_ -> do
let h = head s
case h of
' > ' -> return tagAttributes
' < ' -> trimTagname >> parseTagAttributes'
_ -> parseTagAttributes'
where
parseTagAttributes'
:: ReadP [ TagAttribute ]
parseTagAttributes'
= do
tagAttribute <- parseTagAttribute
parseTagAttributes
( add
( a b -> fst a /= fst b)
tagAttributes
tagAttribute
) parseTagAttributes wird rekursiv durch die Eingangszeichenfolge durchlaufen und sammelt die Schlüsselwertpaare. Zu Beginn des Tags ( < ) wird zunächst den Tag -Namen vorgezogen, bevor es sich mit den Attributen befasst. Es hört auf, Attribute zu analysieren, wenn es die Schließwinkelhalterung ( > ) erreicht. Wenn ein Tag doppelte Attribute (basierend auf dem Schlüssel) hat, stellt add sicher, dass nur die neueste in der Liste bleibt.
trimTagname
:: ReadP ()
trimTagname
=
char ' < '
>> skipSpaces
>> munch1 ( c -> c /= ' ' && c /= ' > ' )
>> return ()Dies ist der Tag -Name ab oder verworfen.
parseTagAttribute
:: ReadP TagAttribute
parseTagAttribute
= do
_ <- skipSpaces
k <- munch1 ( /= ' = ' )
_ <- string " = " "
v <- munch1 ( /= ' " ' )
_ <- char ' " '
_ <- skipSpaces
return (toLower' k, v)Der Attributschlüssel ist eine Zeichenfolge von Nicht-Whitespace-Zeichen vor dem gleichen Vorzeichen. Der Attributwert sind Zeichen nach dem gleichen Vorzeichen und doppeltes Zitat und vor dem nächsten sofortigen Doppelzitat.
isTag
:: String
-> Bool
isTag
s
=
isOpeningTag s || isClosingTag sEine Zeichenfolge ist ein Tag, wenn es sich entweder um ein Öffnungs -Tag oder ein Schlussetikett handelt.
isOpeningTag
:: String
-> Bool
isOpeningTag
s
=
isPresent $ readP_to_S parseOpeningTag sEine Zeichenfolge ist ein Eröffnungs -Tag, wenn der Eröffnungs -Tag -Parser erfolgreich ist.
isClosingTag
:: String
-> Bool
isClosingTag
s
=
isPresent $ readP_to_S parseClosingTag sEine Zeichenfolge ist ein Schlussetikett, wenn der Abschluss -Tag -Parser erfolgreich ist.
Nachdem wir den Parser zusammengestellt haben, probieren wir es aus.
> let srt =
> " 1 n
> :0:0,1 --> 0:1:0.2 x1:1 X2:3 y1:4 y2:10 n
> <font color= " red " color= " blue " >This is some <b><u><i> n
> subtitle n
> </u>text.</b> "
> readP_to_S parseSrt srt
[([ SrtSubtitle
{ index = 1
, start = Timestamp {hours = 0 , minutes = 0 , seconds = 0 , milliseconds = 1 }
, end = Timestamp {hours = 0 , minutes = 1 , seconds = 0 , milliseconds = 2 }
, coordinates = Just ( SrtSubtitleCoordinates {x1 = 1 , x2 = 3 , y1 = 4 , y2 = 10 })
, taggedText = [ TaggedText
{ text = " This is some "
, tags = [ Tag {name = " font " , attributes = [( " color " , " blue " )]}
]
}
, TaggedText
{ text = " n subtitle n "
, tags = [ Tag {name = " font " , attributes = [( " color " , " blue " )]}
, Tag {name = " b " , attributes = [] }
, Tag {name = " u " , attributes = [] }
, Tag {name = " i " , attributes = [] }
]
}
, TaggedText
{ text = " text. "
, tags = [ Tag {name = " font " , attributes = [( " color " , " blue " )]}
, Tag {name = " b " , attributes = [] }
, Tag {name = " i " , attributes = [] }
]
}
, TaggedText
{ text = " "
, tags = [ Tag {name = " font " , attributes = [( " color " , " blue " )]}
, Tag {name = " i " , attributes = [] }
]
}
]
}
]
, " "
)]Hier sehen Sie das Ergebnis des Parsens einer Testzeichenfolge. Beachten Sie die Fehler in der Testzeichenfolge wie die Verwendung eines Zeitraums anstelle eines Kommas oder des doppelten Tag -Attributs.
(C) 2019 David Lettier
lettier.com
