Как заменить макросы грамматическим парсером?

Question

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

Пример программы для анализа обычно выглядит так:

instructionA parameter1, parameter2
instructionB parameter1
instructionC parameter1, parameter2, parameter3

Пока проблем нет. Но язык также поддерживает макросы:

Define MacroX { foo, bar }
instructionD parameter1, MacroX, parameter4

Define MacroY(macroParameter1, macroParameter2) {
  instructionE parameter1, macroParameter1
  instructionF macroParameter2, MacroX
}

instructionG parameter1, MacroX
MacroY

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

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

Помощь очень ценится.

Answer 1

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

Если это так, у вас мало выбора: вам нужно создать макропроцессор, который может сохранять номера строк.

Если макросы всегда содержат хорошо структурированные языковые элементы и они всегда встречаются в структурированных местах кода, то вы можете добавить понятие определения макроса и вызвать вашу грамматику. Это может сделать ваши разборы неоднозначными; foo (x) в коде C может быть вызовом макроса или вызовом функции. Вам придется как-то решить эту двусмысленность. С-парсеры использовали для решения таких проблем неоднозначности путем сбора информации таблицы символов при их разборе; если вы собираете is-foo-a-macro при разборе, то вы можете определить, является ли foo (x) вызовом макроса или нет.

Answer 2

С помощью PEG вы должны вручную определить места, где вы можете проверять макросы. Вы можете добавить свой макрос в хеш и проверить его в правилах PEG, которые разрешают макросы (infix expr, postfix expr, unop, binop, вызов функции, ...). Это не так просто, как в lisp, но намного проще, чем в случае с YACC и его взломами приоритетов операторов:)

Другие известные PEG-фреймворки, которые позволяют использовать макросы, такие как parrot, perl6, katahdin или PFront, используют прием для выполнения анализа во время выполнения, торгуя против производительности. Или вы можете сделать и то, и другое, и разрешить предварительно скомпилированный и интерпретированный разбор PEG. Есть несколько проектов, которые думают об этом, но вам нужна быстрая ВМ, например, luajit, java, clr или friends.

Я использую специальные ключевые слова синтаксического блока для загрузки внешних общих библиотек с помощью внешнего предварительно скомпилированного анализатора PEG. Например. проанализировать объявления SQL или FFI в вашем AST. Но вы также можете потребовать компилятор C и скомпилировать анализ во время выполнения для всех макросов.

Answer 3

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

Другая возможность состоит в цепочке синтаксических анализаторов, что также тривиально с подходами на основе PEG.