Это часть серии вопросов, посвященных проекту, связанному с проектом Abstraction Project, целью которого является абстракция концепций, используемых в языковом дизайне, в форме фреймворка. Родственный проект называется OILexer, целью которого является создание синтаксического анализатора из файлов грамматики без использования внедрения кода в совпадениях.
Некоторые другие страницы, связанные с этими вопросами, связанные со структурной типизацией, можно посмотреть здесь , а простоту использования можно найти здесь . Мета-тема, связанная с запросом о фреймворке и подходящем месте для публикации, может быть найдена здесь .
Я подхожу к тому, что собираюсь начать извлечение дерева разбора из заданной грамматики, за которым следует парсер рекурсивного спуска, который использует DFA для распознавания прямых путей (аналогично LL (*)) в ANTLR 4, поэтому я подумал, что я открою это, чтобы получить представление.
Какие компиляторы идеальны в компиляторе парсера?
Итак, вот краткий обзор того, что реализовано:
- Шаблоны
- Посмотрите вперед прогнозирование, зная, что действительно в данный момент.
- Правило «Делитерализация» берет литералы в правилах и определяет, из какого они токена.
- Недетерминированные автоматы
- Детерминированные автоматы
- Простой лексический конечный автомат для распознавания токенов
- Методы автоматизации токенов:
- Сканирование - полезно для комментариев: Комментарий: = "/ *" Сканирование ("* /");
- Subtract - полезно для идентификаторов: Identifier: = Subtract (IdentifierBody, Keywords);
- Гарантирует, что идентификатор не принимает ключевые слова.
- Кодировать - кодирует автоматизацию в виде серии X с количеством базовых N переходов.
- UnicodeEscape: = "\\ u" BaseEncode (IdentifierCharNoEscape, 16, 4);
- Делает Unicode escape в шестнадцатеричном, с шестнадцатеричным 4-переходом. Разница между этим и: [0-9A-Fa-f] {4} заключается в том, что автоматизация с Encode ограничивает допустимый набор шестнадцатеричных значений областью действия IdentifierCharNoEscape. Так что, если вы дадите ему \ u005c, версия кодирования не примет значение. Такие вещи имеют серьезное предостережение: используйте экономно. В результате автоматизация может быть довольно сложной.
- UnicodeEscape: = "\\ u" BaseEncode (IdentifierCharNoEscape, 16, 4);
Что не реализовано, так это генерация CST, мне нужно настроить детерминированные автоматы, чтобы перенести соответствующий контекст, чтобы заставить это работать.
Для всех, кто интересуется, я загрузил довольно напечатанную оригинальную форму проекта T * y♯ . Каждый файл должен ссылаться на каждый другой файл, я начал ссылаться в отдельных правилах, чтобы следовать им, но это заняло бы слишком много времени (было бы проще автоматизировать!)
Если нужно больше контекста, пожалуйста, напишите соответственно.
Изменить 5-14-2013 : я написал код для создания графиков GraphViz для конечных автоматов в рамках данного языка. Вот орграф GraphViz AssemblyPart . Члены, связанные в описании языка, должны иметь rulename.txt в соответствующей папке с орграфом для этого правила. Некоторое описание языка изменилось с момента публикации примера, это связано с упрощением грамматики. Вот интересное графическое изображение .
источник
Ответы:
Это отличный вопрос.
В последнее время я много работаю над разбором, и ИМХО некоторые из ключевых особенностей:
программный API - так что его можно использовать из языка программирования, в идеале просто импортировав библиотеку. Он также может иметь GUI или BNF-подобный интерфейс, но программный является ключевым, потому что вы можете повторно использовать свои инструменты, IDE, статический анализ, тестирование, средства абстрагирования языка, знакомство программиста, генератор документации, процесс сборки, и т.д. Кроме того, вы можете в интерактивном режиме играть с крошечными парсерами, что значительно сокращает кривую обучения. Эти причины ставят его на первое место в моем списке «важных функций».
сообщение об ошибке, как упоминал @guysherman. Когда ошибка найдена, я хочу знать, где была ошибка и что происходило, когда она произошла. К сожалению, я не смог найти хороших ресурсов для объяснения того, как генерировать приличные ошибки, когда в игру вступает возвратный путь. (Хотя обратите внимание на комментарий @ Sk-logic ниже).
частичные результаты. Когда синтаксический анализ завершается неудачно, я хочу иметь возможность увидеть, что было успешно проанализировано из той части ввода, которая была до обнаружения ошибки.
абстракция. Вы никогда не сможете встроить достаточное количество функций, и пользователю всегда будет нужно больше, поэтому попытка выяснить все возможные функции заранее обречена на провал. Это то, что вы подразумеваете под шаблонами?
Я согласен с вашей № 2 (прогноз на будущее). Я думаю, что это помогает генерировать хорошие отчеты об ошибках. Это полезно для чего-то еще?
поддержка построения дерева разбора при синтаксическом анализе, возможно:
какая-то регистрация. Я не уверен в этом; может быть, чтобы показать след правил, которые пробовал анализатор, или отследить ненужные токены, такие как пробелы или комментарии, в случае (если) вы хотите использовать токены для генерации HTML-документации.
умение работать с контекстно-зависимыми языками. Не уверен, насколько важен этот вариант - на практике кажется более понятным анализировать расширенный набор языков с контекстно-свободной грамматикой, а затем проверять контекстно-зависимые ограничения в дополнительных последующих проходах.
настраиваемые сообщения об ошибках, чтобы я мог настраивать отчеты об ошибках в определенных ситуациях и, возможно, быстрее понимать и устранять проблемы.
С другой стороны, я не считаю исправление ошибок особенно важным - хотя я не в курсе текущих достижений. Проблемы, которые я заметил, заключаются в том, что потенциальные исправления, которые предоставляют инструменты: 1) слишком много, и 2) не соответствуют фактическим ошибкам, и поэтому не все так полезно. Надеемся, что эта ситуация улучшится (или, возможно, уже сделал это).
источник
У меня нет опыта в языковом дизайне, но я однажды попробовал написать парсер, когда создавал IDE для игрового движка.
На мой взгляд, важными для конечных пользователей являются сообщения об ошибках, которые имеют смысл. Я знаю, что это не особенно ошеломляющий момент, но, следуя за ним в обратном направлении, одним из ключевых последствий этого является то, что вам необходимо избегать ложных срабатываний. Откуда ложные срабатывания? Они происходят от парсера, падающего при первой ошибке и никогда не восстанавливающегося. C / C ++ печально известен этим (хотя новые компиляторы немного умнее).
Так что вам нужно вместо этого? Я думаю, что вместо того, чтобы просто знать, что является / не является действительным в определенный момент, вам нужно знать, как принять то, что не является действительным, и внести минимальные изменения, чтобы сделать его действительным, чтобы вы могли продолжить анализ, не создавая ложных ошибок, связанных с к вашему рекурсивному спуску запутаться. Возможность создания анализатора, который может генерировать эту информацию, не только дает вам очень надежный анализатор, но и открывает некоторые фантастические возможности для программного обеспечения, которое использует анализатор.
Я понимаю, что могу предложить что-то действительно сложное или глупо очевидное, извините, если это так. Если это не та вещь, которую вы ищете, я с удовольствием удалю свой ответ.
источник
Грамматика не должна иметь ограничений, таких как «не оставлять рекурсивные правила». Смешно, что инструменты, широко используемые сегодня, имеют это и могут понимать только грамматику сосания LL - почти через 50 лет после того, как yacc сделал это правильно.
Пример правильной рекурсии (с использованием синтаксиса yacc):
Пример левой рекурсии (с использованием yacc synatx):
Теперь это может быть «реорганизовано» во что-то другое, но в обоих случаях конкретный тип рекурсии - это просто «правильный» способ написать это, поскольку (в примере языка) списки являются рекурсивными справа, в то время как приложение функции остается рекурсивным ,
Можно ожидать от продвинутых инструментов, что они поддерживают естественный способ записывать вещи, вместо того, чтобы требовать, чтобы один «рефакторинг» все было влево / вправо рекурсивно, навязывая инструмент одному.
источник
*
или+
квантификаторы)? Я свободно признаю, что мои знания в этой области ограничены, но я никогда не сталкивался с использованием левой рекурсии, которая не может быть преобразована в повторение. И я обнаружил, что версия с повторениями также более понятна (хотя это всего лишь личные предпочтения).list = sepBy1(',', elem)
иfunapp = term{+}
(и, конечно,sepBy1
и+
было бы реализовано с точки зрения рекурсии влево / вправо и создавать стандартные синтаксические деревья). Так что не то, чтобы я думал, что левая и правая рекурсия плохие, просто я чувствую, что они низкоуровневые и хотели бы использовать абстракцию более высокого уровня, где это возможно, чтобы прояснить ситуацию. Еще раз спасибо!