Разбор случаев, требующих много внимания

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

Существуют ли какие-либо практические случаи - для языков программирования или форматов данных в реальном использовании - которые требуют нескольких или неопределенно много символов просмотра вперед (или, что то же самое, обратного отслеживания)?


parsing grammar lookahead
person rwallace    schedule 17.09.2011    source источник

Ответы (2)


arrow_upward
2
arrow_downward

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

Также см. выбранный ответ для Почему C++ не может быть проанализирован с парсером LR(1)?. В частности, цитата:

«Грамматика C ++ неоднозначна, зависит от контекста и потенциально требует бесконечного просмотра вперед для устранения некоторых неоднозначностей».

person Jim Mischel    schedule 17.09.2011
comment
Эта цитата верна? Я думал, что хорошо доказано, что C++ может анализироваться синтаксическим анализатором LALR(1), который, очевидно, является синтаксическим анализатором с ограниченным опережением… - person Nowhere man; 17.03.2012
comment
@Nowhereman: прочитайте выбранный ответ на связанный вопрос, включая упомянутую докторскую диссертацию и второй комментарий, который дает особенно хороший пример. - person Jim Mischel; 19.03.2012

arrow_upward
2
arrow_downward

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

Я никогда не изучал преобразование LR(k) -> LR(1), поэтому вполне возможно, что в некоторых случаях это не так практично.

person Nowhere man    schedule 17.09.2011