stringtranslate.com

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 .

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 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:

Cómo evitar la ambigüedad modificando 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 suele ayudar a evitar errores humanos. [7]

Las posibles soluciones son:

Ejemplos

A continuación se presentan ejemplos concretos.

do

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.

Cómo evitar conflictos en los 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: 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óndeclaración abiertaSI '(' 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óndeclaración abiertaDeclaración IF '('expresión')'SI '(' expresión ')' instrucción cerradaSI '(' a ')' (SI '(' expresión ')' declaración_cerrada SI NO declaración_cerrada)SI '(' a ')' (SI '(' b ')' c SI NO 'd')

Véase también

Referencias

  1. ^ Abrahams, PW (1966). "Una solución final para el Dangling else de ALGOL 60 y lenguajes relacionados". Comunicaciones de la ACM . 9 (9): 679–682. doi : 10.1145/365813.365821 . S2CID  6777841.
  2. ^ ab "5.2 Cambiar/Reducir conflictos". Bison 3.7.6 . Consultado el 7 de agosto de 2021 . {{cite book}}: |website=ignorado ( ayuda )
  3. ^ 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.
  4. ^ ab ISO 9899:1999 (C): 6.8.4.1(3): "Un else se asocia con el precedente léxico más cercano si la sintaxis lo permite.", disponible en WG14 N1256, p. 134
  5. ^ "La especificación del lenguaje Java, Java SE 9 Edition, 14.5. Declaraciones".
  6. ^ Dale, Nell B.; Weems, Chip (noviembre de 1996). "Dangling Else". Introducción a Pascal y al diseño estructurado. Jones & Bartlett Learning. págs. 160-161. ISBN 9780763703974.
  7. ^ Ambigüedad de los demás elementos: las gramáticas no libres de contexto son semánticamente opacas
  8. ^ 4.5.1 Enunciados condicionales: sintaxis en P. Nauer (ed.), Informe revisado sobre el lenguaje algorítmico ALGOL 60 , CACM 6,1, 1963 págs. 1-17
  9. ^ Ambigüedad de else colgante: se requieren llaves cuando else sigue a if
  10. ^ Davie, Antony JT; Ronald Morrison (1981), Brian Meek (ed.), Recursive Descent Compiling , serie Ellis Horwood sobre computadoras y sus aplicaciones, Chichester, West Sussex: Ellis Horwood, pág. 20, ISBN 0-470-27270-8