Болтается еще - Dangling else

В болтается еще проблема в компьютерное программирование в котором необязательное предложение else в if – then (–else) оператор приводит к неоднозначности вложенных условных выражений. Формально ссылка контекстно-свободная грамматика языка двусмысленный, что означает, что существует более одного правильного дерево синтаксического анализа.

Во многих языки программирования можно написать условно исполняемый код в двух формах: форма if-then и форма if-then-else - предложение else является необязательным:

если а тогда sесли б тогда s1 еще s2

Это приводит к двусмысленности в интерпретации, когда есть вложенные операторы, особенно когда форма «если-то» выглядит как s1 в форме if-then-else:

если а тогда если б тогда s еще s2

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

если а тогда (если б тогда s) еще s2если а тогда (если б тогда s еще s2)

Проблема с болтающимся остальным относится к АЛГОЛ 60,[1] и был разрешен различными способами в последующих языках. В Парсеры LR, висящее else является архетипическим примером конфликт смены-уменьшения.

Избегайте двусмысленности при сохранении синтаксиса

Это проблема, которая часто возникает в конструкция компилятора, особенно разбор без сканирования. При работе с висячим else условием является присоединение else к ближайшему оператору if,[2] позволяя, в частности, создавать недвусмысленные контекстно-свободные грамматики. Языки программирования, такие как Паскаль,[3] C[4] и Java[5] следуйте этому соглашению, чтобы не было двусмысленности в семантике язык, хотя использование генератора парсера может привести к неоднозначному грамматики. В этих случаях альтернативная группировка выполняется явными блоками, такими как начало ... конец в Паскале[6] и {...} в C.

В зависимости от подхода к построению компилятора, можно предпринять различные корректирующие действия, чтобы избежать двусмысленности:

  • Если парсер производится SLR, LR (1) или LALR Парсер LR генератор, программист часто будет полагаться на сгенерированную функцию синтаксического анализатора, предпочитая сдвиг сокращению всякий раз, когда возникает конфликт.[2] В качестве альтернативы, грамматику можно переписать, чтобы устранить конфликт, за счет увеличения размера грамматики (см. ниже ).
  • Если синтаксический анализатор написан от руки, программист может использовать однозначный контекстно-свободная грамматика. В качестве альтернативы можно полагаться на неконтекстно-свободную грамматику или анализ грамматики выражений.

Избегайте двусмысленности за счет изменения синтаксиса

Проблема также может быть решена путем явного указания ссылки между else и его if в синтаксисе. Обычно это помогает избежать человеческих ошибок.[7]

Возможные решения:

  • Наличие оператора "конец, если". Примеры таких языков: АЛГОЛ 68, Ада, Эйфель, PL / SQL и Visual Basic
  • Запрещение оператору, следующему за «then», быть самим «if» (однако это может быть пара скобок оператора, содержащая только предложение if-then). Этому подходу следуют АЛГОЛ 60.[8]
  • Требование фигурных скобок (скобок), когда "else" следует за "if".[9] Это действительно так в Python поскольку его правила отступа ограничивают каждый блок, а не только те, что указаны в операторах «if».
  • Требование, чтобы каждое «если» было соединено с «иначе». Чтобы избежать подобной проблемы с семантикой, а не синтаксисом, Ракетка отклоняется от Схема рассматривая если без запасного предложения, чтобы быть ошибкой, эффективно различая условные выражения (т.е. если) от условного заявления (т.е. когда и если только, в которых нет резервных предложений).
  • Использование разных ключевых слов для одно- и двухальтернативных операторов if. S-алгол использует если я сделаю с для одноальтернативного случая и если e1, то e2, иначе e3 для общего случая.[10]
  • Безоговорочно требовать скобки, например Swift и Модула-2. Чтобы уменьшить беспорядок, Модула-2 устраняет открыватель блоков на нефункциональных уровнях.

Примеры

Ниже приводятся конкретные примеры.

C

В C, грамматика частично гласит:

 заявление = ... | оператор выбора оператор выбора = ... | IF (выражение) оператор | IF (выражение) инструкция ELSE инструкция

Таким образом, без дополнительных правил, утверждение

если (а) если (б) s; еще s2;

можно неоднозначно проанализировать, как если бы это было либо:

если (а){  если (б)    s;  еще    s2;}

или:

если (а){  если (б)    s;}еще  s2;

На практике в C первое дерево выбирается путем связывания еще с ближайшим если.

Как избежать конфликта в парсерах LR

Приведенный выше пример можно переписать следующим образом, чтобы устранить двусмысленность:

заявление: open_statement | closed_statement; open_statement: IF '(' выражение ')' инструкция | IF '(' выражение ')' closed_statement ELSE open_statement; closed_statement: non_if_statement | IF '(' выражение ')' closed_statement ELSE closed_statement; non_if_statement: ...;

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

Однако мы даем грамматику, которая включает в себя как операторы if, так и while.

заявление: open_statement | closed_statement; open_statement: IF '(' выражение ')' инструкция | IF '(' выражение ')' closed_statement ELSE open_statement | WHILE '(' выражение ')' open_statement; closed_statement: simple_statement | IF '(' выражение ')' closed_statement ELSE closed_statement | WHILE '(' выражение ')' closed_statement; simple_statement: ...;

Наконец, мы даем грамматику, запрещающую неоднозначные операторы IF.

заявление: open_statement | closed_statement; open_statement: IF '(' выражение ')' простое_выражение | IF '(' выражение ')' open_statement | IF '(' выражение ')' closed_statement ELSE open_statement | WHILE '(' выражение ')' open_statement; closed_statement: simple_statement | IF '(' выражение ')' closed_statement ELSE closed_statement | WHILE '(' выражение ')' closed_statement; simple_statement: ...;

С этим грамматическим синтаксическим анализом "if (a) if (b) c else d" не удается:

оператор open_statementIF '(' выражение ')' closed_statement ELSE open_statement'if '' ('' a '') 'closed_statement' else '' d '

а затем синтаксический анализ не пытается сопоставить closed_statement на «если (б) в». Попытка с closed_statement терпит неудачу точно так же.

Смотрите также

использованная литература

  1. ^ Абрахамс, П. В. (1966). «Окончательное решение проблемы Dangling else Алгола 60 и родственных языков». Коммуникации ACM. 9 (9): 679. Дои:10.1145/365813.365821.
  2. ^ а б 5.2 Конфликты сдвига / уменьшения от Операционная система GNU интернет сайт
  3. ^ ISO 7185: 1990 (Паскаль) 6.8.3.4: Оператор if без части else не должен сопровождаться сразу токеном else.
  4. ^ ISO 9899: 1999 (C): 6.8.4.1 (3): «else связан с лексически ближайшим предшествующим, если это разрешено синтаксисом.», Доступно по адресу WG14 N1256, п. 134
  5. ^ «Спецификация языка Java, Java SE 9 Edition, 14.5. Заявления».
  6. ^ Паскаль, Нелл Дейл и Чип Уимс, «Висячие другие», п. 160–161
  7. ^ Двусмысленность висячего else: неконтекстные грамматики семантически непрозрачны
  8. ^ 4.5.1 Условные операторы - синтаксис в П. Науэр (ред.), Пересмотренный отчет по алгоритмическому языку АЛГОЛ 60, CACM 6,1, 1963, стр. 1-17
  9. ^ Неоднозначность свисания else: требуются фигурные скобки, когда следует else, если
  10. ^ Дэви, Энтони Дж. Т .; Рональд Моррисон (1981), Брайан Мик (редактор), Компиляция с рекурсивным спуском, Серия Эллиса Хорвуда в компьютерах и их приложениях, Чичестер, Западный Суссекс: Эллис Хорвуд, стр. 20, ISBN  0-470-27270-8