Как мне реализовать прямые ссылки в компиляторе?
Я создаю компилятор с Lex и YACC (на самом деле Flex и Bison). Язык допускает неограниченные прямые ссылки на любой символ (например, C#). Проблема в том, что невозможно разобрать язык, не зная, что такое идентификатор.
Единственное известное мне решение состоит в том, чтобы лексировать весь исходный код, а затем выполнить анализ "в ширину", чтобы такие вещи более высокого уровня, как объявления классов и объявления функций, анализировались перед функциями, которые их используют. Однако для больших файлов это заняло бы большой объем памяти, и было бы трудно справиться с YACC (мне пришлось бы создавать отдельные грамматики для каждого типа объявления / тела). Я также должен был бы написать лексер (что не так уж и сложно).
Меня не волнует эффективность (хотя это все еще важно), потому что я собираюсь переписать компилятор сам по себе, когда я закончу его, но я хочу, чтобы эта версия была быстрой (так что если есть какие-то быстрые общие методы, которые не могут быть выполнены в Lex/YACC, но могут быть сделаны вручную, пожалуйста, предложите их также). Так что сейчас простота разработки является наиболее важным фактором.
Есть ли хорошие решения этой проблемы? Как это обычно делается в компиляторах для языков, таких как C# или Java?
2 ответа
Это вполне возможно разобрать. Хотя между идентификаторами и ключевыми словами существует неоднозначность, lex с радостью справится с этим, предоставив ключевым словам приоритет.
Я не вижу других проблем. Вам не нужно определять, действительны ли идентификаторы на этапе анализа. Вы создаете либо дерево синтаксического анализа, либо абстрактное синтаксическое дерево (разница невелика, но не имеет значения для целей этого обсуждения) во время синтаксического анализа. После этого вы создаете свои вложенные структуры таблиц символов, выполняя проход по AST, который вы сгенерировали во время анализа. Затем вы делаете еще один проход по AST, чтобы проверить правильность используемых идентификаторов. Затем выполните один или несколько дополнительных разборов по AST для генерации выходного кода или другой промежуточной структуры данных, и все готово!
РЕДАКТИРОВАТЬ: Если вы хотите увидеть, как это делается, проверьте исходный код для компилятора Mono C#. На самом деле это написано на C#, а не на C или C++, но в нем используется.NET-порт Jay, который очень похож на yacc.
Один из вариантов - работать с прямыми ссылками, просто сканируя и кэшируя токены до тех пор, пока вы не наткнетесь на то, с чем умеете работать (что-то вроде "исправления ошибок в режиме" паники ")". После того, как вы запустили полный файл, вернитесь назад и попробуйте проанализировать биты, которые раньше не анализировались.
Что касается необходимости писать лексер; не используйте lex для генерации обычного синтаксического анализатора и просто читайте из него рукописный шим, который позволяет вам вернуться назад и передать анализатор из кэша, а также узнать, что делает lex.
Что касается создания нескольких грамматик, немного повеселитесь с препроцессором в файле yacc, и вы сможете сделать их все из одного исходного источника.