висит еще

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

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

if a then s
if b then s1 else s2

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

if a then if b then s else s2

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

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

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

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

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

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

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

Как избежать двусмысленности за счет изменения синтаксиса

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

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

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

Примеры

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

С

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

 statement = ...
    | selection-statement

 selection-statement = ...
    | IF ( expression ) statement
    | IF ( expression ) statement ELSE statement

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

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

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

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

или:

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

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

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

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

statement: open_statement
         | closed_statement
         ;

open_statement: IF '(' expression ')' statement
              | IF '(' expression ')' closed_statement ELSE open_statement
              ;

closed_statement: non_if_statement
                | IF '(' expression ')' closed_statement ELSE closed_statement
                ;

non_if_statement: ...
                ;

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

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

statement: open_statement
         | closed_statement
         ;

open_statement: IF '(' expression ')' statement
              | IF '(' expression ')' closed_statement ELSE open_statement
              | WHILE '(' expression ')' open_statement
              ;

closed_statement: simple_statement
                | IF '(' expression ')' closed_statement ELSE closed_statement
                | WHILE '(' expression ')' closed_statement
                ;

simple_statement: ...
                ;

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

statement: open_statement
         | closed_statement
         ;

open_statement: IF '(' expression ')' closed_statement
              | IF '(' expression ')' open_statement
              | IF '(' expression ')' closed_statement ELSE open_statement
              | WHILE '(' expression ')' open_statement
              ;

closed_statement: simple_statement
                | IF '(' expression ')' closed_statement ELSE closed_statement
                | WHILE '(' expression ')' closed_statement
                ;

simple_statement: ...
                ;

С помощью этой грамматики утверждение if (a) if (b) c else d можно анализировать только одним способом, потому что другая интерпретация ( if (a) {if (b) c} else d) производится как

statement
open_statement
IF '(' expression ')' closed_statement ELSE open_statement
'if' '(' 'a' ')' closed_statement 'else' 'd'

и затем синтаксический анализ не удается сопоставить closed_statement на «если (b) c». Попытка с closed_statement терпит неудачу таким же образом. Другой разбор, if (a) {if (b) c else d}) удается:

statement
open_statement
IF '(' expression ')' closed_statement
IF '(' a ')' (IF '(' expression ')' closed_statement ELSE closed_statement)
IF '(' a ')' (IF '(' b ')' c ELSE 'd')

См. также

• Лексер хак
• Самый неприятный разбор