Композиционные грамматики

Question

Существует так много языков программирования, которые поддерживают включение мини-языков. PHP встроен в HTML. XML может быть встроен в JavaScript. Linq может быть встроен в C #. Регулярные выражения могут быть встроены в Perl.

// JavaScript example
var a = <node><child/></node>

Если задуматься, большинство языков программирования можно моделировать как разные мини-языки. Например, Java можно разбить как минимум на четыре отдельных мини-языка:

• Язык объявления типа (директива пакета, директивы импорта, объявление класса)
• Язык объявления членов (модификаторы доступа, объявления методов, переменные-члены)
• Язык операторов (поток управления, последовательное выполнение)
• Язык выражений (литералы, присваивания, сравнения, арифметика)

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

Ранее я реализовал синтаксические анализаторы для различных языков (с использованием ANTLR, JavaCC и пользовательских синтаксических анализаторов с рекурсивным спуском), и когда язык становится действительно большим и сложным, вы обычно получаете одну грамматику huuuuuuuge и Реализация парсера становится очень уродливой и очень быстрой.

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

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

my $result ~= m|abc.*xyz|i;

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

Или, допустим, у меня был язык, который позволял включать выражения Linq, но вместо окончания с точкой с запятой (как это делает C #) я хотел, чтобы выражения Linq отображались в квадратных скобках:

var linq_expression = [from n in numbers where n < 5 select n]

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

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

Что вы, ребята, думаете? Каковы наилучшие методы, доступные на сегодняшний день для реализации отдельных, разрозненных и составных языковых грамматик для включения мини-языков в более крупные родные языки?

Answer 1

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

Answer 2

Я работаю над этой проблемой. Я поделюсь своими мыслями:

Грамматики трудно отлаживать. Я отладил несколько в Bison и ANTLR, и это было не красиво. Если вы хотите, чтобы пользователь вставлял DSL как грамматику в ваш парсер, то вы должны найти способ сделать так, чтобы он не взрывался. Мой подход состоит в том, чтобы не разрешать произвольные DSL, а разрешать только те, которые следуют двум правилам:

• Типы токенов (идентификаторы, строки, числа) одинаковы для всех DSL в файле.
• Несбалансированные скобки, скобки или скобки не допускаются

Причина первого ограничения в том, что современные парсеры разбивают синтаксический анализ на лексическую стадию и затем применяют ваши традиционные правила грамматики. К счастью, я считаю, что одного универсального токенизатора достаточно для 90% DSL, которые вы хотите создать, даже если он не поддерживает уже созданные вами DSL, которые вы хотите встроить.

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

Другая часть решения заключается в разрешении макросов. Например, regex("abc*/[^.]") выглядит хорошо для меня. Таким образом, макрос "regex" может анализировать регулярное выражение вместо встраивания грамматики регулярного выражения в основной язык. Конечно, вы не можете использовать разные разделители для своего регулярного выражения, но в моем разуме вы получаете определенную последовательность.

Answer 3

Perl 6 можно рассматривать как набор DSL, специально созданных для написания программ.

Фактически реализация Rakudo построена именно таким образом.

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

Q
:closure
:backslash
:scalar
:array
:hash
"{ 1 + 3 } \n $a @a<> %a<>"

qq"{1+2}" eq ｢3｣

qq:!closure"{1+2}" eq ｢{1+2}｣

Это должно быть сделано из составных грамматик, чтобы это работало:

sub circumfix:«:-) :-)» (@_) { say @_ }

:-) 1,2,3 :-)

---

В Perl 6 грамматики являются просто типом класса, а токены - типом метода.

role General-tokens {
  token start-of-line { ^^ }
  token end-of-line { $$ }
}
grammar Example does General-tokens {
  token TOP {
    <start-of-line> <stuff> <end-of-line>
  }
  token stuff { \N+ }
}

role Other {
  token start-of-line { <alpha> ** 5 }
}
grammar Composed-in is Example does Other {
  token alpha { .. }
}

say Composed-in.parse: 'abcdefghijklmnopqrstuvwxyz';

｢abcdefghijklmnopqrstuvwxyz｣
 start-of-line => ｢abcdefghij｣
  alpha => ｢ab｣
  alpha => ｢cd｣
  alpha => ｢ef｣
  alpha => ｢gh｣
  alpha => ｢ij｣
 stuff => ｢klmnopqrstuvwxyz｣
 end-of-line => ｢｣

Обратите внимание, что я не показал класс действий, который удобен для преобразования дерева разбора при его создании.

Answer 4

Взгляните на SGLR , Обобщенный LR-анализ без сканирования. Вот несколько ссылок и URL. Эта техника разбора делает составление таблиц разбора очень простым. Особенно в сочетании с SDF .

Мартин Бравенбур и Элко Виссер. Разработка синтаксических вложений и ассимиляций для языковых библиотек. В Модели в разработке программного обеспечения: семинары и симпозиумы на MoDELS 2007, том 5002 LNCS, 2008.

МетаБорг и МетаБорг в действии

Answer 5

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

Не то, чтобы я понимал, что они на самом деле делают, но очень интересное место для поиска вдохновения - FoNC . Кажется, они движутся в направлении, которое позволяет беспрепятственно взаимодействовать различным вычислительным движкам.

Answer 6

Если подумать, это действительно то, как работает рекурсивный анализ спуска. Каждое правило и все правила зависят от формы мини грамматики. Все, что выше, не имеет значения. Например, вы можете написать грамматику Java с помощью ANTLR и разделить все разные «мини-языки» на разные части файла.

Это не очень распространено просто по той причине, что эти "мини-языки" часто имеют много общих правил. Однако было бы неплохо, если бы такие инструменты, как ANTLR, позволяли включать отдельные грамматики из разных файлов. Это позволит вам логически разделить их. Причина, по которой это, вероятно, не реализовано, заключается, вероятно, в том, что это «косметическая» проблема, она связана исключительно с самими файлами грамматики, а не с самим парсингом. Это также не сделает ваш код короче (хотя может быть немного легче следовать). Единственная техническая проблема, которую это решит, - это конфликт имен.