Глава 7. Синтаксический анализатор строковых данных

Аннотация

Публикация
Учебник библиотеки FParsec
Дата
Ссылки

FParsec содержит различные встроенные синтаксические анализаторы для символов, строк, чисел и пробелов. В этой главе мы представим несколько синтаксических анализаторов символов и строк. Обзор всех доступных синтаксических анализаторов см. в руководстве пользователяen.

Вы уже видели несколько применений синтаксического анализатора pstring (сокращенно str ), который просто пропускает строку определенного формата на входе. Когда синтаксический анализатор pstring успешно выполнился, он также возвращает пропущенную строку в качестве результата анализатора. Следующий пример демонстрирует это:

> test (many (str "a" <|> str "b")) "abba";;
Success: ["a"; "b"; "b"; "a"]

В этом примере мы так же использовали синтаксический анализатор <|> для объединения двух альтернативных анализаторов. Мы обсудим этот комбинатор более подробно ниже.

Мы говорим, что pstring и pstring "a" это «синтаксические анализаторы». Но строго говоря, pstring - это функция, принимающая строку и возвращающая Parser, но удобнее про нее говорить как (параметрический) синтаксический анализатор.

Когда вам не нужен результат синтаксического анализатора pstring, вы можете в качестве альтернативы использовать синтаксический анализатор skipString, который возвращает unit значение () вместо строки аргумента. В приведенном примере для производительности не имеет значения, используете ли вы pstring или skipString, так как возвращаемая строка является константой. Однако для большинства других встроенных синтаксических анализаторов и комбинаторов вы должны предпочесть варианты с префиксом в имени skip, когда вам не нужны значения результата синтаксического анализатора, поскольку они, как правило, будут быстрее. Если вы посмотрите обзор библиотеки FParsecen, вы увидите варианты skip для многих встроенных синтаксических анализаторов и комбинаторов.

Если вы хотите проанализировать строку без учета регистра, вы можете использовать pstringCIen и skipStringCIen. Например:

> test (skipStringCI "<float>" >>. pfloat) "<FLOAT>1.0";;
Success: 1.0

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

let identifier =
    let isIdentifierFirstChar c = isLetter c || c = '_'
    let isIdentifierChar c = isLetter c || isDigit c || c = '_'

    many1Satisfy2L isIdentifierFirstChar isIdentifierChar "identifier"
    .>> ws // Пропускает завершающие пробелы

Здесь мы использовали синтаксический анализатор many1Satisfy2Len, который является одним из нескольких примитивов для синтаксического анализа строк на основе предикатов символов (т.е. функций, которые принимают символ на входе и возвращают логическое значение). Он анализирует любую последовательность одного или нескольких символов (отсюда и many1 в имени), чей первый символ удовлетворяет первой предикатной функции, а остальные символы удовлетворяют второму предикату (отсюда Satisfy2). Строковая метка, указанная в качестве третьего аргумента (следовательно, L), используется в сообщении об ошибке для описания ожидаемого ввода.

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

> test identifier "_";;
Success: "_"
> test identifier "_test1=";;
Success: "_test1"
> test identifier "1";;
Failure: Error in Ln: 1 Col: 1
1
^
Expecting: identifier

Если вы хотите анализировать идентификаторы на основе синтаксиса Unicode XIDen, рассмотрите возможность использования встроенного анализатора identifieren.

Многие строковые форматы достаточно сложны, поэтому вам нужно объединить несколько примитивов символьного синтаксического анализатора и строкового синтаксического анализатора. Например, рассмотрим следующий пример анализа строки в формате РНБН:

  normalChar:    any char except '\' and '"'

  escapedChar:   '\\' ('\\'|'"'|'n'|'r'|'t')

  stringLiteral: '"' ( normalChar | escapedChar )* '"'

Прямой перевод этой грамматики в FParsec выглядит так:

let stringLiteral =
  let normalChar = 
    let anyCharExcept c = c <> '\\' && c <> '"'
    satisfy anyCharExcept
  let escapedChar = 
    let unescape c = 
      match c with
      | 'n' -> '\n'
      | 'r' -> '\r'
      | 't' -> '\t'
      | c   -> c
    pstring "\\" >>. (anyOf "\\nrt\"" |>> unescape)
  let quote = pstring "\"" 
  between quote quote ( manyChars (normalChar <|> escapedChar) )

В этом примере появилось несколько новых функций библиотеки. Давайте рассмотрим их подробнее:

Давайте протестируем синтаксический анализатор stringLiteral:

> test stringLiteral "\"abc\"";;
Success: "abc"
> test stringLiteral "\"abc\\\"def\\\\ghi";;
Success: "abc"def\ghi"
> test stringLiteral "\"abc\\def\"";;
Failure: Error in Ln: 1 Col: 6
"abc\def"
     ^
Expecting: any char in ‘\nrt"’

Вместо разбора строкового литерала посимвольно мы могли бы также разобрать его построчно:

let stringLiteral2 =
  let normalString = 
    let anyCharExcept c = c <> '\\' && c <> '"'
    many1Satisfy anyCharExcept
  let escapedChar = 
    let unescape c = 
      match c with
      | 'n' -> '\n'
      | 'r' -> '\r'
      | 't' -> '\t'
      | c   -> c
    pstring "\\" >>. (anyOf "\\nrt\"" |>> unescape)
  let quote = pstring "\"" 
  between quote quote ( manyStrings (normalString <|> escapedChar) )

Здесь мы использовали комбинатор manyStringsen , который анализирует последовательность строк с заданным синтаксическим анализатором строк и возвращает объединённую строку.

Мы должны настроить синтаксический анализатор normalString что бы он требовал по крайней мере один символ, т.е. нужно использовать many1Satisfyen вместо manySatisfyen . В противном случае normalString успешно выполниться, даже если нет входных данных, escapedChar никогда не вызовется вызываться, а manyStringsen в конечном итоге вызовет исключение для предотвращения бесконечного цикла.

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

let stringLiteral3 =
  let normalString = 
    let anyCharExcept c = c <> '\\' && c <> '"'
    manySatisfy anyCharExcept
  let escapedChar = 
    let unescape c = 
      match c with
      | 'n' -> '\n'
      | 'r' -> '\r'
      | 't' -> '\t'
      | c   -> c
    pstring "\\" >>. (anyOf "\\nrt\"" |>> unescape)
  let quote = pstring "\"" 
  between quote quote ( stringsSepBy normalString escapedChar) )

Синтаксический анализатор stringsSepByen анализирует последовательность строк (первый аргумент), разделенных другими строками (второй аргумент). Он возвращает все разобранные строки, включая строки разделителя, в виде новой объединённой строки.

Обратите внимание, что stringLiteral3 использует manySatisfyen вместо many1Satisfyen в своем определении normalString, так что он может анализировать экранированные символы, которые не разделены обычными символами. Это приведет к бесконечному циклу, потому что escapedChar не будет исполнено при отсутствии входных данных.