Проект компилятора: Является ли "переменная не объявлена" синтаксической или семантической ошибкой?

Question

Возникает ли такой тип ошибки во время проверки типа или когда анализируется ввод? По какому типу следует исправлять ошибку?

Answer 1

На мой взгляд, это семантическая ошибка, потому что ваш язык очень хорошо разбирается, даже если вы используете идентификатор, который вы ранее не связывали - т.е. синтаксический анализ только проверяет правильность сформированной программы. Семантический анализ фактически проверяет, что ваша программа имеет правильное значение - например, привязки, область видимости или типирование. Как сказал @pst, вы можете выполнять проверку области во время синтаксического анализа, но это деталь реализации. Старые компиляторы AFAIK раньше делали это, чтобы сэкономить время и пространство, но я думаю, что сегодня такой подход сомнителен, если у вас нет жестких ограничений производительности / памяти.

Answer 2

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

Значение, если таковое имеется, каждого является семантической проблемой. Фрэнк деРемер назвал такие проблемы "статической семантикой".

Answer 3

На мой взгляд, это не строго синтаксическая ошибка - не семантическая. Если бы я реализовал это для статически типизированного, скомпилированного языка (например, C или C++), то я бы не ставил проверку в парсер (потому что парсер практически неспособен проверить эту ошибку), а скорее в генератор кода (часть компилятора, которая обходит абстрактное синтаксическое дерево и превращает его в ассемблерный код). Так что, на мой взгляд, это лежит между синтаксическими и семантическими ошибками: это ошибка, связанная с синтаксисом, которую можно проверить только с помощью семантического анализа кода.

Однако, если мы рассмотрим примитивный язык сценариев, где AST выполняется напрямую (без компиляции в байт-код и без JIT), то это сама функция оценщика / исполнителя, которая обходит AST и находит необъявленную переменную - в этом случае это будет ошибка во время выполнения. Разница заключается в том, что подпрограмма "AST_walk()" находится в разных частях жизненного цикла программы (время компиляции и время выполнения), если язык является сценарием или скомпилированным.

Answer 4

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

Обычный способ справиться с этим - включить информацию о символах в таблицу символов, чтобы анализ мог использовать эту информацию.

Вот несколько примеров того, как тип идентификатора влияет на синтаксический анализ:

C / C++

Классический кейс:

(a)-b;

В зависимости от aЭто либо приведение, либо вычитание:

#include <stdio.h>

#if TYPEDEF
typedef double a;
#else
double a = 3.0;
#endif

int main() {
  int b = 3;
  printf("%g\n", (a)-b);
  return 0;
}

Следовательно, если a не был объявлен вообще, компилятор должен отклонить программу как синтаксически некорректную (и это именно то слово, которое стандарт использует).

XML

Это просто:

<block>Hello, world</blob>

Это неправильно сформированный XML, но его нельзя обнаружить с помощью CFG. (Тем не менее, все синтаксические анализаторы XML будут правильно отклонять его как неправильно сформированные.) В случае HTML/SGML, где конечные теги могут быть опущены при некоторых четко определенных обстоятельствах, синтаксический анализ сложнее, но, тем не менее, детерминирован; Опять же, точное объявление тега будет определять синтаксический анализ допустимого ввода, и легко придумать входные данные, которые анализируются по-разному в зависимости от объявления.

английский

ОК, не язык программирования. У меня есть много других примеров языков программирования, но я подумал, что этот может вызвать другие интуиции.

Рассмотрим два грамматически правильных предложения:

The sheep is in the meadow.
The sheep are in the meadow.

Теперь, что насчет:

The cow is in the meadow.
(*) The cow are in the meadow.

Второе предложение понятно, хотя и неоднозначно (неправильное существительное или глагол?), Но оно, безусловно, не грамматически правильно. Но чтобы знать это (и другие подобные примеры), мы должны знать, что sheep имеет безымянное множественное число. Действительно, у многих животных есть немаркированные множественные числа, поэтому я признаю все следующее грамматическим:

The caribou are in the meadow.
The antelope are in the meadow.
The buffalo are in the meadow.

Но определенно нет:

(*) The mouse are in the meadow.
(*) The bird are in the meadow.

и т.п.

---

Кажется, что существует распространенное заблуждение, что поскольку синтаксический анализатор использует синтаксический анализатор без контекста, этот синтаксический анализ ограничен синтаксическим анализом грамматики без контекста. Это просто неправда.

В случае C (и семейства) анализатор синтаксиса использует таблицу символов, чтобы помочь ему разобрать. В случае XML он использует стек тегов, а в случае обобщенного SGML (включая HTML) он также использует объявления тегов. Следовательно, анализатор синтаксиса, рассматриваемый в целом, является более мощным, чем CFG, который является лишь частью анализа.

Тот факт, что данная программа проходит синтаксический анализ, не означает, что она семантически верна. Например, синтаксический анализатор должен знать, a это тип или нет для того, чтобы правильно разобрать (a)-b, но это не должно знать, возможно ли на самом деле приведение, в случае, если это a это тип, или что a а также b может быть существенно вычтено, в случае, если a переменная Эти проверки могут происходить во время анализа типов после построения дерева разбора, но они все еще являются ошибками во время компиляции.