Zephyr ASDL (абстрактный язык описания синтаксиса)

Вопрос:

Что такое Zephyr ASDL и как оно относится к другим технологиям компилятора, таким как лексеры и генераторы парсеров?

(Я был бы признателен, если бы вы были достаточно полны, но указывали на другие ссылки в Интернете, когда они приобретают довольно технический характер, потому что большинство из того, что я знаю о компиляторах, происходит от игры с yacc и flex, пишу простую максимальную лексерную запись в C, и поиск и чтение материала в Интернете)

Вопрос:

Я читал http://docs.python.org/devguide/compiler.html, и я наткнулся на следующую строку:

Спецификация узлов AST указана с использованием Zephyr Абстрактный язык определения синтаксиса (ASDL).

Я последовал за цитированием внизу, чтобы найти: http://www.cs.princeton.edu/research/techreps/TR-554-97.

Мое первое чтение этой статьи было довольно шумным, и я надеялся, что сначала смогу лучше понять, что было целью ASDL (в контексте процесса компиляции), прежде чем повторять попытку.

Ответ 1

Генераторы Lexer и Parser принимают описания лексем и грамматик и генерируют код, реализующий соответствующий артефакт. Лекс требует регулярного выражения для описания токенов. Генераторы синтаксических анализаторов принимают различные виды расширенных нотаций BNF.

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

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

В идеале вы хотели бы, чтобы языки описания для целевых наборов команд, анализа потоков, переводов (вы упомянули максимальный munch) из абстрактных деревьев в целевой набор команд и способ описания оптимизаций. Затем с соответствующими инструментами для каждой части вы можете собрать весь компилятор из "спецификаций". На самом деле было много работы в этой области; люди сделали все это отдельно и вместе. Неудивительно, что некоторые из них происходят из проекта "Зефир", который ранее был из Принстона (кажется, веб-сайт "Зефир" там уже мертв), целью которого было сделать именно такую вещь.

В любом случае попробуйте поискать в Google Scholar "генератор компилятора".

Ответ 2

ASDL используется, когда вам нужно сгенерировать дерево в модуле и ввести одно и то же дерево в другом модуле (или почти такое же дерево, каким-то образом оптимизированным).

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

ASDL принимает в качестве входного данных какое-то дерево, написанное в синтаксисе, почти идентичном синтаксису типа алгебраических данных (например, в haskell или ml) или синтаксис в BNF, но гораздо более упрощенный, и автоматически генерирует все конструкторы, функции печати начиная с простого описания дерева.

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

   lexeme=
       ID(STRING)
     | INT(num_integer)
     | FLOAT(num_float)
     attributes(int coord_x, int coord_y)
   num_integer:
     ....
   num_float:
     ....

и вы вызываете идентификаторы конструкторов, INT, FLOAT и т.д. из вашего лексера. ASDL преобразует этот простой синтаксис во все функции, которые вам нужны, либо для создания узлов для AST, либо для печати, или того, что вам нужно. ASDL не налагает ограничений на сгенерированный код.

Если вы добавляете attributes к типу, например, к координатам маркера, такие атрибуты добавляются к параметрам каждого конструктора из этого типа.

Более сложное дерево, созданное парсером, будет выглядеть так:

expr:  SUM(expr, expr)
      |PRODUCT(expr, expr)
      |number
number: num_integer

В этом случае asdl проверит, что вызов SUM (_ _), созданный синтаксическим анализатором, перейдет к суммарным узлам, созданным с помощью одного из конструкторов expr. num_integer определяется извне, возможно, деревом asdl для lexer.

Обратите внимание, что вам не разрешено определять конструкторы, содержащие регулярные выражения, например number: [0-9]+. ASDL проще, чем EBNF.

Эти конструкторы будут определены так, чтобы строить то, что вам нужно, и более того, они печатают проверку, чтобы убедиться, что ваш генератор lexer/parser/code выводит деревья, которые соответствуют языку, определенному asdl.

Чтобы понять ASDL, вам нужно написать 3-4 парсера и посмотреть, что общего в генерируемом им коде. Эта общая часть на самом деле является ASDL, поэтому это абстракция для вывода парсеров в частности.