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

Question

Вопрос:

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

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

Справочная информация:

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

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

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

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

Answer 1

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

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

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

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

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

Answer 2

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

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

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

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

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

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

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

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

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

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

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

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

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