Как работает парсер (например, HTML)?

Для аргумента so позволяет взять парсер HTML.

Я читал, что сначала он все токенизирует, а затем анализирует его.

Что означает токенизация?

Анализирует ли каждый анализатор каждый символ, создавая многомерный массив для хранения структуры?

Например, читает ли он <, а затем начинает захватывать элемент, а затем, когда он встречает закрытие > (вне атрибута), он куда-то помещается в стек массива?

Меня интересует ради знания (мне любопытно).

Если бы я прочитал источник чего-то вроде HTML Purifier, это даст мне хорошее представление о том, как анализируется HTML?

Ответ 1

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

Получение вашего прямого вопроса: токенизация примерно эквивалентна принятию английского языка и разбиению на слова. На английском языке большинство слов представляют собой последовательные потоки букв, возможно, включая апостроф, дефис и т.д. В основном слова окружены пробелами, но период, знак вопроса, восклицательный знак и т.д. Также могут сигнализировать о конце слова. Аналогично для HTML (или любого другого) вы указываете некоторые правила о том, что может составлять токен (слово) на этом языке. Часть кода, которая разбивает входные данные на токены, обычно называется лексером.

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

В общем, вы правы в том, как работает парсер, но (по крайней мере, в типичном синтаксическом анализаторе) он использует стек во время анализа синтаксического анализа, но то, что он создает для представления оператора, обычно является tree (и Abstract Syntax Tree, aka AST), а не многомерный массив.

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

Ответ 2

Маркировка может состоять из нескольких шагов, например, если у вас есть этот HTML-код:

<html>
    <head>
        <title>My HTML Page</title>
    </head>
    <body>
        <p style="special">
            This paragraph has special style
        </p>
        <p>
            This paragraph is not special
        </p>
    </body>
</html>

токенизатор может преобразовать эту строку в плоский список значимых токенов, ~~отбрасывание пробелов~~ (спасибо, SasQ для коррекции):

["<", "html", ">", 
     "<", "head", ">", 
         "<", "title", ">", "My HTML Page", "</", "title", ">",
     "</", "head", ">",
     "<", "body", ">",
         "<", "p", "style", "=", "\"", "special", "\"", ">",
            "This paragraph has special style",
        "</", "p", ">",
        "<", "p", ">",
            "This paragraph is not special",
        "</", "p", ">",
    "</", "body", ">",
"</", "html", ">"
]

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

[("<html>", {}), 
     ("<head>", {}), 
         ("<title>", {}), "My HTML Page", "</title>",
     "</head>",
     ("<body>", {}),
        ("<p>", {"style": "special"}),
            "This paragraph has special style",
        "</p>",
        ("<p>", {}),
            "This paragraph is not special",
        "</p>",
    "</body>",
"</html>"
]

тогда синтаксический анализатор преобразует этот список токенов, чтобы сформировать дерево или график, который представляет исходный текст способом, который более удобен для доступа/управления программой:

("<html>", {}, [
    ("<head>", {}, [
        ("<title>", {}, ["My HTML Page"]),
    ]), 
    ("<body>", {}, [
        ("<p>", {"style": "special"}, ["This paragraph has special style"]),
        ("<p>", {}, ["This paragraph is not special"]),
    ]),
])

в этот момент разбор завершен; и тогда пользователь должен интерпретировать дерево, изменять его и т.д.

Ответ 3

Не пропустите примечания W3C на разбор HTML5.

Для интересного введения в сканирование/лексирование выполните поиск в Интернете для эффективного генерации настольных сканеров. Он показывает, как сканирование в конечном счете обусловлено теорией автоматов. Коллекция регулярных выражений преобразуется в одиночный NFA. Затем NFA преобразуется в DFA, чтобы сделать переход состояния детерминированным. Затем в документе описывается метод преобразования DFA в таблицу перехода.

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

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

Пара ресурсов разбора:

Ответ 4

Синтаксис HTML и XML (и другие на основе SGML) довольно сложны для синтаксического анализа, и они не очень хорошо вписываются в сценарий лексинга, потому что они не являются регулярными. В теории разбора регулярная грамматика - та, которая не имеет никакой рекурсии, то есть автомодельные, вложенные шаблоны или скобки, подобные оболочкам, которые должны соответствовать друг другу. Но языки на основе HTML/XML/SGML имеют вложенные шаблоны: теги могут быть вложенными. Синтаксис с шаблонами вложенности более высокий по уровню в классификации Хомского: он контекстно-свободный или даже контекстно-зависимый.

Но вернемся к вашему вопросу о lexer:
Каждый синтаксис состоит из двух видов символов: нетерминальные символы (те, которые раскручиваются в другие правила синтаксиса) и терминальные символы (те, которые являются "атомарными" - это листья дерева синтаксиса и не раскручиваются ни на что другое). Символы терминалов часто являются только токенами. Токены перекачиваются один за другим из лексера и сопоставляются с соответствующими символами терминалов.

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

Итак, чтобы написать лексер для языка HTML/XML/SGML, вам нужно найти части синтаксиса, достаточно атомные и регулярные, с которыми легко справляется лексер. И здесь возникает проблема, потому что сначала не очевидно, какие именно эти части. Я долгое время боролся с этой проблемой.

Но Lie Ryan выше проделали очень хорошую работу по распознаванию этих частей. Браво за него! Типы токенов следующие:

TagOpener: < lexeme, используемый для запуска тегов.
TagCloser: > lexeme, используемый для окончания тегов.
ClosingTagMarker: / lexeme используется в закрывающих тегах.
Имя: буквенно-цифровая последовательность, начинающаяся с буквы, используемая для имен тегов и имен атрибутов.
Значение: текст, который может содержать различные символы, пробелы и т.д. Используется для значений атрибутов.
Равно: = lexeme, используемый для разделения имен атрибутов по его значениям.
Цитата: ' lexeme, используемый для включения значений атрибутов.
DoubleQuote: " lexeme, используемый для включения значений атрибутов.
PlainText: Любой текст, не содержащий < символ напрямую и не охватываемый указанными выше типами.

Вы также можете иметь некоторые токены для ссылок на сущности, например   или &. Возможно:

EntityReference: лексема, состоящая из &, за которой следуют некоторые буквенно-цифровые символы и заканчивается на ;.

Почему я использовал отдельные токены для ' и ", а не один токен для значения атрибута? Поскольку регулярный синтаксис не мог распознать, какой из этих символов должен закончить последовательность, это зависит от характера, который его запустил (символ окончания должен соответствовать стартовому символу). Эта "скобка" считается нерегулярным синтаксисом. Поэтому я продвигаю его на более высокий уровень - в Парсер. Его задача совместить эти маркеры (начало и конец) вместе (или вообще ничего, для простых значений атрибутов, не содержащих пробелов).

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

Ответ 5

Вот как работает HTML 5 Parser: