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

Question

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

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

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

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

Answer 1

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

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

EDIT: Если вы хотите посмотреть, как это делается, проверьте исходный код для компилятора Mono C#. Это фактически написано на C#, а не на C или C++, но оно использует порт .NET Jay, который очень похож на yacc.

Answer 2

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

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

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