Write Yourself a Scheme in 48 Hours/Парсинг

Пишем простой Синтаксический Анализатор

Давайте попробуем написать очень простой синтаксический анализатор. Мы будем использовать библиотеку Parsec (Установите parsec, если вы еще не сделали этого, самостоятельно или в составе Haskell Platform.).

Начнем мы с добавления следующей строки в секцию импорта:

 import Text.ParserCombinators.Parsec hiding (spaces)

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

Теперь определим синтаксический анализатор, который будет распознавать символы, разрешенные для определения идентификаторов в Scheme:

 symbol :: Parser Char
 symbol = oneOf "!#$%&|*+-/:<=>?@^_~"

Это еще один пример монады: в данном случае «дополнительная информация», которая скрыта, это информация о позиции во входном потоке данных, о предыдущей записи, о первом и последующих наборах и т. д. Parsec позаботится обо всем за нас. Нам нужно лишь воспользоваться функцией oneOf из библиотеки Parsec, и она разберет символы в переданной ей строке. Parsec предоставляет множество готовых синтаксических анализаторов: например, letter и digit. Вы так же можете создавать более сложные синтаксические анализаторы из более простых.

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

 readExpr :: String -> String
 readExpr input = case parse symbol "lisp" input of
     Left err -> "No match: " ++ show err
     Right val -> "Found value"

Из сигнатуры функции вы можете видеть, что readExpr это функция (->) из String в String. Мы назвали параметр input и передали его дальше, вместе с синтаксическим анализатором symbol, определенным ранее, в функцию parse из библиотеки Parsec. Второй параметр функции parse это имя для передаваемых данных. Оно используется для вывода сообщений об ошибках.

parse может вернуть либо разобранное значение, либо ошибку, так что нам нужно иметь возможность отлавливать ошибки. Следуя принятым в Haskell соглашениям, Parsec возвращает тип Either, в котором конструктор Left используется для указания на ошибку, а конструктор Right для возврата нормального значения.

Используем конструкцию case...of, чтобы проверить, какой результат вернула функция parse. Если мы получили значение Left (ошибка), то присваиваем ошибке имя err и возвращаем «No match» с текстовым представлением ошибки. Если же мы получили значение Right, то присваиваем значению имя val и, игнорируя его, возвращаем строку «Found value».

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

Напоследок, нам нужно изменить нашу функцию так, чтобы вызывать readExpr и выводить на печать результат (необходимо добавить import System в начале файла):

 main :: IO ()
 main = do args <- getArgs
           putStrLn (readExpr (args !! 0))

Теперь можно запустить нашу программу:

debian:/home/jdtang/haskell_tutorial/code# ghc -o simple_parser listing3.1.hs
debian:/home/jdtang/haskell_tutorial/code# ./simple_parser $
Found value
debian:/home/jdtang/haskell_tutorial/code# ./simple_parser a
No match: "lisp" (line 1, column 1):
unexpected "a"

Пробел

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

debian:/home/jdtang/haskell_tutorial/code# ./simple_parser "   %"
No match: "lisp" (line 1, column 1):
unexpected " "

Давайте исправим это, просто игнорируя пробелы.

Сначала определим синтаксический анализатор, который распознает любое число пробелов. Кстати, именно поэтому мы указали hiding (spaces), когда импортировали библиотеку Parsec: в ней уже есть функция «spaces», однако она делает не совсем то, что нам нужно. (Вообще-то, есть еще синтаксический анализатор lexeme, который делает в точности то, что нам нужно, однако мы проигнорируем этот факт в учебных целях.)

 spaces :: Parser ()
 spaces = skipMany1 space

Так же как функции могут быть переданы в качестве параметров другим функциям, так же мы можем поступить и с действиями. Здесь мы передаем Parser действие space в качестве параметра в Parser действие skipMany1, чтобы получить Parser, который будет распознавать один или несколько пробелов.

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

 readExpr input = case parse (spaces >> symbol) "lisp" input of
     Left err -> "No match: " ++ show err
     Right val -> "Found value"

Мы уже встречались с оператором >> («оператор связывания») во втором уроке, там упоминалось, что он используется для "закулисного" связывания строк в блоке do. Здесь мы используем его явно, чтобы скомбинировать наши парсеры пробелов и символов. Однако, это связывание имеет принципиально различную семантику в монадах IO и Parser. В монаде Parser связывание значит «Попытаться сопоставить данные с первым парсером, потом, оставшиеся данные попытаться сопоставить со вторым и выдать ошибку, если сопоставление с обоими провалилось.» В общем, связывание будет вызывать разный эффект в разных монадах; оно задумывалось как обобщенный способ структурирования вычислений, поэтому оно должен быть обобщено настолько, чтобы вместить все возможные типы вычислений. За подробностями о том, что действительно делает этот оператор, обращайтесь к документации по монадам.

Скомпилируем и запустим код. Обратите внимание, что с тех пор как мы определили spaces в терминах skipMany1, наш парсер не будет больше распознавать простой старый единичный символ. Вместо этого мы должны предварить символ несколькими пробелами. Мы скоро увидим, как это полезно:

debian:/home/jdtang/haskell_tutorial/code# ghc -package parsec -o simple_parser [../code/listing3.2.hs listing3.2.hs]
debian:/home/jdtang/haskell_tutorial/code# ./simple_parser "   %"
Found value
debian:/home/jdtang/haskell_tutorial/code# ./simple_parser %
No match: "lisp" (line 1, column 1):
unexpected "%"
expecting space
debian:/home/jdtang/haskell_tutorial/code# ./simple_parser "   abc"
No match: "lisp" (line 1, column 4):
unexpected "a"
expecting space

Возвращаем значения

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

 data LispVal = Atom String
              | List [LispVal]
              | DottedList [LispVal] LispVal
              | Number Integer
              | String String
              | Bool Bool

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

1. Atom, который хранит String имя атома
2. List, который хранит список других LispVals (списки в Haskell обозначаются квадратными скобками); также называемый правильным списком
3. DottedList, представляющий Scheme форму (a b . c); также называемую неправильным списком. Он хранит список всех элементов кроме последнего, а затем хранит последний элемент в другом поле
4. Number, содержащий Haskell Integer
5. String, содержащий Haskell String
6. Bool, содержащий логическое значение Haskell

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

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

 parseString :: Parser LispVal
 parseString = do char '"'
                  x <- many (noneOf "\"")
                  char '"'
                  return $ String x

Мы возвращаемся к использованию do-нотации вместо оператора >>. Это потому, что мы будем получать значение нашего анализа (возвращённое через many (noneOf «\»")) и манипулировать им, чередуя с некоторыми другими операциями синтаксического анализа в то же время. В общем случае используйте >> если действия не возвращают значение, >>= если вы сразу же передаёте это значение в следующее действие и do-нотацию в ином случае.

Как только мы закончим синтаксический анализ и получим Haskell String, возвращённую из many, мы применяем конструктор String (из нашего типа данных LispVal), чтобы превратить его в LispVal. Каждый конструктор в алгебраическом типе данных действует также как функция, которая превращает свои аргументы в значения своего типа. Он также служит шаблоном, который можно использовать в левой части выражения сопоставления шаблонов; мы видели пример этого в Урок 3.1, когда мы сопоставили результат нашего синтаксического анализатора с двумя конструкторами в Either тип данных.

Затем мы применяем встроенную функцию return чтобы поднять наш LispVal в Parser монаду. Помните, что каждая строка do-блока должна иметь один и тот же тип, но результат нашего конструктора String - это просто старый LispVal. Return позволяет нам обернуть это в Parser действие, которое не потребляет ввода, но возвращает его как внутреннее значение. Таким образом, всё действие parseString будет иметь тип Parser LispVal.

Оператор $ это инфиксное применение функции: это то же самое, как если бы мы написали return (String x), но $ является правоассоциативным, позволяя нам исключить некоторые скобки. Поскольку $ является оператором, мы можем делать с ним все, что обычно делаем с функцией: передавать его, частично применять и т.д. В этом отношении он функционирует как Lisp функция apply.

Теперь перейдем к Scheme переменным. atom - это буква или символ, за которым следует любое количество букв, цифр или символов:

 parseAtom :: Parser LispVal
 parseAtom = do first <- letter <|> symbol
                rest <- many (letter <|> digit <|> symbol)
                let atom = first:rest
                return $ case atom of 
                           "#t" -> Bool True
                           "#f" -> Bool False
                           _    -> Atom atom

Здесь мы вводим еще один Parsec комбинатор, оператор выбора <|>. Он пробует первый парсер, а затем, если он терпит неудачу, пробует второй. Если любой из них завершается успехом, оператор возвращает значение, возвращённое этим анализатором. Первый синтаксический анализатор должен потерпеть неудачу, прежде чем он будет потреблять какие-либо входные данные: мы увидим позже, как реализовать обратное отслеживание (backtracking).

Как только мы прочитаем первый символ и остальную часть атома, нам нужно собрать их вместе. Оператор «let» определяет новую переменную atom. Для этого мы используем списочный cons оператор :. Вместо : мы могли бы использовать оператор конкатенации ++, таким образом [first]++rest; напомним, что first - это всего лишь один символ, поэтому мы преобразуем его в одноэлементный список, заключая в скобки.

Затем мы используем выражение case, чтобы определить, какой LispVal создавать и возвращать, сопоставляя строковые литералы для true и false. Вариант с подчеркиванием _ является трюком с читаемостью: блоки case продолжаются до случая _ (или до провала другого сопоставления, что также вызывает провал всего выражения case), думайте о _ как о подстановочном знаке. Поэтому, если исполнение доходит до случая _, он всегда сопоставляется и возвращает значение atom.

Наконец, мы создаем еще один синтаксический анализатор, для чисел. Тут демонстрируется еще один способ работы с монадическими значениями:

 parseNumber :: Parser LispVal
 parseNumber = liftM (Number . read) $ many1 digit

Проще всего прочитать это в обратном порядке, так как обе функции применение ($) и композиция (.) ассоциируются справа. Parsec комбинатор many1 соответствует одному или нескольким его аргументам, поэтому здесь мы сопоставляем одну или несколько цифр. Мы хотели бы построить число LispVal из результирующей строки, но у нас есть несколько несоответствий типов. Во-первых, мы используем встроенную функцию read для преобразования этой строки в число. Затем мы передаем результат Number, чтобы получить LispVal. Оператор композиции функции . создает функцию, которая применяет свой правый аргумент, а затем передает результат в левый аргумент, поэтому мы используем его для объединения применения двух функций.

К сожалению, результат many1 digit на самом деле является Parser String, поэтому наш объединенный Number . read все еще не может работать на нем. Нам нужен способ сказать чтобы он просто действовал на значение внутри монады, возвращая нам Parser LispVal. Стандартная функция liftM делает именно это, поэтому мы применяем liftM к нашему Number . read, а затем применяем результат этого к нашему парсеру.

Мы также должны импортировать модуль Monad в верхней части нашей программы, чтобы получить доступ к liftM:

 import Control.Monad

Этот стиль программирования — в значительной степени основанный на композиции функций, применении функций и передаче функций функциям — очень распространен в коде Haskell. Он часто позволяет выразить очень сложные алгоритмы в одной строке, разбивая промежуточные шаги на другие функции, которые могут быть объединены различными способами. К сожалению, это означает, что вам часто придётся читать код Haskell справа налево и внимательно отслеживать типы. Мы увидим еще много примеров на протяжении всей остальной части урока, так что, надеюсь, вы освоитесь с этим.

Давайте создадим синтаксический анализатор, который принимает любые строку, число или атом:

 parseExpr :: Parser LispVal
 parseExpr = parseAtom
         <|> parseString
         <|> parseNumber

И отредактируем readExpr так, чтобы он вызывает наш новый парсер:

 readExpr :: String -> String
 readExpr input = case parse parseExpr "lisp" input of
     Left err -> "No match: " ++ show err
     Right _ -> "Found value"

Скомпилируйте и запустите этот код, и вы заметите, что он принимает любое число, строку или символ, но не другие строки:

debian:/home/jdtang/haskell_tutorial/code# ghc -package parsec -o simple_parser [.../code/listing3.3.hs listing3.3.hs]
debian:/home/jdtang/haskell_tutorial/code# ./simple_parser "\"this is a string\""
Found value
debian:/home/jdtang/haskell_tutorial/code# ./simple_parser 25
Found value
debian:/home/jdtang/haskell_tutorial/code# ./simple_parser symbol
Found value
debian:/home/jdtang/haskell_tutorial/code# ./simple_parser (symbol)
bash: syntax error near unexpected token `symbol'
debian:/home/jdtang/haskell_tutorial/code# ./simple_parser "(symbol)"
No match: "lisp" (line 1, column 1):
unexpected "("
expecting letter, "\"" or digit

Упражнения

Перепишите parseNumber используя do-нотацию явную последовательность с помощью оператора >>= Наши строки не совсем R5RS совместимы, потому что они не поддерживают экранирование внутренних кавычек в строке. Измените parseString так, чтобы \" давал именно символ кавычки вместо завершения строки. Вы, возможно, захотите заменить noneOf "\"" новым действием синтаксического анализатора, которое принимает любой символ, кроме кавычек либо обратную косую черту, за которой следует кавычка. Измените предыдущее упражнение для поддержки \n, \r, \t, \\, и любых других желаемых escape-символов Измените parseNumber для поддержки стандарта Scheme для разных оснований. Вы, возможно, найдёте readOct и readHex функции полезными. Добавьте конструктор Character в LispVal, и создайте синтаксический анализатор для символьных констант как описано в R5RS. Добавьте конструктор Float в LispVal, и поддержку R5RS синтаксиса для типов decimal. Haskell функция readFloat может быть полезной. Добавьте типы данных и синтаксические анализаторы для поддержки полной числовой башни числовых типов Scheme. Haskell имеет встроенные типы для представления многих из них; проверьте Prelude. Для других, вы можете определить составные типы, которые представляют, например, Rational как числитель и знаменатель, или Complex как действительная и мнимая части (каждая сама по себе число Real).

Recursive Parsers: Adding lists, dotted lists, and quoted datums

Next, we add a few more parser actions to our interpreter. Start with the parenthesized lists that make Lisp famous:

 parseList :: Parser LispVal
 parseList = liftM List $ sepBy parseExpr spaces

This works analogously to parseNumber, first parsing a series of expressions separated by whitespace (sepBy parseExpr spaces) and then apply the List constructor to it within the Parser monad. Note too that we can pass parseExpr to sepBy, even though it’s an action we wrote ourselves.

The dotted-list parser is somewhat more complex, but still uses only concepts that we’re already familiar with:

 parseDottedList :: Parser LispVal
 parseDottedList = do
     head <- endBy parseExpr spaces
     tail <- char '.' >> spaces >> parseExpr
     return $ DottedList head tail

Note how we can sequence together a series of Parser actions with >> and then use the whole sequence on the right hand side of a do-statement. The expression char '.' >> spaces returns a Parser (), then combining that with parseExpr gives a Parser LispVal, exactly the type we need for the do-block.

Next, let’s add support for the single-quote syntactic sugar of Scheme:

 parseQuoted :: Parser LispVal
 parseQuoted = do
    char '\''
    x <- parseExpr
    return $ List [Atom "quote", x]

Most of this is fairly familiar stuff: it reads a single quote character, reads an expression and binds it to x, and then returns (quote x), to use Scheme notation. The Atom constructor works like an ordinary function: you pass it the String you’re encapsulating, and it gives you back a LispVal. You can do anything with this LispVal that you normally could, like put it in a list.

Finally, edit our definition of parseExpr to include our new parsers:

 parseExpr :: Parser LispVal
 parseExpr = parseAtom
         <|> parseString
         <|> parseNumber
         <|> parseQuoted
         <|> do char '('
                x <- try parseList <|> parseDottedList
                char ')'
                return x

This illustrates one last feature of Parsec: backtracking. parseList and parseDottedList recognize identical strings up to the dot; this breaks the requirement that a choice alternative may not consume any input before failing. The try combinator attempts to run the specified parser, but if it fails, it backs up to the previous state. This lets you use it in a choice alternative without interfering with the other alternative.

Compile and run this code:

debian:/home/jdtang/haskell_tutorial/code# ghc -package parsec -o simple_parser [../code/listing3.4.hs listing3.4.hs]
debian:/home/jdtang/haskell_tutorial/code# ./simple_parser "(a test)"
Found value
debian:/home/jdtang/haskell_tutorial/code# ./simple_parser "(a (nested) test)"
Found value
debian:/home/jdtang/haskell_tutorial/code# ./simple_parser "(a (dotted . list) test)"
Found value
debian:/home/jdtang/haskell_tutorial/code# ./simple_parser "(a '(quoted (dotted . list)) test)"
Found value
debian:/home/jdtang/haskell_tutorial/code# ./simple_parser "(a '(imbalanced parens)"
No match: "lisp" (line 1, column 24):
unexpected end of input
expecting space or ")"

Note that by referring to parseExpr within our parsers, we can nest them arbitrarily deep. Thus, we get a full Lisp reader with only a few definitions. That’s the power of recursion.

Упражнения

Add support for the backquote syntactic sugar: the Scheme standard details what it should expand into (quasiquote/unquote). Add support for vectors. The Haskell representation is up to you: GHC does have an Array data type, but it can be difficult to use. Strictly speaking, a vector should have constant-time indexing and updating, but destructive update in a purely functional language is difficult. You may have a better idea how to do this after the section on set!, later in this tutorial. Instead of using the try combinator, left-factor the grammar so that the common subsequence is its own parser. You should end up with a parser that matches a string of expressions, and one that matches either nothing or a dot and a single expressions. Combining the return values of these into either a List or a DottedList is left as a (somewhat tricky) exercise for the reader: you may want to break it out into another helper function.