¿Qué tiene que ver el análisis sin escáner con el "Problema de Dangling Else"?

No entiendo esta oración del artículo de Wikipedia sobre el problema de Dangling Else :

[El problema de Dangling Else] es un problema que a menudo surge en la construcción del compilador, especialmente el análisis sin escáner.

¿Puede alguien explicarme cómo las técnicas de análisis sin escáner pueden exacerbar este problema? Me parece que el problema es con la gramática, ya que es ambigua, no con la elección de la técnica de análisis. ¿Qué me estoy perdiendo?

Mi mejor suposición es que la oración en el artículo de Wikipedia es el resultado de un malentendido del trabajo de E. Visser.

Las gramáticas para analizadores sin escáner (es decir, las gramáticas que describen un lenguaje como un conjunto de secuencias de caracteres en lugar de un conjunto de secuencias de tokens con los tokens descritos por separado como cadenas de caracteres) tienden a tener muchas ambigüedades. E. Los filtros de desambiguación de papel Visser para analizadores LR generalizados sin escáner (*) proponen varios mecanismos para resolver ambigüedades, uno de los cuales es útil para resolver el problema de colgar otros. Pero el documento no establece que la ambigüedad precisa llamada "problema de colgar de otro modo" esté relacionada con analizadores sin escáner (ni siquiera que el mecanismo sea especialmente útil para analizadores sin escáner).

El hecho de que proponga un mecanismo para resolverlo no es una declaración implícita, ya que otro mecanismo de resolución de ambigüedad (prioridad y prioridad del operador) tampoco parece estar totalmente relacionado con la naturaleza sin escáner de los analizadores considerados (considere, por ejemplo, que esas ambigüedades no pueden ser presente en gramáticas regulares como resultado de la anidación, mientras que las manejadas por una regla de coincidencia más larga pueden).

(*) Cuál es probablemente el artículo que sirve como base del artículo de Wikipedia sobre analizadores sin escáner, incluso si hacen referencia a otro, también por E. Visser, Scannerless Generalized-LR Parsing .

Solo para exponer el problema, el problema Dangling Else es una ambigüedad en la especificación de la sintaxis del código, donde puede no estar claro, en casos de ifs y elses nexted, qué más pertenece a cuál if.

El ejemplo más simple y clásico:

if(conditionA)
if(conditionB)
   doFoo();
else
   doBar();

No está claro, para aquellos que no conocen los detalles de la especificación del lenguaje de memoria, que ifobtiene el else(y este fragmento de código en particular es válido en media docena de idiomas, pero puede funcionar de manera diferente en cada uno).

La construcción Dangling Else plantea un problema potencial para las implementaciones de analizador sin escáner, porque la estrategia es absorber el flujo de archivos de un carácter a la vez, hasta que el analizador vea que tiene suficiente para tokenizar (resumen en el ensamblado o lenguaje intermedio que está compilando) . Esto permite que el analizador mantenga un estado mínimo; tan pronto como crea que tiene suficiente información para escribir los tokens que se analizan en el archivo, lo hará. Ese es el objetivo final de un analizador sin escáner; Compilación rápida, simple y ligera.

Suponiendo que las nuevas líneas y los espacios en blanco antes o después de la puntuación no tengan sentido (como lo son en la mayoría de los lenguajes de estilo C), esta declaración parecería al compilador como:

if(conditionA)if(conditionB)doFoo();else doBar;

Perfectamente analizable en una computadora, así que veamos. Obtengo un personaje a la vez hasta que tengo:

if(conditionA)

Oh, sé lo que eso significa (en C #), significa " pushcondición A en la pila de evaluación y luego llamar brfalsepara saltar a la declaración después del siguiente punto y coma si no es cierto". En este momento no veo un punto y coma, así que por ahora estableceré mi desplazamiento de salto al siguiente espacio después de esta instrucción, e incrementaré ese desplazamiento a medida que inserte más instrucciones hasta que vea un punto y coma. Continuar analizando ...

if(conditionB)

OK, esto se analiza en un par similar de operaciones IL, e inmediatamente después de la instrucción que acabo de analizar. No veo un punto y coma, por lo que incrementaré el desplazamiento de salto de mi declaración anterior por la longitud de mis dos comandos (uno para el empuje y otro para el descanso) y seguiré buscando.

doFoo();

Ok, eso es facil. Eso es " calldoFoo". ¿Y eso es un punto y coma que veo? Bueno, eso es genial, ese es el final de la línea. Incrementaré las compensaciones de salto de mis dos bloques por la longitud de estos dos comandos y olvidaré que alguna vez me importó. OK, continuando ...

else

... UH oh. Esto no es tan simple como parecía. OK, olvidé lo que estaba haciendo, pero elsesignifica que hay una declaración de interrupción condicional en algún lugar que ya he visto, así que déjenme mirar hacia atrás ... sí, ahí está brfalse, justo después de presionar alguna "condición B" en la pila, lo que sea que fuera eso. OK, ahora necesito un incondicional breakcomo la próxima declaración. La declaración que vendrá después de eso ahora es definitivamente el objetivo de mi descanso condicional, así que me aseguraré de tenerlo bien, y aumentaré el descanso incondicional que puse. Continuando ...

doBar();

Eso es fácil. " calldoBar". Y hay un punto y coma, y ​​nunca vi ningún paréntesis. Entonces, lo incondicional breakdebería saltar a la siguiente declaración, sea lo que sea, y puedo olvidar que alguna vez me importó.

Entonces, ¿qué tenemos ... (nota: son las 10:00 PM y no tengo ganas de convertir las compensaciones de bits en hexadecimal o completar el shell IL completo de una función con estos comandos, por lo que esto es solo pseudo-IL usando números de línea donde normalmente habría desplazamientos de bytes):

ldarg.1 //conditionA
brfalse <line 6> //jumps to "break"
ldarg.2 //conditionB
brfalse <line 7> //jumps to "call doBar"
call doFoo
break <line 8> //jumps beyond statement in scope
call doBar
<line 8 is here>

Bueno, eso realmente se ejecuta correctamente, SI la regla (como en la mayoría de los lenguajes de estilo C) es que elseva con el más cercano if. Con sangría para seguir el anidamiento de ejecución, se ejecutaría de esta manera, donde si la condición A es falsa, se omite todo el resto del fragmento:

if(conditionA)
    if(conditionB)
       doFoo();
    else
       doBar();

... pero lo hace por casualidad, porque la ruptura asociada con la ifdeclaración externa salta a la breakdeclaración al final de la interna if , que lleva el puntero de ejecución más allá de la declaración completa. Es un salto adicional innecesario, y si este ejemplo fuera más complejo, podría no funcionar si se analiza y se tokeniza de esta manera.

Además, ¿qué pasa si la especificación del lenguaje dice que un colgante elsepertenece al primero if, y si la condición A es falsa, entonces se ejecuta doBar, mientras que si la condición A es verdadera pero no la condición B, entonces no sucede nada?

if(conditionA)
    if(conditionB)
       doFoo();
else
   doBar();

El analizador olvidó ifque existía el primero , por lo que este algoritmo analizador simple no produciría el código correcto, por no mencionar el código eficiente.

Ahora, el analizador podría ser lo suficientemente inteligente como para recordar los ifsys elseque tiene durante más tiempo, pero si la especificación del lenguaje dice que un solo elsedespués de dos ifs coincide con el primero if, eso causa un problema con dos ifs con elses coincidentes :

if(conditionA)
    if(conditionB)
       doFoo();
    else
       doBar();
else
    doBaz();

El analizador verá el primero else, coincidirá con el primero if, luego verá el segundo y entrará en pánico "qué demonios estaba haciendo de nuevo". En este punto, el analizador obtuvo bastante código en un estado mutable que preferiría haber enviado al flujo de archivos de salida.

Hay soluciones para todos estos problemas y qué pasa si. Pero, o bien el código debe ser tan inteligente que aumenta la complejidad del algoritmo del analizador, o la especificación del lenguaje que permite que el analizador sea tan tonto aumenta la verbosidad del código fuente del idioma, por ejemplo, al requerir declaraciones de terminación end ifo paréntesis que indican anidado bloquea si la ifdeclaración tiene un else(los cuales se ven comúnmente en otros estilos de lenguaje).

Este es solo un ejemplo simple de un par de ifdeclaraciones, y mira todas las decisiones que el compilador tuvo que tomar, y dónde podría haberse equivocado fácilmente de todos modos. Este es el detalle detrás de esa declaración inocua de Wikipedia en su pregunta.