Составляемые грамматики

Question

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

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

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

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

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

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

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

Сложная вещь заключается в том, что, как правило, содержащая langauge (например, 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», используя синтаксический lookahead, чтобы найти шкафы. Но тогда моя родительская грамматика должна была бы поглотить всю спецификацию Linq. И это перетащить. С другой стороны, у отдельного детского анализатора Linq было бы очень трудное время выяснить, где остановиться, потому что ему нужно будет реализовать lookahead для иностранных типов токенов.

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

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

Answer 1

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

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

Answer 2

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

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

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

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

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

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

Answer 3

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

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

Answer 4

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

Answer 5

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

Martin Bravenboer и Eelco Visser. Проектирование синтаксических вложений и ассимиляции для языковых библиотек. В модели в программной инженерии: Семинары и симпозиумах в MODELS 2007, объем 5002 из LNCS, 2008.

MetaBorg и MetaBorg in action

Answer 6

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 => ｢｣ 

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