PEG парсеры

[barbashovtd]

Не знаю что было раньше, но Гвидо активно обсуждает вещи в довольно интересном проекте Tatsu

[george3]

Он также позволяет создавать узлы с нуля и изменять существующие, а также компилировать части в байт-код. Последнее позволило создать целую индустрию языковых расширений для Python.

Это что за расширения? Хотелось бы расширение позволящее писать в питоне на coffeescript!

[TyVik]

Насколько я помню, в PyCharm до версии 3.6 дебаггер анализировал байт-код и переписывал его на лету, чтобы иметь возможность вставить свои управляющие конструкции. Доклад на Youtube.

[TyVik]

Именно так оно и было, но около 15 лет назад мы обнаружили, что компилятор переусложнён. Так что мы выделили отдельно AST и фазу трансформации AST из дерева разбора.

Изначально так и было — AST генерировался в процессе парсинга. Но, видимо, поддерживать это стало проблематичным, так что генерацию AST вынесли отдельно.

[TyVik]

Скорее всего 2. Вернее, технически возможно, но очень сложно стало со временем. В итоге Гвидо сделал промежуточное представление (интерфейс, абстракцию). Скорее всего смысл был в том, чтобы совсем не трогать генерацию AST при изменении работы парсера (добавлении нового синтаксиса). В итоге такого разбиения мы получаем 2 вещи попроще — одна константна, а меняется только парсинг.

Видимо, сейчас он пробует всё-таки эти 2 модуля совместить обратно. Надеюсь, что получится.

[KvanTTT]

Я правильно понимаю что дерево разбора было просто следствием использования генератора парсеров (pgen)?

По факту даже с использованием генератора парсеров дерево разбора можно не строить, если использовать Listener прямо во время парсинга. ANTLR позволяет такое делать. Обработка узлов усложняется, т.к. она становится восходящей и менее явной. Однако это дает сильную экономию памяти, т.к. "вавилонские башни" при этом можно сразу схлопывать и проводить другие оптимизации.

В Positive Technologies мы работаем над статическими анализаторами кода, в которых на одном этапе деревья разбора конвертируются в универсальные AST. Однажды столкнулись с проблемой: дерево разбора PL/SQL файла в 1 млн. строк занимает в памяти примерно 2.5 Гб (используется огромная грамматика PL/SQL). Мы переписали старый код на новый, в котором универсальное AST строится сразу вообще без использования дерева разбора. Это дало уменьшение потребления памяти в 2.5 раза, а также увеличило производительность.