Здравствуйте, vdimas, Вы писали:
V>А зачем знать? V>На одной строке один оператор языка или ошибка трансляции.
Оператор-то один. Только надо далеко продвинуться, чтобы понять, это оператор присваивания или цикла
Pzz>>Насколько я понимаю, синтаксис Фортрана вообще нельзя описать контекстно-свободной грамматикой.
V> V>Синтаксис каждой отдельно взятой строки того Фортрана можно описать регулярной грамматикой (по Холмскому, а не перловой).
Уже даже просто выражения со скобками не описываются регулярной грамматикой.
Здравствуйте, Pzz, Вы писали:
V>>А зачем знать? V>>На одной строке один оператор языка или ошибка трансляции. Pzz>Оператор-то один. Только надо далеко продвинуться, чтобы понять, это оператор присваивания или цикла
V>>Синтаксис каждой отдельно взятой строки того Фортрана можно описать регулярной грамматикой (по Холмскому, а не перловой). Pzz>Уже даже просто выражения со скобками не описываются регулярной грамматикой.
Поймал. ))
Я в голове прикидывал остальные операторы языка.
Здравствуйте, netch80, Вы писали:
N>Большинство движков регэкспов давно содержат фичи типа negative lookahead
Это всё еще регулярная грамматика по Холмскому.
(это что-то "синтаксического сахара" описания грамматики)
N>или ссылок типа \1.
А здесь уже зависит от.
Обратная ссылка может сделать грамматику контекстно-зависимой.
(т.е. класс контекстно-свободных, то бишь стековых грамматик пропускается, что забавно)
N>И packrat в движках вокруг меня уже типовой вариант
Не нашлось рядом никого с профильным образованием?
Здравствуйте, netch80, Вы писали:
N>По-вашему ДКА предполагает построение полной таблицы символов для лукапа, то есть 256 при восьмибитке и 64K при 16-битке?
Или таблицу подстановки до ДКА.
N>варианты всяких деревьев лукапов
Принцип устройства такой таблицы (хеш, дерево или индексный массив), а так же декомпозиция ДКА не делает грамматику нерегулярной.
Это всё относится, скорее, к оптимизации реализации.
Здравствуйте, vdimas, Вы писали:
V>Это всё еще регулярная грамматика по Холмскому. V>(это что-то "синтаксического сахара" описания грамматики)
А не начинает зависеть от сложности выражений? Я этот момент уже плохо помню, но, кажется, сложность начинает "перемножаться" на каждый такой терм.
N>>или ссылок типа \1.
V>А здесь уже зависит от. V>Обратная ссылка может сделать грамматику контекстно-зависимой. V>(т.е. класс контекстно-свободных, то бишь стековых грамматик пропускается, что забавно)
Да.
N>>И packrat в движках вокруг меня уже типовой вариант
V>Не нашлось рядом никого с профильным образованием?
Как профильное образование мешает наличию packrat в PEG?
Здравствуйте, vdimas, Вы писали:
N>>варианты всяких деревьев лукапов
V>Принцип устройства такой таблицы (хеш, дерево или индексный массив), а так же декомпозиция ДКА не делает грамматику нерегулярной. V>Это всё относится, скорее, к оптимизации реализации.
Ну я о том же. А НС почему-то намекает на тяжёлые проблемы, вплоть до невозможности работы.
Здравствуйте, netch80, Вы писали:
V>>Это всё еще регулярная грамматика по Холмскому. V>>(это что-то "синтаксического сахара" описания грамматики) N>А не начинает зависеть от сложности выражений? Я этот момент уже плохо помню, но, кажется, сложность начинает "перемножаться" на каждый такой терм.
Не принципиально, т.к. размер таблицы переходов (если парсер табличный), зависит от кол-ва состояний, а не от кол-ва дуг (переходов).
Т.е., грубо, если в при обычной дуге у нас почти во всех клетках будет из данного состояния переход в ошибочное, и только по нужному символу (символам) в следующее (следующие), то тут наоборот — по заданным символам будет переход в ошибочное состояние, а по остальным — в целевое (целевые).
V>>Не нашлось рядом никого с профильным образованием? N>Как профильное образование мешает наличию packrat в PEG?
Ну, наколенный детерминированный LL(1) не сложнее.
Или можно взять бизоны для LR(x)/GLR-граматик или ANTLR для LL(1).
Просто есть же стандартные бока с левосторонней рекурсией для нисходящих парсеров, что там с этим у packrat?
ANTLR сам производит факторизацию грамматики для удаления левосторонней рекурсии, в этом его главная киллер-фича, как по мне.
Т.е. можно продолжать описывать правила в "человеческом виде", а далее "машина разберется".
И что характерно — если не разберется, то сообщит об этом еще на этапе построения парсера.
А наколенный нисходящий парсер может однажды уйти в stack overflow на машине клиента. ))
Здравствуйте, vdimas, Вы писали:
Pzz>>Оператор-то один. Только надо далеко продвинуться, чтобы понять, это оператор присваивания или цикла
V>'DO' space* var space* '=' space* digit [space* ',' space* digit [space* ',' space* digit]] V>
Там это так не работало, например, вот это должно было быть понято как оператор DO:
D O1 0I J=1,1 0
до метки 10 по переменной IJ от 1 до 10 включительно.
Реально можно считать, что там вначале некий... мнэээ... прототип лексического анализатора делил весь ввод на текстовые константы (в кавычках или холлеритовские) и всё остальное, а дальше работал грамматический анализатор, который уже пробелы не знал в своих определениях.
V>>>Синтаксис каждой отдельно взятой строки того Фортрана можно описать регулярной грамматикой (по Холмскому, а не перловой). Pzz>>Уже даже просто выражения со скобками не описываются регулярной грамматикой.
V>Поймал. )) V>Я в голове прикидывал остальные операторы языка.
Остальные — да, по крайней мере до введения всяких "структурных IF" в F77.
Здравствуйте, netch80, Вы писали:
N>Там это так не работало, например, вот это должно было быть понято как оператор DO:
Я вообще изначально написал без space*, потом добавил.
В общем, пропуск пробелов — не принципиальный, реализуется одним лишним if в парсере.
И да, тот Фортран был позиционным, т.е. до какой-то позиции в строке операторы не должны были встречаться, там можно было только метки размещать, что еще больше упрощало парсер.
Здравствуйте, vdimas, Вы писали:
V>Я вообще изначально написал без space*, потом добавил. V>В общем, пропуск пробелов — не принципиальный, реализуется одним лишним if в парсере.
Да. Но логика не соответствует современной.
V>И да, тот Фортран был позиционным, т.е. до какой-то позиции в строке операторы не должны были встречаться, там можно было только метки размещать, что еще больше упрощало парсер.
Ну не то чтобы упрощало... значения в позициях 7-72 всех строк надо было таки разбирать как я описал.
Здравствуйте, 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.
Здравствуйте, netch80, Вы писали:
N>Но итоговая машина состояний должна одновременно сочетать два поиска — по нужным символам и по недопустимой комбинации.
Сначала строится НКА
N>Кто выдержит составление такой таблицы, и на каком количестве состояний генератор решит "а не пошло бы оно к бениной бабушке"?
Потом НКА приводится к ДКА.
Если такое приведение невозможно, то имеем конфликты.
Если никаких ср-в разрешения конфликтов нет, то ошибка.
Но тут есть ср-во разрешения конфликтов — сама цель регулярных выражений, например, поиск, т.е. работает ИЛИ, поэтому конфликт может выигрывать любая дуга из набора конфликтующих их.
N>Кто выдержит составление такой таблицы N>Или я не вижу тут ещё какого-то фокуса?
Для юникода тут, действительно, слишком дофига дуг, поэтому еще с далеких первых экспериментов с парсерами на C# (там же юникод сплошной) я проводил минимизацию по терминалам в два этапа (а не в один этап, как по классике).
По классике все терминалы после минимизации ДКА разбиваются на группы, по которым происходят идентичные переходы (например, зачастую по символам 0..9).
А с юникодом пришёл к тому, что такую минимизацию имеет смысл выполнять еще на этапе составления НКА, т.е. все 64к символов схлопываются в небольшой алфавит (обычно единицы-десятки символов).
Потом опять в конце минимизация по терминалам и выведение в кодогенераторе конечной lookup-таблицы из этих двух.
V>>Просто есть же стандартные бока с левосторонней рекурсией для нисходящих парсеров, что там с этим у packrat? N>то есть ты типа сам должен перевести рекурсию в цикл
Сам я и обычную грамматику смогу подвергнуть факторизации, но хочется этого не делать, бо левосторонне-рекурсивная запись выражений наиболее читабельна человеку (ИМХО).
V>>ANTLR сам производит факторизацию грамматики для удаления левосторонней рекурсии, в этом его главная киллер-фича, как по мне. N>И у него явно описаны ограничения возможности этой его логики. Я бы в сложных случаях на это не залагался.
В любом случае конфликты будут обнаружены еще в процессе работы над грамматикой.
V>>А наколенный нисходящий парсер может однажды уйти в stack overflow на машине клиента. )) N>В наколенном нисходящем... ну если его автор не протестировал
Я уже говорил — это аналогично рассуждениям о статической типизации vs динамической.
Нужного теста разработчик может быть не сможет изобрести.
А потом в продакшене классический shit happens.
Здравствуйте, Marty, Вы писали:
M>Точнее — парсинг и построение AST
Это не самая важная часть ДСЛ. Изначально дсл это решаемые задачи, кейсы и решения на этом языке. Как и чем ты это будешь парсить, насколько элегантным и красивым будет язык — дело вообще мало кому интересное.
Здравствуйте, Marty, Вы писали:
M>Если не жалко, помоги мне поднять мой технологический уровень
щас я подниму.
способ первый: берешь "IntelliJ-based IDE" и устанавливаешь в неё https://plugins.jetbrains.com/plugin/7358-antlr-v4-grammar-plugin
после этого у тебя будет очень классно подсвечиваться грамматика, появятся инструменты для отладки грамматики, можно будет настраивать язык для генерации парсера.
удобно для освоения инструмента: умеет рисовать дерево разбора, сразу видна реакция на правки в грамматике.
способо второй: берешь Visual Studio, создаешь проект на C#, через NuGet ставишь Antlr4.4.6.6, Antlr4.CodeGenerator.4.6.6, Antlr4.Runtime.4.6.6.
грамматика тоже будет подсвечиваться, но не так классно, как в первом способе, зато antlr4 само скачает и поставит, т.е. вообще ничего больше не надо будет делать.
есть и свои удобства: сгенерированный код в проект не добавляется, но генерируется автоматически при изменении грамматики и включается в сборку.
Здравствуйте, Marty, Вы писали: M>Запилил статейку на эту тему со своими практиками, предлагаю обсудить. Но — с конструктивом, а не просто: "ты лошара неграмотная, я тебя на работу не возьму". Хочу понять, как таки это делать правильно и быстро.
Я юзал Coco/R + .NET Code DOM
Здравствуйте, Pzz, Вы писали: Pzz>Язык, на котором нельзя сказать обидную гадость, не может считаться естественным
В С++ "обидная гадость" — это либо SFINAE, либо ошибка компиляции
Здравствуйте, Kolesiki, Вы писали:
M>>На высокий технологический уровень я и не претендовал, я и писал с целью вызвать дискуссию
K>Нафиг ты тогда пишешь СТАТЬЮ?? Ты же "никто" в этой теме! Не умнее ли задавать вопросы?
То есть, тебе можно писать откровенную чушь и рассовывать по всем форумам, а мне нельзя запилить статейку с описанием своего личного опыта по предлагаемой теме с приглашением к обсуждению того, где я что не так делал?
