Преобразование определения одной из функций в определение эквивалентной функции

@Hellner · Регистрация: 17.03.2015

Студворк — интернет-сервис помощи студентам

Есть грамматика некоторого языка

функция ::= имя_функции "(" список_параметров ")" "=>" "{" выражение "}"
список_параметров ::= параметр | параметр "," список_параметров
выражение ::= терм | условный_оператор
условный_оператор ::= условие "?" выражение ":" выражение
условие ::= терм ( "<" | "=" | ">" ) терм
терм ::= параметр | целое_число

Имя функции и название параметра состоят из латинских символов.
Обратите внимание, что количество параметров функции и глубина вложения условных операторов не ограничены.

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

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

Например, для исходной функции f( x ) => {10} определение эквивалентной функции будем таким: (defun f (x) 10) .

Определение исходной функции будет передано в виде списка, для вышеприведённого примера такого: ( f \( x \) => { 10 } ) . Каждая лексема будет представлять отдельный элемент списка, так что лексическим анализом заниматься не нужно.

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

Примеры входных и выходных данных

>>> (tt '( func \( x \, y \) => { x > y ? -1 \: 1 } ) ) ; "func(x, y) => { x>y ? -1 : 1 }"
( defun func ( x y ) ( if ( > x y ) -1 1 ) )

>>> ( tt '( max \( x \, y \, z \) => { x > y ? x > z ? x \: z \: y > z ? y \: z } ) ); "max( x, y, z ) => { x > y ? x > z ? x : z : y > z ? y : z }"
( defun max (x y z) ( if (> x y) (if ( > x z ) x z) ( if (> y z) y z) ))

@Catstail · 07.05.2015, 11:10

Как я понял, "\(" - это фигурная скобка "{"; "\)" - соответственно "}", "\," - это запятая. Так?

@castorsky · 07.05.2015, 13:36

Hellner, что Вам непонятно? Никаких попыток решения не видно.

@nullxdth · 07.05.2015, 16:04

Hellner, о, курсач что-ли?
Я бы взял yacc и красиво написал. Хотя можно и руками нисходящий парсер написать, благо грамматика тривиальная.

Добавлено через 3 минуты
Вот компилятор этого Blub-а. cl-ppcre и cl-yacc. Правда лексер велосипедный, но большего для этой задачи и не требуется.

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
(defmacro defhelper (function-name lambda-list &body body)
  `(eval-when (:load-toplevel :compile-toplevel :execute)
     (defun ,function-name ,lambda-list
       ,@body)))
 
(defun make-dummy-lexer (lexeme-table string)
  (check-type string string)
  (let ((i 0)
        (length (length string)))
    (lambda ()
      (when (< i length)
        (let ((result
               (dolist (lexeme (cons (list "\\s+" 'ignore) lexeme-table))
                 (let ((pattern  (car lexeme))
                       (terminal (cdr lexeme)))
                   (multiple-value-bind (start end)
                       (cl-ppcre:scan (concatenate 'string "^" pattern) string :start i)
                     (when start
                       (setf i end)
                       (destructuring-bind (terminal &optional (tfn #'identity)) terminal
                         (unless (eq 'ignore terminal)
                           (return (list terminal
                                         (funcall tfn (subseq string start end))))))))))))
          (if result
              (values-list result)
              (error "Lexeme not found")))))))
 
(defparameter *blub-lexeme-table*
  `(("\\("  |(|)
    ("\\)"  |)|)
    (","    |,|)
    ("=>"   =>)
    ("{"    {)
    ("}"    })
    (":"    |:|)
    ("="    =)
    ("<"    <)
    (">"    >)
    ("\\?"  ?)
    ("\\d+" uint  ,#'parse-integer)
    ("\\w+" ident ,(lambda (ident)
                      (intern (string-upcase ident))))))
 
(defhelper translate-function (ident |(| args |)| => { expression })
  (declare (ignore |(| |)| => { }))
  `(defun ,ident ,args
     ,expression))
 
(defhelper translate-arguments (ident |,| args)
  (declare (ignore |,|))
  (cons ident args))
 
(defhelper translate-condition (condition ? a |:| b)
  (declare (ignore ? |:|))
  `(if ,condition
       ,a
       ,b))
 
(defhelper translate= (a = b)
  (declare (ignore =))
  `(equal ,a ,b))
 
(defhelper translate< (a < b)
  (declare (ignore <))
  `(< ,a ,b))
 
(defhelper translate> (a < b)
  (declare (ignore <))
  `(> ,a ,b))
 
(define-parser *blub-parser*
  (:start-symbol function)
  (:terminals (ident uint |(| |)| |,| => { } |:| ? < > =))
  (function
   (ident |(| arguments |)| => { expression } #'translate-function))
  (arguments
   (ident |,| arguments #'translate-arguments)
   (ident #'list))
  (expression
   term
   if-else)
  (term
   ident
   uint)
  (if-else
   (condition ? expression |:| expression #'translate-condition))
  (condition
   (term = term #'translate=)
   (term < term #'translate<)
   (term > term #'translate>)))
 
(defmacro compile-blub-function (blub-string)
  (check-type blub-string string)
  (parse-with-lexer (make-dummy-lexer *blub-lexeme-table* blub-string)
                    *blub-parser*))
 
 
(compile-blub-function
 "blubmax (x, y, z) => { x > y ? x > z ? x : z : y > z ? y : z }")
 
(blubmax 1 666 200)
;; => 666

Добавлено через 4 минуты
Такой вот eDSL получился.

Lisp
1
2
3
4
5
6
7
8
(let ((y 100))
  (compile-blub-function
   "fn (x) => { x > y ? x : y }"))
 
(fn 10)
;; => 100
(fn 101)
;; => 101

@smoke853 · 07.05.2015, 21:30

Решил тоже попробовать набросать решение для себя, но т.к. в парсерах я полный 0 и даже не знаю с чего начать, то взял библиотеку instaparse для этого дела. Удивительно, но каким-то чудом это даже вроде работает

Кликните здесь для просмотра всего текста

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
(ns aeon.core
  (:require [instaparse.core :as insta]))
 
(def parser
  (insta/parser
   "function = name <'('> params <')'> <'=>'> <'{'> expr <'}'>
    name = #'\\p{Alpha}+'
    params = param | param <','> params
    param = #'\\p{Alpha}+'
    expr = term | cond
    cond = clause <'?'> expr <':'> expr
    clause = term ('<' | '=' | '>') term
    <term> = param | int
    int = #'[-]?\\d+'"
   :auto-whitespace :standard))
 
(defn transform [s]
  (let [clause (fn [x op y]
                 (case op
                   "<" `(< ~x ~y)
                   ">" `(> ~x ~y)
                   "=" `(= ~x ~y)))
        transform-map {:int read-string
                       :clause clause
                       :cond (fn [clause x y]
                               `(if ~clause ~x ~y))
                       :expr identity
                       :param read-string
                       :params vector
                       :name read-string
                       :function (fn [name args body]
                                   `(fn ~name ~((comp vec flatten) args) ~body))}]
    (->> (parser s) (insta/transform transform-map) eval)))
 
((transform "func(x, y) => {x < y ? x : y}") 2 10)
;; => 2
((transform "func(x, y) => {x > y ? 1 : -1}") 2 10)
;; => -1
((transform "func(x) => {10}") 5)
;; => 10
((transform "func(x,y,z) => {x > y ? x > z ? x : z : y > z ? y : z}") 1 7 4)
;; => 7

@nullxdth · 07.05.2015, 23:59

Сообщение от smoke853

в парсерах я полный 0

Уже не 0

Сообщение от smoke853

даже не знаю с чего начать

Уже начал

Можешь продолжить.

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами 8Observer8 20.02.2026 Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .	Конвертировать закладки radiotray-ng в m3u-плейлист damix 19.02.2026 Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .	Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI Eddy_Em 18.02.2026 Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .
И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»	SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 12.02.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .

Преобразование определения одной из функций в определение эквивалентной функции

Решение

Решение

@Hellner 0 / 0 / 0 Регистрация: 17.03.2015 Сообщений: 14

	Преобразование определения одной из функций в определение эквивалентной функции 07.05.2015, 08:59. Показов 959. Ответов 5 Метки нет (Все метки) Есть грамматика некоторого языка функция ::= имя_функции "(" список_параметров ")" "=>" "{" выражение "}" список_параметров ::= параметр \| параметр "," список_параметров выражение ::= терм \| условный_оператор условный_оператор ::= условие "?" выражение ":" выражение условие ::= терм ( "<" \| "=" \| ">" ) терм терм ::= параметр \| целое_число Имя функции и название параметра состоят из латинских символов. Обратите внимание, что количество параметров функции и глубина вложения условных операторов не ограничены. На языке, который описывается данной грамматикой, можно определять различные функции. Ваша задача состоит в том, что бы написать на языке Лисп программу, преобразующую определение одной из таких функций (заранее неизвестно, какой) в определение эквивалентной функции на языке Лисп. Результирующая функция для каждого набора аргументов должна выдавать тот же результат, что и исходная функция - в этом смысл эквивалентности. Например, для исходной функции f( x ) => {10} определение эквивалентной функции будем таким: (defun f (x) 10) . Определение исходной функции будет передано в виде списка, для вышеприведённого примера такого: ( f \( x \) => { 10 } ) . Каждая лексема будет представлять отдельный элемент списка, так что лексическим анализом заниматься не нужно. Для простоты давайте считать, что определение исходной функции не содержит ошибок и может быть успешно преобразовано в описание Лисп-функции. Примеры входных и выходных данных >>> (tt '( func \( x \, y \) => { x > y ? -1 \: 1 } ) ) ; "func(x, y) => { x>y ? -1 : 1 }" ( defun func ( x y ) ( if ( > x y ) -1 1 ) ) >>> ( tt '( max \( x \, y \, z \) => { x > y ? x > z ? x \: z \: y > z ? y \: z } ) ); "max( x, y, z ) => { x > y ? x > z ? x : z : y > z ? y : z }" ( defun max (x y z) ( if (> x y) (if ( > x z ) x z) ( if (> y z) y z) )) 0

@Catstail Супер-модератор 38174 / 21109 / 4307 Регистрация: 12.02.2012 Сообщений: 34,711 Записей в блоге: 14
	07.05.2015, 11:10
	Как я понял, "\(" - это фигурная скобка "{"; "\)" - соответственно "}", "\," - это запятая. Так? 0

@castorsky 1978 / 1082 / 87 Регистрация: 29.11.2013 Сообщений: 3,353
	07.05.2015, 13:36
	Hellner, что Вам непонятно? Никаких попыток решения не видно. 2