Частичная оценка для разбора

Question

Я работаю над макросистемой для Python (, как описано здесь ), и одна из вещей, которые я рассматривал, - это единицы измерения. Хотя единицы измерения могут быть реализованы без макросов или с помощью статических макросов (например, определяя все ваши единицы заранее), я склоняюсь к идее динамического расширения синтаксиса во время выполнения.

Чтобы сделать это, я рассматриваю возможность использования своего рода частичной оценки кода во время компиляции. Если синтаксический анализ для данного выражения завершается неудачно из-за отсутствия макроса для его синтаксиса, компилятор останавливает оценку функции / блока и генерирует код, который уже есть, с заглушкой, в которой находится неизвестное выражение. Когда эта заглушка нажата во время выполнения, функция перекомпилируется с текущим набором макросов. Если эта компиляция не удалась, возникнет ошибка разбора, потому что выполнение не может быть продолжено. Если компиляция завершается успешно, новая функция заменяет старую, и выполнение продолжается.

Самая большая проблема, которую я вижу, заключается в том, что вы не можете найти ошибки разбора, пока не будет запущен уязвимый код. Однако это не затронет многие случаи, например, групповые операторы, такие как [], {}, () и ``, все еще должны быть сопряжены (требование моего анализатора токенов / списков), и синтаксис верхнего уровня, такой как классы и функции, не будет затронут, поскольку действительно время загрузки, где синтаксис оценивается и генерируются их объекты.

Помимо сложности реализации и проблемы, которую я описал выше, какие проблемы возникают с этой идеей?

Answer 1

Вот несколько возможных проблем:

• Возможно, вам будет трудно предоставить пользователю полезные сообщения об ошибках в случае возникновения проблемы. Это кажется вероятным, поскольку любая синтаксическая ошибка времени компиляции может быть просто расширением синтаксиса.
• Хит производительности.

Я пытался найти некоторые обсуждения плюсов, минусов и / или реализации динамического анализа в Perl 6, но я не смог найти ничего подходящего. Тем не менее, вы можете найти эту цитату из Никлауса Вирта (дизайнера Паскаля и других языков) интересной:

Фантазии компьютерных ученых в 1960-х не было предела. Отвергнутый благодаря успеху автоматического синтаксиса анализ и генерация парсера, некоторые предложил идею гибкого, или по крайней мере расширяемый язык. Понятие было то, что программа будет предшествуют синтаксические правила, которые будет тогда вести общего парсера при разборе последующей программы. Шаг вперед: правила синтаксиса не только предшествуют программе, но они может быть вкраплен в любом месте по всему тексту. Например, если кто-то хотел использовать особенно причудливая частная форма для выписки, он мог сделать это элегантно, даже указав различные варианты для та же концепция в разных разделах та же программа. Концепция, которая языки служат для общения между люди были полностью смешаны вне, как, очевидно, все могли теперь определить свой собственный язык на лету. Большие надежды, однако, были скоро затухает от возникающих трудностей при попытке указать, что это частные конструкции должны означать. Как следствие, интригующая идея расширяемые языки исчезли довольно быстро.

Редактировать : Вот Perl 6 Синопсис 6: Подпрограммы , к сожалению, в форме разметки, потому что я не смог найти обновленную, отформатированную версию; искать внутри для «макроса». К сожалению, это не слишком интересно, но вы можете найти некоторые важные вещи, такие как правило однопроходного синтаксического анализа Perl 6 или его синтаксис для абстрактных синтаксических деревьев. Подход, который использует Perl 6, заключается в том, что макрос - это функция, которая выполняется сразу после анализа его аргументов и возвращает либо AST, либо строку; Perl 6 продолжает синтаксический анализ, как если бы источник действительно содержал возвращаемое значение. Существует упоминание о генерации сообщений об ошибках, но из-за них создается впечатление, что если макросы возвращают AST, вы можете сделать это хорошо.

Answer 2

Если продвинуться на один шаг дальше, вы можете выполнить «ленивый» анализ и всегда только анализировать достаточно для оценки следующего оператора. Как какой-то парсер точно в срок. Тогда синтаксические ошибки могут стать обычными ошибками времени выполнения, которые просто вызывают нормальное исключение, которое может быть обработано окружающим кодом:

def fun():
   not implemented yet

try:
  fun()
except:
  pass

Это был бы интересный эффект, но если он полезен или желателен, это другой вопрос. Как правило, полезно знать об ошибках, даже если вы не вызываете код в данный момент.

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

В любом случае вы должны убедиться, что анализируете код только один раз, а если он выполняется второй раз, используйте уже проанализированное выражение, чтобы это не приводило к проблемам с производительностью.

Answer 3

Вот некоторые идеи из магистерской диссертации, которые могут быть полезны или не полезны. Тезис был о надежном разборе естественного языка. Основная идея: учитывая контекстную грамматику для языка, попробуйте разобрать текст (или, в вашем случае, программа на Python). Если разбор не удался, у вас будет частично сгенерированное дерево разбора. Используйте древовидную структуру, чтобы предложить новые правила грамматики, которые будут лучше охватывать анализируемый текст. Я мог бы выслать вам свою диссертацию, но если вы не читаете на иврите, это, вероятно, будет бесполезно.

В двух словах: Я использовал восходящий анализатор диаграммы . Этот тип синтаксического анализатора генерирует ребра для производств из грамматики. Каждое ребро помечено той частью дерева, которая была израсходована. Каждое ребро получает оценку в зависимости от того, насколько близко оно было к полному покрытию, например:

S -> NP . VP

Имеет счет в половину (Нам удалось покрыть NP, но не VP). Края с наибольшим количеством баллов предлагают новое правило (например, X-> NP). В целом, синтаксический анализатор диаграмм менее эффективен, чем обычный анализатор LALR или LL (типы, обычно используемые для языков программирования) - сложность O (n ^ 3) вместо сложности O (n), но опять же вы пытаетесь сделать что-то более сложное, чем просто разбор существующего языка. Если вы можете сделать что-то с идеей, я могу отправить вам более подробную информацию. Я считаю, что анализ парсеров на естественном языке может дать вам другие идеи.

Answer 4

Еще одна вещь, которую я рассмотрел, - это сделать это стандартным поведением по всем направлениям, но разрешить языкам (т. Е. Ряду макросов для разбора данного языка) выдавать ошибку разбора во время компиляции. Например, Python 2.5 в моей системе сделает это.

Вместо идеи заглушки, просто перекомпилируйте функции, которые не могли быть полностью обработаны во время компиляции, когда они выполняются. Это также упростит самоизменяющийся код, так как вы можете изменить код и перекомпилировать его во время выполнения.

Answer 5

Я не думаю, что ваш подход будет работать очень хорошо. Давайте рассмотрим простой пример, написанный на псевдокоде:

define some syntax M1 with definition D1
if _whatever_:
    define M1 to do D2
else:
    define M1 to do D3
code that uses M1

Таким образом, есть один пример, когда, если вы разрешите переопределение синтаксиса во время выполнения, у вас возникнет проблема (поскольку при вашем подходе код, использующий M1, будет скомпилирован по определению D1). Обратите внимание, что проверка, происходит ли переопределение синтаксиса, неразрешима. Чрезмерное приближение может быть вычислено какой-либо системой типирования или каким-либо другим видом статического анализа, но Python не очень известен для этого: D.

Еще одна вещь, которая беспокоит меня, это то, что ваше решение не «чувствует» себя правильным. Я считаю плохим хранить исходный код, который вы не можете проанализировать только потому, что вы можете анализировать его во время выполнения.

Другой пример, который приходит мне на ум:

...function definition fun1 that calls fun2...
define M1 (at runtime)
use M1
...function definition for fun2

Технически, когда вы используете M1, вы не можете его проанализировать, поэтому вам нужно сохранить остальную часть программы (включая определение функции fun2) в исходном коде. Когда вы запустите всю программу, вы увидите вызов fun2, который вы не можете вызвать, даже если он определен.

Answer 6

Возможно, вам потребуется разделить биты входного текста с неизвестным синтаксисом, чтобы можно было разрешить оставшуюся часть синтаксического дерева, за исключением некоторых узлов последовательностей символов, которые будут раскрыты позже. В зависимости от вашего синтаксиса верхнего уровня, это может быть хорошо.

Вы можете обнаружить, что алгоритм синтаксического анализа, лексер и интерфейс между ними нуждаются в обновлении, что может исключить большинство инструментов создания компилятора.

(Более обычный подход - использовать для этой цели строковые константы, которые можно проанализировать небольшому интерпретатору во время выполнения).