0

我是 Common Lisp 的新手，作为第一个项目，我一直在研究一个简单的模式匹配器。我在使用星号 (*) 运算符表示列表中任何元素的 0 个或多个时遇到问题。因此模式 (x * z) 和匹配器 (xyyyz) 将返回 true，但模式 (x * z) 和匹配器 (xy) 将返回 false。

我的第一个想法：

(loop for x in pattern-list
  (eq x '*)
  ;if x is *, pause iterating through this list
  (loop for y in matcher-list
        ;somehow iterate one more value in the pattern list
        (eq x y) ;does the value just after the * in the pattern list equal the value in y?
        ;if they aren't the same symbol, just iterate matcher until they match, then resume incrementing though the pattern list
))

对不起，如果我的语法和括号有点不对劲。

这是我正在研究的较大模式匹配器的较小部分。这是我到目前为止所拥有的（在这种情况下，list1 是模式列表，而 list2 是匹配器列表）：

此代码的大部分来自此 SO 帖子：

仅使用“eq”在 common lisp 中设置相等函数

(defun comp-q (list1 list2) ;defun
  (if (and (not (null list1)) ;if list1 is not null AND
       (not (null list2))) ;if list2 is not null
  (let ((a (car list1)) (b (car list2))) ;a is the car (front) of list1 and b is the car of list 2
    (cond ((and (listp a) (listp b)) ;cond, evaluate the first thing in the list - are a and b lists?
           (and (comp-q a b) ;recursive call on a and b
                (comp-q (cdr list1) (cdr list2)))) ;recursive call on the cdr (tail) of a and b
          (t ;like an else for cond
           (and (or (eq a b) (eq a '?)) ;are a and b equal OR is a a '?'
                (comp-q (cdr list1) (cdr list2)))))) ;recursive call on the cdr of a and b
  (= (length list1) (length list2)))) ;are the lists equal?  only triggered if the null test fails (are they both not null)

使用loop宏是我最好的选择吗？是否可以“暂停”或跟踪列表上的迭代（我知道这是数组式的）？或者我应该尝试通过调用comp-q 中正在实现的每个列表的carand来继续递归工作？cdrdefun

谢谢。

4

1 回答 1

1

由于还没有人给出任何答案，并且由于建议使用递归方法，因此我在 Racket 中提出了一个示例来帮助您入门。转换为 Common Lisp 应该很简单。

(define (match pattern matcher)

  ; is the symbol a wildcard (i.e. does it end with an asterisk?
  ;   yes -> return true + the symbol without the asterisk
  ;   no  -> return false + the symbol itself
  (define (is-wildcard sym)
    (let ((str (symbol->string sym)))
      (if (string=? (substring str (sub1 (string-length str))) "*")
          (values #t (string->symbol (substring str 0 (sub1 (string-length str)))))
          (values #f sym))))

  ; we know wi is a wildcard; let's loop over matcher until done
  (define (match-wildcard wi pattern matcher)
    (if (empty? matcher)
        (list (cdr pattern) matcher)
        (if (eq? wi (car matcher))
            (match-wildcard wi pattern (cdr matcher))
            (list (cdr pattern) matcher))))

  ; main loop
  (if (or (empty? pattern) (empty? matcher))
      (and (empty? pattern )(empty? matcher))
      (let ((pa (car pattern)) (ma (car matcher)))
        (if (eq? pa ma)
            (match (cdr pattern) (cdr matcher))
            (let-values (((wildcard wi) (is-wildcard pa)))
              (if wildcard
                  (apply match (match-wildcard wi pattern matcher))
                  #f))))))

例子：

(match '(x y* z) '(x y y y z))
=> #t

(match '(x z* y) '(x y))
=> #t

(match '(x y* z) '(x y))
=> #f

(match '(x y*) '(x y))
=> #t

！

于 2013-09-16T19:58:50.913 回答