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

V>>>Это всё еще регулярная грамматика по Холмскому.
V>>>(это что-то "синтаксического сахара" описания грамматики)
N>>А не начинает зависеть от сложности выражений? Я этот момент уже плохо помню, но, кажется, сложность начинает "перемножаться" на каждый такой терм.

V>Не принципиально, т.к. размер таблицы переходов (если парсер табличный), зависит от кол-ва состояний, а не от кол-ва дуг (переходов).

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

Я вот к чему. Представь себе выражение типа ^X(?!.*zuka$)[a-z]+$
(Не будем обсуждать психические свойства автора, он просто сэкономил на мышлении.)
Но итоговая машина состояний должна одновременно сочетать два поиска — по нужным символам и по недопустимой комбинации. Значит, у нас получится u-простое и u-после-z, a-простое и a-после-zuk...
теперь усложним заменой zuka на (zuka){3,30}buka ... таблица всё ещё конечна, но состояний до чёрта.
Кто выдержит составление такой таблицы, и на каком количестве состояний генератор решит "а не пошло бы оно к бениной бабушке"?

Или я не вижу тут ещё какого-то фокуса?

V>>>Не нашлось рядом никого с профильным образованием?
N>>Как профильное образование мешает наличию packrat в PEG?

V>Ну, наколенный детерминированный LL(1) не сложнее.
V>Или можно взять бизоны для LR(x)/GLR-граматик или ANTLR для LL(1).

V>Просто есть же стандартные бока с левосторонней рекурсией для нисходящих парсеров, что там с этим у packrat?

Фиг его знает как у packrat в принципе, но например последний мной виденный PEG с packrat — TatSu — явно пишет в доке, что умеет её раскручивать. Я это не пробовал, не дошли до такой глубины.

А вообще в PEG это принципиально решается элементом типа e* — вики его явно перечисляет в базовых конструктах, что даёт варианты типа

addsub :== muldiv (("+"/"-") muldiv)*

то есть ты типа сам должен перевести рекурсию в цикл, но при этом сложность внутрициклового выражения не ограничивается (теоретически).

V>ANTLR сам производит факторизацию грамматики для удаления левосторонней рекурсии, в этом его главная киллер-фича, как по мне.

И у него явно описаны ограничения возможности этой его логики. Я бы в сложных случаях на это не залагался.

V>Т.е. можно продолжать описывать правила в "человеческом виде", а далее "машина разберется".
V>И что характерно — если не разберется, то сообщит об этом еще на этапе построения парсера.
V>А наколенный нисходящий парсер может однажды уйти в stack overflow на машине клиента. ))

В наколенном нисходящем... ну если его автор не протестировал, то ССЗБ, но таки делается такой же перевод в цикл, как в базовом PEG.