Еще болтается - Dangling else

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

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

if a then s
if b then s1 else s2

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

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)

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

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

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

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

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

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

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

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

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

Примеры

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

C

В языке 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 ')' simple_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" не удается: 

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

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

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

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