Зачем разделять лексинг и разбор?

15

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

compilers parsers казарка
источник
2
Связанный: programmers.stackexchange.com/questions/128888/…
пользователь
2
Это уже обсуждалось на CS, stackexchange, со многими очень техническими комментариями в ответ на выразительную силу lexer + parser . Но там может быть место для дальнейших ответов.
Бабу
Интересно, может ли параллелизм в конвейерном стиле (хотя и сильно несбалансированный) быть побочным преимуществом? Поведение кэша команд и данных также может быть интересным. Насколько (если вообще) такое уменьшит время компиляции, будет зависеть от конкретного оборудования.
Пол А. Клейтон,
Одна довольно очевидная (по крайней мере для меня) причина в том, что вы можете использовать сканер отдельно. На практике я часто использую flex для сканирования ввода, но редко требуется полная мощность yacc.
jamesqf

Ответы:

13

Вы не должны разделять их. Люди объединяют их в парсеры без сканера .

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

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

Мартин Бергер
источник
1
TпппT
@babou Да, это правильно. Я не знаю никаких формальных результатов вида регулярного выражения, составленного из LL (k), выходит из LL (k) или подобного. Более того, лексические операции обычно не выполняются с обычными языками, а с чем-то более мощным, а именно с обычными языками, расширенными с приоритетами с наибольшим соответствием и первыми ключевыми словами. Я не уверен, что это за класс языка и каковы его свойства замыкания.
Мартин Бергер
2
Если ваш предварительный просмотр предполагает чтение идентификатора, для композиции потребуется неограниченный предварительный просмотр, поскольку (в принципе) нет ограничений на длину идентификаторов.
Бабу
@babou Я не уверен. Если самое длинное ключевое слово имеет длину 17 символов, то любая длинная строка должна быть идентификатором или лексически недействительной.
Мартин Бергер
Но ваш идентификатор, или, возможно, строка, число или другой литерал, представляет собой последовательность из более чем 17 отдельных символов, которая может стоять перед токеном, который вам действительно нужен. Это большой прогноз, неограниченный. Вы можете получить недетерминированный язык.
Бабу