Форум программистов, компьютерный форум, киберфорум
Наши страницы
Lisp
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.67/3: Рейтинг темы: голосов - 3, средняя оценка - 4.67
rennnorb
19 / 10 / 6
Регистрация: 28.05.2014
Сообщений: 140
Завершенные тесты: 1
1

Парсер lisp на lisp

09.09.2017, 16:45. Просмотров 540. Ответов 13

Здравствуйте! Решил написать компилятор racket (диалект lisp) на racket, для того, чтобы легко можно было проверить его полноценность (компилирует сам себя - все хорошо, нет - нужно пилить дальше). До этого писал компилятор для маленького lisp на с++, так что (примерно) представляю, что нужно делать.

Это первая большая программа на lisp, так что пока тяжело.

Например: вот такую простую функцию:

Javascript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
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; 
}
Я попытался написать вот так (код страшный и нерабочий):

Lisp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
(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)))]
              )
            )]) )
Помогите, пожалуйста, переписать.
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
09.09.2017, 16:45
Ответы с готовыми решениями:

Книги или другой источник, где описана история версий Lisp и Common Lisp
Доброго времени суток.Такой вопрос,знаете какой-нибудь источник,где описана история версий Lisp и...

Организация циклов в Lisp (bee lisp demo)
разбираюсь с простыми задачами, эти пока не знаю, как решать... помогите пожалуйста. 1. Слова в...

Парсер тэга размера текста на Lisp
Здравствуйте! Как сделать простой парсер тега изменения размера текста? Например такой:...

Lisp и БД
Может кто подсказать, могут ли программы на диспе работать с такими БД как My SQL, SQL или другими?...

PC-Lisp v.3.00
Как загрузить файл (исходный код программы) в PC-lisp?

13
vlisp
509 / 481 / 114
Регистрация: 10.08.2015
Сообщений: 1,715
Завершенные тесты: 1
09.09.2017, 20:16 2
Может не стоит сразу заниматься ерундой, а для затравки заняться прикладным программированием, а то такое впечатление, что лисп создали для того, чтоб на нем дурью маялись. Это первое.
Второе - научись писать понятный код. Есть книги, в которых объясняется, что это такое и как его писать.
Третье, заведи себе гитхаб и там складируй свои наработки, авось кого-то и заинтересуешь
Когда приходишь на форум и заявляешь
Цитата Сообщение от rennnorb Посмотреть сообщение
Помогите, пожалуйста, переписать.
то таким образом позиционируешь себя не как, программиста, а как халявщика. А это прямой путь во фриланс и вообще вопрос о продолжении карьеры программиста.
1
rennnorb
09.09.2017, 22:33  [ТС]
  #3

Не по теме:


Я не очень понимаю, чем вас так задел мой вопрос.
Я знаю, что тот код, который я привел - далеко не самый лучший. Именно по этому я и пришел спросить, как его переписать. Заметьте, я прошу помочь переписать, а не написать за меня.

Причем тут фриланс и карьера, я не понял.



Не по теме:


Что-то мне подсказывает, что на других языках дурью занимаются не меньше, просто это вызывает меньше вопросов.

0
helter
Эксперт по математике/физике
3814 / 2841 / 307
Регистрация: 12.03.2013
Сообщений: 5,176
10.09.2017, 00:15 4
Неохота ставить Racket. vector-has — есть в нём такая функция? end в шестой ― это что за функция? Она следит за уровнями вложенности скобок?

На что ругается?

Вообще, общая идея понятна. Она очень нерациональная, потому что рекурсия нехвостовая. В учебниках часто объясняют разницу на примере нехвостовых и хвостовых Фибоначчи. Исходный код симпатичный, можно переделать его в хвостовую рекурсию, а в рэкете, наверно, и в цикл.

Не по теме:

Нормальная тема, не обращайте внимания на троллей.

0
Catstail
Модератор
24265 / 12234 / 2206
Регистрация: 12.02.2012
Сообщений: 19,860
10.09.2017, 12:08 5
А какой код должен парсить этот парсер? Лисповский?
0
rennnorb
19 / 10 / 6
Регистрация: 28.05.2014
Сообщений: 140
Завершенные тесты: 1
10.09.2017, 12:56  [ТС] 6
vector-has — есть в нём такая функция? end в шестой ― это что за функция? Она следит за уровнями вложенности скобок?
vector-has и end писал сам, код ниже. Вроде проверял, что они работают правильно, сейчас проверю еще раз.

Lisp
1
2
3
4
5
6
7
8
9
10
11
12
(define (vector-has v e [pos 0])
  (cond
    [(= pos (- (vector-length v) 1)) #f]
    [(equal? e (vector-ref v pos)) #t]
    [else (vector-has v e (+ pos 1))]) )
 
 
(define (end text level pos)
    (let ((nlevel (cond
     [(equal? "(" (vector-ref text pos))  (+ level 1)]
     [(equal? ")" (vector-ref text pos))  (- level 1)]
     [else level]))) (if (= nlevel 0) pos (end text nlevel (+ pos 1)))) )
А какой код должен парсить этот парсер? Лисповский?
Да, на лиспе. В идеале - свой собственный.
0
cybersatyr
Заблокирован
11.09.2017, 00:09 7
На мой взгляд всё не правильно. Начинается с простого: match-list. Дальше match-keyword, match-symbol, match-number, match-function. И хэш таблица или на худой конец список для хранения полученной информации об элементах. И только после начинаем строить аст с использованием имеющихся базовых примитивов.
0
rennnorb
19 / 10 / 6
Регистрация: 28.05.2014
Сообщений: 140
Завершенные тесты: 1
11.09.2017, 00:55  [ТС] 8
На мой взгляд всё не правильно. Начинается с простого: match-list. Дальше match-keyword, match-symbol, match-number, match-function. И хэш таблица или на худой конец список для хранения полученной информации об элементах. И только после начинаем строить аст с использованием имеющихся базовых примитивов.
Мне кажется, что последовательность действий должна быть такой:
Код
"(define (fact n) (if (= n 1) 1 (* (fact (- n 1)) n)))" =>
["(", "define", "(", "fact", "n", ")", "(", "if", "(", "=", "n", "1", ")", "1", "(", "*", "(", "fact", "(", "-", "n", "1", ")", ")", "n", ")", ")", ")"] =>
[["define", [ "fact", "n"], ["if", [ "=", "n", "1"], "1", ["*", ["fact", [ "-", "n", "1"]], "n"]]]]
И только после этого можно понять, где имя, где число, а где список.
0
cybersatyr
Заблокирован
11.09.2017, 00:57 9
lisp -- list processing. Поэтому читая поток из файла, нам надо первым делом формировать списки. В противном случае парсинг можно прерывать, т.к. если объект не список, то это не соответствует соглашению.
0
rennnorb
19 / 10 / 6
Регистрация: 28.05.2014
Сообщений: 140
Завершенные тесты: 1
11.09.2017, 01:00  [ТС] 10
Именно это я и пытаюсь сделать. Я получаю на вход текст, а получить хочу список, который представляет собой структуру программы.
0
cybersatyr
Заблокирован
11.09.2017, 01:29 11
Цитата Сообщение от rennnorb Посмотреть сообщение
а получить хочу список, который представляет собой структуру программы
Это уже готовое аст дерево. До него еще доработать надо. Вот для старта:
Lisp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
(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")
0
budden
198 / 99 / 4
Регистрация: 16.08.2015
Сообщений: 193
18.09.2017, 18:08 12
В целом же лисп разбирается методом рекурсивного спуска.

На верхнему уровне находится ф-я "прочитай, а что- я сам не знаю". Эта функция read смотрит на первую букву. Если видит скобку, запускаешь функцию "читать список", к-рая должна выбрать из входного потока всё вплоть до соответствующей закрывающей скобки. Функция "читать список" пропускает открывающую скобку и начинает строить список. Пропускает пробелы и пытается найти за ними закрывающую скобку. Если находит, то завершает сбор списка и возвращает его. Если находит не скобку, то пытается прочитать "что-то".

Если видишь открывающую кавычку, запускаешь функцию "читать строку", края читает и возвращает строку.
Если видишь минус или цифру - читаешь цифру. Если видишь букву - читаешь букву. Видишь ; - читаешь всё до конца строки .

На первый взгляд просто, и сделать читатель простого лиспа просто. В сложных лиспах всегда есть какие-нибудь нюансы, так что это будет выглядеть гораздо сложнее.

Посмотри, как сам racket это делает, в его же исходниках.
2
castorsky
1973 / 1076 / 87
Регистрация: 29.11.2013
Сообщений: 3,354
18.09.2017, 21:42 13
Цитата Сообщение от budden Посмотреть сообщение
На первый взгляд просто, и сделать читатель простого лиспа просто
Оно и в реальности просто. Другой вопрос что читать поток в список char'ов накладно и вообще не логично, только на троечку для студентов. А парсить string или raw-bytes уже не так тривиально для студентов.
2
budden
198 / 99 / 4
Регистрация: 16.08.2015
Сообщений: 193
18.09.2017, 23:24 14
Ну, раз ссылки не работают, то нечего и писать зря.

Добавлено через 1 час 19 минут
Общий смысл был в том, что github sbcl src/code/reader.lisp - это реальный код ридера common lisp.
2
18.09.2017, 23:24
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
18.09.2017, 23:24

lisp
Необходимо решить задания из текстового документа. Буду очень благодарен.

LISP
of the expressions: E→T E→E+T T→F T→T*F F→atom numeric F→atom simbolic Formula SOLUTIA=...

LISP рекурсии
Здравствуйте. Помогите пожалуйста решить. Атомы даны произвольные списки L1 и L2. Применение...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
14
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.
Рейтинг@Mail.ru