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

«Вне зависимости от контекста» - термин относительный. Большинство контекстно-свободных парсеров фактически анализируют надмножество языка, не зависящее от контекста, а затем проверяют результирующее дерево синтаксического анализа, чтобы убедиться, что оно допустимо. Например, следующие две программы C действительны в соответствии с контекстно-свободной грамматикой языка C, но одна из них быстро дает сбой во время проверки контекста:

int main()
{
    int i;
    i = 1;
    return 0;
}

int main()
{
    int i;
    i = "Hello, world";
    return 0;
}

Вне контекста i = "Hello, world"; - вполне допустимое присвоение, но в контексте вы можете видеть, что все типы неверны. Если бы контекст был char* i;, все было бы хорошо. Таким образом, контекстно-свободный синтаксический анализатор не увидит ничего плохого в этом назначении. Только когда компилятор начнет проверять типы (которые зависят от контекста), он поймает ошибку.

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

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

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

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

При этом хорошим ресурсом является инструмент antlr (http://www.antlr.org). Автор инструмента также выпустил книгу по созданию парсеров для языков с использованием antlr (http://www.antlr.org). Есть неплохая документация и множество примеров грамматик.

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

• Прагматика языка программирования, Скотт и др.
• Концепции дизайна в языках программирования, Turbak et al.
• Современный дизайн компилятора, Grune et al. (Я кощунственно предпочитаю это "Книге дракона" Ахо и др.)

Мягкие введения, такие как:

• Учебник Креншоу (как предлагает @ 'Jonas Gorauskas' здесь)
• Окончательная ссылка на ANTLR от Парра
• Недавняя работа Мартина Фаулера над DSL

Вы также должны учитывать свой язык реализации. Это одна из тех областей, где разные языки сильно различаются по тому, что они облегчают. Вам следует рассмотреть такие языки, как LISP, F # / OCaml и новый язык Гилада Браха новояз.

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

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

Если вы напишете рукописный нисходящий синтаксический анализатор, вы сможете реализовать любые правила, которые захотите, и где угодно. Это то, что упрощает восстановление после ошибок. Это также сделает тривиальным использование значительных пробелов. Вы можете просто сохранить текущий уровень отступа в переменной внутри вашего класса синтаксического анализатора и можете остановить синтаксический анализ блоков, когда вы встретите токен в новой строке, у которой позиция столбца меньше текущего уровня отступа. Кроме того, велика вероятность того, что вы столкнетесь с двусмысленностями в своей грамматике. Большинство широко используемых «производственных» языков имеют синтаксические неоднозначности. Хорошим примером являются универсальные шаблоны в C # (есть двусмысленность вокруг «‹ »в контексте выражения, это может быть либо оператор« меньше », либо начало« универсального списка аргументов »). В рукописном синтаксическом анализаторе решение подобных неоднозначностей тривиально. Вы можете просто добавить немного недетерминированности там, где вам это нужно, с относительно небольшим влиянием на остальную часть синтаксического анализатора,

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

Я бы сказал, что генераторы парсеров - хороший выбор, только если:

1. Вы никогда не планируете писать IDE,
2. Язык имеет действительно простой синтаксис, или
3. Вам нужен синтаксический анализатор очень быстро, и все в порядке с плохим пользовательским интерфейсом

Вы читали Ахо, Сетхи, Уллмана: «Составители: принципы, методы и инструменты»? Справочник по классическому языку.

/ Аллан

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

Чтение Ахо, Сетхи и Уллмана (она известна как «Книга Дракона») - хороший план. В отличие от других участников, я говорю, что вы должны сначала поиграть с более простыми генераторами парсеров, такими как Yacc и Bison, и только тогда, когда вы обожжетесь, потому что вы не можете что-то сделать с этим инструментом, если вы попытаетесь создать что-то с LL (* ) парсер вроде Antlr.

Тот факт, что в языке используются значительные отступы, не означает, что он по своей сути зависит от контекста. Например, Haskell использует значительные отступы, и (насколько мне известно) его грамматика контекстно-независима.

Примером источника, требующего контекстно-зависимой грамматики, может быть следующий фрагмент из Ruby:

my_essay = << END_STR
This is within the string
END_STR

<< self
  def other_method
    ...
  end
end

Другой пример - режим XML в Scala:

def doSomething() = {
  val xml = <code>def val <tag/> class</code>
  xml
}

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

В заключение, если вам действительно нужны контекстно-зависимые инструменты синтаксического анализа, вы можете попробовать некоторые из менее строго формальных методов. Комбинаторы синтаксического анализатора используются при синтаксическом анализе Scala. У них есть некоторые досадные ограничения (без лексирования), но они неплохой инструмент. Инструменты LL (*), такие как ANTLR, также кажутся более искусными в выражении таких "специальных" выходов синтаксического анализа. Не пытайтесь использовать Yacc или Bison с контекстно-зависимой грамматикой, они слишком строги, чтобы легко выразить такие концепции.

Контекстно-зависимый язык? Это без отступа: Protium (http://www.protiumble.com)