El else pendiente es un problema en la programación de computadoras en el que una cláusula else opcional en una declaración if – then (–else) da como resultado que los condicionales anidados sean ambiguos. Formalmente, la gramática libre de contexto de referencia del lenguaje es ambigua , lo que significa que hay más de un árbol de análisis correcto .
En muchos lenguajes de programación, uno puede escribir código ejecutado condicionalmente en dos formas: la forma if-then y la forma if-then-else; la cláusula else es opcional:
si a entonces s si b entonces s1 si no s2
Esto da lugar a una ambigüedad en la interpretación cuando hay declaraciones anidadas, específicamente siempre que una forma if-then aparece como s1
en una forma if-then-else:
si a entonces si b entonces s si no s2
En este ejemplo, s
se ejecuta sin ambigüedades cuando a
es verdadero y b
es verdadero, pero se puede interpretar s2
que se está ejecutando cuando a
es falso (por lo tanto, adjunta el else al primero si) o when a
es verdadero y b
es falso (por lo tanto, adjunta el else al segundo si). ). En otras palabras, uno puede ver la declaración anterior como cualquiera de las siguientes expresiones:
si a entonces ( si b entonces s) si no s2 si a entonces ( si b entonces s si no s2)
El problema colgando else data de ALGOL 60 , [1] y se ha resuelto de varias formas en los idiomas posteriores. En los analizadores sintácticos LR , el colgando else es el ejemplo arquetípico de un conflicto de reducción de cambios .
Evitar la ambigüedad manteniendo la sintaxis
Este es un problema que surge a menudo en la construcción de compiladores , especialmente en el análisis sintáctico sin escáner . La convención cuando se trata de colgar else es adjuntar el else a la instrucción if cercana, [2] permitiendo gramáticas libres de contexto inequívocas, en particular. Los lenguajes de programación como Pascal, [3] C [4] y Java [5] siguen esta convención, por lo que no hay ambigüedad en la semántica del lenguaje , aunque el uso de un generador de analizador sintáctico puede conducir a gramáticas ambiguas . En estos casos, el agrupamiento alternativo se logra mediante bloques explícitos, como begin...end
en Pascal [6] y {...}
en C.
Dependiendo del enfoque de construcción del compilador, se pueden tomar diferentes acciones correctivas para evitar la ambigüedad:
- Si el analizador sintáctico es producido por un generador de analizador sintáctico SLR, LR (1) o LALR LR , el programador a menudo se basará en la característica del analizador sintáctico generado de preferir shift sobre reducir siempre que haya un conflicto. [2] Alternativamente, la gramática se puede reescribir para eliminar el conflicto, a expensas de un aumento en el tamaño de la gramática (ver más abajo ).
- Si el analizador está escrito a mano, el programador puede usar una gramática libre de contexto no ambigua . Alternativamente, uno puede confiar en una gramática sin contexto o en una gramática de expresión sintáctica .
Evitar la ambigüedad cambiando la sintaxis
El problema también se puede resolver haciendo explícito el vínculo entre un else y su if, dentro de la sintaxis. Esto generalmente ayuda a evitar errores humanos. [7]
Las posibles soluciones son:
- Tener una declaración de "fin si". Ejemplos de dichos lenguajes son ALGOL 68 , Ada , Eiffel , PL / SQL , Visual Basic y AppleScript .
- No permitir que la declaración que sigue a un "entonces" sea un "si" en sí misma (sin embargo, puede ser un par de corchetes de declaración que contengan sólo una cláusula si-entonces-entonces). Este enfoque es seguido por ALGOL 60 . [8]
- Requiere llaves (entre paréntesis) cuando un "más" sigue a un "si". [9]
- Exigir que cada "si" se empareje con un "más". Para evitar un problema similar con respecto a la semántica en lugar de la sintaxis, Racket se desvía de Scheme al considerar que una
if
cláusula sin respaldo es un error, distinguiendo efectivamente las expresiones condicionales (es decirif
) de las declaraciones condicionales (es decir ,when
yunless
, que no tienen cláusulas alternativas). - Usar palabras clave diferentes para las declaraciones "si" de una alternativa y dos alternativas. Se utiliza S-algol
if e do s
para el caso de una alternativa yif e1 then e2 else e3
para el caso general. [10] - Requerir frenillos incondicionalmente, como Swift y Modula-2 . Esto es efectivamente cierto en Python ya que sus reglas de sangría delimitan cada bloque, no solo los de las declaraciones "if". Para reducir el desorden resultante, Modula-2 elimina el abridor de bloques en los niveles sin función.
Ejemplos de
A continuación se muestran ejemplos concretos.
C
En C , la gramática dice, en parte:
declaración = ... | declaración-selección instrucción-selección = ... | Declaración IF (expresión) | Sentencia IF (expresión) sentencia ELSE
Por lo tanto, sin más reglas, la declaración
si ( a ) si ( b ) s ; else s2 ;
podría analizarse ambiguamente como si fuera:
if ( a ) { if ( b ) s ; else s2 ; }
o:
if ( a ) { if ( b ) s ; } más s2 ;
En la práctica, en C se elige el primer árbol, asociando el else
con el más cercano if
.
Evitar el conflicto en analizadores LR
El ejemplo anterior podría reescribirse de la siguiente manera para eliminar la ambigüedad:
declaración: open_statement | declaración_cerrada ;open_statement: IF '(' expresión ')' declaración | IF '(' expresión ')' closed_statement ELSE open_statement ;Closed_statement: non_if_statement | IF '(' expresión ')' closed_statement ELSE closed_statement ;non_if_statement: ... ;
Cualquier otra regla gramatical relacionada con declaraciones también puede tener que ser duplicada de esta manera si pueden terminar directa o indirectamente con una statement
o selection-statement
no terminal.
Sin embargo, proporcionamos gramática que incluye tanto declaraciones if como while.
declaración: open_statement | declaración_cerrada ;open_statement: IF '(' expresión ')' declaración | IF '(' expresión ')' closed_statement ELSE open_statement | WHILE '(' expresión ')' open_statement ;estado_cerrado: estado_simple | IF '(' expresión ')' closed_statement ELSE closed_statement | WHILE '(' expresión ')' closed_statement ;declaración_simple: ... ;
Finalmente, damos la gramática que prohíbe declaraciones IF ambiguas.
declaración: open_statement | declaración_cerrada ;open_statement: IF '(' expresión ')' simple_statement | IF '(' expresión ')' open_statement | IF '(' expresión ')' closed_statement ELSE open_statement | WHILE '(' expresión ')' open_statement ;estado_cerrado: estado_simple | IF '(' expresión ')' closed_statement ELSE closed_statement | WHILE '(' expresión ')' closed_statement ;declaración_simple: ... ;
Con este análisis gramatical de "if (a) if (b) c else d" falla:
declaraciónopen_statementIF '(' expresión ')' closed_statement ELSE open_statement'if' '(' 'a' ')' closed_statement 'else' 'd'
y luego el análisis falla al intentar coincidir closed_statement
con "if (b) c". Un intento con closed_statement
falla de la misma manera.
Ver también
Referencias
- ^ Abrahams, PW (1966). "Una solución final para el resto de colgantes de ALGOL 60 y lenguajes relacionados". Comunicaciones de la ACM . 9 (9): 679. doi : 10.1145 / 365813.365821 .
- ^ a b 5.2 Shift / Reduce Conflicts desde el sitio web del sistema operativo GNU
- ^ ISO 7185: 1990 (Pascal) 6.8.3.4: Una declaración if sin una parte else no debe ser seguida inmediatamente por el token else.
- ^ ISO 9899 : 1999 (C): 6.8.4.1 (3): "Un else se asocia con el precedente léxico más cercano si así lo permite la sintaxis", disponible en WG14 N1256 , p. 134
- ^ "La especificación del lenguaje Java, Java SE 9 Edition, 14.5. Declaraciones" .
- ^ Pascal, Nell Dale y Chip Weems, "Colgando más", p. 160-161
- ^ Ambigüedad de colgar else: las gramáticas no libres de contexto son semánticamente opacas
- ^ 4.5.1 Declaraciones condicionales - Sintaxis en P. Nauer (ed.), Informe revisado sobre el lenguaje algorítmico ALGOL 60 , MCCA 6,1, 1963 pp. 1-17
- ^ Ambigüedad de colgar else: se requieren llaves cuando else sigue si
- ^ Davie, Antony JT; Ronald Morrison (1981), Brian Meek (ed.), Recursive Descent Compiling , serie de Ellis Horwood en computadoras y sus aplicaciones, Chichester, West Sussex: Ellis Horwood, p. 20, ISBN 0-470-27270-8