Формальный метод для семантического анализа в компиляторе

Question

Я знаю, что существует формализм, называемый атрибутной грамматикой, и метод неформализма, называемый синтаксически-ориентированным переводом, но первый неэффективен, а второй трудно автоматизировать.

Существует ли другой недавний формализм о семантическом анализе?

Answer 1

OP предполагает, что "грамматики атрибутов" неэффективны, а синтаксически-ориентированный перевод трудно автоматизировать. Ниже я предлагаю доказательство, показывающее иное, назовите несколько других семантических систем и предложите, как они могут быть интегрированы.

Наш инструментарий реинжиниринга программного обеспечения DMS поддерживает обе эти операции и многое другое.

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

Учитывая (DMS) грамматическое правило:

  LHS = RHS1 ... RHSN ;

один пишет правило грамматики атрибута DMS для вычисления грамматики именованного атрибута Pass1 (по практическим причинам может быть много разных проходов, некоторые даже создают результаты друг друга) в виде:

  <<Pass1>>:  {  LHS.propertyI=fn1(RHSx.propertyY,...);
                 ...
                 RHSa.propertyB=fn2(RHSp.propertyQ,...);
                 ...
              }

для набора свойств (произвольного типа), связанных с каждым элементом грамматики, в левой или правой части правила грамматики, с использованием произвольных функций fnI, определенных для задействованных типов, реализованных на базовом (параллельном) языке DMS, PARLANSE. DMS вычисляет потоки данных по набору правил и определяет вычисление частичного порядка (параллельного), которое выполняет вычисление, и компилирует его в код PARLANSE для выполнения. Результатом вычисления атрибута является дерево, украшенное вычисленными свойствами.

Осторожно, однажды должна быть возможность определить денотационную семантику языка, вычисляемого по грамматике атрибута. Одним из ключевых понятий в DS является понятие "среда", которое отображает идентификаторы на типы и, возможно, символические значения. (Первый традиционно называется таблицей символов). В узлах AST, которые вводят новые области, можно написать функцию атрибута, которая создала новую среду, путем объединения родительской среды с вновь введенными идентификаторами, и передать ее от узла AST его дочерним элементам, например, для правила

exp = 'let' ID '=' exp1 'in' exp2;

можно закодировать правило грамматики атрибута:

<<Denotation>>: {
     exp2.env = augment_environment(exp.env,
                                    new_variable_and_value_pair(name(ID.),
                                                                exp1.value));
     exp.value=exp2.value;
               }

Я не уверен, что ОП означает (грамматики атрибутов) "неэффективно". Мы использовали грамматики атрибутов DMS для вычисления семантических свойств (разрешение имен и типов) для всего C++14. Хотя такое определение является огромным по большинству академических бумажных стандартов, так оно и есть, потому что сам C++ 14 является огромным и удивительным беспорядком ("верблюд за комитетом"). Несмотря на это, наша грамматика атрибутов, кажется, работает достаточно хорошо. Что еще более важно, он достаточно мощный, чтобы построить его очень маленькая команда (в отличие от масштаба "команды", поддерживающей Clang).

DMS также предоставляет возможность кодировать преобразования "источник-источник" ("переписывает") с использованием поверхностного синтаксиса исходного и целевого (если он отличается от исходного) языков в форме "если вы видите это, замените его этим ", Эти переписывания применяются к деревьям разбора, чтобы обеспечить пересмотренные деревья; prettyprinter ("анти-парсер"), предоставляемый DMS, может затем восстановить исходный код для целевого языка. Если кто-то ограничивает себя в переписывании, которое в точности совпадает с исходным AST, он получает "синтаксически-ориентированный перевод". OP может утверждать, что это (синтаксически направленный перевод) трудно автоматизировать; Я бы согласился, но работа сделана и доступна. ОП должна решить, какие правила она хочет определить и выполнить.

Правила перезаписи DMS имеют вид:

 rule rule_name(parameter1:syntax_category1, ... parameterN...)
   :  source_syntax_category -> target_syntax_category
   "  <text in source language>  "
  ->
   "  <text in target language> "
  if  condition_of_matched_source_pattern;

где параметры являются заполнителями для поддеревьев с синтаксическим типом, правило отображает дерево типа source_syntax_category -> target_syntax_category (часто того же самого), а "..." - это мета-кавычки, обернутые вокруг поверхностного синтаксиса с пометкой "\" встроенные экраны для параметров, где это необходимо. Фрагменты кода в мета-кавычках интерпретируются как спецификации для деревьев (с использованием того же механизма синтаксического анализа, который читает исходный код); это не строковое совпадение. Пример:

  rule simplify_if_then_else(c:condition,t:then_clause,e:else_clause)
     statement->statement
  =  " if \c then \t else \e "
  -> " \t "
  if c == "true";

Обобщение проверки (выше чисто синтаксической), которая является более "семантической", будет

  ...
  if can_determine_is_true(c);

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

Я предположил, что предикат поддержки, определенный в DMS, "can_determine_if_true". Это просто немного пользовательского кода PARLANSE.

Однако, поскольку перезаписи преобразуют одно дерево в другое, можно применять произвольно длинный / сложный набор правил преобразования повторно ко всему дереву. Это дает DMS переписывает всю мощь системы переписывания Post (string [generalized to tree]), что позволяет использовать Turing. Технически вы можете произвести любое произвольное преобразование исходного дерева с достаточным количеством преобразований. Обычно каждый использует другие функции DMS, чтобы немного облегчить написание преобразований; например, правило перезаписи может обращаться к результату вычисления грамматики конкретного атрибута, чтобы "легко" использовать информацию из "далекого дерева" (отдельные правила перезаписи всегда имеют фиксированный, максимальный "радиус").

DMS предоставляет множество дополнительных вспомогательных механизмов, помогающих создавать графы потоков управления и / или вычислять потоки данных с помощью эффективных параллельных решателей. У DMS также есть широкий выбор доступных интерфейсов для различных языков, таких как C, C++14, Java1.8, IBM Enterprise COBOL, ... доступных для того, чтобы инженер по инструментам мог сосредоточиться на создании необходимого инструмента, а не на борьба за создание парсера с нуля (только чтобы обнаружить, что нужно жить Life After Sarsing).

Если OP интересуется недавним обзором семантики другого стиля (структурированной операционной), он может обратиться к примечаниям к курсу по семантике языков программирования. Мы утверждаем, что методы в таких статьях могут быть реализованы поверх DMS, если кто-то хочет.

Можно составить длинный список различных академических инструментов, которые реализуют (некоторые) из этих идей. Большинство из них являются инструментами исследования и не являются зрелыми. Одна из таких исследовательских систем, JastAdd, представляет собой систему оценки грамматики атрибутов, и я слышал, что она отличается возможностями и производительностью, но у меня нет конкретного опыта работы с ней.