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

Question

Я создаю компилятор с Lex и YACC (на самом деле Flex и Bison). Язык допускает неограниченные прямые ссылки на любой символ (например, C #). Проблема в том, что невозможно разобрать язык, не зная, что такое идентификатор.

Единственное известное мне решение состоит в том, чтобы лексировать весь исходный код, а затем выполнить анализ "в ширину", чтобы вещи более высокого уровня, такие как объявления классов и объявления функций, анализировались перед функциями, которые их используют. Однако это заняло бы большой объем памяти для больших файлов, и было бы трудно справиться с YACC (мне пришлось бы создавать отдельные грамматики для каждого типа объявления / тела). Мне также пришлось бы написать лексер (что не так уж и сложно).

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

Есть ли хорошие решения этой проблемы? Как это обычно делается в компиляторах для таких языков, как C # или Java?

Answer 1

Это вполне возможно разобрать. Хотя между идентификаторами и ключевыми словами существует неоднозначность, lex с радостью справится с этим, предоставив ключевым словам приоритет.

Я не вижу других проблем. Вам не нужно определять, действительны ли идентификаторы на этапе анализа. Вы создаете либо дерево синтаксического анализа, либо абстрактное синтаксическое дерево (разница невелика, но не имеет значения для целей этого обсуждения) во время синтаксического анализа. После этого вы создаете свои вложенные структуры таблиц символов, выполняя проход по AST, который вы сгенерировали во время анализа. Затем вы делаете еще один проход по AST, чтобы проверить правильность используемых идентификаторов. Затем выполните один или несколько дополнительных разборов по AST для генерации выходного кода или другой промежуточной структуры данных, и все готово!

РЕДАКТИРОВАТЬ: Если вы хотите увидеть, как это делается, проверьте исходный код для компилятора Mono C #. На самом деле это написано на C #, а не на C или C ++, но использует порт .NET Jay, который очень похож на yacc.

Answer 2

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

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

Что касается создания нескольких грамматик, немного повеселится с препроцессором в файле yacc, и вы сможете сделать их все из одного исходного источника