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

N>Но итоговая машина состояний должна одновременно сочетать два поиска — по нужным символам и по недопустимой комбинации.

Сначала строится НКА


N>Кто выдержит составление такой таблицы, и на каком количестве состояний генератор решит "а не пошло бы оно к бениной бабушке"?

Потом НКА приводится к ДКА.
Если такое приведение невозможно, то имеем конфликты.
Если никаких ср-в разрешения конфликтов нет, то ошибка.

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


N>Кто выдержит составление такой таблицы
N>Или я не вижу тут ещё какого-то фокуса?

Для юникода тут, действительно, слишком дофига дуг, поэтому еще с далеких первых экспериментов с парсерами на C# (там же юникод сплошной) я проводил минимизацию по терминалам в два этапа (а не в один этап, как по классике).

По классике все нетерминалы после минимизации ДКА разбиваются на группы, по которым происходят идентичные переходы (например, зачастую по символам 0..9).

А с юникодом пришёл к тому, что такую минимизацию имеет смысл выполнять еще на этапе составления НКА, т.е. все 64к символов схлопываются в небольшой алфавит (обычно единицы-десятки символов).

Потом опять в конце минимизация по терминалам и выведение в кодогенераторе конечной lookup-таблицы из этих двух.


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

Сам я и обычную грамматику смогу подвергнуть факторизации, но хочется этого не делать, бо левосторонне-рекурсивная запись выражений наиболее читабельна человеку (ИМХО).


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

В любом случае конфликты будут обнаружены еще в процессе работы над грамматикой.


V>>А наколенный нисходящий парсер может однажды уйти в stack overflow на машине клиента. ))
N>В наколенном нисходящем... ну если его автор не протестировал

Я уже говорил — это аналогично рассуждениям о статической типизации vs динамической.
Нужного теста разработчик может быть не сможет изобрести.
А потом в продакшене классический shit happens.

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

N>Но итоговая машина состояний должна одновременно сочетать два поиска — по нужным символам и по недопустимой комбинации.

Сначала строится НКА


N>Кто выдержит составление такой таблицы, и на каком количестве состояний генератор решит "а не пошло бы оно к бениной бабушке"?

Потом НКА приводится к ДКА.
Если такое приведение невозможно, то имеем конфликты.
Если никаких ср-в разрешения конфликтов нет, то ошибка.

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


N>Кто выдержит составление такой таблицы
N>Или я не вижу тут ещё какого-то фокуса?

Для юникода тут, действительно, слишком дофига дуг, поэтому еще с далеких первых экспериментов с парсерами на C# (там же юникод сплошной) я проводил минимизацию по терминалам в два этапа (а не в один этап, как по классике).

По классике все терминалы после минимизации ДКА разбиваются на группы, по которым происходят идентичные переходы (например, зачастую по символам 0..9).

А с юникодом пришёл к тому, что такую минимизацию имеет смысл выполнять еще на этапе составления НКА, т.е. все 64к символов схлопываются в небольшой алфавит (обычно единицы-десятки символов).

Потом опять в конце минимизация по терминалам и выведение в кодогенераторе конечной lookup-таблицы из этих двух.


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

Сам я и обычную грамматику смогу подвергнуть факторизации, но хочется этого не делать, бо левосторонне-рекурсивная запись выражений наиболее читабельна человеку (ИМХО).


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

В любом случае конфликты будут обнаружены еще в процессе работы над грамматикой.


V>>А наколенный нисходящий парсер может однажды уйти в stack overflow на машине клиента. ))
N>В наколенном нисходящем... ну если его автор не протестировал

Я уже говорил — это аналогично рассуждениям о статической типизации vs динамической.
Нужного теста разработчик может быть не сможет изобрести.
А потом в продакшене классический shit happens.