лексические анализаторы по сравнению с синтаксическими анализаторами
Действительно настолько отличаются лексические анализаторы и синтаксические анализаторы в теории?
Кажется модным ненавидеть регулярные выражения: кодируя ужас, другое сообщение в блоге.
Однако популярный lexing основывал инструменты: пигменты, geshi, или украшают, все регулярные выражения использования. Они кажутся закону чем-либо...
Когда lexing достаточно при необходимости в EBNF?
Кто-либо использовал маркеры, произведенные этими лексическими анализаторами с бизоном или antlr парсерами-генераторами?
1 ответ
Да, они очень разные по теории и по реализации.
Лексеры используются для распознавания «слов», составляющих языковые элементы, потому что структура таких слов обычно проста. Регулярные выражения очень хорошо справляются с этой более простой структурой, и для реализации лексеров используются очень высокопроизводительные механизмы сопоставления регулярных выражений.
Синтаксические анализаторы используются для распознавания «структуры» языковых фраз. Такая структура, как правило, выходит за рамки того, что могут распознать «регулярные выражения», поэтому нужно "контекстно-зависимые" парсеры для извлечения такой структуры. Контекстно-зависимые парсеры сложно построить, поэтому инженерный компромисс заключается в использовании "контекстно-свободных" грамматик. и добавить хаки в парсеры («таблицы символов» и т. д.) для обработки контекстно-зависимой части.
Ни технологии лексирования, ни синтаксического анализа вряд ли скоро исчезнут.
Их можно объединить, решив использовать технологию «синтаксического анализа» для распознавания «слов», как это в настоящее время исследуется так называемыми бессканерными синтаксическими анализаторами GLR. Это связано с затратами времени выполнения, поскольку вы применяете более общий механизм к тому, что часто является проблемой, которая в нем не нуждается, и обычно вы платите за это накладными расходами. Если у вас много свободных циклов, эти накладные расходы могут не иметь значения. Если вы обрабатываете большой объем текста, накладные расходы имеют значение, и классические синтаксические анализаторы регулярных выражений будут по-прежнему использоваться.