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

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

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

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

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

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

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

def fun():
   not implemented yet

try:
  fun()
except:
  pass

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

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

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

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

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

S -> NP . VP

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

Еще одна вещь, которую я рассматривал, - это сделать это поведение по умолчанию для всех, но позволить языкам (имеется в виду набор макросов для анализа данного языка) выдавать ошибку анализа во время компиляции. Python 2.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, который вы не можете вызвать, даже если он определен.