Парсер lisp на lisp

Узнай цену своей работы

Формулировка задачи:

Здравствуйте! Решил написать компилятор racket (диалект lisp) на racket, для того, чтобы легко можно было проверить его полноценность (компилирует сам себя - все хорошо, нет - нужно пилить дальше). До этого писал компилятор для маленького lisp на с++, так что (примерно) представляю, что нужно делать. Это первая большая программа на lisp, так что пока тяжело. Например: вот такую простую функцию:
function ast(tokens, from, to)
{
  if(from == undefined)
    from = 0;
 
  if(to == undefined)
    to = tokens.length
 
  var ret = [];
 
  for(var i=from; i<to; i++)
  {
    if(tokens[i] == "(")
    {
      var level = 1;
      var start = i;
      while(level!=0)
      {
        i++;
 
        if(tokens[i] == "(")
            level++;
 
         if(tokens[i] == ")")
            level--;
      }
 
      ret.push(ast(tokens, start+1, i));
    }
    else
        ret.push(tokens[i])
  }
 
  return ret; 
}
Я попытался написать вот так (код страшный и нерабочий):
(define (parse tokens from to)
  (cond
    [(>= from to) '#()]
    [(not (and (vector-has tokens "(") (vector-has tokens ")"))) tokens]
     [else (let* [(fb (vector-index tokens "("))
                (lb (end tokens 1 (+ fb 1)))]
            (println (string-append "fb = " (number->string fb)))
            (println (string-append "lb = " (number->string lb)))
 
            (cond
              [(and (= fb 0) (= lb (- (vector-length tokens) 1))) (parse tokens (+ fb 1) (- lb 1))]
              [(= fb 0) (vector-append (parse tokens (+ fb 1) lb) (parse tokens (+ lb 1) (- (vector-length tokens) 1)))]
              [(= lb (- (vector-length tokens) 1)) (vector-append (parse tokens 0 (- fb 1)) (parse tokens (+ fb 1) (- (vector-length tokens) 1)))]
              [else (vector-append (parse tokens 0 (- fb 1)) (parse tokens (+ fb 1) (- lb 1)) (parse tokens (+ lb 1) (- (vector-length tokens) 1)))]
              )
            )]) )
Помогите, пожалуйста, переписать.

Решение задачи: «Парсер lisp на lisp»

textual
Листинг программы
(define (delimiter? ch)
  (or (equal? ch #\()
      (equal? ch #\))
      (char-whitespace? ch)))
 
(define (match-token src)
  (let loop ((src src) (acc null))
    (if (delimiter? (first src))
        (values (list->string (reverse acc)) (rest src))
        (loop (rest src) (cons (first src) acc)))))
 
(define (match-list src)
  (cond ((and (list? src) (null? src)) src)
        ((equal? (first src) #\()
         (let ((src (rest src)))
           (cond ((null? src) src)
                 ((equal? (first src) #\)) null)
                 (else (let-values (((token rest) (match-token src)))
                         (cons token (match-list rest)))))))
        ((equal? (first src) #\)) null)
        (else (let-values (((token rest) (match-token src)))
                         (cons token (match-list rest))))))
 
(match-list (string->list "(defun foo nil)"))
'("defun" "foo" "nil")

Объяснение кода листинга программы

  1. delimiter? - это функция, которая проверяет, является ли символ ch разделителем. Она возвращает true, если символ является (, ) или пробелом, и false в противном случае.
  2. match-token - это функция, которая пытается сопоставить токен с помощью разделителя. Если следующий символ является разделителем, функция возвращает пару, состоящую из сопоставленного токена и оставшейся строки. Если это не так, функция вызывает себя рекурсивно для оставшейся строки и добавляет текущий символ к результату.
  3. match-list - это функция, которая пытается сопоставить список с помощью разделителя. Если входной список пуст, функция возвращает его. Если первый символ в списке является (, функция вызывает себя рекурсивно для оставшейся части списка и добавляет ( как первый элемент результата. Если первый символ является ), функция возвращает nil. В противном случае функция вызывает себя рекурсивно для оставшейся части списка и добавляет первый символ как первый элемент результата.
  4. (match-list (string->list(defun foo nil))) - это вызов функции match-list с входным списком, полученным из строки (defun foo nil). Функция возвращает список, содержащий defun, foo, nil.
  5. Результат вызова match-list (string->list(defun foo nil)) - это список, содержащий defun, foo, nil.

ИИ поможет Вам:


  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

9   голосов , оценка 3.778 из 5