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

Question

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

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

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

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

Answer 1

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

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

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

Answer 2

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

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

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