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

Ответ 1

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

Язык программирования D является примером контекстной свободной грамматики. С++ является контекстно-зависимым. (Например, T * x объявляет, что x является указателем на T, или он умножает T на x? Мы можем только сказать, просмотрев T в таблице символов, чтобы увидеть, является ли это типом или переменной.)

Пробел не имеет к этому никакого отношения.

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

Ответ 2

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

Пока я не пытался написать контекстный свободный парсер, используя что-то вроде yacc, я думаю, что возможно использовать условный лексер для возврата токенов изменения отступа, как описано в url.

Кстати, вот официальная грамматика python из python.org: http://www.python.org/doc/current/ref/grammar.txt

Ответ 3

Сначала я познакомился с проблемой, прочитав некоторые из литературы, которые доступны по этому вопросу. Классический сборник компиляторов Aho et. и др. может быть тяжелым для математики и comp sci, но гораздо более подходящий текст - это Let Build the Compiler статьи Джека Креншоу. Это серия статей, которые г-н Креншоу написал в конце 80-х, и это самый недооцененный текст компиляторов, когда-либо написанных. Подход прост и доведен до конца: г-н Креншоу показывает " A", который работает. Вы можете легко пройти через контент в течение нескольких вечеров и лучше понять, что такое компилятор. Пара предостережений заключается в том, что примеры в тексте написаны в Turbo Pascal, а компиляторы испускают 68K-ассемблер. Примеры достаточно легки для переноса на более современный язык программирования, и я рекомендую Python для этого. Но если вы захотите следовать, как только будут представлены примеры, вам, по крайней мере, понадобится Turbo Pascal 5.5 и 68K ассемблер и эмулятор. Текст по-прежнему актуальен сегодня, и использование этих старых технологий действительно забавно. Я очень рекомендую его как кому-то первый текст в компиляторах. Отличная новость заключается в том, что языки, такие как Python и Ruby, открыты, и вы можете загрузить и изучить исходный код C, чтобы лучше понять, как это делается.

Ответ 4

"Контекстно-свободный" - относительный термин. Большинство контекстно-свободных парсеров фактически анализируют надмножество языка, который не содержит контекста, а затем проверяет полученное дерево синтаксического анализа, чтобы убедиться, что оно действительно. Например, следующие две программы 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, представляет собой контекстно-свободную грамматику). Единственным ограничением является то, насколько полезной ваша грамматика и сколько контекстно-зависимая проверка, которую вы должны сделать в полученном дереве синтаксического анализа.

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

Ответ 5

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

Ответ 6

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

Таким образом, хорошим ресурсом является инструмент antlr (http://www.antlr.org). Автор инструмента также выпустил книгу о создании парсеров для языков с использованием antlr (http://www.pragprog.com/titles/tpantlr/the- окончательная-ANTLR ссылка). Существует довольно хорошая документация и множество примеров грамматик.

Ответ 7

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

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

Более мягкие интродукции, такие как:

• Учебник Crenshaw (как предложил @Jonas Gorauskas здесь)
• Окончательный ANTLR Reference by Parr
• Мартин Фаулер недавно работал над DSL

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

Ответ 8

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

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

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

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

Я бы сказал, что генераторы парсеров являются хорошим выбором, если:

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

Ответ 9

Вы читали Ахо, Сетхи, Ульман: "Составители: принципы, методы и инструменты"? Это классический справочник.

/Allan

Ответ 10

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

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

Ответ 11

Просто потому, что язык использует значительный отступ, это не означает, что он по своей сути является контекстно-зависимым. В качестве примера, Haskell использует значительный отступ, и, насколько мне известно, его грамматика не имеет контекста.

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

my_essay = << END_STR
This is within the string
END_STR

<< self
  def other_method
    ...
  end
end

Другим примером может быть режим Scala XML:

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

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

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

Ответ 12

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