Предварительные замечания
Библиотека fparsec – это библиотека парсер-комбинаторов для языка F#. Здесь мы создадим проект .Net Core в Visual Studio Code и с помощью данной библиотеки создадим парсер HTML-подобного языка разметки. Цели написания парсера полноценного HTML я не ставлю, поскольку задача состоит в том, чтобы разобраться в библиотеке, а не во всех подробностях спецификации HTML, поэтому вряд ли стоит ожидать, что наш парсер будет справляться с документами из сети, хотя его и можно будет доработать. Наша задача состоит в том, чтобы написать парасер упрощенного HTML, и чтобы он справлялся с документами, содержащими те особенности, которые мы заложим в наш парсер.
Пара слов о терминологии. Парсером называется программа, получающая на вход текст, а на выходе выдающая абстрактное синтаксическое дерево. В библиотеке тип Parser является аббревиатурой для функции, которая как раз и делает эту работу. У парсера есть два джинерик-параметра: первый – это тип объекта дерева, который будет получен в результате выполнения этого парсера, а второй – тип объекта, содержащий контекстную информацию, здесь мы его рассматривать не будем. Комбинаторами здесь будут функции высшего порядка, которые принимают папрсеры как аргументы и возвращают новые парсеры, построенные на основе полученных. Чтобы было понятнее, пара иллюстраций. Комбинатор может принимать парсер конкретной строки, например «Итого: » и парсер чисел с плавающей точкой и возвращать он будет парсер, задаче которого будет разбирать строку «Итого: число», где вместо «число» может быть любое число указанного формата. Другой пример комбинатора choise, он принимает список парсеров и возвращает парсер, разбирающий строку, которая может быть разобрана одним из парсеров в списке. Комбинаторы, принимающие только два парсера, как правило реализованы в виде бинарных операторов. Кроме того, в библиотеке есть ряд функций, с помощью которых можно строить собственные парсеры заданного вида. Например, для создания парсера конкретной строки используется функция pstring, она принимает строку и возвращает парсер этой строки. Из простых парсеров с помощью комбинаторов строятся более сложные и так до тех пор, пока не будет получен парсер заданной грамматики. Это если в двух словах.
Чтобы лучше понимать то, что я буду здесь писать, очень желательно сначала ознакомиться с руководством из официальной документации.
Создание проекта
1. Создаем папку FParsecHtml и открываем ее в VSCode. Это можно сделать просто, открыв папку в проводнике и в контекстном меню рабочей области папки выбрать «Open with code».
2. Открываем
встроенный терминал программы (Ctrl+`) и выполняем в
нем следующую команду (на компьютере должен быть установлен .Net Core, разумеется).
dotnet new console -lang f#
Эта команда создаст новый проект во вновь созданной папке.
3. Далее
нам надо установить NuGet-пакет с FParsec.
Актуальную на данный момент версию пакета можно установить, выполнив в
терминале следующую команду
dotnet add package FParsec --version 1.0.3
Создание модели дерева
Поскольку задача парсера состоит в том, чтобы получить дерево, нам сначала надо это дерево описать. Для этого мы создадим два типа: Attribute – это будет просто кортеж из двух строк, представляющих имя и значение атрибута; Node – это будет размеченное объединение, представляющее все узды документа, которые мы намерены различать. Можно было бы сразу использовать, к примеру, классы Linq to XML, но с функциональными типами нам будет работать проще, а в XML мы можем потом просто конвертировать результат.
Добавим в проект новый файл AST.fs и пропишем его в файле проекта.
<ItemGroup>
<Compile Include="AST.fs" />
<Compile Include="Program.fs" />
</ItemGroup>
В самом файле определим нужные нам типы
module AST
type Attribute = string * string
type Node =
| Text of string
| Element of
name: string *
attributes : Attribute list *
childNodes : Node list
| Comment of string
| Doctype of string
| Document of Node list
Хоть этого и достаточно, но еще желательно сделать пару вещей. Во-первых, как уже писалось выше, очень желательно иметь возможность конвертировать это дело в xml-документ, а также форматировать вывод ToString в xml-предствлении – это более привычно для восприятия такого кода, нежели то, что мы будем получать форматирование с помощью printfn "%A". Во-вторых, нам понадобится функция преобразования текста, в частности HTML содержит ряд объектов Entity, которые при конвертировании в XML могут вызвать ошибки, поскольку там их все надо объявлять. Все подобные объекты лучше предварительно заменить символами, которые они обозначают. Список я получил отсюда, с помощью скрипта Violent Monkey в Firefox
// ==UserScript==
// @name Extract html entities as F# list
// @namespace Violentmonkey Scripts
// @match https://www.freeformatter.com/html-entities.html
// @grant GM_registerMenuCommand
// ==/UserScript==
GM_registerMenuCommand("Собрать объекты подстановки", function(){
let dict = {}, fslist = "["
for(let tr of document.querySelectorAll("tr"))
{
let tds = tr.querySelectorAll("td");
if(tds.length == 4 && tds[1].textContent.trim().length > 0)
{
dict[tds[1].textContent.trim()] = tds[2].textContent.trim();
}
}
let a = Object.keys(dict).map(k => `("${k}", "${String.fromCharCode(dict[k].slice(2, -1))}")`).join("; ");
console.log("[" + a + "]");
});
Он выводит в консоль браузера F#-список кортежей, который потом можно легко конвертировать в словарь.
Теперь наш модуль будет иметь следующий вид
module AST
open System.Text.RegularExpressions
open System.Xml.Linq
let entities =
Map.ofList
<| [("&", "&"); ("<", "<"); (">", ">"); ("À", "À"); ("Á", "Á"); ("Â", "Â"); ("Ã", "Ã"); ("Ä", "Ä"); ("Å", "Å"); ("Æ", "Æ"); ("Ç", "Ç"); ("È", "È"); ("É", "É"); ("Ê", "Ê"); ("Ë", "Ë"); ("Ì", "Ì"); ("Í", "Í"); ("Î", "Î"); ("Ï", "Ï"); ("Ð", "Ð"); ("Ñ", "Ñ"); ("Ò", "Ò"); ("Ó", "Ó"); ("Ô", "Ô"); ("Õ", "Õ"); ("Ö", "Ö"); ("Ø", "Ø"); ("Ù", "Ù"); ("Ú", "Ú"); ("Û", "Û"); ("Ü", "Ü"); ("Ý", "Ý"); ("Þ", "Þ"); ("ß", "ß"); ("à", "à"); ("á", "á"); ("â", "â"); ("ã", "ã"); ("ä", "ä"); ("å", "å"); ("æ", "æ"); ("ç", "ç"); ("è", "è"); ("é", "é"); ("ê", "ê"); ("ë", "ë"); ("ì", "ì"); ("í", "í"); ("î", "î"); ("ï", "ï"); ("ð", "ð"); ("ñ", "ñ"); ("ò", "ò"); ("ó", "ó"); ("ô", "ô"); ("õ", "õ"); ("ö", "ö"); ("ø", "ø"); ("ù", "ù"); ("ú", "ú"); ("û", "û"); ("ü", "ü"); ("ý", "ý"); ("þ", "þ"); ("ÿ", "ÿ"); (" ", " "); ("¡", "¡"); ("¢", "¢"); ("£", "£"); ("¤", "¤"); ("¥", "¥"); ("¦", "¦"); ("§", "§"); ("¨", "¨"); ("©", "©"); ("ª", "ª"); ("«", "«"); ("¬", "¬"); ("­", ""); ("®", "®"); ("¯", "¯"); ("°", "°"); ("±", "±"); ("²", "²"); ("³", "³"); ("´", "´"); ("µ", "µ"); ("¶", "¶"); ("¸", "¸"); ("¹", "¹"); ("º", "º"); ("»", "»"); ("¼", "¼"); ("½", "½"); ("¾", "¾"); ("¿", "¿"); ("×", "×"); ("÷", "÷"); ("∀", "∀"); ("∂", "∂"); ("∃", "∃"); ("∅", "∅"); ("∇", "∇"); ("∈", "∈"); ("∉", "∉"); ("∋", "∋"); ("∏", "∏"); ("∑", "∑"); ("−", "−"); ("∗", "∗"); ("√", "√"); ("∝", "∝"); ("∞", "∞"); ("∠", "∠"); ("∧", "∧"); ("∨", "∨"); ("∩", "∩"); ("∪", "∪"); ("∫", "∫"); ("∴", "∴"); ("∼", "∼"); ("≅", "≅"); ("≈", "≈"); ("≠", "≠"); ("≡", "≡"); ("≤", "≤"); ("≥", "≥"); ("⊂", "⊂"); ("⊃", "⊃"); ("⊄", "⊄"); ("⊆", "⊆"); ("⊇", "⊇"); ("⊕", "⊕"); ("⊗", "⊗"); ("⊥", "⊥"); ("⋅", "⋅"); ("Α", "Α"); ("Β", "Β"); ("Γ", "Γ"); ("Δ", "Δ"); ("Ε", "Ε"); ("Ζ", "Ζ"); ("Η", "Η"); ("Θ", "Θ"); ("Ι", "Ι"); ("Κ", "Κ"); ("Λ", "Λ"); ("Μ", "Μ"); ("Ν", "Ν"); ("Ξ", "Ξ"); ("Ο", "Ο"); ("Π", "Π"); ("Ρ", "Ρ"); ("Σ", "Σ"); ("Τ", "Τ"); ("Υ", "Υ"); ("Φ", "Φ"); ("Χ", "Χ"); ("Ψ", "Ψ"); ("Ω", "Ω"); ("α", "α"); ("β", "β"); ("γ", "γ"); ("δ", "δ"); ("ε", "ε"); ("ζ", "ζ"); ("η", "η"); ("θ", "θ"); ("ι", "ι"); ("κ", "κ"); ("λ", "λ"); ("μ", "μ"); ("ν", "ν"); ("ξ", "ξ"); ("ο", "ο"); ("π", "π"); ("ρ", "ρ"); ("ς", "ς"); ("σ", "σ"); ("τ", "τ"); ("υ", "υ"); ("φ", "φ"); ("χ", "χ"); ("ψ", "ψ"); ("ω", "ω"); ("ϑ", "ϑ"); ("ϒ", "ϒ"); ("ϖ", "ϖ"); ("Œ", "Œ"); ("œ", "œ"); ("Š", "Š"); ("š", "š"); ("Ÿ", "Ÿ"); ("ƒ", "ƒ"); ("ˆ", "ˆ"); ("˜", "˜"); (" ", " "); (" ", " "); (" ", " "); ("‌", ""); ("‍", ""); ("‎", ""); ("‏", ""); ("–", "–"); ("—", "—"); ("‘", "‘"); ("’", "’"); ("‚", "‚"); ("“", "“"); ("”", "”"); ("„", "„"); ("†", "†"); ("‡", "‡"); ("•", "•"); ("…", "…"); ("‰", "‰"); ("′", "′"); ("″", "″"); ("‹", "‹"); ("›", "›"); ("‾", "‾"); ("€", "€"); ("™", "™"); ("←", "←"); ("↑", "↑"); ("→", "→"); ("↓", "↓"); ("↔", "↔"); ("↵", "↵"); ("⌈", "⌈"); ("⌉", "⌉"); ("⌊", "⌊"); ("⌋", "⌋"); ("◊", "◊"); ("♠", "♠"); ("♣", "♣"); ("♥", "♥"); ("♦", "♦")]
let h2xText text =
let re = Regex(@"\&[a-zA-Z]+;", RegexOptions.IgnoreCase)
re.Replace(text, fun (m:Match) ->
if entities.ContainsKey(m.Value)
then entities.Item(m.Value)
else "")
type Attribute = string * string
type Node =
| Text of string
| Element of
name: string *
attributes : Attribute list *
childNodes : Node list
| Comment of string
| Doctype of string
| Document of Node list
with
member this.ToXNode() =
let (!) s = XmlConvert.EncodeName(if (s:string).ToLower().StartsWith("xml") then "_" + s else s)
let rec getNode = function
| Text(t) -> XText(h2xText t) :> XNode
| Doctype(dt) ->
XComment(sprintf "Doctype node content : %s" dt) :> XNode
| Comment(c) -> XComment(c) :> XNode
| Element(n, a, c) ->
let atts = List.map (fun (name:string, value) ->
XAttribute(XName.Get(!name), h2xText value) :> obj) a
let children = List.map getNode c
XElement(XName.Get(!n), atts, children) :> XNode
| Document(nl) -> XDocument(List.map getNode nl |> Seq.ofList) :> XNode
getNode this
override this.ToString() = this.ToXNode().ToString()
В коде я кое-что упростил. Например doctype нам, в принципе, не особо нужен для извлечения данных из документа, но, на случай, если в документе он будет, мы его получаем, не разбирая на составляющие, а при преобразовании в XML заменяем его комментарием, в котором будет указано, что это содержимое узла doctype.
Парсер
Далее создаем собственно сам парсер. В проект добавим файл Parser.fs. В файле проекта он должен быть описан ниже файла AST.fs, при этом надо помнить, что файл Program.fs всегда должен оставаться в списке самым последним. На данный момент код данного файла должен быть следующим
module Parser
open FParsec
open AST
Если FParsec недоступен, то надо
выполнить команду
dotnet restore
Для начала сделаем как в руководстве в официальной документации и определим три функции str, ws и str_ws. Первая будет псевдонимом библиотечной функции pstringCI, которая принимает строку и возвращает регистронезависимый парсер этой сроки. В документации в аналогичной ситуации использовалась фунция pstring, но, поскольку мы разбираем регистронезависимый язык, стало быть – лучше использовать pstringCI, где постфикс CI означает Case Insensetive. Вторая функция ws – парсер необязательных пробельных литер. И третья – работает как первая, за которой следует вторая.
let str = pstringCI
let ws = spaces
let str_ws s = str s .>> ws
Теперь разберемся с несколькими комбинаторами, которые мы будем часто использовать. В первую очередь рассмотрим комбинаторы .>>, >>. и .>>.
Эти три комбинатора объединяют два последовательно идущих
друг за другом парсера. Точки указывают с какой стороны находится значимая
часть. Например, возьмем открывающий тег, он начинается со знака <, за
которым следует имя тега. При этом, при создании объекта элемента из этих двух
парсеров, только второй будет содержать информацию, которая нам нужна, а именно
– имя элемента. Стало быть для построения нового парсера из этих двух нам
понадобится второй комбинатор
str "<" >>. nameparser
В результате будет получен парсер, который парсит имя элемента, которому предшествует знак <, но возвратит только имя. При этом комбинатор с двумя точками будет делать то же самое, но вернет кортеж, который будет содержать значения, полученные обоими парсерами. Думаю, пока непонятно, но дальше картина прорисуется.
Далее нам довольно часто будет нужно создавать парсеры, которые будут брать любую строку, не содержащую определенных символов. Аргументом функции будет строка из запрещенных символов.
let notContains (s:string):Parser<string,unit> = isNoneOf s |> many1Satisfy
Здесь использованы функции isNoneOf и many1Satisfy. Функция many1Satisfy принимает функцию-предикат char->bool и возвращает парсер, для строки, все символы которой удовлетворяют этому предикату. Функция isNoneOf принимает набор символов и возвращает функцию-предикат, возвращающую true для всех символов, кроме содержащихся в наборе. Объединение этих функций как раз дает то, что нам нужно.
Следует также обратить внимание на то, что здесь время-от-времени требуется аннотация типов. Поскольку мы не используем контекстные данные, второй джинерик-параметр типа Parser надо прописывать как unit явным образом.
Простые узлы
К простым узлам мы отнесем текстовые узлы, doctype и комментарии.
Текстовые узлы не должны содержать символов "<>". Для их парсинга мы можем использовать определенную выше функцию notContains, мало того – мы так и поступим, но прежде чем это делать нам надо решить еще одну проблему. Дело в том, что функция notContains возвращает парсер Parser<string, unit>, но после парсинга любого узла мы хотели бы получить парсер Parser<Node, unit>, где Node – это как раз то самое размеченное объединение, которые мы определили в модуле AST. Поэтому нам придется познакомиться с еще одним важным оператором |>> . В двух словах: левый операнд – это парсер, правый – функция, которая принимает объект полученный левым парсером, и возвращает объект, заключенный в результирующий парсер. На примере будет более понятно. Если слева будет парсер Parser<string, unit>, а справа – функция, которая конвертирует строку в текстовый узел, то на выходе мы получим Parser<Node, unit>, где Node как раз и будет тем самым текстовым узлом. Таким образом парсер текстовых узлов у нас будет выглядеть так
let text = notContains "<>" |>> Text
Комментарии начинаются с последовательности "<!--" и заканчиваются последовательностью "-->". Между ними может быть любой текст.
let comment : Parser<Node, unit> = (str "<!--") >>. (charsTillString "-->" false 10000) .>> str "-->" |>> Comment
Здесь использована функция charsTillString. С ее помощью мы строим парсер, который будет брать символы, пока не наткнется на строку, которую мы передаем первым аргументом. Второй аргумент указывает следует ли захватить эту строку (из первого аргумента), а третий – максимальное количество символов, которое будет взято. Ограничения количества символов – не очень хорошая новость, но там можно прописать довольно большое число.
Узел doctype нам, в общем-то, не очень-то и нужен, но, поскольку в документе он есть, его надо как-то обработать. Мы будем брать текст между "<!doctype" и ">". Здесь необязательно использовать charsTillString, поскольку признаком завершения узла является только один символ. Нам достаточно определить текст узла как любую последовательность символов, не содержащую этого символа и этого будет достаточно.
let doctype: Parser<Node, unit> =
pipe3
(str_ws "<!doctype")
(notContains ">")
(str ">")
(fun _ t _ -> Doctype t)
Здесь можно было как и раньше использовать комбинаторы >>. , >>. и |>>, но, поскольку мы учимся, лучше попробовать что-то новое. Комбинатор pipe3, равно как и другие подобные ему, объединяет в цепочку три парсера и последний аргумент – это функция, принимающая три аргумента (по одному на каждый парсер) и возвращающая нужный узел. Такие комбинаторы удобно использовать в тех случаях, когда нужно обработать данные всех парсеров, а не только тех, возле которых стоят точки (.>>, >>., .>>. и т. п.). Хотя в данном случае мы используем данные только одного парсера, поэтому можно было бы записать это так
let doctype: Parser<Node, unit> =
(str_ws "<!doctype")
>>.(notContains ">")
.>>(str ">")
|>> Doctype
Тестирование парсеров
Здесь все просто: возьмем функцию тестирования из руководства и разместим ее в файле Program.fs, разумеется выше функции main, помеченной как точка входа.
let test p str =
match run p str with
| Success(result, _, _) -> printfn "Success: %A" result
| Failure(errorMsg, _, _) -> printfn "Failure: %s" errorMsg
Кроме того, в нашем случае полезно будет туда же добавить еще одну похожую функцию
let printDoc p str =
match run p str with
| Success(result, _, _) -> printfn "Success:\n %O" result
| Failure(errorMsg, _, _) -> printfn "Failure: %s" errorMsg
Отличается она от первой только строкой форматирования результата. Если мы вспомним наш тип Node, то там мы переопределили метод ToString, который сначала конвертирует узел в XNode и уже у него вызывает ToString. Благодаря этому, при желании, мы можем отображать результат парсинга в XML-формате, что более удобно, учитывая, что парсить мы взялись HTML.
Теперь можно добавить код типа
test comment "<!-- alsdfja;s lasdjfalsdjf alsdjf a; --> ajlsdf;asd-->"
и запустить проект на выполнение, а в выводе посмотреть, был ли парсинг удачным.
Атрибуты
Существуют следующие формы атрибутов:
1. Со значением в двойных кавычках
2. Со значением в одинарных кавычках
3. Со значением без кавычек
4. Без значения
В связи с тем, что атрибуты определяются по-разному, по всей видимости, пришло время познакомиться с комбинаторами <|> и choice. Данные комбинаторы позволяют создавать альтернативные ветви разбора текста. То есть из нескольких парсеров создается один, который будет сначала использовать первый, при неудаче (не фатальной ошибке) переходить к следующему и т.д. Комбинатор <|> объединяет таким образом два парсера, а choice может работать с целым списком, при этом запись
choice [a; b; c; d] равносильна
a <|> b <|> c <|> d
Таким образом нам нужно создать три парсера для разных типов значений атрибутов, объединив их в один. Построить парсер полного атрибута и объединить его с парсером атрибута без значения.
let attribute : Parser<Attribute, unit> =
let value1 = (str "'") >>. notContains "'<>" .>> (str "'")
let value2 = (str "\"") >>. notContains "\"<>" .>> (str "\"")
let value3 = notContains "'\" \t\r\n"
choice [
notContains " \t\r\n=<>/" .>> str "=" .>>. (value1 <|> value2 <|> value3)
many1Satisfy isLetter |>> fun a -> (a, a)
]
Функция many1Satisfy принимает функцию-предикат char->bool и возвращает парсер строки, состоящей из символов, удовлетворяющих функции-предикату. Единица в названии говорит о том, что требуется как минимум один символ. isLetter – готовая функция-предикат, возвращающая true только для букв.
Можно протестировать наш парсер
test attribute "qwerty другой текст"
test attribute "qwerty=wasd другой текст"
test attribute "qwerty='wasd этот же текст' другой текст"
test attribute """qwerty="wasd этот же текст" другой текст"""
В первом случае мы получили атрибут, в котором имя и значение равно qwerty. Во втором – в качестве значения было взято только слово wasd. В последних двух – только содержимое кавычек или апострофов попало в значение атрибутов.
Пустые элементы
Под пустыми элементами я подразумеваю те элементы, которые в HTML не могут иметь дочерних узлов и для которых запрещен закрывающий тег. Есть фиксированный список таких элементов, также надо учесть возможное использование XML-синтаксиса и завершаться такой элемент может сочетанием "/>".
let emptyElement =
let emptyTags = ["area"; "base"; "br"; "col"; "command"; "embed"; "hr"; "img"; "input"; "keygen"; "link"; "menuitem"; "meta"; "param"; "source"; "track"; "wbr"]
let name = List.map str emptyTags |> choice
str "<" >>. name .>> ws .>>. sepEndBy attribute ws
.>> ( str "/>" <|> str ">")
|>> (fun (n, al) -> Element(n, al, []))
Здесь общий смысл должен быть понятен, объяснения требует только функция sepEndBy. Функция принимает парсер и разделитель и порождает парсер, который будет «брать» элементы, соответствующие парсеру, разделенные разделителем, при этом последовательность может заканчиваться необязательным разделителем. Это как раз то, что нам нужно, чтобы указать список атрибутов, разделенных пробельными литерами. Здесь надо сказать, что, строго говоря, мы сделали все не совсем как надо. Дело в том, что парсер ws, определенный вначале как псевдоним spaces соответствует необязательным пробельным литерам, а между атрибутами пробел обязателен. Но в нашем случае это не особенно важно, поскольку задачу написания парсера с валидацией мы не ставили.
Тестируем парсер на примере элемента area
test emptyElement """<area qwerty=wasd asdf='ldfj salfja' zxcv="lf bb" readonly/>"""
test emptyElement """<base qwerty=wasd asdf='ldfj salfja' zxcv="lf bb" readonly/>"""
test emptyElement """<br qwerty=wasd asdf='ldfj salfja' zxcv="lf bb" readonly/>"""
Все работает. Теперь можно также использовать для теста printDoc вместо test и получать вывод в XML-формате.
printDoc emptyElement """<area qwerty=wasd
asdf='ldfj salfja'
zxcv="lf bb" readonly />"""
printDoc emptyElement """<base qwerty=wasd asdf='ldfj salfja' zxcv="lf bb" readonly>"""
printDoc emptyElement """<br qwerty=wasd asdf='ldfj salfja' zxcv="lf bb" readonly >"""
Элементы, которым «можно все»
Конечно же, надо отдельно рассмотреть такие элементы как script и style. Там потенциально может присутствовать все, что угодно и это не следует разбирать как разметку, то есть все содержимое этих элементов должно интерпретироваться как текстовый узел.
let scriptAndStyle =
let elt name =
let endtag = str "</" >>. str_ws name .>> str ">"
(str_ws ("<" + name))
>>. (sepEndBy attribute ws .>> str ">")
.>>. (manyCharsTill anyChar endtag)
|>> (fun (atts, text) -> Element(name, atts, [Text text]))
choice [elt "script"; elt "style"]
Здесь из интересного – функция manyCharsTill, которая принимает два аргумента: певрый – парсер, который будет многократно отбираться до тех пор, пока не будет найдено соответствие второму; второй – как раз стоп-парсер, указывающий признак прекращения операции. Здесь в качестве первого парсера мы взяли всеядный anyChar, вторым будет закрывающий тег элемента. Здесь надо иметь в виду одну особенность функции manyCharsTill: стоп-парсер (второй аргумент) захватывается тем парсером, который порождает эта функция, но при этом его данные нигде не отображены. В нашем случае это подходит, поскольку данные закрывающего тега нам не нужны, а сам тег используется как признак закрытия элемента, но вообще, при использовании этой функции эту особенность надо иметь в виду. Следует также заметить, что в определении парсера комментария эта функция тоже подошла бы больше, поскольку она не ограничивает длину комментария. Но поскольку главная наша цель – разобраться в библиотеке, стало быть – чем больше функций мы используем - тем лучше.
Обычные элементы
При описании парсера обычного элемента есть две проблемы:
1. Рекурсивная природа элемента (элемент может содержать дочерние узлы, среди которых могут быть другие элементы), при том, что рекурсивные парсеры не предусмотрены (насколько мне известно).
2. При описании закрывающего тега, его имя надо получать из тега открывающего, а это сложно сделать без контроля контекстной информации с помощью пользовательских данных, которые здесь мы не рассматриваем.
Для решения первой проблемы в библиотеке предусмотрена специальная функция createParserForwardedToRef. Работает эта функция следующим образом, объясню сразу на нашем примере. Нам нужен общий парсер узлов, независимо от их типа, поскольку элемент может включать в себя разные узлы. «Забить» в такой узел элемент до его определения мы не можем, поэтому и прибегаем к этой функции. Функция порождает парсер, но не определяет его, а кроме парсера, она создает ссылочную ячейку, которая будет с этим парсером связана. Возвратит функция как раз кортеж с парсером и ячейкой. После того как мы определим элемент и другие узлы мы можем дать определение и парсеру. Но поскольку переопределить существующий парсер мы не можем, мы будем использовать для этой цели связанную с парсером ссылочную ячейку. То есть, выглядеть все это будет следующим образом.
let node, nodeRef = createParserForwardedToRef<Node, unit>()
let nodeList = many node
let element =
tuple3
(str "<" >>. notContains "<>/ \t\r\n='\"" .>> ws)
(sepEndBy attribute ws .>> str ">")
nodeList
>>= (fun (name, atts, children) ->
str ("</" + name) .>> ws .>> str ">"
|>> fun _ -> Element(name, atts, children))
do nodeRef :=
choice [
attempt doctype
attempt comment
attempt scriptAndStyle
attempt emptyElement
attempt element
text]
Вторую проблему мы решили с помощью комбинатора >>= . Этот комбинатор действует следующим образом: парсер слева возвращает какое-то значение и к нему прибавляется… нет не парсер справа, а парсер, который возвращает функция справа. Функция принимает все, что напарсил левый парсер как аргумент, на базе этих данных создает парсер, который и будет применен к следующему участку текста и вся эта конструкция будет возвращать то, что возвратит этот новый парсер. Таким образом мы взяли все вплоть до закрывающего тега, создали на базе этого кортеж с помощью комбинатора tuple3, передали его функции, которая создала на базе полученных данных парсер закрывающего тега и с помощью уже известного нам комбинатора |>> задала для него в качестве возвращаемого значения новый элемент с данными, опять-таки, полученными из того же кортежа.
Теперь об определении узла. Как уже было сказано выше, определение мы передаем не самому узлу, который мы не можем изменить, а связанной с ним ссылочной ячейкой. Но тут следует обратить внимание на использование функции attempt. Я уже упоминал выше, что комбинаторы типа choice или <|> могут подбирать нужный парсер, если предыдущий завершился с не фатальной ошибкой. Но проблема в том, что определения узлов достаточно сильно отличаются и поэтому, когда ожидается, скажем, комментарий, а вместо него попадается элемент, в котором после «<» не может идти восклицательный знак, то это приводит к фатальной ошибке и разбор на этом заканчивается. Функция attempt позволяет указать, что такую ошибку не следует считать фатальной и перейти к следующему парсеру.
Теперь, если мы добавим еще и определение всего документа, то уже можно будет посмотреть на наш парсер в работе на примере простых документов.
test document """<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" dir="ltr" lang="ru">
<head>
<title>Test</title>
</head>
<body>
Hello world! <br/>
<script type="text/javascript">
for(let i = 0; i < 10; i++)
console.log(i);
</script>
<a href='#' nofollow>Go</a>
</body>
</html>
"""
Что касается реальных документов из сети, то здесь все не так просто. Я в самом начале написал, что не ставлю целью написание полноценного парсера реального HTML, тем не менее выяснить, почему наш парсер не справляется с тем или иным документом – есть смысл. Например, возьмем вот эту страницу
https://docs.microsoft.com/ru-ru/dotnet/fsharp/language-reference/tuples
В таком виде какой сейчас имеет наш парсер, при попытке «взять» эту страницу мы получим кучу ошибок
let wc = new WebClient()
test document (wc.DownloadString("https://docs.microsoft.com/ru-ru/dotnet/fsharp/language-reference/tuples"))
Однако, если просмотреть сообщения об ошибках, то можно заметить, что ругается парсер на атрибут, который не имеет значения. Мы определили такие атрибуты таким образом, что имена в них состоят исключительно из букв, а там помимо букв есть еще и тире. Если это исправить, то с этой страницей наш парсер справится.
let attribute : Parser<Attribute, unit> =
let value1 = (str "'") >>. manySatisfy (isNoneOf "'") .>> (str "'")
let value2 = (str "\"") >>. manySatisfy (isNoneOf "\"") .>> (str "\"")
let value3 = notContains "'\" \t\r\n"
choice [
attempt(notContains " \t\r\n=<>/" .>> str "=" .>>. (value1 <|> value2 <|> value3))
many1Satisfy (fun c -> isLetter c || c = '-') |>> fun a -> (a, a)
]
Кроме того, здесь я изменил определение значений атрибутов, теперь «закавыченные» значения не могут содержать только кавычек, в которые они обрамлены, а все остальное разрешено.
Таким образом изучение спецификации HTML поможет написать полноценный парсер, но мы здесь занимаемся не этим.
Также столкнулся с неожиданной проблемой, что парсер на сайте MDN споткнулся на пустом элементе (без закрывающего тега). Мы вроде все предусмотрели, но у нас есть список HTML-элементов, в которых запрещен закрывающий тег, а там встретились элементы SVG, которые предусмотрены не были. Все это решаемо, но требует изучения формата.
Элементы с необязательным закрывающим тегом
Последний вопрос, который мы здесь рассмотрим – это элементы, в которых закрывающий тег нужен, но не обязателен, то есть если он пропущен, то парсер сам должен определить место, в котором элемент следует закрыть.
Рассматриваются три признака закрытие таких элементов:
1. У элемента все-таки есть закрывающий тег
2. В документе встречается элемент, который не может быть непосредственным потомком данного элемента
3. Закрывается родительский элемент.
Ну с первым пунктом все более-менее понятно: в случае если встречается закрывающий тег элемента, мы действуем так же, как с обычным элементом.
По второму пункту нам нужно будет составить словарь, в котором для каждого такого элемента мы определим, чего не может быть среди его детей.
С третьим пунктом не все так просто. Дело в том, что с самого начала мы не стали отслеживать контекстную информацию с помощью пользовательских данных, поэтому мы не знаем, какой именно элемент был в документе открыт последним. С другой стороны, если мы предполагаем, что в документе нет ошибок, то любой закрывающий тег, кроме того, который закрывает текущий элемент, можно считать закрывающим родительский. Такой подход может сильно испортить структуру документа, если в нем попадется потерянный тег, но в случае, если документ правильный – проблем быть не должно.
Для построения карты элементов, создал отдельный модуль, но можно сделать это и в модуле Parser.
let elems =
let (!) l = List.map ((+) "<" >>pstringCI) l |> choice : Parser<string, unit>
[
("p", !["address"; "article"; "aside"; "blockquote"; "div"; "dl";
"fieldset"; "footer"; "form"; "h1"; "h2"; "h3"; "h4";
"h5"; "h6"; "header"; "hr"; "menu"; "nav"; "ol"; "pre";
"section"; "table"; "ul"])
("body", ![])
("colgroup", !["colgroup"; "thead"; "tbody"; "tfoot"; "tr"])
("dd", !["dd"; "dt"])
("dt", !["dd"; "dt"])
("head", !["body"])
("html", ![])
("li", !["li"])
("option", !["option"; "optgroup"])
("thead", !["thead"; "tbody"; "tfoot"; "tr"])
("tbody", !["thead"; "tbody"; "tfoot"; "tr"])
("tfoot", !["thead"; "tbody"; "tfoot"; "tr"])
("tr", !["thead"; "tbody"; "tfoot"; "tr"])
("th", !["thead"; "tbody"; "tfoot"; "tr"])
("td", !["thead"; "tbody"; "tfoot"; "tr"])
]
Здесь список кортежей, в которых первый элемент – имя тега, второй – парсер, соответсвующий началу открывающих тегов, которые не могут быть его непосредственными потомками. Парсеры ищут только текст типа "<dd". То есть это не совсем точное определение, поскольку на элемент, имя которого только начинается с данной строки он тоже отреагирует, но это несложно исправить, а для демонстрации этого достаточно.
Ну и, собственно, код парсера.
let optinalEndedElement =
let elemsMap = Map.ofList elems
let unclosed name =
let endp = choice [elemsMap.[name] |> attempt; str "</"]
pipe3
(str "<" >>. str name .>> ws)
(sepEndBy attribute ws .>> str ">")
(notFollowedBy endp >>. node |> many)
(fun _ atts chn -> Element(name, atts, chn))
List.map (fst >> unclosed >> attempt) elems |> choice : Parser<Node, unit>
Здесь из интересного только использование конструкции
notFollowedBy endp >>. node |> many
Она делает то же самое, что сделала бы функция manyTill, которая уже была ранее использована, с той лишь разницей, что в данном случае, строка, полученная с помощью стоп-парсера (того, что указывает в каком месте надо прекратить отбирать узлы) не «съедается», а оставляется следующему парсеру. А в общем, мы создаем функцию unclosed, которая получает имя элемента и на его основе создает парсер незакрытого элемента и далее, на базе созданного ранее списка создаем из имен список парсеров и передаем его фукнции choice.
Далее, полученный парсер добавляем в список узлов и можно тестировать.
do nodeRef :=
choice [
attempt doctype
attempt comment
attempt scriptAndStyle
attempt element
attempt emptyElement
attempt optinalEndedElement
text]
Заключение
В общем и целом, поставленная задача решена. Документ, написанный на HTML, включающий возможности, которые мы закладывали в наш парсер – вполне разбирается и даже некоторые документы, скачанные из сети – тоже оказались под силу нашему парсеру. Некоторые документы из сети не поддаются разбору с его помощью в силу того, что они содержат ошибки, обработку которых мы не предусмотрели. Например, парсеры, используемые в браузерах, легко справляются с «потерянными тегами». То есть, если в документе мы имеем следующий код
<div>
qwerty<div style="color: brown;">asdf
</div>
То браузер его отобразит и текст “asdf” будет подкрашен коричневым. То есть такой код будет интерпретирован следующим образом
<div>
qwerty<div style="color: brown;">asdf
</div></div>
Другой вариант – это «безхозные» закрывающие теги. Браузеры их тоже обрабатывают. Раньше IE даже создавал элемент с именем, начинающимся со слеша.
И если открывающий тег можно легко закрыть, в случае закрытия родительского элемента, то с для того, чтобы отследить закрывающие, придется удерживать контекстную информацию в пользовательских данных. В нашем случае любая из этих ошибок будет фатальной. Есть и другие нюансы. Например, текстовые узлы у нас могут содержать любой текст, не содержащий символов «<» и «>». Но в реальных документах они могут встречаться, просто отслеживание таких вариантов потребовало бы дополнительных усилий - я упростил.
Таким образом, даже если учесть все особенности языка, этого недостаточно для обработки документов из сети, а нужно еще обрабатывать те ошибки, которые обрабатывают веб-движки, поскольку документов, содержащих такие ошибки в сети полно.
Еще следует добавить, что полноценного тестирования парсера я не проводил, документы, на которых выполнялись тесты, есть во вложении, ничего большего гарантировать не могу. Это учебный пример.
Комментариев нет :
Отправить комментарий