Dangling else

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

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

ifa then s ifb then s1 else s2

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

ifa затем ifb затем s else s2

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

ifa затем (ifb затем s) else s2 ifa затем (ifb затем s else s2)

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

• 1 Избегание двусмысленности при сохранении синтаксиса
• 2 Избегание двусмысленности путем изменения синтаксиса
• 3 Примеры
  • 3.1 C
• 4 Предотвращение конфликта в парсерах LR
• 5 См. Также
• 6 Ссылки

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

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

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

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

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

• Наличие оператора «end if». Примеры таких языков: ALGOL 68, Ada, Eiffel, PL / SQL и Visual Basic
• Запрещение инструкции, следующей за «then», быть самой «if» ( однако это может быть пара скобок оператора, содержащая только предложение if-then). За этим подходом следует АЛГОЛ 60.
• Требование фигурных скобок (скобок), когда "else" следует за "if". Это фактически верно в Python a s его правила отступа ограничивают каждый блок, а не только те, что указаны в операторах «if».
• Требование, чтобы каждое «if» было соединено с «else». Чтобы избежать аналогичной проблемы, связанной с семантикой, а не синтаксисом, Racket отклоняется от Scheme, считая ifбез запасного предложения ошибкой, эффективно различая условные выражения (т. е. if) из условных операторов (т. е. whenи кроме, которые не имеют запасных предложений).
• Использование разных ключевых слов для одноальтернативный и двухальтернативный «если» утверждения. S-algol использует if e do sдля одноальтернативного случая и если e1, то e2 else e3для общего случая.
• Безоговорочно требовать фигурные скобки, например Swift и Modula-2. Чтобы уменьшить возникающий беспорядок, Modula-2 устраняет открыватель блоков на нефункциональных уровнях.

Далее следуют конкретные примеры.

C

В C грамматика частично читается:

утверждение =... | оператор выбора оператор выбора =... | IF (выражение) оператор | IF (выражение) оператор ELSE оператор

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

if (a) if (b) s; else s2;

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

if (a) {if (b) s; else s2; }

или:

if (a) {if (b) s; } else s2;

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

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

инструкция: 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_statement IF '(' выражение ')' closed_statement ELSE open_statement 'if' '( '' a '') 'closed_statement' else '' d '

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

• Взлом лексера