Академия: Введение в функциональное программирование. 8 неделя, ч. 2: создаем домен-специфические языки с помощью функциональных парсеров

4 месяца назад
65 в академия

Привет. Я участвую в проекте Академия от @ontofractal и публикую конспекты курса  Введение в функциональное программирование от Delft University of Technology. В этой части конспекта я пролжу рассказывать о функциональных парсерах. В прошлый раз мы научились комбинировать отдельные парсеры в общую структуру с помощью монад. Сегодня я продолжу эту тему и к концу занятия расскажу, как построить парсер, способный вычислять простые выражения

Еще немного парсеров

Для начала напишем еще несколько парсеров, которые могут пригодиться нам в будущем

Например, мы можем написать функцию, которая принимает предикат (условное выражение) и символ. Если символ подходит под предикат, мы возвращаем парсер return (напомню, что он в свою очередь, вссегда возвращает без изменений поступающее к нему значение), а если не подходит - парсер failure

sat p = do x <- item
   if p x then
      return x
   else failure

Функции, которые парсят цифры и специальные символы:

digit :: Parser Char
digit = sat isDigit
char:: Char -> Parser Char
char x = sat (x==)

Кроме того, было бы полезно иметь функцию, которая применяет парсер к входному значению 0 или больше раз:

many :: Parser a -> Parser [a]
many p = many1 p +++ return []

Если функция принимает подходящее значение, она возвращает функцию many1, если неподходящее - пустой список

Функцию many1 можно определить следующим способом:

many1 p :: Parser a -> Parser [a]
many1 p = do v <- p
             vs <- many p
             return (v:vs)

Как видите, здесь использован рекурсивный паттерн: мы разбиваем входное значение на начало и остаток (v:vs), применяем к начальному элементу парсер (v <- p), а затем применяем к остатку функцию many, которая в свою очередь проверяет входное значение, и если оно подходит, применяет к нему функцию many1

Подобный подход можно применить для функции, которая парсит определенную строку:

string :: String -> Parser String
string [] = return []
string (x:xs) = do char x
                   string xs
                   return (x:xs)

Парсим выражения

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

Однако, прежде чем приступить к его написанию, нужно немного подумать о синтаксисе выражений. Предположим, что парсер может распознавать два вида арифметических выражений: сложение и умножение, а также знает о правилах ассоциативности и о том, что умножение имеет приоритет перед сложением. Тогда синтаксис выражений можно описать так:

expr -> term '+' expr | term

  Здесь мы описываем строение всего выражения: оно состоит из первого слагаемого (term), и второго слагаемого, которое может быть либо слагаемым (term), либо другим выражением

Слагаемое в свою очередь описывается так:

term -> factor '*' term | factor

То есть, оно состоит из первого множителя (factor) и второго множителя, который может быть либо выражением (term), либо множителем (factor)

Множитель мы определим так:

factor -> digit | expr

Ну а digit мы определим как цифры от 0 до 9

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

expr :: Parser Int
expr = do t <- term
          do char '+'
             e <- expr
             return (t + e)
          +++ return t

Теперь определим функцию для слагаемого:

term :: Parser Int
term = do f <- factor
          do char '*'
             t <- term
             return (f * t)
        +++ return f

И для множителя:

factor :: Parser Int
factor = do d <- digit
            return (digitToInt d)
         +++ do char '('
                e <- expr
                char ')'
                return e

И теперь остается лишь определить функцию eval, которая и будет принимать выражения:

eval :: String -> Int
eval xs = fst (head (parse expr xs ))

Домен-специфические языки

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

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

Еще один рекордсмен в этой области - язык Lisp. Его синтаксис, построенный вокруг последовательной обработки элементов списков, позволяет легко создавать интерпретаторы для новых языков. Поэтому на сегодняшний день существует огромное число диалектов Лиспа, часть из которых используется в качестве языков широкого профиля, часть - в качестве домен-специфических языков (например, AutoLisp, используемый в AutoCAD)

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

Что показалось самым интересным на этой неделе?

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

“Конспект подготовлен для Академии Голоса @academy.

Авторы получают вознаграждение, когда пользователи голосуют за их посты.
Голосующие читатели также получают вознаграждение за свой голос.
Порядок сортировки:  Популярное
70
  ·  4 месяца назад

Ваш пост поддержали следующие Инвесторы Сообщества "Добрый кит":
chiliec, lenarius, orezaku, stranniksenya, boltyn, vika-teplo, borisss, kondratij, del137, dmitrijv, lokkie
Поэтому я тоже проголосовал за него!

Узнать подробности о сообществе можно тут:
Разрешите представиться - Кит Добрый
Правила
Инструкция по внесению Инвестиционного взноса
Вы тоже можете стать Инвестором и поддержать проект!!!


Если Вы хотите отказаться от поддержки Доброго Кита, то ответьте на этот комментарий командой "!нехочу"


dobryj.kit теперь стал Делегатом! Ваш голос важен для всего сообщества!!!
Поддержите нас на странице https://golos.io/~witnesses, вот так: