Re: rfc: curvbol - a lisp language for processing text (long)
Klaus Harbo <[email protected]> Sun, 06 Jun 2004 00:06:28 +0200
| Newsgroups | gmane.lisp.clump |
|---|---|
| Message-ID | <[email protected]> |
Marco Baringer wrote: >Arthur Lemmens <[email protected]> writes: > > >>Your specification looks interesting at first sight, but would be a lot >>more readable if you included examples of each operator. Some kind of >>motivation and a comparison with other systems (why/when is this better= / >>worse than regular expressions, recursive decent parsers, parser genera= tors) >>would also help a lot. >> > >lisp already has regexps, recursive desecent parsers and parser >generators, i'm not trying to replace/improve any of those, i'm >attempting a different way looking at the problem. instead of >describing the grammar of the file (which i many not know, or may not >be expressable as a context free grammar) or mixing lisp code with >regexp checks (which gets very messy if the logic is complicated) i >want to express how to move around in the text and say what to do with >certain sections of the text. basically this is another tool to put in >the toolbox, not a replacement for the other techniques. > >Anyway here's the list of ops with examples. at the end of this >(rather long) email i've put a real life curvbol program. it is in >fact the only existing real life curvbol program :). > >Before i begin, curvbol programs are called via the curvbol macro: > > <snip> >well, at least this takes care of the docs :) > Hi- Since it seems that I have been struggling with similar challenges as=20 Marco's, I thought I'd chip in with the approach I've taken to deal with=20 the horrors of using regular expressions to do text pattern matching. =20 I've put a (thin) syntactical layer on top of Edi Weitz' cl-ppcre=20 package which enables the definition and use of (Perl) regular=20 expression abstractions. To illustrate the use of this layer (which I'be dubbed 'defpatt'), I've=20 taken Marco's example (to the best of my ability, the explanations are=20 brief, and I'm not entirely sure I've understood completely the nature=20 of the data Marco's curvbol program is intended to match) and matched=20 the data using cl-ppcre and defpatt, which results in the following=20 snippet of code: (in-package :cl-user) (use-package :cl-ppcre) (use-package :defpatt) (defpatt-initialize) (setf *example* ; my take on a potential instance of Marco's data "Some arbitrary data - does not matter what it is Padiglione Some arbitrary data - does not matter what it is <FONT color=3D\"red\"> 123 456 444 Some arbitrary data - does not matter what it is Some arbitrary data - does not matter what it is <b><span style=3D\"background-color: #000000\"><font=20 color=3D\"#FFFFFF\">the-ragione-sociale<BR> Some arbitrary data - does not matter what it is Some arbitrary data - does not matter what it is <font>address-value<BR>zzzz 2222222 Some arbitrary data, it does not matter what it is Some arbitrary data, it does not matter what it is -citta value-some unused text-paese value- blah blah <blah>Tel. 2323-321313</blah> blah blah blah blah <blah>Fax 4444-343434</blah> blah blah blah blah <TD WIDTH =3D\"305\"> E-Mail: [email protected]</TD>=20 blah blah ") (defpatt match-upto-and-consume (patt) (seq (reg (upto patt)) patt)) 'seq' is the sequential operator, 'reg' creates a cl-ppcre register=20 binding, 'upto' is a defpatt pattern matching abstraction which matches=20 data up-to-but-not-including the pattern given as argument. (defpatt match-the-data () =A4(seq (upto+ "Padiglione") (upto+ "<FONT color=3D\"red\">") (reg (++ (alt #\Space digit))) ; REGISTER padiglione (upto+ "<b><span style=3D\"background-color: #000000\"><font=20 color=3D\"#FFFFFF\">") ws* (match-upto-and-consume (alt ws+ "<BR>")) ; REGISTER=20 ragione-sociale (upto+ "<font>") ws* (match-upto-and-consume (alt ws+ "<BR>")) ; REGISTER address (?? (seq (upto digit) (reg digit+))) ; REGISTER cap (upto+ "-") ws* (?? (match-upto-and-consume "-")) ; REGISTER citta (upto+ "-") ws* (?? (match-upto-and-consume "-")) ; REGISTER paese )) Note that defpatt introduces (by default, not required) #\=A4 as a=20 macro-character for referencing defpatt definitions. (defpatt contact-info () (alt (seq (alt "Tel." "Fax") ws+ (++ (alt ws digit =A4"[-\\+ ()/]"))) (seq "E-Mail:" (upto "</TD>")))) So much for the defitions. The above defitions lets us do the following matching on *example*: CL-USER > (cl-ppcre:register-groups-bind (padiglione ragione-social= e address cap=20 citta paese) (=A4match-the-data *example*) (list padiglione ragione-sociale address cap citta paese)) (" 123 456 444" "the-ragione-sociale" "address-value" "2222222" "citta value" "paese value") This does not deal with the contact info (phone, fax, email data), and -=20 judging from the explanation Marco provides, it is not simple to match=20 with REs when the order of the contact info pieces is not known. However - at the price of scanning the text twice - they could be fairly=20 easy to pick out, and it is then trivial to extract the values from the=20 contact strings... CL-USER > (cl-ppcre:all-matches-as-strings =A4contact-info *example= *) =3D> ("Tel. 2323-321313" "Fax 4444-343434" "E-Mail: [email protected]= ") The expansion of the `defpatt' expressions to cl-ppcre's internal=20 representation is easy to retrieve (although you do not normally need it=20 when using `defpatt'): CL-USER > =A4(seq (upto+ "Padiglione") (upto+ "<FONT color=3D\"red\">") (reg (++ (alt #\Space digit))) ; REGISTER=20 padiglione (upto+ "<b><span style=3D\"background-color:=20 #000000\"><font color=3D\"#FFFFFF\">") ws* (match-upto-and-consume (alt ws+ "<BR>")) ; REGISTER=20 ragione-sociale (upto+ "<font>") ws* (match-upto-and-consume (alt ws+ "<BR>")) ; REGISTER=20 address (?? (seq (upto digit) (reg digit+))) ; REGISTER ca= p (upto+ "-") ws* (?? (match-upto-and-consume "-")) ; REGISTER ci= tta (upto+ "-") ws* (?? (match-upto-and-consume "-")) ; REGISTER pa= ese ) (:SEQUENCE (:SEQUENCE (:SEQUENCE (:FLAGS :SINGLE-LINE-MODE-P) (:GREEDY-REPETITION 0 NIL (:SEQUENCE :EVERYTHING=20 (:NEGATIVE-LOOKAHEAD "Padiglione"))) :EVERYTHING) "Padiglione") (:SEQUENCE (:SEQUENCE (:FLAGS :SINGLE-LINE-MODE-P) (:GREEDY-REPETITION 0 NIL (:SEQUENCE :EVERYTHING=20 (:NEGATIVE-LOOKAHEAD "<FONT color=3D\"red\">"))) :EVERYTHING) "<FONT color=3D\"red\">") (:REGISTER (:GREEDY-REPETITION 1 NIL (:ALTERNATION #\Space=20 (:CHAR-CLASS (:RANGE #\0 #\9))))) (:SEQUENCE (:SEQUENCE (:FLAGS :SINGLE-LINE-MODE-P) (:GREEDY-REPETITION 0 NIL (:SEQUENCE :EVERYTHING (:NEGATIVE-LOOKAHEAD "<b><span=20 style=3D\"background-color: #000000\"><font color=3D\"#FFFFFF\">"))) :EVERYTHING) "<b><span style=3D\"background-color: #000000\"><font=20 color=3D\"#FFFFFF\">") (:GREEDY-REPETITION 0 NIL :WHITESPACE-CHAR-CLASS) (:SEQUENCE (:REGISTER (:SEQUENCE (:FLAGS :SINGLE-LINE-MODE-P) (:GREEDY-REPETITION 0 NIL (:SEQUENCE :EVERYTHING (:NEGATIVE-LOOKAHEAD=20 (:ALTERNATION (:GREEDY-REPETITION 1 NIL :WHITESPACE-CHAR-CLASS) "<BR>")))= ) :EVERYTHING)) (:ALTERNATION (:GREEDY-REPETITION 1 NIL=20 :WHITESPACE-CHAR-CLASS) "<BR>")) (:SEQUENCE (:SEQUENCE (:FLAGS :SINGLE-LINE-MODE-P) (:GREEDY-REPETITION 0 NIL (:SEQUENCE :EVERYTHING=20 (:NEGATIVE-LOOKAHEAD "<font>"))) :EVERYTHING) "<font>") (:GREEDY-REPETITION 0 NIL :WHITESPACE-CHAR-CLASS) (:SEQUENCE (:REGISTER (:SEQUENCE (:FLAGS :SINGLE-LINE-MODE-P) (:GREEDY-REPETITION 0 NIL (:SEQUENCE :EVERYTHING (:NEGATIVE-LOOKAHEAD=20 (:ALTERNATION (:GREEDY-REPETITION 1 NIL :WHITESPACE-CHAR-CLASS) "<BR>")))= ) :EVERYTHING)) (:ALTERNATION (:GREEDY-REPETITION 1 NIL=20 :WHITESPACE-CHAR-CLASS) "<BR>")) (:GREEDY-REPETITION 0 1 (:SEQUENCE (:SEQUENCE (:FLAGS :SINGLE-LINE-MODE-P) (:GREEDY-REPETITION 0 NIL (:SEQUENCE :EVERYTHING=20 (:NEGATIVE-LOOKAHEAD (:CHAR-CLASS (:RANGE #\0 #\9))))) :EVERYTHING) (:REGISTER (:GREEDY-REPETITION 1 NIL (:CHAR-CLASS=20 (:RANGE #\0 #\9)))))) (:SEQUENCE (:SEQUENCE (:FLAGS :SINGLE-LINE-MODE-P) (:GREEDY-REPETITION 0 NIL (:SEQUENCE :EVERYTHING=20 (:NEGATIVE-LOOKAHEAD "-"))) :EVERYTHING) "-") (:GREEDY-REPETITION 0 NIL :WHITESPACE-CHAR-CLASS) (:GREEDY-REPETITION 0 1 (:SEQUENCE (:REGISTER (:SEQUENCE (:FLAGS :SINGLE-LINE-MODE-P) (:GREEDY-REPETITION 0 NIL (:SEQUENCE :EVERYTHING=20 (:NEGATIVE-LOOKAHEAD "-"))) :EVERYTHING)) "-")) (:SEQUENCE (:SEQUENCE (:FLAGS :SINGLE-LINE-MODE-P) (:GREEDY-REPETITION 0 NIL (:SEQUENCE :EVERYTHING=20 (:NEGATIVE-LOOKAHEAD "-"))) :EVERYTHING) "-") (:GREEDY-REPETITION 0 NIL :WHITESPACE-CHAR-CLASS) (:GREEDY-REPETITION 0 1 (:SEQUENCE (:REGISTER (:SEQUENCE (:FLAGS :SINGLE-LINE-MODE-P) (:GREEDY-REPETITION 0 NIL (:SEQUENCE :EVERYTHING=20 (:NEGATIVE-LOOKAHEAD "-"))) :EVERYTHING)) "-"))) Quite a bit! - Compared to the above, the `defpatt' expression for=20 'match-the-data' is relatively easy to understand. Using macroexpansion, we can see how the `defpatt' expression is=20 expanded using labels' and `symbol-macrolet': CL-USER > (macroexpand-1 '=A4(seq (upto+ "Padiglione") (upto+ "<FONT color=3D\"red\">") (reg (++ (alt #\Space=20 digit))) ; REGISTER padiglione (upto+ "<b><span=20 style=3D\"background-color: #000000\"><font color=3D\"#FFFFFF\">") ws* (match-upto-and-consume (alt ws+=20 "<BR>")) ; REGISTER ragione-sociale (upto+ "<font>") ws* (match-upto-and-consume (alt ws+=20 "<BR>")) ; REGISTER address (?? (seq (upto digit) (reg=20 digit+))) ; REGISTER cap (upto+ "-") ws* (?? (match-upto-and-consume=20 "-")) ; REGISTER citta (upto+ "-") ws* (?? (match-upto-and-consume=20 "-")) ; REGISTER paese )) (LABELS ((SEQ (&REST DEFPATT::ARGS) `(:SEQUENCE ,@DEFPATT::ARG= S)) (UPTO (DEFPATT::PATT) `(:SEQUENCE (:FLAGS :SINGLE-LINE-MODE-P) (:GREEDY-REPETITION 0 NIL (:SEQUENCE :EVERYTHING=20 (:NEGATIVE-LOOKAHEAD ,DEFPATT::PATT))) :EVERYTHING)) (++ (DEFPATT::PATT) (REP DEFPATT::PATT 1 NIL)) (?? (DEFPATT::PATT) (REP DEFPATT::PATT 0 1)) (UPTO+ (DEFPATT::PATT) `(:SEQUENCE ,(UPTO=20 DEFPATT::PATT) ,DEFPATT::PATT)) (ALT (&REST DEFPATT::ARGS) `(:ALTERNATION=20 ,@DEFPATT::ARGS)) (** (DEFPATT::PATT) (REP DEFPATT::PATT 0 NIL)) (MATCH-UPTO-AND-CONSUME (PATT) (SEQ (REG (UPTO=20 PATT)) PATT)) (REG (&REST DEFPATT::ARGS) `(:REGISTER ,@DEFPATT::ARG= S)) (REP (DEFPATT::PATT &OPTIONAL (MIN 0) (MAX NIL))=20 `(:GREEDY-REPETITION ,MIN ,MAX ,DEFPATT::PATT))) (SYMBOL-MACROLET ((WS :WHITESPACE-CHAR-CLASS) (CONTACT-INFO (ALT (SEQ (ALT "Tel." "Fax") WS+ (++ (ALT WS=20 DIGIT (DEFPATT-PATTERN "[-\\+ ()/]")))) (SEQ "E-Mail:" (UPTO "</TD>")))) (DIGIT '(:CHAR-CLASS (:RANGE #\0 #\9))) (WS* (** WS)) (DIGIT* (** DIGIT)) (WS+ (++ WS)) (DIGIT+ (++ DIGIT))) (SEQ (UPTO+ "Padiglione") (UPTO+ "<FONT color=3D\"red\">") (REG (++ (ALT #\Space DIGIT))) (UPTO+ "<b><span=20 style=3D\"background-color: #000000\"><font color=3D\"#FFFFFF\">") WS* (MATCH-UPTO-AND-CONSUME (ALT WS+ "<BR>")) (UPTO+ "<font>") WS* (MATCH-UPTO-AND-CONSUME (ALT WS+ "<BR>")) (?? (SEQ (UPTO DIGIT) (REG DIGIT+))) (UPTO+ "-") WS* (?? (MATCH-UPTO-AND-CONSUME "-")) (UPTO+ "-") WS* (?? (MATCH-UPTO-AND-CONSUME "-"))))) I've found the ability the create pattern matching abstractions goes a=20 long way. As you can see above, the expressions do enable you capture=20 the data Marco wanted to match inside 'match-the-data' - the lack of=20 knowledge of the order of the data makes it impossible to bind cl-ppcre=20 registers. Clearly that is a weakness relative to the curvbol=20 approach. On the other hand, I find that although the curvbol code=20 enables the capture of the data comes at a price: a more imperative=20 operation which (I think, at least) makes the code somewhat harder to=20 understand. `defpatt' is freely available for download at=20 http://www.harbo.net/downloads/defpatt-0.2.tar.gz. best, -Klaus.