Еще болтающийся

Проблема в программировании

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

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

если а, то s, если б, то s1 , иначе s2

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

если а, то  если б, то с, иначе с2

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

если а, то ( если б, то с) иначе с2 если а , то ( если б, то с, иначе с2)

Проблема висячего else датируется ALGOL 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]

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

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

Примеры

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

С

В языке C грамматика, в частности, выглядит следующим образом:

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

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

если ( а ) если ( б ) s ; иначе s2 ;      

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

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

или:

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

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

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

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

заявление: open_statement | закрытое_заявление  ;open_statement: IF '(' выражение ')' оператор | ЕСЛИ '(' выражение ')' закрытый_оператор ИНАЧЕ открытый_оператор  ;закрытое_утверждение: не_если_утверждение | ЕСЛИ '(' выражение ')' закрытый_оператор ИНАЧЕ закрытый_оператор  ;не_if_statement: ...  ;

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

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

заявление: open_statement | закрытое_заявление  ;open_statement: IF '(' выражение ')' оператор | ЕСЛИ '(' выражение ')' закрытый_оператор ИНАЧЕ открытый_оператор | WHILE '(' выражение ')' open_statement  ;закрытое_утверждение: простое_утверждение | ЕСЛИ '(' выражение ')' закрытый_оператор ИНАЧЕ закрытый_оператор | WHILE '(' выражение ')' закрытый_оператор  ;простое_утверждение: ...  ;

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

заявление: open_statement | закрытое_заявление  ;open_statement: IF '(' выражение ')' оператор | ЕСЛИ '(' выражение ')' закрытый_оператор ИНАЧЕ открытый_оператор | WHILE '(' выражение ')' open_statement  ;закрытое_утверждение: простое_утверждение | ЕСЛИ '(' выражение ')' закрытый_оператор ИНАЧЕ закрытый_оператор | WHILE '(' выражение ')' закрытый_оператор  ;простое_утверждение: ...  ;

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

заявлениеоткрытый_учетЕСЛИ '(' выражение ')' закрытый_оператор ИНАЧЕ открытый_оператор'if' '(' 'a' ')' закрытый_оператор 'else' 'd'

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

заявлениеоткрытый_учетIF '(' выражение ')' операторЕСЛИ '(' выражение ')' закрытый_операторЕСЛИ '(' а ')' (ЕСЛИ '(' выражение ')' закрытый_оператор ИНАЧЕ закрытый_оператор)ЕСЛИ '(' а ')' (ЕСЛИ '(' б ')' в ИНАЧЕ ' г')

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

• Взлом лексера
• Самый досадный разбор

Ссылки

1. Абрахамс, П. В. (1966). «Окончательное решение проблемы висячего else в АЛГОЛЕ 60 и родственных языках». Сообщения ACM . 9 (9): 679–682. doi : 10.1145/365813.365821 . S2CID  6777841.
2. "5.2 Конфликты сдвига/сокращения". Bison 3.7.6 . Получено 2021-08-07 . {{cite book}}: |website=проигнорировано ( помощь )
3. ISO 7185:1990 (Pascal) 6.8.3.4: За оператором if без части else не должен сразу следовать токен else.
4. ISO 9899:1999 (C): 6.8.4.1(3): «Elese ассоциируется с лексически ближайшим предшествующим, если это допускается синтаксисом.», доступно в WG14 N1256, стр. 134
5. «Спецификация языка Java, Java SE 9 Edition, 14.5. Утверждения».
6. Дейл, Нелл Б.; Вимс, Чип (ноябрь 1996 г.). «Dangling Else». Введение в Pascal и структурное проектирование. Jones & Bartlett Learning. стр. 160–161. ISBN 9780763703974.
7. Неоднозначность висячего else: неконтекстно-свободные грамматики семантически непрозрачны
8. 4.5.1 Условные операторы — Синтаксис в P. Nauer (ред.), Revised Report on the Algorithmic Language ALGOL 60 , CACM 6,1, 1963 стр. 1-17
9. Неоднозначность висячего else: требуются фигурные скобки, когда else следует за if
10. Дэви, Энтони Дж. Т.; Рональд Моррисон (1981), Брайан Мик (ред.), Компиляция методом рекурсивного спуска , серия Эллиса Хорвуда по компьютерам и их приложениям, Чичестер, Западный Суссекс: Эллис Хорвуд, стр. 20, ISBN 0-470-27270-8