Recursion in Common Lisp

Question

I am trying to use recursion in a Common Lisp project to check if a regular expression follows specific "rules". Here is precisely what I need to achieve:

I can have different types of regular expressions (RE), the basic one is just an atom (e.g. 'a), then we can have more complex expressions represented as follows (e.g '(star (seq a b)):

• [re1][re2]…[rek] becomes (seq [re1] [re2] … [rek])
• [re1]|[re2]…[rek] becomes (or [re1] [re2] … [rek])
• [re]* becomes (star [re])
• [re]+ becomes (plus [re])

The alphabet of the symbols is composed of Lisp S-exps.

I want to implement this function in COMMON LISP:

(is-regular-xp RE) returns TRUE when RE is a regular expression; false (NIL) in any other case.

This is what I have already written, it works in every case, EXCEPT when I check a RE that starts with an accepted atom, but then contains a not accepted one. For example: if you try to check (is-regexp '(seq a b)) LispWorks returns TRUE. Which is correct! But if you try (is-regexp '(seq (crazytest a b))) it returns, again TRUE, which is wrong! In this case "crazytest" doesn't exist in my grammar and the console should return NIL.

(defun is-regexp (RE)

  ;;Enters this check only if RE is a list

  (if (listp RE)
      (if (atom (car RE))

          ;;Verifies that the first element of the list is accepted

          (cond ((eql (car RE) 'seq) T)
                ((eql (car RE) 'or) T)
                ((eql (car RE) 'star) T)
                ((eql (car RE) 'plus) T)))

    ;;Enters this check only if RE is not a list

    (if (not(listp RE))
        (if (atom 'RE) T)
      )
    )  
  )

The problem that I want to resolve is the recursive check of the inner regular expressions, I tried to put a recursive call to "is-regexp" using "cdr" to analyze only the rest of the list, but it still doesn't work...

Thank you in advance for your precious help!

Answer 1

Try this:

CL-USER> (defun is-regexp (RE)
           (cond ((null RE) nil)
                 ((atom RE) t)
                 ((consp RE)
                  (and (member (car RE) '(seq or star plus))
                       (every #'is-regexp (cdr RE))))
                 (t nil)))
IS-REGEXP
CL-USER> (is-regexp 'a)
T
CL-USER> (is-regexp '(star (seq a b)))
T
CL-USER> (is-regexp '(seq (crazytest a b)))
NIL

Note that this function does not check for the length of the list of the operators as it should. This is left as exercise to you.

Answer 2

This sort of problem is quite a natural fit for CLOS, if you have the right mindset. Using CLOS also has the advantage that it's probably not something people can submit as homework.

This code doesn't do quite what you want (it assumes that the basic regexps are only symbols), but could be changed to do so.

(defgeneric valid-regexp-p (r)
  ;; Is something a valid regular expression?
  (:method ((r t))
   nil))

(defmethod valid-regexp-p ((r symbol))
  t)

(defmethod valid-regexp-p ((r cons))
  (valid-operator-regexp-p (first r) (rest r)))

(defgeneric proper-list-p (l)
  (:method ((l t))
   nil)
  (:method ((l null))
   t)
  (:method ((l cons))
   (proper-list-p (rest l))))

(defgeneric valid-operator-regexp-p (op body)
  (:method :around (op body)
   (and (proper-list-p body)
        (call-next-method)
        (every #'valid-regexp-p body)))
  (:method (op body)
   nil))

(defmethod valid-operator-regexp-p ((op (eql 'seq)) body)
  t)

(defmethod valid-operator-regexp-p ((op (eql 'or)) body)
  t)

(defmethod valid-operator-regexp-p ((op (eql 'star)) body)
  (= (length body) 1))

(defmethod valid-operator-regexp-p ((op (eql '+)) body)
  (= (length body) 1))

I don't think that, in real life, I'd write proper-list-p like that, but it's quite cool I think.