Здравствуйте, VladD2, Вы писали:

VD>алгоритм нисходящего синтаксического анализа, реализуемый путём взаимного вызова процедур, где каждая процедура соответствует одному из правил контекстно-свободной грамматики или БНФ. Применения правил последовательно, слева-направо поглощают токены, полученные от лексического анализатора. Это один из самых простых алгоритмов синтаксического анализа, подходящий для полностью ручной реализации.

Это самое общее описание, которое подходит под целый класс алгоритмов.

"Комбинаторные парсеры" подходят под это определение?
А генерируемые ANTLR анализаторы для LL(k) грамматик подходят под это определение?

Например, LL(k)-парсер может работать по интерпретируемой таблице, т.е. обслуживать выделенную сущность-стек самостоятельно, но может работать и без таблицы, т.е. "напрямую", используя естественный стек взаимных вызовов ф-ий. Говорят, так эффективней. ANTLR генерит именно такой вариант для LL(k).

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


VD>ПЕГ — это вообще не алгоритм:
VD>PEG, is a type of analytic formal grammar, i.e. it describes a formal language in terms of a set of rules for recognizing strings in the language.

ОК, принимается.
Вы тут рассматривали вполне конкретный алгоритм Packrat всвязи с ПЕГ, замени на Packrat в моём посте и ву а ля — в исходном виде алгоритм Packrat представлен как вызывающие друг друга процедуры парсинга.


V>>"Комбинаторные парсеры" входят в этот класс.
VD>Ты очередной раз говоришь ерунду.

Я очередной раз не люблю слабовольных, которые не в состоянии собой владеть.


VD>Рекурсивный спуск, Пакрат, LR(k), LALR(k), GLR, GLL, TDOP (Top Down Operator Precedence) — это алгритмы.

А чего ж LL(k) забыл? )))

Еще раз, медленно.
Рекурсивный спуск — это СПОСОБ реализации некоего алгоритма нисходящего разбора.
В простейшем случае это простая интерпретация БНФ, т.е. привет бесконечная левая рекурсия.

Поэтому, такие алгоритмы разбора как Пакрат или LL(k)-анализатор — это вовсе не простая интерпретация БНФ, там кое-что предварительно делается с грамматикой, а потом и во время разбора кое-что дополнительно происходит. Но оба алгоритма могут быть и часто реализуются именно методом рекурсивного спуска.


VD>Комбинаторные парсеры могут использовать разные алгоритмы.

Именно так!

Одно "но": парсер самого верхнего уровня — это комбинация парсеров нижнего уровня.

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

комбинатор альтернативного соединения. Принимает на вход два парсера, возвращает парсер, который ведёт себя как "или то или это".

+ парсер терминала (в т.ч. пустого).

Через эти комбинаторы можно выражать правила из БНФ.
Комбинаторные парсеры пришли им мира ФЯ, т.е. речь всегда идёт о комбинации ф-ий, т.е. сами комбинаторы — тоже ф-ии.

В "чистом виде" достаточно описанных 4-х сущностей, чтобы распарсить грамматику класса LL (после факторизации, без левых циклов).
Но в чистом виде мало кто делает, добавляют "черных ящиков", которые лучше справляются с некоторыми цепочками терминалов/нетерминалов.

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

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

Все еще не?


V>>А так же алгоритмы *LL(*)-разбора.
VD>LL — это действительно класс грамматик задающий класс грамматик которые можно разобрать нисходящим парсером (делающим левое порождение, Leftmost derivation). Что означает "*" спереди я не знаю.

Есть подклассы грамматик, например SLL(1).


VD>Соответственно LR(k) описывает классы грамматик разбираемые восходящим анализом (делающим правый вывод).

Ну и?

VD>При этом LR(k) и LL(m) эквивалентны (т.е. их можно преобразовать один в другой, возможно с изменением глубины заглядывания).

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

Но алгоритмы-то разные.

Нисходящий разбор поочередно "пробует" доступные из текущего состояния варианты (если есть варианты), а восходящий разбор выплёвывает "наверх" уже готовый нетерминал, точно так же, как аналогичный нетерминал выплёвывает "наверх" лексер. Один в один.


VD>PEG же описывает более широкий класс грамматик включающий часть контекстно-зависимых грамматик.

ОК, PEG — это эдакий способ борьбы с неоднозначностью. В предыдущем сообщении я имел ввиду нисходящий алгоритм парсера под эту грамматику.


VD>К алогритмам все это имеет опосредованное отношение.

А что ты называешь "алгоритмом"-то?
Переходы по goto, интерпретацию таблиц автомата? ))


VD>Так и LL- и LR-грамматики могут разбираться автоматными парсерами.

Различные алгоритмы разбора автоматными парсерами LL и LR отличаются кардинально. Общее у них только слово "автоматными". Ну и еще слово "таблица", если автомат представлен в виде таблицы. Но содержимое таблиц (семантика ячеек) для LL и LR анализаторов будет резко отличаться.


VD>Хотя обычно LL-грамматики разбираются алгоритмами основанными на рекурсивном спуске.

Во-о-о-от! ЧТД.

Именно что речь идёт о целом классе алгоритмов, даже в случае семейства LL.
Например LL(k) — анализатор имеет вполне себе конкретный алгоритм для конкретного класса грамматик.
Уже писал выше — этот анализатор может работать по таблице, а может быть реализован методом рекурсивного спуска.


VD>До сих пор не понимаю зачем мне нужно работать Камитаном Очевидность, ведь все это написано в Википедии и любом учебнике.

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


VD>Но раз ты намешал все в кашу, приходится писать банальности.

Ну вот прямо отсюда вернись на предыдущий пост и еще раз, не торопясь, прочти написанное.

Потому что пока мест ты потребляешь моё терпение в стиле:
— ты куда, в баню?
— да нет же, я в баню!

Здравствуйте, VladD2, Вы писали:

VD>алгоритм нисходящего синтаксического анализа, реализуемый путём взаимного вызова процедур, где каждая процедура соответствует одному из правил контекстно-свободной грамматики или БНФ. Применения правил последовательно, слева-направо поглощают токены, полученные от лексического анализатора. Это один из самых простых алгоритмов синтаксического анализа, подходящий для полностью ручной реализации.

Это самое общее описание, которое подходит под целый класс алгоритмов.

"Комбинаторные парсеры" подходят под это определение?
А генерируемые ANTLR анализаторы для LL(k) грамматик подходят под это определение?

Например, LL(k)-парсер может работать по интерпретируемой таблице, т.е. обслуживать выделенную сущность-стек самостоятельно, но может работать и без таблицы, т.е. "напрямую", используя естественный стек взаимных вызовов ф-ий. Говорят, так эффективней. ANTLR генерит именно такой вариант для LL(k).

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


VD>ПЕГ — это вообще не алгоритм:
VD>PEG, is a type of analytic formal grammar, i.e. it describes a formal language in terms of a set of rules for recognizing strings in the language.

ОК, принимается.
Вы тут рассматривали вполне конкретный алгоритм Packrat всвязи с ПЕГ, замени на Packrat в моём посте и ву а ля — в исходном виде алгоритм Packrat представлен как вызывающие друг друга процедуры парсинга.


V>>"Комбинаторные парсеры" входят в этот класс.
VD>Ты очередной раз говоришь ерунду.

Я очередной раз не люблю слабовольных, которые не в состоянии собой владеть.


VD>Рекурсивный спуск, Пакрат, LR(k), LALR(k), GLR, GLL, TDOP (Top Down Operator Precedence) — это алгритмы.

А чего ж LL(k) забыл? )))

Еще раз, медленно.
Рекурсивный спуск — это СПОСОБ реализации некоего алгоритма нисходящего разбора.
В простейшем случае это простая интерпретация БНФ, т.е. привет бесконечная левая рекурсия.

Поэтому, такие алгоритмы разбора как Пакрат или LL(k)-анализатор — это вовсе не простая интерпретация БНФ, там кое-что предварительно делается с грамматикой, а потом и во время разбора кое-что дополнительно происходит. Но оба алгоритма могут быть и часто реализуются именно методом рекурсивного спуска.


VD>Комбинаторные парсеры могут использовать разные алгоритмы.

Именно так!

Одно "но": парсер самого верхнего уровня — это комбинация парсеров нижнего уровня.

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

комбинатор альтернативного соединения. Принимает на вход два парсера, возвращает парсер, который ведёт себя как "или то или это".

+ парсер терминала (в т.ч. пустого).

Через эти комбинаторы можно выражать правила из БНФ.
Комбинаторные парсеры пришли им мира ФЯ, т.е. речь всегда идёт о комбинации ф-ий, т.е. сами комбинаторы — тоже ф-ии.

В "чистом виде" достаточно описанных 4-х сущностей, чтобы распарсить грамматику класса LL (после факторизации, без левых циклов).
Но в чистом виде мало кто делает, добавляют "черных ящиков", которые лучше справляются с некоторыми цепочками терминалов/нетерминалов.

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

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

Все еще не?


V>>А так же алгоритмы *LL(*)-разбора.
VD>LL — это действительно класс грамматик задающий класс грамматик которые можно разобрать нисходящим парсером (делающим левое порождение, Leftmost derivation). Что означает "*" спереди я не знаю.

Есть подклассы грамматик, например SLL(1).


VD>Соответственно LR(k) описывает классы грамматик разбираемые восходящим анализом (делающим правый вывод).

Ну и?

VD>При этом LR(k) и LL(m) эквивалентны (т.е. их можно преобразовать один в другой, возможно с изменением глубины заглядывания).

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

Но алгоритмы-то разные.

Нисходящий разбор поочередно "пробует" доступные из текущего состояния варианты (если есть варианты), а восходящий разбор выплёвывает "наверх" уже готовый нетерминал, точно так же, как аналогичный нетерминал выплёвывает "наверх" лексер. Один в один.


VD>PEG же описывает более широкий класс грамматик включающий часть контекстно-зависимых грамматик.

ОК, PEG — это эдакий способ борьбы с неоднозначностью. В предыдущем сообщении я имел ввиду нисходящий алгоритм парсера под эту грамматику.


VD>К алогритмам все это имеет опосредованное отношение.

А что ты называешь "алгоритмом"-то?
Переходы по goto, интерпретацию таблиц автомата? ))


VD>Так и LL- и LR-грамматики могут разбираться автоматными парсерами.

Различные алгоритмы разбора автоматными парсерами LL и LR отличаются кардинально. Общее у них только слово "автоматными". Ну и еще слово "таблица", если автомат представлен в виде таблицы. Но содержимое таблиц (семантика ячеек) для LL и LR анализаторов будет резко отличаться.


VD>Хотя обычно LL-грамматики разбираются алгоритмами основанными на рекурсивном спуске.

Во-о-о-от! ЧТД.

Именно что речь идёт о целом классе алгоритмов, даже в случае семейства LL.
Например LL(k) — анализатор имеет вполне себе конкретный алгоритм для конкретного класса грамматик.
Уже писал выше — этот анализатор может работать по таблице, а может быть реализован методом рекурсивного спуска.


VD>До сих пор не понимаю зачем мне нужно работать Камитаном Очевидность, ведь все это написано в Википедии и любом учебнике.

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


VD>Но раз ты намешал все в кашу, приходится писать банальности.

Ну вот прямо отсюда вернись на предыдущий пост и еще раз, не торопясь, прочти написанное.

Потому что пока мест ты потребляешь моё терпение в стиле:
— ты куда, в баню?
— да нет же, я в баню!


UPD
Добавлю (для уменьшения пинг-понга).
В общем, терминологические споры по-определению бессмысленные и беспощадные.

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