Абстрактное синтаксическое дерево - Фазы компилятора
На вход семантического анализатора входит AST (синтаксическое дерево асбракта). У меня вопрос: вывод семантического анализатора - это тот же оформленный AST, или должно быть новое дерево? Как называется это дерево? Чтобы создать это новое дерево, могу ли я использовать шаблон посетителей? В приведенном ниже примере новый узел был создан внутри AST (inttofloat). Поэтому я считаю, что всегда должно быть создано новое дерево.
1 ответ
Хотя это старый вопрос, это стандартный учебный материал по компиляции, поэтому, возможно, нужен записанный ответ.
На ваш вопрос нет единственного ответа, потому что нет единого способа реализации компилятора. Не существует идеального и правильного ответа, который, как полагают многие студенты, должен быть всегда. Экзаменаторы часто задают такой вопрос студентам, чтобы показать, что понимание и понимание не могут быть продемонстрированы наизусть памятью одного ответа, который, как я полагаю, ищется здесь.
Компиляторы могут быть реализованы как один проход или несколько проходов; абстрактное синтаксическое дерево может быть структурой данных в памяти, или оно может быть записано более существенным образом путем вывода в файл, который в самых ранних компиляторах имел физическое представление, будучи перфорированным на бумажную ленту или карты! Если бы данные, которые перемещались между фазами компилятора (будь то токены, деревья абстрактного синтаксиса, промежуточный код или целевой код), выводились, таким образом, набор карточек, содержащих одно дерево абстрактного синтаксиса, и набор карточек, содержащих другую абстрактную -syntax-tree - это разные деревья или оригинальное дерево и другая версия этого дерева? Даже тогда, с философской точки зрения, вы можете утверждать, что в любом случае.
В современных компиляторах данные могут (часто это происходит) перемещаться между фазами по каналам между несколькими параллельными задачами, образуя различные компоненты компилятора; затем снова у нас есть одно дерево на одной трубе и другое дерево на другой трубе.
Однако, если мы реализовали компилятор в одной программе, работающей в одном процессе, нам не нужно иметь одно дерево и одно дерево. Все части компилятора могут видеть все хранилища. После завершения синтаксического анализа в памяти появляется древовидная структура, которая может быть обработана семантическим анализатором. Поскольку синтаксический анализатор больше никогда не понадобится, и семантический анализатор никогда не будет работать снова после обработки синтаксического дерева, нет необходимости создавать другое дерево. Более эффективно обходить дерево в памяти как структуру данных и изменять дерево на месте. В вашем примере семантический анализатор вставляет intofloat узла в дерево, чтобы представить преобразование типов, требуемое в этой точке кода. Поэтому в этом случае мы можем сказать, что у нас есть одно единственное дерево, которым манипулируют все фазы компилятора.
Теперь следует рассмотреть добавленный узел intofloat. Возможно, вы предположили, что это новый тип или атрибут объекта узла дерева. Это может быть не так. Это можно считать формой оператора, такой как узлы =, + и *, которые уже существуют. Это может быть уже в наборе доступных операторов. Все, что сделал семантический анализ, - это явное добавление оператора к дереву, который мог бы быть явно включен в код в первую очередь. Никакая новая форма узла фактически не создается, только другой экземпляр существующего типа узла. Это может быть так, как вы себе это представляете, или нет. Ни одна из версий не является правильной или неправильной.
Вопрос о шаблонах посетителей ортогонален вопросу о компиляторе. Шаблоны посетителей в основном являются особенностью объектно-ориентированного программирования и языков. Вы можете реализовать семантический анализатор, используя шаблон посетителя на дереве, или не можете, как указано в последнем абзаце. Это может быть сделано в любом случае, и опять же нет единого правильного ответа. Именно обсуждение роли шаблонов посетителей в таком вопросе может быть использовано для демонстрации как понимания шаблонов посетителей и их применения, так и цели и роли абстрактных синтаксических деревьев. Таким образом, если вы ищете один правильный ответ (да / нет), он не существует. Существует только дискуссия.
Посредством обсуждения и сравнения того, что означают слова в вопросе, мы можем проявить понимание.
Если это часть экзаменационного задания, то это стремление к пониманию, а не единственный волшебный ответ.