Как работает парсер (например, HTML)? - PullRequest
Новая
       38

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

37 голосов
/ 30 июня 2010

Ради аргумента предположим, что HTML-парсер.

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

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

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

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

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

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

Ответы [ 5 ]

56 голосов
/ 30 июня 2010

Токенизация может состоять из нескольких шагов, например, если у вас есть этот 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"]),
    ]),
])

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

30 голосов
/ 30 июня 2010

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

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

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

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

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

9 голосов
/ 30 июня 2010

Не пропустите заметки W3C по парсингу HTML5 .

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

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

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

Пара ресурсов для разбора:

7 голосов
/ 09 сентября 2011

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

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

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

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

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

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

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

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

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

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

2 голосов
/ 12 февраля 2017

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

This is how HTML 5 Parser works

...