Сообщение Re[11]: Опциональные типы от 09.03.2017 6:39
Изменено 09.03.2017 6:53 vdimas
Re[11]: Опциональные типы
Здравствуйте, VladD2, Вы писали:
VD>Я не знаю, что ты там за цифры давал. Но на свете нет ни одного GLR-а пригодного для промышленного использования.
Мде? А я думал, что самый ходовой генератор парсеров всех времен — это Бизон.
Который прекрасно генерить GLR.
VD>У них и с производительностью проблемы, и с восстановлением после ошибок.
Восстановление после ошибок — это специфичное требование.
VD>Если я ошибаюсь, дай ссылок.
Бизон:
https://www.gnu.org/software/bison/manual/html_node/GLR-Parsers.html
"Умный Яндекс":
https://habrahabr.ru/company/yandex/blog/219311/
V>>Т.е., когда лексер-парсер работают в паре, то лексический анализатор занимает львиную долю тиков процессора из затрат на парсинг (формирование AST — это, считай, "отдельная" нагрузка). Т.е. синтаксический анализ занимает меньшую долю тиков в совместной работе.
VD>Само наличие лексера сокращает число этих самых тактов на порядки. Парсеру приходится работать не с миллионами символов, а с тысячами или даже сотнями. Число неоднозначностей падает с тысяч, до единиц или даже нуля.
Верно. Я же говорил — трафик у парсера сильно меньше, чем у лексера.
Я писал, что подключение парсера к лексеру на моих данных давало лишь 5%-10% проседания производительности, т.е. парсер+лексер работают примерно так же, как один лексер.
VD>Слушай читать твои фантазии у меня никакого желания нет.
Читать мало, надо понимать.
Итого, лексер производит сдвиг (в терминах LR) по цепочке символов, потом сворачивает (в терминах LR) эту цепочку терминалов в один нетерминал и подаёт "наверх" в виде кода нетерминала. Так трафик-то нетерминалов получается меньше?
А теперь на более высоком уровне опять происходит сдвиг по накопленной цепочке нетерминалов и опять сворачивание цепочки нетерминало в один нетерминал — и опять получается трафик в разы меньший для еще более вышестоящего уровня, верно?
Итого, чем глубже вложенность выражения (скажем, при парсинге некоего ЯП), тем меньше трафик нетерминалов самого высокого уровня? Т.е., получается, что от глубины вложенности выражений скорость LR-парсинга практически не зависит, верно?
А вот для парсера с откатами в случае недостаточности просмотра на 1, глубокая вложенность выражений может стать больным местом. Не зря расширения Пакрата и ALL используют мемоизацию и прочие трюки.
VD>Но сам лексер работает просто на порядки быстрее.
ЗА СЧЕТ ЧЕГО?
VD>"Отлексить" с помощью качественного компилированного кода основанного на ДКА даже десятимегабайтный файл — это денницы миллисекунд. А вот парсинг того же самого — это совсем другой расклад.
Ну скорми LR(0)-парсеру грамматику от лексера (почему бы и нет?) и проверь.
Ну будет у тебя стек разбора с фиксированной глубиной 1, и?
Алгоритм же тот же...
V>>Потому что трафик символов разный, ес-но.
VD>Ты говоришь полную чушь! Трафик ничто по сравнению с вычислительными затратами.
Лексер тоже выполняет сдвиг и свертку, напомню.
Сделай эти операции такими же дешевыми, как в лексере.
Просто я часто видел, как хранят стек разбора LR-парсера в виде linked list. Но? если ты для лексера будет представлять входные терминалы как linked list, то вычислительные затраты лексера тоже станут ого. ))
VD>А главное, что GLR (ну, если это реально GLR, а не что нибудь) являются безлексерными и разбирают отдельные символы далекими от эффективности алгоритмами.
Вот это чушь как она есть.
Самой граматике глубоко до фени как она получена, т.е. является ли исходной или же является результатом декомпозиции грамматик, когда регулярную часть выделили в отдельный парсер, который назвали лексером.
А что мешает, кстате, произвести подобную декомпозицию более одного раза?
V>>Только на неоднозначностях.
VD>Хрен там. У них и константа во много раз выше. Не может быть обобщенный алгоритм столь же эффективным, как специализированный.
Может на единственной ветке разбора.
VD>Вот ДКА ты хрен когда догонишь. Хот ты лопни.
LR(0) и LR(1) — это и есть ДКА, принцип работы которых близок к ДКА лексера.
А GLR парсит по НКА, вот и вся разница. Т.е. от каждой ячейки по данному символу может быть более одного перехода.
Но пока двигаемся по детерминированной цепочке — получается эквивалент ДКА.
VD>Плюс ты похоже не понимаешь принципов работы GLR-ов. Они сворачивают продункции в обратную сторону
LR-разбор сворачивает цепочки в такую же сторону, в какую их сворачивает лексер.
Да, надо хранить текущую цепочку свернутых нетерминалов, т.е. "отображать" входную цепочку на "свернутую" точно так же, как лексер отображает цепочку терминалов на цепочку нетерминалов после их "сворачивания". Просто в случае лексера у нас всего один уровень такого отображения, а в случае LR-разбора кол-во уровней "сворачивания" зависит от уровня вложенности конкретного выражения во входных данных.
V>>Почитай внимательно вот это:
V>>https://ru.wikipedia.org/wiki/LR(0)
VD>Спасибо. Читай это сам.
ЧТД.
V>>Обрати внимание, что по если по каждой свертке у нас будет конечный (выходной) нетерминал, то получаем в точности автоматный лексер.
VD>Языком в основном. На практике код там будет долек от того, что можно сгенерировать для ДКА.
Ты совершенно не в курсе про технику восходящего разбора. ))
VD>Блин, клинический детский сад! Открой для себя понятие константы. Тогда узнаешь, что линейное != быстрое. Если ты на разбор символа в потоке тратишь секунду, то твой алгоритм линейный, но он никому не нужный, так как даже на 100 символов ты потратишь неприемлемо много времени. Вот именно это и происходит со всеми G.
VD>И еще задумайся на фиг нужен GLR, если грамматика полностью детерминирована?
Грамматика и так обычно в конце концов детерминированная (по крайней мере так всегда для ЯП).
Просто не всегда парсится алгоритмами навроде LR(1).
Ну и бывают задачи недетерминированного парсинга, когда каждому из вариантов присваивают вес и получивший больший вес из всех вариантов выигрывает.
VD>Не хочу. Мне время дорого. Приведи тесты GLR vs лексер и за одно дай ссылки те самые С++-парсеры, которые используют GLR для разбора С++.
Угу, как там у прапорщика, "трясти надо"?
Ты же потратил время на Эрли, хотя он хуже в разы, чем GLR?
Ты же потратил на Пакрат, хотя алгоритм сложней и константа у него больше, чем GLR?
Если ты занимаешься этой темой, то это твоя обязанность — разбираться в предмете.
Хотя бы разобраться с алгоритмом восходящего разбора как такового.
VD>Вот мы используем модифицированный Эрли для качественного восстановления после ошибок.
Эрли заведомо хуже GLR и на всех углах это написано.
Ты убил своё время.
VD>При этом числ неоднозначностей растет просто лавинообразно.
Не "лавинообразно", а зависит от длины цепочки.
У GLR в общем случае такой зависимости НЕТ.
И это — ключевое.
VD>Но по другому нельзя, так как только обобщенный алгоритм может найти все пути.
Тогда тем более.
Блин, а чего вы мне голову морочите, если у вас вообще Эрли???
V>>Поэтому, я не просто говорил про GLR, я говорил о сценариях, где он очень хорошо себя показывает.
VD>Нет таких сценариев на практике.
Из пальца насосал? ))
VD>GLR используется исключительно в научных целях. Я просто ржал читая научные статьи где на полном серьезе говорилось об восстановлении после ошибок за 10 секунд. Успехов всем кто готов ждать отклика редактора по 10 секунд.
Там где GLR восстановится за 10 секунд, там Эрли восстановится за 10 минут.
VD>1. ПЕГ — это формат грамматики. Алгоритм парсинга ПЕГ-а называется Пакрат.
Алгоримов парсинга ПЕГ более одного.
Почти все с откатами.
VD>2. Пакрат работает без откатов на любой грамматике описываемой ПЕГ-ом.
Пакрат — это крайний случай мемоизации.
В этом смысле и GLR-эдакая "мемоизация".
V>>Однако, где нисходящему алгоритму надо будет регулярно откатываться на много мегабайт назад, GRL рвет его как тузик грелку.
VD>Пипец ты берд несешь!
Я говорю аксиомы, просто ты не в курсе.
VD>Весь смысл Пакрата в том, что он безоткатный, т.е. гарантирует линейное время.
Как и Эрли. )))
VD>Вот константа у него опять же достаточно высокая. Но все же ниже чем у GRL.
Ты несешь бред.
У алгоритмов с мемоизацией тоже время НЕ линейное, потому что стоимость мемоизации тем больше, чем её больше.
А когда контсанта начинает зависеть от n, то это уже нефига не константа.
VD>Хуже с восстановлением. Но и с ним в большинстве случаев все не плохо работает.
Потому что Эрли.
VD>>>А он о константе, которая у GLR будет сушественно выше чем у ДКА.
V>>Я уже говорил, суть алгоритма LR(0) — это, грубо, лексер вызывает лексер и так рекурсивно.
VD>Пипец! Эта песня хороша, начинай сначала. Не я на тебя время тратить не буду.
А ты не на меня трать, а на своё образование.
Помнится, ты дофига потратил времени на Пакрат.
Еще помнится, что когда вам советовали Ахо и Ульмана, вы посылали точно так же нах, как ты сейчас, хотя это именно они придумали ПЕГ (TDPL изначально).
Как грится на форумах компиляторописателей:
VD>Я не знаю, что ты там за цифры давал. Но на свете нет ни одного GLR-а пригодного для промышленного использования.
Мде? А я думал, что самый ходовой генератор парсеров всех времен — это Бизон.
Который прекрасно генерить GLR.
VD>У них и с производительностью проблемы, и с восстановлением после ошибок.
Восстановление после ошибок — это специфичное требование.
VD>Если я ошибаюсь, дай ссылок.
Бизон:
https://www.gnu.org/software/bison/manual/html_node/GLR-Parsers.html
"Умный Яндекс":
https://habrahabr.ru/company/yandex/blog/219311/
V>>Т.е., когда лексер-парсер работают в паре, то лексический анализатор занимает львиную долю тиков процессора из затрат на парсинг (формирование AST — это, считай, "отдельная" нагрузка). Т.е. синтаксический анализ занимает меньшую долю тиков в совместной работе.
VD>Само наличие лексера сокращает число этих самых тактов на порядки. Парсеру приходится работать не с миллионами символов, а с тысячами или даже сотнями. Число неоднозначностей падает с тысяч, до единиц или даже нуля.
Верно. Я же говорил — трафик у парсера сильно меньше, чем у лексера.
Я писал, что подключение парсера к лексеру на моих данных давало лишь 5%-10% проседания производительности, т.е. парсер+лексер работают примерно так же, как один лексер.
VD>Слушай читать твои фантазии у меня никакого желания нет.
Читать мало, надо понимать.
Итого, лексер производит сдвиг (в терминах LR) по цепочке символов, потом сворачивает (в терминах LR) эту цепочку терминалов в один нетерминал и подаёт "наверх" в виде кода нетерминала. Так трафик-то нетерминалов получается меньше?
А теперь на более высоком уровне опять происходит сдвиг по накопленной цепочке нетерминалов и опять сворачивание цепочки нетерминало в один нетерминал — и опять получается трафик в разы меньший для еще более вышестоящего уровня, верно?
Итого, чем глубже вложенность выражения (скажем, при парсинге некоего ЯП), тем меньше трафик нетерминалов самого высокого уровня? Т.е., получается, что от глубины вложенности выражений скорость LR-парсинга практически не зависит, верно?
А вот для парсера с откатами в случае недостаточности просмотра на 1, глубокая вложенность выражений может стать больным местом. Не зря расширения Пакрата и ALL используют мемоизацию и прочие трюки.
VD>Но сам лексер работает просто на порядки быстрее.
ЗА СЧЕТ ЧЕГО?
VD>"Отлексить" с помощью качественного компилированного кода основанного на ДКА даже десятимегабайтный файл — это денницы миллисекунд. А вот парсинг того же самого — это совсем другой расклад.
Ну скорми LR(0)-парсеру грамматику от лексера (почему бы и нет?) и проверь.
Ну будет у тебя стек разбора с фиксированной глубиной 1, и?
Алгоритм же тот же...
V>>Потому что трафик символов разный, ес-но.
VD>Ты говоришь полную чушь! Трафик ничто по сравнению с вычислительными затратами.
Лексер тоже выполняет сдвиг и свертку, напомню.
Сделай эти операции такими же дешевыми, как в лексере.
Просто я часто видел, как хранят стек разбора LR-парсера в виде linked list. Но? если ты для лексера будет представлять входные терминалы как linked list, то вычислительные затраты лексера тоже станут ого. ))
VD>А главное, что GLR (ну, если это реально GLR, а не что нибудь) являются безлексерными и разбирают отдельные символы далекими от эффективности алгоритмами.
Вот это чушь как она есть.
Самой граматике глубоко до фени как она получена, т.е. является ли исходной или же является результатом декомпозиции грамматик, когда регулярную часть выделили в отдельный парсер, который назвали лексером.
А что мешает, кстате, произвести подобную декомпозицию более одного раза?
V>>Только на неоднозначностях.
VD>Хрен там. У них и константа во много раз выше. Не может быть обобщенный алгоритм столь же эффективным, как специализированный.
Может на единственной ветке разбора.
VD>Вот ДКА ты хрен когда догонишь. Хот ты лопни.
LR(0) и LR(1) — это и есть ДКА, принцип работы которых близок к ДКА лексера.
А GLR парсит по НКА, вот и вся разница. Т.е. от каждой ячейки по данному символу может быть более одного перехода.
Но пока двигаемся по детерминированной цепочке — получается эквивалент ДКА.
VD>Плюс ты похоже не понимаешь принципов работы GLR-ов. Они сворачивают продункции в обратную сторону
LR-разбор сворачивает цепочки в такую же сторону, в какую их сворачивает лексер.
Да, надо хранить текущую цепочку свернутых нетерминалов, т.е. "отображать" входную цепочку на "свернутую" точно так же, как лексер отображает цепочку терминалов на цепочку нетерминалов после их "сворачивания". Просто в случае лексера у нас всего один уровень такого отображения, а в случае LR-разбора кол-во уровней "сворачивания" зависит от уровня вложенности конкретного выражения во входных данных.
V>>Почитай внимательно вот это:
V>>https://ru.wikipedia.org/wiki/LR(0)
VD>Спасибо. Читай это сам.
ЧТД.
V>>Обрати внимание, что по если по каждой свертке у нас будет конечный (выходной) нетерминал, то получаем в точности автоматный лексер.
VD>Языком в основном. На практике код там будет долек от того, что можно сгенерировать для ДКА.
Ты совершенно не в курсе про технику восходящего разбора. ))
VD>Блин, клинический детский сад! Открой для себя понятие константы. Тогда узнаешь, что линейное != быстрое. Если ты на разбор символа в потоке тратишь секунду, то твой алгоритм линейный, но он никому не нужный, так как даже на 100 символов ты потратишь неприемлемо много времени. Вот именно это и происходит со всеми G.
VD>И еще задумайся на фиг нужен GLR, если грамматика полностью детерминирована?
Грамматика и так обычно в конце концов детерминированная (по крайней мере так всегда для ЯП).
Просто не всегда парсится алгоритмами навроде LR(1).
Ну и бывают задачи недетерминированного парсинга, когда каждому из вариантов присваивают вес и получивший больший вес из всех вариантов выигрывает.
VD>Не хочу. Мне время дорого. Приведи тесты GLR vs лексер и за одно дай ссылки те самые С++-парсеры, которые используют GLR для разбора С++.
Угу, как там у прапорщика, "трясти надо"?
Ты же потратил время на Эрли, хотя он хуже в разы, чем GLR?
Ты же потратил на Пакрат, хотя алгоритм сложней и константа у него больше, чем GLR?
Если ты занимаешься этой темой, то это твоя обязанность — разбираться в предмете.
Хотя бы разобраться с алгоритмом восходящего разбора как такового.
VD>Вот мы используем модифицированный Эрли для качественного восстановления после ошибок.
Эрли заведомо хуже GLR и на всех углах это написано.
Ты убил своё время.
VD>При этом числ неоднозначностей растет просто лавинообразно.
Не "лавинообразно", а зависит от длины цепочки.
У GLR в общем случае такой зависимости НЕТ.
И это — ключевое.
VD>Но по другому нельзя, так как только обобщенный алгоритм может найти все пути.
Тогда тем более.
Блин, а чего вы мне голову морочите, если у вас вообще Эрли???
V>>Поэтому, я не просто говорил про GLR, я говорил о сценариях, где он очень хорошо себя показывает.
VD>Нет таких сценариев на практике.
Из пальца насосал? ))
VD>GLR используется исключительно в научных целях. Я просто ржал читая научные статьи где на полном серьезе говорилось об восстановлении после ошибок за 10 секунд. Успехов всем кто готов ждать отклика редактора по 10 секунд.
Там где GLR восстановится за 10 секунд, там Эрли восстановится за 10 минут.
VD>1. ПЕГ — это формат грамматики. Алгоритм парсинга ПЕГ-а называется Пакрат.
Алгоримов парсинга ПЕГ более одного.
Почти все с откатами.
VD>2. Пакрат работает без откатов на любой грамматике описываемой ПЕГ-ом.
Пакрат — это крайний случай мемоизации.
В этом смысле и GLR-эдакая "мемоизация".
V>>Однако, где нисходящему алгоритму надо будет регулярно откатываться на много мегабайт назад, GRL рвет его как тузик грелку.
VD>Пипец ты берд несешь!
Я говорю аксиомы, просто ты не в курсе.
VD>Весь смысл Пакрата в том, что он безоткатный, т.е. гарантирует линейное время.
Как и Эрли. )))
VD>Вот константа у него опять же достаточно высокая. Но все же ниже чем у GRL.
Ты несешь бред.
У алгоритмов с мемоизацией тоже время НЕ линейное, потому что стоимость мемоизации тем больше, чем её больше.
А когда контсанта начинает зависеть от n, то это уже нефига не константа.
VD>Хуже с восстановлением. Но и с ним в большинстве случаев все не плохо работает.
Потому что Эрли.
VD>>>А он о константе, которая у GLR будет сушественно выше чем у ДКА.
V>>Я уже говорил, суть алгоритма LR(0) — это, грубо, лексер вызывает лексер и так рекурсивно.
VD>Пипец! Эта песня хороша, начинай сначала. Не я на тебя время тратить не буду.
А ты не на меня трать, а на своё образование.
Помнится, ты дофига потратил времени на Пакрат.
Еще помнится, что когда вам советовали Ахо и Ульмана, вы посылали точно так же нах, как ты сейчас, хотя это именно они придумали ПЕГ (TDPL изначально).
Как грится на форумах компиляторописателей:
В точку.PEG — удел неосиляторов LR/GLR парсеров.
Re[11]: Опциональные типы
Здравствуйте, VladD2, Вы писали:
VD>Я не знаю, что ты там за цифры давал. Но на свете нет ни одного GLR-а пригодного для промышленного использования.
Мде? А я думал, что самый ходовой генератор парсеров всех времен — это Бизон.
Который прекрасно генерить GLR.
VD>У них и с производительностью проблемы, и с восстановлением после ошибок.
Восстановление после ошибок — это специфичное требование.
VD>Если я ошибаюсь, дай ссылок.
Бизон:
https://www.gnu.org/software/bison/manual/html_node/GLR-Parsers.html
"Умный Яндекс":
https://habrahabr.ru/company/yandex/blog/219311/
V>>Т.е., когда лексер-парсер работают в паре, то лексический анализатор занимает львиную долю тиков процессора из затрат на парсинг (формирование AST — это, считай, "отдельная" нагрузка). Т.е. синтаксический анализ занимает меньшую долю тиков в совместной работе.
VD>Само наличие лексера сокращает число этих самых тактов на порядки. Парсеру приходится работать не с миллионами символов, а с тысячами или даже сотнями. Число неоднозначностей падает с тысяч, до единиц или даже нуля.
Верно. Я же говорил — трафик у парсера сильно меньше, чем у лексера.
Я писал, что подключение парсера к лексеру на моих данных давало лишь 5%-10% проседания производительности, т.е. парсер+лексер работают примерно так же, как один лексер.
VD>Слушай читать твои фантазии у меня никакого желания нет.
Читать мало, надо понимать.
Итого, лексер производит сдвиг (в терминах LR) по цепочке символов, потом сворачивает (в терминах LR) эту цепочку терминалов в один нетерминал и подаёт "наверх" в виде кода нетерминала. Так трафик-то нетерминалов получается меньше?
А теперь на более высоком уровне опять происходит сдвиг по накопленной цепочке нетерминалов и опять сворачивание цепочки нетерминало в один нетерминал — и опять получается трафик в разы меньший для еще более вышестоящего уровня, верно?
Итого, чем глубже вложенность выражения (скажем, при парсинге некоего ЯП), тем меньше трафик нетерминалов самого высокого уровня? Т.е., получается, что от глубины вложенности выражений скорость LR-парсинга практически не зависит, верно?
А вот для парсера с откатами в случае недостаточности просмотра на 1, глубокая вложенность выражений может стать больным местом. Не зря расширения Пакрата и ALL используют мемоизацию и прочие трюки.
VD>Но сам лексер работает просто на порядки быстрее.
ЗА СЧЕТ ЧЕГО?
VD>"Отлексить" с помощью качественного компилированного кода основанного на ДКА даже десятимегабайтный файл — это денницы миллисекунд. А вот парсинг того же самого — это совсем другой расклад.
Ну скорми LR(0)-парсеру грамматику от лексера (почему бы и нет?) и проверь.
Ну будет у тебя стек разбора с фиксированной глубиной 1, и?
Алгоритм же тот же...
V>>Потому что трафик символов разный, ес-но.
VD>Ты говоришь полную чушь! Трафик ничто по сравнению с вычислительными затратами.
Лексер тоже выполняет сдвиг и свертку, напомню.
Сделай эти операции такими же дешевыми, как в лексере.
Просто я часто видел, как хранят стек разбора LR-парсера в виде linked list. Но? если ты для лексера будет представлять входные терминалы как linked list, то вычислительные затраты лексера тоже станут ого. ))
VD>А главное, что GLR (ну, если это реально GLR, а не что нибудь) являются безлексерными и разбирают отдельные символы далекими от эффективности алгоритмами.
Вот это чушь как она есть.
Самой граматике глубоко до фени как она получена, т.е. является ли исходной или же является результатом декомпозиции грамматик, когда регулярную часть выделили в отдельный парсер, который назвали лексером.
А что мешает, кстате, произвести подобную декомпозицию более одного раза?
V>>Только на неоднозначностях.
VD>Хрен там. У них и константа во много раз выше. Не может быть обобщенный алгоритм столь же эффективным, как специализированный.
Может на единственной ветке разбора.
VD>Вот ДКА ты хрен когда догонишь. Хот ты лопни.
LR(0) и LR(1) — это и есть ДКА, принцип работы которых близок к ДКА лексера.
А GLR парсит по НКА, вот и вся разница. Т.е. от каждой ячейки по данному символу может быть более одного перехода.
Но пока двигаемся по детерминированной цепочке — получается эквивалент ДКА.
VD>Плюс ты похоже не понимаешь принципов работы GLR-ов. Они сворачивают продункции в обратную сторону
LR-разбор сворачивает цепочки в такую же сторону, в какую их сворачивает лексер.
Да, надо хранить текущую цепочку свернутых нетерминалов, т.е. "отображать" входную цепочку на "свернутую" точно так же, как лексер отображает цепочку терминалов на цепочку нетерминалов после их "сворачивания". Просто в случае лексера у нас всего один уровень такого отображения, а в случае LR-разбора кол-во уровней "сворачивания" зависит от уровня вложенности конкретного выражения во входных данных.
V>>Почитай внимательно вот это:
V>>https://ru.wikipedia.org/wiki/LR(0)
VD>Спасибо. Читай это сам.
ЧТД.
V>>Обрати внимание, что по если по каждой свертке у нас будет конечный (выходной) нетерминал, то получаем в точности автоматный лексер.
VD>Языком в основном. На практике код там будет долек от того, что можно сгенерировать для ДКА.
Ты совершенно не в курсе про технику восходящего разбора. ))
VD>Блин, клинический детский сад! Открой для себя понятие константы. Тогда узнаешь, что линейное != быстрое. Если ты на разбор символа в потоке тратишь секунду, то твой алгоритм линейный, но он никому не нужный, так как даже на 100 символов ты потратишь неприемлемо много времени. Вот именно это и происходит со всеми G.
VD>И еще задумайся на фиг нужен GLR, если грамматика полностью детерминирована?
Грамматика и так обычно в конце концов детерминированная (по крайней мере так всегда для ЯП).
Просто не всегда парсится алгоритмами навроде LR(1).
Ну и бывают задачи недетерминированного парсинга, когда каждому из вариантов присваивают вес и получивший больший вес из всех вариантов выигрывает.
VD>Не хочу. Мне время дорого. Приведи тесты GLR vs лексер и за одно дай ссылки те самые С++-парсеры, которые используют GLR для разбора С++.
Угу, как там у прапорщика, "трясти надо"?
Ты же потратил время на Эрли, хотя он хуже в разы, чем GLR?
Ты же потратил на Пакрат, хотя алгоритм сложней и константа у него больше, чем GLR?
Если ты занимаешься этой темой, то это твоя обязанность — разбираться в предмете.
Хотя бы разобраться с алгоритмом восходящего разбора как такового.
VD>Вот мы используем модифицированный Эрли для качественного восстановления после ошибок.
Эрли заведомо хуже GLR и на всех углах это написано.
Ты убил своё время.
VD>При этом числ неоднозначностей растет просто лавинообразно.
Не "лавинообразно", а зависит от длины цепочки.
У GLR в общем случае такой зависимости НЕТ.
И это — ключевое для цепочек в мегабайты длинной, когда неоднозначность цепочки ресолвится в самом её конце.
VD>Но по другому нельзя, так как только обобщенный алгоритм может найти все пути.
Тогда тем более.
Блин, а чего вы мне голову морочите, если у вас вообще Эрли??? ))
Уже надо были сидеть тише воды и не отсвечивать.
Небось взяли вот ту реализацию, которую разбирали когда-то на RSDN.
Кстате, я брал именно твой порт на .Net и с пол-тыка ускорил его втрое.
И всё-равно оно тормозит безбожно...
V>>Поэтому, я не просто говорил про GLR, я говорил о сценариях, где он очень хорошо себя показывает.
VD>Нет таких сценариев на практике.
У нас разные практики.
VD>GLR используется исключительно в научных целях. Я просто ржал читая научные статьи где на полном серьезе говорилось об восстановлении после ошибок за 10 секунд. Успехов всем кто готов ждать отклика редактора по 10 секунд.
Плохо ты читал.
Там где GLR восстановится за 10 секунд, там Эрли восстановится за 10 минут.
VD>1. ПЕГ — это формат грамматики. Алгоритм парсинга ПЕГ-а называется Пакрат.
Алгоримов парсинга ПЕГ более одного.
Почти все с откатами.
VD>2. Пакрат работает без откатов на любой грамматике описываемой ПЕГ-ом.
Пакрат — это крайний случай мемоизации.
В этом смысле и GLR-эдакая "мемоизация".
И что самое ужасное — что мемоизация в Пакрате строится всегда, но может не понадобиться. ))
V>>Однако, где нисходящему алгоритму надо будет регулярно откатываться на много мегабайт назад, GRL рвет его как тузик грелку.
VD>Пипец ты берд несешь!
Я говорю аксиомы.
VD>Весь смысл Пакрата в том, что он безоткатный, т.е. гарантирует линейное время.
Как Эрли?
VD>Вот константа у него опять же достаточно высокая. Но все же ниже чем у GRL.
Ты несешь бред.
У алгоритмов с мемоизацией тоже время НЕ линейное, потому что стоимость мемоизации тем больше, чем её больше.
Мемоизация НЕ бесплатна.
А когда твоя "константа" начинает зависеть от n, то это уже нифига не константа.
VD>Хуже с восстановлением. Но и с ним в большинстве случаев все не плохо работает.
Потому что Эрли.
Потому что обобщенный алгоритм ест фсё.
VD>>>А он о константе, которая у GLR будет сушественно выше чем у ДКА.
V>>Я уже говорил, суть алгоритма LR(0) — это, грубо, лексер вызывает лексер и так рекурсивно.
VD>Пипец! Эта песня хороша, начинай сначала. Не я на тебя время тратить не буду.
А ты не на меня трать, а на себя.
Помнится, ты дофига потратил времени на Пакрат?
Еще помнится, что когда вам советовали Ахо и Ульмана, вы посылали точно так же нах и даже еще более эмоционально (моложе были, понятно), хотя это именно они придумали ПЕГ (TDPL изначально) как способ избежать неоднозначности описания грамматик.
Как грится на форумах компиляторописателей:
VD>Я не знаю, что ты там за цифры давал. Но на свете нет ни одного GLR-а пригодного для промышленного использования.
Мде? А я думал, что самый ходовой генератор парсеров всех времен — это Бизон.
Который прекрасно генерить GLR.
VD>У них и с производительностью проблемы, и с восстановлением после ошибок.
Восстановление после ошибок — это специфичное требование.
VD>Если я ошибаюсь, дай ссылок.
Бизон:
https://www.gnu.org/software/bison/manual/html_node/GLR-Parsers.html
"Умный Яндекс":
https://habrahabr.ru/company/yandex/blog/219311/
V>>Т.е., когда лексер-парсер работают в паре, то лексический анализатор занимает львиную долю тиков процессора из затрат на парсинг (формирование AST — это, считай, "отдельная" нагрузка). Т.е. синтаксический анализ занимает меньшую долю тиков в совместной работе.
VD>Само наличие лексера сокращает число этих самых тактов на порядки. Парсеру приходится работать не с миллионами символов, а с тысячами или даже сотнями. Число неоднозначностей падает с тысяч, до единиц или даже нуля.
Верно. Я же говорил — трафик у парсера сильно меньше, чем у лексера.
Я писал, что подключение парсера к лексеру на моих данных давало лишь 5%-10% проседания производительности, т.е. парсер+лексер работают примерно так же, как один лексер.
VD>Слушай читать твои фантазии у меня никакого желания нет.
Читать мало, надо понимать.
Итого, лексер производит сдвиг (в терминах LR) по цепочке символов, потом сворачивает (в терминах LR) эту цепочку терминалов в один нетерминал и подаёт "наверх" в виде кода нетерминала. Так трафик-то нетерминалов получается меньше?
А теперь на более высоком уровне опять происходит сдвиг по накопленной цепочке нетерминалов и опять сворачивание цепочки нетерминало в один нетерминал — и опять получается трафик в разы меньший для еще более вышестоящего уровня, верно?
Итого, чем глубже вложенность выражения (скажем, при парсинге некоего ЯП), тем меньше трафик нетерминалов самого высокого уровня? Т.е., получается, что от глубины вложенности выражений скорость LR-парсинга практически не зависит, верно?
А вот для парсера с откатами в случае недостаточности просмотра на 1, глубокая вложенность выражений может стать больным местом. Не зря расширения Пакрата и ALL используют мемоизацию и прочие трюки.
VD>Но сам лексер работает просто на порядки быстрее.
ЗА СЧЕТ ЧЕГО?
VD>"Отлексить" с помощью качественного компилированного кода основанного на ДКА даже десятимегабайтный файл — это денницы миллисекунд. А вот парсинг того же самого — это совсем другой расклад.
Ну скорми LR(0)-парсеру грамматику от лексера (почему бы и нет?) и проверь.
Ну будет у тебя стек разбора с фиксированной глубиной 1, и?
Алгоритм же тот же...
V>>Потому что трафик символов разный, ес-но.
VD>Ты говоришь полную чушь! Трафик ничто по сравнению с вычислительными затратами.
Лексер тоже выполняет сдвиг и свертку, напомню.
Сделай эти операции такими же дешевыми, как в лексере.
Просто я часто видел, как хранят стек разбора LR-парсера в виде linked list. Но? если ты для лексера будет представлять входные терминалы как linked list, то вычислительные затраты лексера тоже станут ого. ))
VD>А главное, что GLR (ну, если это реально GLR, а не что нибудь) являются безлексерными и разбирают отдельные символы далекими от эффективности алгоритмами.
Вот это чушь как она есть.
Самой граматике глубоко до фени как она получена, т.е. является ли исходной или же является результатом декомпозиции грамматик, когда регулярную часть выделили в отдельный парсер, который назвали лексером.
А что мешает, кстате, произвести подобную декомпозицию более одного раза?
V>>Только на неоднозначностях.
VD>Хрен там. У них и константа во много раз выше. Не может быть обобщенный алгоритм столь же эффективным, как специализированный.
Может на единственной ветке разбора.
VD>Вот ДКА ты хрен когда догонишь. Хот ты лопни.
LR(0) и LR(1) — это и есть ДКА, принцип работы которых близок к ДКА лексера.
А GLR парсит по НКА, вот и вся разница. Т.е. от каждой ячейки по данному символу может быть более одного перехода.
Но пока двигаемся по детерминированной цепочке — получается эквивалент ДКА.
VD>Плюс ты похоже не понимаешь принципов работы GLR-ов. Они сворачивают продункции в обратную сторону
LR-разбор сворачивает цепочки в такую же сторону, в какую их сворачивает лексер.
Да, надо хранить текущую цепочку свернутых нетерминалов, т.е. "отображать" входную цепочку на "свернутую" точно так же, как лексер отображает цепочку терминалов на цепочку нетерминалов после их "сворачивания". Просто в случае лексера у нас всего один уровень такого отображения, а в случае LR-разбора кол-во уровней "сворачивания" зависит от уровня вложенности конкретного выражения во входных данных.
V>>Почитай внимательно вот это:
V>>https://ru.wikipedia.org/wiki/LR(0)
VD>Спасибо. Читай это сам.
ЧТД.
V>>Обрати внимание, что по если по каждой свертке у нас будет конечный (выходной) нетерминал, то получаем в точности автоматный лексер.
VD>Языком в основном. На практике код там будет долек от того, что можно сгенерировать для ДКА.
Ты совершенно не в курсе про технику восходящего разбора. ))
VD>Блин, клинический детский сад! Открой для себя понятие константы. Тогда узнаешь, что линейное != быстрое. Если ты на разбор символа в потоке тратишь секунду, то твой алгоритм линейный, но он никому не нужный, так как даже на 100 символов ты потратишь неприемлемо много времени. Вот именно это и происходит со всеми G.
VD>И еще задумайся на фиг нужен GLR, если грамматика полностью детерминирована?
Грамматика и так обычно в конце концов детерминированная (по крайней мере так всегда для ЯП).
Просто не всегда парсится алгоритмами навроде LR(1).
Ну и бывают задачи недетерминированного парсинга, когда каждому из вариантов присваивают вес и получивший больший вес из всех вариантов выигрывает.
VD>Не хочу. Мне время дорого. Приведи тесты GLR vs лексер и за одно дай ссылки те самые С++-парсеры, которые используют GLR для разбора С++.
Угу, как там у прапорщика, "трясти надо"?
Ты же потратил время на Эрли, хотя он хуже в разы, чем GLR?
Ты же потратил на Пакрат, хотя алгоритм сложней и константа у него больше, чем GLR?
Если ты занимаешься этой темой, то это твоя обязанность — разбираться в предмете.
Хотя бы разобраться с алгоритмом восходящего разбора как такового.
VD>Вот мы используем модифицированный Эрли для качественного восстановления после ошибок.
Эрли заведомо хуже GLR и на всех углах это написано.
Ты убил своё время.
VD>При этом числ неоднозначностей растет просто лавинообразно.
Не "лавинообразно", а зависит от длины цепочки.
У GLR в общем случае такой зависимости НЕТ.
И это — ключевое для цепочек в мегабайты длинной, когда неоднозначность цепочки ресолвится в самом её конце.
VD>Но по другому нельзя, так как только обобщенный алгоритм может найти все пути.
Тогда тем более.
Блин, а чего вы мне голову морочите, если у вас вообще Эрли??? ))
Уже надо были сидеть тише воды и не отсвечивать.
Небось взяли вот ту реализацию, которую разбирали когда-то на RSDN.
Кстате, я брал именно твой порт на .Net и с пол-тыка ускорил его втрое.
И всё-равно оно тормозит безбожно...
V>>Поэтому, я не просто говорил про GLR, я говорил о сценариях, где он очень хорошо себя показывает.
VD>Нет таких сценариев на практике.
У нас разные практики.
VD>GLR используется исключительно в научных целях. Я просто ржал читая научные статьи где на полном серьезе говорилось об восстановлении после ошибок за 10 секунд. Успехов всем кто готов ждать отклика редактора по 10 секунд.
Плохо ты читал.
Там где GLR восстановится за 10 секунд, там Эрли восстановится за 10 минут.
VD>1. ПЕГ — это формат грамматики. Алгоритм парсинга ПЕГ-а называется Пакрат.
Алгоримов парсинга ПЕГ более одного.
Почти все с откатами.
VD>2. Пакрат работает без откатов на любой грамматике описываемой ПЕГ-ом.
Пакрат — это крайний случай мемоизации.
В этом смысле и GLR-эдакая "мемоизация".
И что самое ужасное — что мемоизация в Пакрате строится всегда, но может не понадобиться. ))
V>>Однако, где нисходящему алгоритму надо будет регулярно откатываться на много мегабайт назад, GRL рвет его как тузик грелку.
VD>Пипец ты берд несешь!
Я говорю аксиомы.
VD>Весь смысл Пакрата в том, что он безоткатный, т.е. гарантирует линейное время.
Как Эрли?
VD>Вот константа у него опять же достаточно высокая. Но все же ниже чем у GRL.
Ты несешь бред.
У алгоритмов с мемоизацией тоже время НЕ линейное, потому что стоимость мемоизации тем больше, чем её больше.
Мемоизация НЕ бесплатна.
А когда твоя "константа" начинает зависеть от n, то это уже нифига не константа.
VD>Хуже с восстановлением. Но и с ним в большинстве случаев все не плохо работает.
Потому что Эрли.
Потому что обобщенный алгоритм ест фсё.
VD>>>А он о константе, которая у GLR будет сушественно выше чем у ДКА.
V>>Я уже говорил, суть алгоритма LR(0) — это, грубо, лексер вызывает лексер и так рекурсивно.
VD>Пипец! Эта песня хороша, начинай сначала. Не я на тебя время тратить не буду.
А ты не на меня трать, а на себя.
Помнится, ты дофига потратил времени на Пакрат?
Еще помнится, что когда вам советовали Ахо и Ульмана, вы посылали точно так же нах и даже еще более эмоционально (моложе были, понятно), хотя это именно они придумали ПЕГ (TDPL изначально) как способ избежать неоднозначности описания грамматик.
Ы-Ы-Ы много раз...A more formal approach to backtracking is represented by Aho and Ullman’s TDPL language (recently repopularised as Parsing Expression Grammars and their associated memoized Packrat parsers).
... but, of course, PEG’s are not context-free grammars, and as Aho and Ullman said:
“it can be quite difficult to determine what language is defined by a TDPL program.”
The current interest in PEG’s is another manifestation of users’ need for parsers which are human readable.
Как грится на форумах компиляторописателей:
PEG — удел неосиляторов LR/GLR парсеров.