Как делает синтаксический анализатор (например, HTML) работа?
Поскольку польза аргумента позволяет, принимают синтаксический анализатор HTML.
Я считал, что это маркирует все сначала и затем анализирует его.
Что действительно маркирует средний?
Синтаксический анализатор читает каждый символ каждый, создавая многомерный массив для хранения структуры?
Например, делает это, считал a < и затем начните получать элемент, и затем после того как он встречает закрытие > (за пределами атрибута), это продвинуто на стопку массива где-нибудь?
Мне интересно ради знания (мне любопытно).
Если бы я должен был прочитать источник чего-то как Очиститель HTML, который дал бы мне хорошую идею того, как HTML анализируется?
3 ответа
Прежде всего, вы должны знать, что синтаксический анализ HTML особенно уродлив - HTML широко (и расходился) использовался до того, как был стандартизован. Это приводит ко всевозможным уродствам, таким как стандарт, определяющий, что некоторые конструкции не разрешены, но в любом случае определяет требуемое поведение для этих конструкций.
Переходя к вашему прямому вопросу: токенизация примерно эквивалентна взятию английского языка и его разбиению на слова. В английском языке большинство слов представляют собой последовательные потоки букв, возможно, включая апостроф, дефис и т. Д. В основном слова окружены пробелами, но точка, вопросительный знак, восклицательный знак и т. Д. Также могут обозначать конец слова. Точно так же для HTML (или чего-то еще) вы указываете некоторые правила о том, что может составлять токен (слово) на этом языке. Часть кода, которая разбивает ввод на токены, обычно называется лексером.
По крайней мере, в обычном случае вы не , а не разбиваете весь ввод на токены перед началом синтаксического анализа. Скорее, синтаксический анализатор вызывает лексер, чтобы получить следующий токен, когда он ему нужен. Когда он вызывается, лексер просматривает достаточное количество входных данных, чтобы найти один токен, доставляет его синтаксическому анализатору, и никакие входные данные не токенизируются до тех пор, пока синтаксическому анализатору не понадобится больше входных данных.
В общем, вы правы относительно того, как работает синтаксический анализатор, но (по крайней мере, в типичном синтаксическом анализаторе) он использует стек во время анализа оператора, но то, что он создает для представления оператора, обычно является дерево (и абстрактное синтаксическое дерево, также известное как AST), а не многомерный массив.
Учитывая сложность синтаксического анализа 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>
токенизатор может преобразовать эту строку в плоский список значимых токенов, отбрасывая пробелы (спасибо, 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"]),
]),
])
на этом этапе синтаксический анализ завершено; а затем пользователь должен интерпретировать дерево, изменить его и т. д.
Не пропустите заметки W3C о синтаксическом анализе HTML5 .
Чтобы получить интересное введение в сканирование / лексирование, поищите в Интернете «Эффективное создание таблично-ориентированных сканеров». Это показывает, как в конечном итоге сканирование определяется теорией автоматов. Набор регулярных выражений преобразуется в единую NFA . Затем NFA преобразуется в DFA , чтобы сделать переходы между состояниями детерминированными. Затем в документе описывается метод преобразования DFA в таблицу перехода.
Ключевой момент: сканеры используют теорию регулярных выражений, но, вероятно, не используют существующие библиотеки регулярных выражений. Для лучшей производительности переходы между состояниями кодируются как гигантские операторы case или в таблицах переходов.
Сканеры гарантируют использование правильных слов (знаков). Парсеры гарантируют, что слова используются в правильной комбинации и в правильном порядке. Сканеры используют регулярные выражения и теорию автоматов. Синтаксические анализаторы используют теорию грамматики, особенно контекстно-свободные грамматики .
Пара ресурсов по синтаксическому анализу: