Colgando de otra cosa

El else pendiente es un problema en la programación de generadores de analizadores sintácticos en el que una cláusula else opcional en una declaración if–then(–else) da como resultado condicionales anidados que son ambiguos. Formalmente, la gramática de referencia independiente del contexto del lenguaje es ambigua , lo que significa que hay más de un árbol de análisis sintáctico correcto .

En muchos lenguajes de programación se 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 De lo contrario s2

Esto da lugar a una ambigüedad en la interpretación cuando hay declaraciones anidadas, específicamente cuando una forma if-then aparece como s1en una forma if-then-else:

Si a entonces  si b entonces s de lo contrario s2

En este ejemplo, sse ejecuta de forma inequívoca cuando aes verdadero y bes verdadero, pero se puede interpretar s2como que se ejecuta cuando aes falso (agregando así el else al primer if) o cuando aes verdadero y bes falso (agregando así el else al segundo if). En otras palabras, se puede ver la declaración anterior como cualquiera de las siguientes expresiones:

si a entonces ( si b entonces s) de lo contrario s2
 si a entonces ( si b entonces s de lo contrario s2)

El problema del else pendiente data de ALGOL 60 , ^[1] y se ha resuelto de diversas maneras en lenguajes posteriores. En los analizadores sintácticos LR , el else pendiente es el ejemplo arquetípico de un conflicto de desplazamiento-reducción .

Este es un problema que surge a menudo en la construcción de compiladores , especialmente en el análisis sin escáner . La convención cuando se trata con el else pendiente es adjuntar el else a la declaración if cercana, ^[2] lo que permite 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, la agrupación alternativa se logra mediante bloques explícitos, como begin...enden 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 es producido por un generador de analizadores sintácticos SLR, LR(1) o LALR LR , el programador a menudo confiará en la característica del analizador generado de preferir el cambio en lugar de la reducción 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 a continuación).
• Si el analizador está escrito a mano, el programador puede utilizar una gramática libre de contexto que no sea ambigua . Como alternativa, se puede confiar en una gramática no libre de contexto o en una gramática de expresión de análisis .

El problema también se puede resolver haciendo explícito el vínculo entre un else y su if, dentro de la sintaxis. Esto suele ayudar a evitar errores humanos. ^[7]

Las posibles soluciones son:

• Que tiene un símbolo "end if" que delimita el final de la construcción if. Algunos ejemplos de estos lenguajes son ALGOL 68 , Ada , Eiffel , PL/SQL , Visual Basic , Modula-2 y AppleScript .
• No permitir que la declaración que sigue a un "then" sea en sí misma un "if" (no obstante, puede ser un par de corchetes de declaración que contengan solo una cláusula if-then). ALGOL 60 sigue este enfoque . ^[8]
• Requerir llaves (paréntesis) cuando un "else" sigue a un "if". ^[9]
• Requiere que cada "if" esté emparejado con un "else". Para evitar un problema similar relacionado con la semántica en lugar de la sintaxis, Racket se desvía de Scheme al considerar que una ifcláusula sin cláusula de reserva es un error, lo que distingue de manera efectiva las expresiones condicionales (ie if) de las declaraciones condicionales (ie wheny unless, que no tienen cláusulas de reserva).
• Uso de palabras clave diferentes para las declaraciones "si" de una alternativa y de dos alternativas. S-algol las utiliza if e do spara el caso de una alternativa y if e1 then e2 else e3para el caso general. ^[10]
• Requerir llaves de forma incondicional, como en Swift . Esto es así en Python , ya que sus reglas de sangría delimitan cada bloque, no solo los de las instrucciones "if".

A continuación se presentan ejemplos concretos.

En C , la gramática se lee, en parte:

declaración = ...
    | declaración de selección

 declaración-de-selección = ...
    | Declaración IF (expresión)
    | Declaración IF (expresión) Declaración ELSE

Así pues, sin más reglas, la declaración

si ( a ) si ( b ) s ; de lo contrario s2 ;      

Podría analizarse ambiguamente como si fuera:

si ( a ) { si ( b ) s ; de lo contrario s2 ; } 

   
    
  
    

o:

si ( a ) { si ( b ) s ; } de lo contrario s2 ; 

   
    


  

El estándar C aclara que un elsebloque está asociado con el árbol más cercano if. ^[4] Por lo tanto, se elige el primer árbol.

El ejemplo anterior podría reescribirse de la siguiente manera para eliminar la ambigüedad:

Declaración: open_statement
         | declaración cerrada
         ;

open_statement: declaración IF '(' expresión ')'
              | SI '(' expresión ')' declaración_cerrada DE LO CONTRARIO declaración_abierta
              ;

declaración cerrada: declaración no if
                | SI '(' expresión ')' declaración_cerrada DE LO CONTRARIO declaración_cerrada
                ;

declaración no_if: ...
                ;

Es posible que también sea necesario duplicar de esta manera cualquier otra regla gramatical relacionada con una declaración si puede terminar directa o indirectamente con un statemento selection-statementno terminal.

Sin embargo, ofrecemos una gramática que incluye declaraciones if y while.

Declaración: open_statement
         | declaración cerrada
         ;

open_statement: declaración IF '(' expresión ')'
              | SI '(' expresión ')' declaración_cerrada DE LO CONTRARIO declaración_abierta
              | WHILE '(' expresión ')' instrucción_abierta
              ;

declaración_cerrada: declaración_simple
                | SI '(' expresión ')' declaración_cerrada DE LO CONTRARIO declaración_cerrada
                | WHILE '(' expresión ')' instrucción cerrada
                ;

declaración_simple: ...
                ;

Finalmente, presentamos la gramática que prohíbe las declaraciones IF ambiguas.

Declaración: open_statement
         | declaración cerrada
         ;

open_statement: declaración IF '(' expresión ')'
              | SI '(' expresión ')' declaración_cerrada DE LO CONTRARIO declaración_abierta
              | WHILE '(' expresión ')' instrucción_abierta
              ;

declaración_cerrada: declaración_simple
                | SI '(' expresión ')' declaración_cerrada DE LO CONTRARIO declaración_cerrada
                | WHILE '(' expresión ')' instrucción cerrada
                ;

declaración_simple: ...
                ;

Con esta gramática, la declaración if (a) if (b) c else dsolo se puede analizar de una manera, porque la otra interpretación ( if (a) {if (b) c} else d) se produce como

declaración
declaración abierta
SI '(' expresión ')' declaración_cerrada DE LO CONTRARIO declaración_abierta
'si' '(' 'a' ')' declaración cerrada 'de lo contrario' 'd'

y luego el análisis falla al intentar hacer coincidir closed_statementcon "si (b) c". Un intento con closed_statementfalla de la misma manera. El otro análisis, if (a) {if (b) c else d}) tiene éxito:

declaración
declaración abierta
Declaración IF '('expresión')'
SI '(' expresión ')' instrucción cerrada
SI '(' a ')' (SI '(' expresión ')' declaración_cerrada SI NO declaración_cerrada)
SI '(' a ')' (SI '(' b ')' c SI NO 'd')

• El truco del analizador léxico
• El análisis más desconcertante