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))
Теперь можно запустить нашу программу:
 |
Внимание! В оригинале автор предлагает использовать ключ --make или -package parsec, но реальной необходимости в них нет, возможно, информация устарела. |
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 может быть:
Atom, который хранит String имя атомаList, который хранит список других LispVals (списки в Haskell обозначаются квадратными скобками); также называемый правильным спискомDottedList, представляющий Scheme форму(a b . c); также называемую неправильным списком. Он хранит список всех элементов кроме последнего, а затем хранит последний элемент в другом полеNumber, содержащий Haskell IntegerString, содержащий Haskell StringBool, содержащий логическое значение 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
| Упражнения |
|---|
|
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.
| Упражнения |
|---|
|