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

Jawsography

Джеймс

23 июня 2015 г.

В честь 40-летия и специального переиздания знаменитого фильма, из-за которого мы боялись плавать в океане, мы представляем Jawsography, интерактивное приложение для анализа кинематография фильма 1975 года «Челюсти».

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

Я хотел проверить, были ли настоящие композиционные сдвиги такими же сильными, как мои первоначальные воспоминания о просмотре фильма, поэтому мы создали инструмент, который позволял нам просматривать все кадры фильма. Мы начали с просмотра 1 кадра за 10 секунд фильма, но в итоге получили слишком много переходных кадров. Последнее приложение тянет 1 кадр в минуту фильма.

Композиционные паттерны начали проявляться довольно четко. Мы создали еще один инструмент, который позволял нам быстро просматривать кадры и отмечать, какие из них имеют левый, центральный или правый визуальный вес. В свое время мы начали описывать позиционирование с морской номенклатуры: левый и правый борт.

Порт

Мидель

Правый борт

Мне было так весело пролистывать кадры и определять, какой композиционный вес был самым сильным, что мне удалось превратить большую часть офиса в очередную бесполезную работу. Я был полон решимости воплотить это приложение в жизнь. Вскоре родилась челюсть. Взгляните на свое мобильное устройство (или ноутбук), чтобы увидеть кинематографию «Челюстей» совершенно по-новому. Нырнуть в!

CSE230 Wi13 — монадический анализ

Home оценка Лекции Задания Ссылки Пьяцца

 > импорт Data. Char 
 > импорт Data.Functor 
 > импорт Control.Monad 

Прежде чем мы продолжим, слово от наших спонсоров:

 **Не бойтесь монад**
 

Это просто (чрезвычайно универсальная) абстракция, например map или fold .

Синтаксический анализатор — это часть программного обеспечения, которая принимает необработанные Строка (или последовательность байтов) и возвращает какой-либо структурированный объект, например, список опций, XML-дерево или объект JSON, Абстрактное синтаксическое дерево программы и так далее. Синтаксический анализ является одной из самых основных вычислительных задач. Каждая серьезная программная система имеет парсер, спрятанный где-то внутри, например

• Сценарии оболочки (параметры командной строки)
• Веб-браузеры (да!)
• Игры (дескрипторы уровней)
• Маршрутизаторы (пакеты)
• и т. д.

(Действительно, я бросаю вам вызов, чтобы найти какую-либо серьезную систему, в которой не где-нибудь выполнял бы какой-то синтаксический анализ!)

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

 тип Parser = String -> StructuredObject 

Составление синтаксических анализаторов

Обычный способ создания синтаксического анализатора заключается в указании грамматики и использовании генератора синтаксического анализа (например, yacc, bison, antlr) для создания фактической функции синтаксического анализа. Несмотря на элегантность, одним из основных ограничений подхода, основанного на грамматике, является отсутствие модульности. Например, предположим, что у меня есть два вида примитивных значений Thingy и Whatsit .

 Thingy: правило {действие} 
; 
 Whatsit: правило {действие} 
; 
 

Если вам нужен синтаксический анализатор для последовательностей Thingy и Whatsit , мы должны тщательно продублировать правила как

 Thingies : Thingy Thingies { ... } 
 EmptyThingy { ... } 
 ; 
 Whatsits: Whatsit Whatsits {...} 
 EmptyWhatsit {...} 
; 
 

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

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

 тип Parser = String -> (StructuredObject, String) 

Конечно, было бы глупо иметь разные типы парсеров для разных типов объектов, поэтому мы можем сделать его параметризованным типом

 тип Parser a = String -> (a, String) 

Последнее обобщение: синтаксический анализатор может возвращать несколько результатов, например, мы можем захотеть проанализировать строку

 "2 - 3 - 4" 

либо как

 Минус (Минус 2 3) 4 

или как

 Минус 2 (Минус 3 4) 

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

 > Парсер нового типа a = P (String -> [(a, String)]) 

Вышеупомянутое просто синтаксический анализатор ( кашель действие) фактический синтаксический анализ выполняется

 > doParse (P p) s = p s 

Давайте создадим несколько парсеров!

Вот очень простой анализатор символов, который возвращает первый символ из списка, если он существует

 > oneChar :: Parser Char 
 > oneChar = P (\cs -> case cs of 
 > c:cs' -> [(c, cs')] 
 > _ -> []) 

 > twoChar0 = P (\cs -> case cs of 
 > c1:c2:cs' -> [((c1,c2), cs')] 
 > _ -> []) 

Запускаем анализатор

 ghci> doParse oneChar "Эй!" 
 [('ч',"эй!")] 
 ghci> doParse oneChar "" 
 [] 
 

Парсер Состав

Мы можем написать комбинатор, который принимает два парсера и возвращает новый парсер, который возвращает пару значений

 параP :: Анализатор a -> Анализатор b -> Анализатор (a,b) 
 пара P p1 p2 = P (\cs -> 
 [((x,y), cs'') | (x, cs' ) <- doParse p1 cs, 
 (y, cs'') <- doParse p2 cs '] 
 ) 

Теперь мы можем написать еще один синтаксический анализатор, который получает пару значений Char

 twoChar :: Parser (Char, Char) 
 twoChar = P (\cs -> случай cs из 
 c1:c2:cs' -> [((c1, c2), cs')] 
 _ -> []) 

или более элегантно, как

 > twoChar = параP oneChar oneChar 

, который будет работать так

 ghci> doParse twoChar "эй!" 
 [(('h','e'), "y!")] 
 ghci> doParse twoChar "" 
 [] 
 

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

Вот тип парсера

 Парсер нового типа a = P (String -> [(a, String)]) 

это должно напоминать тебе о чем-то другом, помнишь это?

 тип ST a = состояние -> (a, состояние) 

Действительно, синтаксический анализатор, как и преобразователь состояний, является монадой! если правильно прищуриться. Нам нужно определить функции return и >>= .

Первый очень простой, мы можем позволить типам вести нас

 :тип returnP 
 returnP :: a -> Parser a 

, что означает, что мы должны игнорировать входную строку и просто вернуть элемент ввода

 > returnP x = P (\cs -> [(x, cs)]) 

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

 :type bindP 
 bindP :: Анализатор a -> (a -> Анализатор b) -> Анализатор b 

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

 > p1 `bindP` fp2 = P (\cs -> 
 > [(y, cs'') | (x, cs') <- doParse p1 cs 
 > , (y, cs'') <- doParse ( fp2 x) cs']) 

Вооружившись ими, мы можем официально называть парсеры монадами

 > экземпляр Monad Parser, где 
 > (>>=) = bindP 
 > return = returnP 

Поскольку синтаксические анализаторы являются монадами, мы можем написать кучу высокоуровневых комбинаторов для объединения меньших синтаксических анализаторов в более крупные.

Например, мы можем использовать нашу любимую нотацию до , чтобы переписать пару P как

 > параP px py = do x <- px 
 > y <- py 
 > возврат (x, y) 

шокирующе, точь-в-точь как 9Отсюда функционируют 0163 пары .

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

 > сбойP = P $ const [] 

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

 > satP :: (Char -> Bool) -> Parser Char 
 > satP p = do 
 > c <- oneChar 
 > если pc, то вернуть c, иначе failP 

мы можем написать несколько простых парсеров для определенных символов

 > нижний регистрP = satP isAsciiLower 

 ghci> doParse (satP ('h' ==)) "mugatu" 
 [] 
 ghci> doParse (satP ('h' ==)) "hello" 
 [('h',"ello")] 

Следующий алфавит и числовые символы разбора соответственно

 > alphaChar = satP isAlpha 
 > digitChar = satP isDigit 

, и этот малыш возвращает первую цифру строки как Int

 > digitInt = do 
 > c <- digitChar 
 > return ((read [c]) :: Int) 

который работает так

 ghci> doParse digitInt "92" 
 [(9,"2")] 
 ghci> doParse digitInt "cat" 
 [] 
 

Наконец, этот синтаксический анализатор будет анализировать только определенный Char передано как ввод

 > char c = satP (== c) 

Комбинатор недетерминированного выбора

Теперь давайте напишем комбинатор, который принимает два подпарсера и недетерминированно выбирает между ними.

 > selectP :: Парсер a -> Парсер a -> Парсер a 

Как нам закодировать выбор в наших парсерах? Что ж, мы хотим вернуть успешный синтаксический анализ, если или синтаксический анализатор успешен. Поскольку наши синтаксические анализаторы возвращают несколько значений,

 > p1 `выбрать P` p2 = P (\cs -> doParse p1 cs ++ doParse p2 cs) 

Мы можем использовать приведенный выше комбинатор для создания синтаксического анализатора, который возвращает либо алфавит, либо числовой символ

 > alphaNumChar = alphaChar `выберитеP` digitChar 

Когда мы запускаем это выше, мы получаем довольно интересные результаты

 ghci> doParse alphaNumChar "cat" 
 [('c',"at")] 
 ghci> doParse alphaNumChar "2cat" 
 [('2',"cat")] 
 ghci> doParse alphaNumChar "2at" 
 [('2',"в")] 

Что еще лучше, так это то, что если оба анализатора завершатся успешно, вы получите все результаты. Например, вот синтаксический анализатор, который берет n символов из ввода

 > захватить :: Int -> Строка синтаксического анализатора 
 > захватить n | n <= 0 = вернуть "" 
 > | в противном случае = do c <- oneChar 
 > cs <- grabn (n-1) 
 > return (c:cs) 

ДЕЛАТЬ В КЛАССЕ Как бы вы уничтожили неприятную рекурсию выше?

Теперь мы можем использовать наш комбинатор выбора

 > захват2или4 = захват 2 `выбратьP` захват 4 

и сейчас, мы вернем оба результата если возможно

 ghci> doParse grab2or4 "mickeymouse" 
 [("mi","ckeymouse"),("mick","eymouse")] 

и только один результат, если это возможно

 ghci> doParse grab2or4 "микрофон" 
 [("mi","c")] 
 ghci> doParse grab2or4 "m" 
 [] 
 

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

 > intOp = плюс `chooseP` минус `chooseP` умножить на `chooseP` разделить 
 > где плюс = char '+' >> возврат (+) 
 > минус = char '-' >> возврат (-) 
 > раз = char '*' >> вернуть (*) 
 > разделить = char '/' >> вернуть div 

DO IN CLASS Можете ли вы угадать тип анализатора выше?

Далее мы можем разобрать выражение

 > calc = do x <- digitInt 
 > op <- intOp 
 > y <- digitInt 
 > return $ x `op` y 

, который при запуске будет анализировать и вычислять

 ghci> doParse calc "8/2" 
 [(4,"")] 
 ghci> doParse calc "8+2cat" 
 [(10,"cat")] 
 
 ghci> doParse calc "8/2cat" 
 [(4,"cat")] 
 
 ghci> doParse calc "8-2cat" 
 [(6,"cat")] 
 
 ghci> doParse calc "8*2cat" 
 [(16,"cat" )] 
 

Рекурсивный анализ

Чтобы начать парсить интересные вещи, нам нужно добавить рекурсию в наши комбинаторы. Например, очень хорошо анализировать отдельные символы (как в char выше), но было бы намного больше, если бы мы могли получить определенные токены String .

Попробуем написать!

 > строка :: строка -> строка анализатора 

 string "" = return "" 
 string (c:cs) = do char c 
 string cs 
 return $ c:cs 

ДЕЛАТЬ В КЛАССЕ Фу-у-у! Это явная рекурсия?! Давайте попробуем еще раз (можете найти закономерность)

 > string = undefined -- введите 

Гораздо лучше!

 ghci> doParse (строка "микрофон") "mickeyMouse" 
 [("микрофон","keyMouse")] 
 ghci> doParse (строка "микрофон") "дональд дак" 
 [] 
 

Хорошо, я думаю, тогда это было не совсем рекурсивно!

Давайте попробуем еще раз.

Давайте напишем комбинатор, который принимает синтаксический анализатор p , который возвращает и , и возвращает синтаксический анализатор, который возвращает много значений и . То есть он продолжает захватывать как можно больше значений a и возвращает их как [a] .

 > manyP :: Parser a -> Parser [a] 
 > manyP p = many1 `chooseP` many0 
 > где many0 = return [] 
 > many1 = do x <- p 
 > xs <- manyP p 
 > return (x:xs) 

Но будьте осторожны! Вышеупомянутое может дать много результатов

 ghci> doParse (manyP digitInt) "123a" 
 [([], "123a"), ([1], "23a"), ([1, 2], "3a"), ([1, 2, 3], "а")] 

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

Детерминированный максимальный анализ

Часто нам нужен один результат, а не набор результатов. Например, более интуитивное поведение много будет возвращать максимальную последовательность элементов, а не все префиксы.

Для этого нам понадобится детерминированный комбинатор выбора

 > (<|>) :: Парсер a -> Парсер a -> Парсер a 
 > p1 <|> p2 = P $ \cs -> case doParse (p1 `chooseP` p2) cs of 
 > [] -> [] 
 > х:_ -> [х] 
 > 

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

 > mmanyP :: Parser a -> Parser [a] 
 > mmanyP p = mmany1 <|> mmany0 
 > где mmany0 = return [] 
 > mmany1 = do x <- p 
 > xs <- mmanyP p 
 > return (х:хс) 

ДЕЛАТЬ В КЛАССЕ Подождите! В чем именно разница между вышеперечисленным и оригинальным manyP ? Как вы это объясните:

 ghci> doParse (manyP digitInt) "123a" 
 [([1,2,3],"a"),([1,2],"3a"),([1],"23a"),( [],"123a")] 
 ghci> doParse (mmanyP digitInt) "123a" 
 [([1,2,3],"a")] 
 

Давайте воспользуемся этим, чтобы написать синтаксический анализатор, который будет возвращать целое число (а не только одну цифру).

 oneInt :: Parser Integer 
 oneInt = do xs <- mmanyP digitChar 
 return $ ((read xs) :: Integer) 

Помимо , можете ли вы найти шаблон выше? Взяли парсер mmanyP digitChar и просто преобразовал его вывод, используя функцию чтения . Это повторяющаяся тема, и тип того, что мы сделали, дает нам подсказку

.

 (a -> b) -> парсер a -> парсер b 

Ага! очень похоже на карту . Действительно, существует обобщенная версия map , которую мы видели ранее ( lift1 ), и мы ограничиваем шаблон, объявляя Parser экземпляром Functor класса типов 9.0003

 > instance Functor Parser, где 
 > fmap f p = do x <- p 
 > return (f x) 

после чего мы можем переписать

 > oneInt :: Parser Int 
 > oneInt = прочитать `fmap` mmanyP digitChar 

Давай попробуем

 ghci> doParse oneInt "123a" 
 [(123, "a")] 

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

 > calc0 :: Parser Int 
 > calc0 = binExp <|> oneInt 
 > где binExp = do x <- oneInt 
 > o <- intOp 
 > y <- calc0 
 > return $ x `o` y 

Это работает очень хорошо!

 ghci> doParse calc0 "1+2+33" 
 [(36,"")] 
 ghci> doParse calc0 "11+22-33" 
 [(0,"")] 
 

, но с минусом

все становится немного странно.

 ghci> doParse calc0 "11+22-33+45" 
 [(-45,"")] 

А? Что ж, если вы снова посмотрите на код, вы поймете, что приведенное выше было проанализировано как

.

 11 + ( 22 - (33 + 45)) 

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

Интересно, можем ли мы попытаться это исправить, просто перевернув заказ

 > calc1 :: Parser Int 
 > calc1 = binExp <|> oneInt 
 > где binExp = do x <- calc1 
 > o <- intOp 
 > y <- oneInt 
 > return $ x `o` y 

ДЕЛАТЬ В КЛАССЕ Но здесь есть ошибка… Вы можете это понять? (Подсказка: что вернет следующее?)

 ghci> doParse calc1 "2+2" 

Хуже того, у нас нет приоритета, и поэтому

 ghci> doParse calc0 "10*2+100" 
 [(1020,"")] 

, так как строка анализируется как

 10*(2+100) 

$> calc2 = oneInt >>= захватить $> где захватить x = кг x <|> вернуть x $> кг x = сделать o <- intOp $> y <- oneInt $> захватить $ x o y

Приоритет

Мы можем добавить и ассоциативность, и приоритет обычным способом, расслоив парсер на разные уровни. Здесь давайте разделим наши операции на приоритет сложения и умножения.

 > addOp = плюс `chooseP` минус 
 > где плюс = char '+' >> return (+) 
 > минус = char '-' >> возврат (-) 
 > 
 > mulOp = умножить `chooseP` разделить 
 > где раз = char '*' >> вернуть (*) 
 > разделить = char '/' >> возврат div 

Теперь мы можем разделить наш язык на (взаимно рекурсивные) подъязыки, где каждое выражение верхнего уровня анализируется как сумма произведений

 > sumE = addE <|> prodE 
 > где addE = do x <- prodE 
 > o <- addOp 
 > y <- sumE 
 > return $ x `o` y 
 > 
 > prodE = mulE <|> factorE 
 > где mulE = do x <- factorE 
 > o <- mulOp 
 > y <- prodE 
 > return $ x `o` y 
 > 
 > factorE = parenE <|> oneInt 
 > где parenE = do char '(' 
 > n <- sumE 
 > char ')' 
 > вернуть номер 

Мы можем запустить это

 ghci> doParse sumE "10*2+100" 
 [(120,"")] 
 ghci> doParse sumE "10*(2+100)" 
 [(1020,"")] 
 

Вы понимаете, почему первый синтаксический анализ вернул 120 ? Что произойдет, если мы поменяем местами порядок prodE и sumE в теле addE (или factorE и prodE в теле prodE )? Почему?

Шаблон синтаксического анализа: Цепочка

Нет особого смысла злорадствовать по поводу комбинаторов, если мы собираемся писать код, подобный приведенному выше — корпуса sumE и prodE практически идентичны!

Давайте посмотрим на них поближе. В сущности, sumE имеет форму

 prodE + < prodE + < prodE + ... < prodE >>> 

, то есть мы продолжаем связывать вместе значения prodE и добавлять их столько, сколько сможем. Аналогично prodE имеет форму

 фактор E * < фактор E * < фактор E * ... < фактор E >>> 

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

 ghci> doParse sumE "10-1-1" 
 [(10,"")] 

Ух! Надеюсь, вы понимаете, почему: это потому, что приведенное выше было проанализировано как 10 - (1 - 1) (правоассоциативный), а не (10 - 1) - 1 (левый ассоциативный). У вас может возникнуть соблазн исправить это, просто поменяв местами prodE и sumE

.

 sumE = addE <|> prodE 
 где addE = do x <- sumE 
 o <- addOp 
 y <- prodE 
 return $ x `o` y 

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

 > sumE1 = prodE1 >>= addE1 
 > где addE1 x = захватить x <|> return x 
 > захватить x = сделать о <- addOp 
 > y <- prodE1 
 > addE1 $ x `o` y 
 > 
 > prodE1 = factorE1 >>= mulE1 
 > где mulE1 x = захватить x <|> вернуть x 
 > захватить x = сделать о <- mulOp 
 > y <- factorE1 
 > mulE1 $ x `o` y 
 > 
 > factorE1 = parenE <|> oneInt 
 > где parenE = do char '(' 
 > n <- sumE1 
 > char ')' 
 > return n 

Легко проверить, что приведенное выше действительно ассоциативно слева.

 ghci> doParse sumE1 "10-1-1" 
 [(8,"")] 

, а также очень легко обнаружить и заблокировать шаблон цепных вычислений: единственное отличие состоит в том, что base парсер ( prodE1 против factorE1 ) и бинарная операция ( addOp против mulOp ). Мы просто вносим эти параметры в наш комбинатор

.

 > p `chainl` pop = p >>= rest 
 > где rest x = схватить x <|> return x 
 > схватить x = do o <- pop 
 > y <- p 
 > rest $ x `o` г 

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

 > parenP l p r = do char l 
 > x <- p 
 > char r 
 > return x 

после чего мы можем переписать грамматику в три строки

 > sumE2 = prodE2 `chainl` addOp 
 > prodE2 = factorE2 `chainl` mulOp 
 > factorE2 = parenP '('sumE2 ')' <|> oneInt 

 ghci> doParse sumE2 "10-1-1" 
 [(8,"")] 
 ghci> doParse sumE2 "10*2+1" 
 [(21,"")] 
 
 ghci> doParse sumE2 "10+2*1" 
 [(12,"")] 
 

На этом мы завершаем наше (в классе) изучение монадического синтаксического анализа. Это всего лишь верхушка айсберга. Хотя синтаксический анализ — очень старая проблема, и ее изучали на заре вычислительной техники, мы увидели, как монады привносят свежий взгляд, который недавно был перенесен из Haskell во многие другие языки.