racket pattern matching do none greedy match

2
votes

Pattern matching in Racket-language has ... to do greedy matching( match 0 or more ), what if I want to match something like this:

#lang racket

(define (Modifier? t)  (equal? t "Modifier"))

(define (SimpleName? t)  (equal? t "SimpleName"))

(define (SimpleType? t)  (equal? t "SimpleType"))

(define (FieldDeclaration? t)  (equal? t "FieldDeclaration"))


(match (match '("FieldDeclaration" ("Modifier") ("Modifier") ("SimpleType") ("VariableDeclarationFragment" ("SimpleName") ("StringLiteral")))
   [(list (? FieldDeclaration? id) (? Modifier? m) ... (? SimpleType? t) (list _ (? SimpleName? n)) _ ...)
'yes]

   [else 'no] )

which print 'no ,while I expect 'yes. I guess it caused by ... which do a greedy matching (just search "greedy" in the linked page) ,However I'm not quite sure about this ....)

there can be 0 to 3 ("Modifier") s in the list, so how can I match this form? ( Actually ,there are more things to do in the function XXX? so I have to use the form (? XXX? x) )

PS: Does it possible to extend the matching syntax so I can use something like n_m which means matching n to m times ,just like {n,m} in regular expression?

2
regexpattern-matchingracket

2 Answers

3
votes

Actually ... isn't greedy and you were very close to having it working. Two problems:

First, three of your predicates were wrong. Since your input is e.g. ("Modifier") not "Modifier", you want to match (list "Modifier") not "Modifier".

(define (Modifier? t)
  (equal? t (list "Modifier")))

(define (SimpleName? t)
  (equal? t (list "SimpleName")))

(define (SimpleType? t)
  (equal? t (list "SimpleType")))

This predicate is OK:

(define (FieldDeclaration? t)
  (equal? t "FieldDeclaration"))

Second, I think you had a misplaced closing paren in the final part of your template -- it should be (list _ (? SimpleName? n) _ ...) not (list _ (? SimpleName? n)) _ ....

Here's the full match expression, I put in some line-breaks to make it more readable to me:

(match '("FieldDeclaration"
         ("Modifier") ("Modifier")
         ("SimpleType")
         ("VariableDeclarationFragment" ("SimpleName") ("StringLiteral")))
  [(list (? FieldDeclaration? id)
         (? Modifier? m) ...
         (? SimpleType? t)
         (list _ (? SimpleName? n) _ ...))
   'yes]
  [_ 'no])

This prints 'yes.

0
votes

Greg writes, "Actually ... isn't greedy", but the ... is greedy as shown in these examples:

[email protected]> (match '(1 2 7 3 4 5 3 6 7 3 8) [(list a ... 3 b ...) (list a b)])
'((1 2 7 3 4 5 3 6 7) (8))

(match '(1 2 7 3 4 5 3 6 7 3 8) [(list (? number? a) ... 3 b ...) (list a b)])
'((1 2 7 3 4 5 3 6 7) (8))

I had expected to see '((1 2 7) (4 5 3 6 7 3 8)). I've run into problems in matching where I want the prefix, but am getting the greedy behavior.