Оборванных еще проблема в компьютерном программировании , в котором дополнительный еще пункт в если-то (-else) приводит заявление в вложенных условной двусмысленности. Формально справочная контекстно-свободная грамматика языка неоднозначна , то есть существует более одного правильного дерева синтаксического анализа .
Во многих языках программирования можно написать условно выполняемый код в двух формах: форме if-then и форме if-then-else - предложение else является необязательным:
если a, то s, если b, то s1, иначе 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 a then ( if b then s) else s2 if a then ( if b then s else s2)
Проблема зависшего else восходит к АЛГОЛУ 60 , [1] и была решена различными способами в последующих языках. В синтаксических анализаторах LR свисающее else является типичным примером конфликта сдвиг-уменьшение .
Избегайте двусмысленности при сохранении синтаксиса
Это проблема, которая часто возникает при создании компилятора , особенно при анализе без сканирования . Соглашение при работе с висячим else состоит в том, чтобы присоединить else к ближайшему оператору if [2] , в частности, с учетом недвусмысленных контекстно-свободных грамматик. Языки программирования, такие как Pascal, [3] C [4] и Java [5], следуют этому соглашению, поэтому нет двусмысленности в семантике языка , хотя использование генератора синтаксического анализатора может привести к неоднозначным грамматикам . В этих случаях альтернативная группировка выполняется явными блоками, например, begin...end
в Pascal [6] и {...}
в C.
В зависимости от подхода к построению компилятора можно предпринять различные корректирующие действия, чтобы избежать двусмысленности:
- Если синтаксический анализатор создается генератором синтаксического анализатора SLR, LR (1) или LALR LR , программист часто будет полагаться на сгенерированную функцию синтаксического анализатора, предпочитая сдвиг сокращению всякий раз, когда возникает конфликт. [2] В качестве альтернативы, грамматика может быть переписана, чтобы устранить конфликт, за счет увеличения размера грамматики (см. Ниже ).
- Если синтаксический анализатор написан от руки, программист может использовать однозначную контекстно-свободную грамматику. В качестве альтернативы можно полагаться на неконтекстную грамматику или грамматику синтаксического анализа .
Избегайте двусмысленности за счет изменения синтаксиса
Проблему также можно решить, указав в синтаксисе явную связь между else и его if. Обычно это помогает избежать человеческих ошибок. [7]
Возможные решения:
- Наличие оператора "конец, если". Примерами таких языков являются ALGOL 68 , Ada , Eiffel , PL / SQL , Visual Basic и AppleScript .
- Запрещение оператору, следующему за «then», быть самим «если» (однако это может быть пара скобок оператора, содержащая только предложение if-then). Этому подходу следует АЛГОЛ 60 . [8]
- Требование фигурных скобок (скобок), когда "else" следует за "if". [9]
- Требование, чтобы каждое «если» было соединено с «иначе». Чтобы избежать подобной проблемы, касающейся семантики, а не синтаксиса, Racket отклоняется от Scheme , рассматривая предложение
if
без запасного варианта как ошибку, эффективно отделяя условные выражения (т.е.if
) от условных операторов (т.е.when
иunless
, которые не имеют резервных предложений). - Использование разных ключевых слов для одно- и двухальтернативных операторов if. S-algol использует как
if e do s
для одноальтернативного, так иif e1 then e2 else e3
для общего случая. [10] - Требование скобок безоговорочно, как у Swift и Modula-2 . Это действительно так в Python, поскольку его правила отступа ограничивают каждый блок, а не только те, которые указаны в операторах «if». Чтобы уменьшить возникающий беспорядок, Modula-2 избавляется от открывателя блоков на нефункциональных уровнях.
Примеры
Ниже приводятся конкретные примеры.
C
В языке C грамматика, в частности, гласит:
заявление = ... | заявление о выборе оператор выбора = ... | IF (выражение) инструкция | Оператор IF (выражение) Оператор ELSE
Таким образом, без дополнительных правил, утверждение
если ( а ) если ( б ) s ; else s2 ;
можно неоднозначно проанализировать, как если бы это было либо:
if ( a ) { if ( b ) s ; else s2 ; }
или же:
if ( a ) { if ( b ) s ; } else s2 ;
На практике в C выбирается первое дерево, связывая его else
с ближайшим if
.
Как избежать конфликта в парсерах 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: ... ;
Любые другие правила грамматики, связанные с утверждениями, также могут быть дублированы таким образом, если они могут прямо или косвенно оканчиваться на statement
или selection-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'если' '(' 'a' ')' closed_statement 'else' 'd'
а затем при синтаксическом анализе не удается сопоставить closed_statement
"if (b) c". Попытка с closed_statement
таким же образом не удалась.
Смотрите также
Рекомендации
- Перейти ↑ Abrahams, PW (1966). «Окончательное решение проблемы Dangling else Алгола 60 и родственных языков». Коммуникации ACM . 9 (9): 679. DOI : 10,1145 / 365813,365821 .
- ^ a b 5.2 Сдвиг / уменьшение конфликтов с веб-сайта операционной системы GNU
- ^ ISO 7185: 1990 (Паскаль) 6.8.3.4: Оператор if без части else не должен сразу сопровождаться токеном else.
- ^ ISO 9899 : 1999 (C): 6.8.4.1 (3): «else связан с лексически ближайшим предшествующим, если это разрешено синтаксисом.», Доступно в WG14 N1256 , p. 134
- ^ «Спецификация языка Java, Java SE 9 Edition, 14.5. Заявления» .
- ^ Паскаль, Нелл Дэйл и Чип Weems, «зависшие Else», стр. 160–161
- ^ Двусмысленность dangling else: неконтекстные грамматики семантически непрозрачны
- ^ 4.5.1 Условные операторы - Синтаксис в П. Науэре (ред.), Пересмотренный отчет по алгоритмическому языку ALGOL 60 , CACM 6,1, 1963, стр. 1-17
- ^ Двусмысленность свисания else: требуются фигурные скобки, когда следует else, если
- ^ Дэви, Энтони JT; Рональд Моррисон (1981), Брайан Мик (редактор), Компиляция по рекурсивному спуску , серия Эллиса Хорвуда по компьютерам и их приложениям, Чичестер, Западный Сассекс: Эллис Хорвуд, стр. 20, ISBN 0-470-27270-8