Написание компилятора - понимание использования и возможностей

10

Это часть серии вопросов, посвященных проекту, связанному с проектом Abstraction Project, целью которого является абстракция концепций, используемых в языковом дизайне, в форме фреймворка. Родственный проект называется OILexer, целью которого является создание синтаксического анализатора из файлов грамматики без использования внедрения кода в совпадениях.

Некоторые другие страницы, связанные с этими вопросами, связанные со структурной типизацией, можно посмотреть здесь , а простоту использования можно найти здесь . Мета-тема, связанная с запросом о фреймворке и подходящем месте для публикации, может быть найдена здесь .

Я подхожу к тому, что собираюсь начать извлечение дерева разбора из заданной грамматики, за которым следует парсер рекурсивного спуска, который использует DFA для распознавания прямых путей (аналогично LL (*)) в ANTLR 4, поэтому я подумал, что я открою это, чтобы получить представление.

Какие компиляторы идеальны в компиляторе парсера?

Итак, вот краткий обзор того, что реализовано:

  1. Шаблоны
  2. Посмотрите вперед прогнозирование, зная, что действительно в данный момент.
  3. Правило «Делитерализация» берет литералы в правилах и определяет, из какого они токена.
  4. Недетерминированные автоматы
  5. Детерминированные автоматы
  6. Простой лексический конечный автомат для распознавания токенов
  7. Методы автоматизации токенов:
    • Сканирование - полезно для комментариев: Комментарий: = "/ *" Сканирование ("* /");
    • Subtract - полезно для идентификаторов: Identifier: = Subtract (IdentifierBody, Keywords);
      • Гарантирует, что идентификатор не принимает ключевые слова.
    • Кодировать - кодирует автоматизацию в виде серии X с количеством базовых N переходов.
      • UnicodeEscape: = "\\ u" BaseEncode (IdentifierCharNoEscape, 16, 4);
        • Делает Unicode escape в шестнадцатеричном, с шестнадцатеричным 4-переходом. Разница между этим и: [0-9A-Fa-f] {4} заключается в том, что автоматизация с Encode ограничивает допустимый набор шестнадцатеричных значений областью действия IdentifierCharNoEscape. Так что, если вы дадите ему \ u005c, версия кодирования не примет значение. Такие вещи имеют серьезное предостережение: используйте экономно. В результате автоматизация может быть довольно сложной.

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

Для всех, кто интересуется, я загрузил довольно напечатанную оригинальную форму проекта T * y♯ . Каждый файл должен ссылаться на каждый другой файл, я начал ссылаться в отдельных правилах, чтобы следовать им, но это заняло бы слишком много времени (было бы проще автоматизировать!)

Если нужно больше контекста, пожалуйста, напишите соответственно.

Изменить 5-14-2013 : я написал код для создания графиков GraphViz для конечных автоматов в рамках данного языка. Вот орграф GraphViz AssemblyPart . Члены, связанные в описании языка, должны иметь rulename.txt в соответствующей папке с орграфом для этого правила. Некоторое описание языка изменилось с момента публикации примера, это связано с упрощением грамматики. Вот интересное графическое изображение .

Александр Мору
источник
8
Стена о 'текст. Не поймите это неправильно, я ценю тщательно объясненную проблему. В этом случае это просто слишком многословно. Из того, что я понял, вы спрашиваете, какие функции должны быть включены в грамматический парсер или как его создать, не начиная с нуля? Пожалуйста, отредактируйте, чтобы ответить на следующие вопросы (вам не нужно переписывать, просто добавьте в конец резюме): В чем ваша проблема? С какими ограничениями вы связаны возможными решениями вашей проблемы (она должна быть быстрой, она должна быть LL * и т. Д.)?
Нейл
1
Я прошу понимания в отношении набора функций. Основное внимание уделяется простоте использования. Трудность заключается в том, чтобы найти кого-то, кто не знает проект, понять проект, чтобы они были в курсе его направленности. Я не спрашиваю «как это сделать», я спрашиваю, что касается удобства использования. Предложения о том, как урезать вопрос, приветствуются.
Аллен Кларк Коупленд-младший
1
Для меня не очевидно, о чем идет речь. Например, со времен yacc мы видели много генераторов парсеров. Чем отличается ваш OILexer? Что нового?
Инго
1
Цель этого проекта - упростить генерацию парсера. Аналогично да, для YACC / Bison и FLEX / LEX. Основное отличие состоит в том, чтобы избежать сложности, связанной с этими программами. Сохранение простоты и сути дела - главная цель. Вот почему я создал формат, который лишен лишних разделов, а скорее ставит целью сделать его похожим на обычное программирование: только специфичным для языковой разработки. Токены определяются с помощью ': =' после их имени, правила определяются с помощью :: = после их имени. Шаблоны используют «<» и «>» в ​​качестве аргументов, за которыми следует «:: =», так как они используют синтаксис правил.
Аллен Кларк Коупленд-младший
3
Этот адский акцент на разборе кажется неуместным; Это хорошо решенная проблема, и она вряд ли вмятина, что вам нужно для обработки языков программирования. Google для моего эссе о "жизни после разбора".
Ира Бакстер

Ответы:

5

Это отличный вопрос.

В последнее время я много работаю над разбором, и ИМХО некоторые из ключевых особенностей:

  • программный API - так что его можно использовать из языка программирования, в идеале просто импортировав библиотеку. Он также может иметь GUI или BNF-подобный интерфейс, но программный является ключевым, потому что вы можете повторно использовать свои инструменты, IDE, статический анализ, тестирование, средства абстрагирования языка, знакомство программиста, генератор документации, процесс сборки, и т.д. Кроме того, вы можете в интерактивном режиме играть с крошечными парсерами, что значительно сокращает кривую обучения. Эти причины ставят его на первое место в моем списке «важных функций».

  • сообщение об ошибке, как упоминал @guysherman. Когда ошибка найдена, я хочу знать, где была ошибка и что происходило, когда она произошла. К сожалению, я не смог найти хороших ресурсов для объяснения того, как генерировать приличные ошибки, когда в игру вступает возвратный путь. (Хотя обратите внимание на комментарий @ Sk-logic ниже).

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

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

  • Я согласен с вашей № 2 (прогноз на будущее). Я думаю, что это помогает генерировать хорошие отчеты об ошибках. Это полезно для чего-то еще?

  • поддержка построения дерева разбора при синтаксическом анализе, возможно:

    • конкретное синтаксическое дерево, для которого структура дерева соответствует непосредственно грамматике и включает в себя информацию компоновки для сообщения об ошибках последующих этапов. В этом случае клиенту не нужно ничего делать, чтобы получить правильную древовидную структуру - это должно напрямую зависеть от грамматики.
    • абстрактное синтаксическое дерево. В этом случае пользователь может поиграть с любыми деревьями разбора
  • какая-то регистрация. Я не уверен в этом; может быть, чтобы показать след правил, которые пробовал анализатор, или отследить ненужные токены, такие как пробелы или комментарии, в случае (если) вы хотите использовать токены для генерации HTML-документации.

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

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

С другой стороны, я не считаю исправление ошибок особенно важным - хотя я не в курсе текущих достижений. Проблемы, которые я заметил, заключаются в том, что потенциальные исправления, которые предоставляют инструменты: 1) слишком много, и 2) не соответствуют фактическим ошибкам, и поэтому не все так полезно. Надеемся, что эта ситуация улучшится (или, возможно, уже сделал это).


источник
Я отредактировал тело вопроса, включив в него ссылку на PrecedenceHelper, которая гласит «Шаблоны». Он допускает кортежи массивов параметров, поэтому, если у вас есть четыре параметра, каждый из которых является массивом параметров, шаблон должен использоваться в наборах аргументов из четырех.
Аллен Кларк Коупленд-младший
Основная причина, по которой вы создадите CST, - это общая структура анализируемого файла. Если вы хотите распечатать документ, вам лучше всего использовать CST, потому что AST, поскольку их название подразумевает отсутствие информации для обработки нечетного интервала, который может захватить CST. Преобразование CST обычно довольно легко, если это хороший CST.
Аллен Кларк Коупленд-младший
Я снова отредактировал вопрос на тему встроенных функций, доступных для использования.
Аллен Кларк Коупленд-младший
Я думаю, что я не очень хорошо выразил свою точку зрения о шаблонах / функциях: я имел в виду, что, поскольку у вас никогда не может быть достаточно, система не должна пытаться выяснить их заранее: пользователь должен уметь создавать его собственный.
1
Я нашел один подход, особенно полезный для отчетов об ошибках с бесконечным обратным отслеживанием (Packrat): каждое производственное правило снабжено сообщениями об ошибках (сформулированных как «ожидается бла-бла-бла»), и при сбое такое сообщение сохраняется в потоке таким же образом как записанные токены. Если все сбои не восстанавливаются (разбор прекращается до достижения конца потока), наиболее подходящим является самое правое сообщение об ошибке (или набор таких сообщений). Это проще всего сделать, конечно, есть способы усовершенствовать его, добавив больше аннотаций.
SK-logic
5

У меня нет опыта в языковом дизайне, но я однажды попробовал написать парсер, когда создавал IDE для игрового движка.

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

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

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

guysherman
источник
Это одна вещь, которую я планирую сделать. Чтобы помочь мне в знании предметной области, мой друг предложил написать настоящий парсер вручную, чтобы освоить его автоматизацию. Я понял это довольно быстро: парсеры сложны, и есть вещи, которые мы делаем вручную, которые упрощают процесс. Правила и шаблоны имеют одинаковый синтаксис; однако, есть языковые элементы, которые действительны в шаблонах, но не в правилах, есть внутренние состояния, которые справляются с этой задачей. Это заставило задуматься: правила должны быть в состоянии указывать средства для облегчения совместного использования подправил.
Аллен Кларк Коупленд-младший
... это должно быть довольно просто перенести в автоматизацию, но потребует, чтобы автоматизация имела условия на основе состояния. Я поработаю над этим и вернусь к вам. ANTLR использует автоматизацию конечных состояний для обработки циклов, скажем, «T» *, где, как я буду использовать, для обработки большей части процесса синтаксического анализа, поскольку сокращения должны быть более чистыми, чем состояния, когда в правиле более 800 вариантов (это приведет к увеличению быстро, как спагетти-код в стандартной форме if / else.)
Аллен Кларк Коупленд-младший
0

Грамматика не должна иметь ограничений, таких как «не оставлять рекурсивные правила». Смешно, что инструменты, широко используемые сегодня, имеют это и могут понимать только грамматику сосания LL - почти через 50 лет после того, как yacc сделал это правильно.

Пример правильной рекурсии (с использованием синтаксиса yacc):

list: 
      elem                  { $$ = singleton($1); }
    | elem ',' list         { $$ = cons($1, $2);  }
    ;

Пример левой рекурсии (с использованием yacc synatx):

funapp:
    term                    { $$ = $1; }
    | funapp term           { $$ = application($1, $2); }
    ;

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

Можно ожидать от продвинутых инструментов, что они поддерживают естественный способ записывать вещи, вместо того, чтобы требовать, чтобы один «рефакторинг» все было влево / вправо рекурсивно, навязывая инструмент одному.

Ingo
источник
Да, приятно не иметь таких произвольных ограничений. Однако, что является примером левой рекурсии, которая не может быть заменена оператором повторения (таким как регулярные выражения *или +квантификаторы)? Я свободно признаю, что мои знания в этой области ограничены, но я никогда не сталкивался с использованием левой рекурсии, которая не может быть преобразована в повторение. И я обнаружил, что версия с повторениями также более понятна (хотя это всего лишь личные предпочтения).
1
@MattFenwick Смотрите мои изменения. Обратите внимание, что синтаксическая директива приводит к простым и естественным семантическим действиям (например) для создания синтаксического дерева. Хотя с повторением (которого нет в yacc, btw), я думаю, вам часто нужно проверять, есть ли у вас пустой список, синглтон и т. Д.
Ingo
Спасибо за ответ. Я думаю, что теперь я понимаю лучше - я бы предпочел записывать эти примеры как list = sepBy1(',', elem)и funapp = term{+}(и, конечно, sepBy1и +было бы реализовано с точки зрения рекурсии влево / вправо и создавать стандартные синтаксические деревья). Так что не то, чтобы я думал, что левая и правая рекурсия плохие, просто я чувствую, что они низкоуровневые и хотели бы использовать абстракцию более высокого уровня, где это возможно, чтобы прояснить ситуацию. Еще раз спасибо!
1
Всегда пожалуйста @MattFenwick. Но тогда это может быть дело вкуса. Для меня рекурсия - это (по крайней мере, в контексте языков, которые по своей природе являются рекурсивными или совершенно неинтересными), более естественный способ думать об этом. Кроме того, дерево является рекурсивной структурой данных, поэтому я не вижу необходимости возвращаться к итерации для имитации рекурсии. Но, конечно, предпочтения разные.
Инго