K
А лексер из регулярок никто делать не заставляет!
Пакрат он как бы O(N)
Пакрат он как бы O(N)
Size: a a a
2021 May 24
DP
Не заставляет, это просто пример. Ускоряемся за счет опрощения, обеднения.
DP
Коэффициент у пакрата большой, конечно, но количество работы на один входной символ/токен ограничего константой (числом правил), так что формально O(N).
DP
Насчет LL(inf), кстати. Тот самый оператор, что монадные парсер комбинаторы делает монадными, дает возможность выбирать поведение динамически в зависимости от того, что недавно (или давно) распарсили. Т.е. это контекстно-зависимая уже? Есть ли формальная разница между контекстно-зависимой грамматикой и LL(inf)?
DP
(if LL(inf) is a thing at all)
K
Есть, это джве разные категории по Хомскому
K
Долгих ему лет
DP
Эти разные категории и их различение мне никогда полностью не давались, выглядели каким-то дуриловом. Когда класс языков (множеств строк) притягивают к особенностям реализации конкретного алгоритма парсинга... Экстенсиональное определение вместо интенсионального.
K
0) регулярки - *, +, ?, нет рекурсии
1) контекстно-свободные грамматики, их сабсет без конфликтов парсит LR - (0) + рекурсия
2) контекстно-зависимые - это когда можно не по одному нетерминалы заменять, а
3) неограниченные грамматики - всё остальное
1) контекстно-свободные грамматики, их сабсет без конфликтов парсит LR - (0) + рекурсия
2) контекстно-зависимые - это когда можно не по одному нетерминалы заменять, а
AB -> CD, это уже лента Тьюринга3) неограниченные грамматики - всё остальное
K
DP
Ну вот "без конфликтов" это прихоть конкретного алгоритма, что именно он считает конфликтом. Добавляем приоритеты или последовательный выбор, конфликт снимается. Это уже другой класс или еще нет?
K
А, вру - машина Тьюринга это уже неограниченные
DP
Просто такая классификация выглядит как "ну я знаю такие три парсера, вот будет вам такие три класса".
K
Не-а. Если LR нашёл конфликт, он будет конфликтом при любых эквивалентных трансформациях, и без дополнительных средств его не разрешить.
KT
привет
а посоветуйте, пожалуйста, что классическое обзорное/короткое почитать про то как правильно писать dataflow/controlflow анализаторы? Без каких-то супер кишок, чтобы можно было за несколько вечеров прочитать
а посоветуйте, пожалуйста, что классическое обзорное/короткое почитать про то как правильно писать dataflow/controlflow анализаторы? Без каких-то супер кишок, чтобы можно было за несколько вечеров прочитать
DP
А что такое "без дополнительных средств"? Кто мешает последовательный выбор использовать, как в PEG?
K
Дополнительные средства - это left-biased choice, которые выводят нас из формализма Хомского
K
И приоритеты, которые то же самое, только ручек настройки больше
DP
Ну вот, шаг в сторону, и классификация разваливается
K
Ну, да. Но, классификация Хомского не только про парсеры, но ещё и про генерацию. LR можно заставть порождать тексты на языке по грамматике. Не знаю, кому это может быть нужно, правда.