Как использовать символы и списки в схеме для обработки данных?

Я новичок в схеме, и я нахожусь в процессе написания функции, которая проверяет парное разделение правил (пока что оно неполное), я использовал символы и списки для представления правил грамматики. Символ в верхнем регистре не является терминалом в грамматике, а символ в нижнем регистре является терминалом. Я пытаюсь проверить, проходит ли правило тест на попарно дизъюнктность.

  1. В основном я проверю, есть ли в правиле только один уникальный терминал. если это так, то это правило проходит тест на попарно дизъюнктность. В схеме я думаю реализовать это, представив символ терминала в нижнем регистре. Примером этого правила будет:

    '(A <= (a b c))

  2. Затем я проверю случай правила, которое содержит или. лайк:

    '(A <= (a (OR (a b) (a c))))

  3. Наконец, я проверю рекурсивно для нетерминалов. Правило для этого случая будет

    '(A <= (B b c))

    Однако, что меня застревает, так это то, как использовать эти символы в качестве данных для их обработки и обработки. Я думал о преобразовании символов в строки, но это было не так в случае, например, такого списка '(a b c) Как мне это сделать? Вот что я достиг до сих пор:

    #lang racket
(define grammar
   '(A <= (a A b))
    )

(define (pairwise-disjoint lst)
  (print(symbol->string (car lst)))
  (print( cddr lst))
 )
Источник

3 ответа

Решение

Попарно не пересекаются

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

(define (contains-match? x lst)
  (cond ((null? x) #f)           ; Nothing to do
        ((null? lst) #f)         ; Finished walking full list
        ((eq? x (car lst)) #t)   ; Found a match, no need to go further
        (else
          (contains-match? x (cdr lst))))) ; recursive call to keep walking

(define (pairwise-disjoint? lst)
  (if (null? lst) #f
    (let ((x (car lst))         ; let inner vars just for readability
          (tail (cdr lst)))
      (not
        ;; for each element, check against all later elements in the list
        (or (contains-match? x tail)
            (contains-match? (car tail) (cdr tail)))))))

Мне не ясно, что еще вы пытаетесь сделать, но это будет общий метод. В зависимости от ваших данных вам может потребоваться использовать другую (или даже сделанную на заказ) проверку на равенство, но это работает так же, как и для обычных символов:

]=> (pairwise-disjoint? '(a b c d e))
;Value: #t

]=> (pairwise-disjoint? '(a b c d e a))
;Value: #f

Символы и данные

Этот раздел основан на том, что я считаю довольно фундаментальным неправильным пониманием основ схемы со стороны OP, и некоторыми предположениями о том, какова их реальная цель. Пожалуйста, уточните вопрос, если следующий бит вам не поможет!

Тем не менее, что меня застревает, так это то, как использовать эти символы в качестве данных...

В схеме вы можете связать символ с тем, что вы хотите. На самом деле, define Ключевое слово действительно просто говорит переводчику "Всякий раз, когда я говорю contains-match? (который является символом) Я на самом деле имею в виду этот большой набор инструкций, поэтому запомните это ". Интерпретатор запоминает это, сохраняя символ и то, на что он ссылается, в большой таблице, чтобы его можно было найти позже.,

Всякий раз, когда интерпретатор сталкивается с символом, он смотрит в свою таблицу, чтобы узнать, знает ли он, что на самом деле означает, и подставляет реальное значение, в данном случае функцию.

]=> pairwise-disjoint?
;Value 2: #[compound-procedure 2 pairwise-disjoint?]

Мы говорим интерпретатору, чтобы символ оставался на месте, а не заменялся с помощью оператора кавычек, ' или же (quote ...):

]=> 'pairwise-disjoint?
;Value: pairwise-disjoint?

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

Чтобы хранить определения всех ваших конкретных символов, важных для грамматики, вы, вероятно, ищете что-то вроде хеш-таблицы, где каждый символ, о котором вы знаете, является ключом, а его особенности - ассоциированным значением.

И, если вы хотите передать символы, вам действительно нужно понять quote а также quasiquote,

Когда у вас есть где-то определения, которые вы можете найти, единственная работа, которая вам остается, - это написать что-то вроде того, что я сделал выше, и, возможно, немного более приспособленное к вашей конкретной ситуации.

Источник

Типы данных

Если у вас есть терминалы и нетерминалы, почему бы не создать типы данных для каждого из них? В #lang racket способ ввести новый тип данных с struct,

;; A Terminal is just has a name. 
(struct Terminal (name))

;; A Non-terminal has a name and a list of terms
;; The list of terms may contain Terminals, Non-Terminals, or both.
(struct Non-terminal (name terms))

Обработка нетерминалов

Теперь мы можем найти терминалы в нетерминальном списке терминов, используя предикат Terminal? который предоставляется автоматически, когда мы определяем Терминал как struct,

(define (find-terminals non-terminal)
  (filter Terminal? (Non-terminal-terms non-terminal)))

Попарно непересекающиеся клеммы

После того, как мы отфильтровали список терминов, мы можем определить свойства:

;; List(Terminal) -> Boolean
define (pairwise-disjoint? terminals)
  (define (roundtrip terms)
    (set->list (list->set terms)))
  (= (length (roundtrip terminals) 
     (length terminals))))

Список туда и обратно ->set->list не обязательно оптимизирован для скорости, конечно, и профилирование реальных рабочих реализаций может оправдать рефакторинг, но, по крайней мере, это был черный ящик.

Заметки

Определение типов данных с struct предоставляет всевозможные опции для проверки данных, когда создается экземпляр типа. Если вы посмотрите на кодовую базу Racket, вы увидите struct часто используется в более поздних порциях.

Источник

Поскольку grammar есть список в списке, я думаю, вам придется либо проверить через list? перед звонком symbol->string (поскольку, как вы обнаружили, symbol->string не будет работать в списке), иначе вы можете сделать что-то вроде этого:

(map symbol->string (flatten grammar))

> '("A" "<=" "a" "A" "b")

Изменить: Для того, что вы делаете, я думаю, flatten маршрут может быть не таким уж полезным. так что, тест через list? каждый раз при разборе и обработке соответственно.

Источник
Другие вопросы по тегам