¿Existe una resolución diferente del problema de "colgar más" además de "coincidencia más cercana"?

9

A continuación se presenta gramática independiente del contexto de una "colgando más" tipo de ambigüedad (imagina que sinónimo de y representa y representa algún otro tipo de instrucción o bloque): $a$ if expr then $b$ else $c$ Por ejemplo,se puede analizar comoo como(esta es la palabra ambigua más simple / más corta para esta gramática).

\begin{aligned} S & \to a S b S | a S | c \end{aligned}

$\begin{aligned} S &\rightarrow aSbS \;|\; aS \;|\; c\\ \end{aligned}$

a a c b c

$aacbc$

(a (a c b c))

$(a(acbc))$

(a (a c) b c)

$(a(ac)bc)$

La forma "estándar" de resolver esta ambigüedad de "colgar otro" obliga a la declaración "más" ( ) a emparejarse con el "si-entonces" más cercano / más interno ( ). Esto se puede lograr de la siguiente manera: $b$ $a$ Esta gramática es inequívoca. En el ejemplo anterior, fuerza elanálisis.

\begin{aligned} S & \to a T b S | a S | c \\ T & \to a T b T | c \end{aligned}

$\begin{aligned} S &\rightarrow aTbS \;|\; aS \;|\; c\\ T &\rightarrow aTbT \;|\; c\\ \end{aligned}$

(a (a c b c))

$(a(acbc))$

Pregunta: ¿Hay otra forma natural de resolver la ambigüedad que forzaría el análisis de ? En otras palabras, estoy buscando una gramática que genere el mismo lenguaje que los dos anteriores, que no sea ambigua y que analice como . $(a(ac)bc)$ $aacbc$ $aacbc$ $(a(ac)bc)$

Observación: Mi primer intento fue el siguiente: que resuelve la ambigüedad desegún sea necesario, pero esta gramática sigue siendo ambigua:puede analizarse comoo como.

\begin{aligned} S & \to a S b S | a U | c \\ U & \to a U | c \end{aligned}

$\begin{aligned} S &\rightarrow aSbS \;|\; aU \;|\; c\\ U &\rightarrow aU \;|\; c\\ \end{aligned}$

a a c b c

$aacbc$

a a c b a c b c

$aacbacbc$

(a (a c) b (a c b c))

$(a(ac)b(acbc))$

(a (a c b (a c)) b c)

$(a(acb(ac))bc)$

context-free formal-grammars parsers ambiguity Gro-Tsen
fuente

1

Y en su último ejemplo, ¿cuál de los dos posibles análisis considera "naturales" o correctos, y por qué?

rici

a a c b a c b c

$aacbacbc$

a a a \dots a a a c b c b c \dots b c

$aaa\ldots aaacbcbc\ldots bc$

a

$a$

b

$b$

k

$k$

b

$b$

k

$k$

a

$a$

a

$a$

7

$a$ $b$ $a$ $b$ $c$ $b$

La tradicional resolución de "colgar más cerca" más coincide con cada cierre con la apertura más reciente aún sin igualar. Eso significa que nunca hay una apertura sin coincidencia (o cierre, para el caso) entre una apertura coincidente y su cierre correspondiente.

$($ $()()$ $)$

Esta coincidencia debe hacerse de afuera hacia adentro, de modo que no se intente una coincidencia para un cierre hasta que se hayan emparejado todos los pares de cerramiento. Este hecho hace que sea imposible producir un análisis con un algoritmo de búsqueda anticipada delimitado, ya que el análisis tiene que trabajar hacia adentro desde ambos extremos, después de haber dividido la cadena en segmentos completamente coincidentes (porque efectivamente limitan el rango de posibles coincidencias).

Sin embargo, el hecho de que no exista un analizador en línea de izquierda a derecha no implica que no haya CFG inequívoco. (Evidentemente: un lenguaje palindrómico debe analizarse desde ambos extremos hacia el centro, pero es fácil escribir una gramática inequívoca).

Para producir una gramática para el problema de paréntesis de "coincidencia más lejana", me basé en el hecho de que una apertura no coincidente no puede ser seguida por una apertura coincidente. Si lo fuera, entonces la propiedad de coincidencia más lejana no se aplicaría porque la apertura no coincidente podría haber coincidido con el cierre de la apertura coincidente, por lo que el hecho de que no coincida viola la propiedad de coincidencia más lejana.

Así que aquí está la gramática un poco torpe:

\begin{aligned} S & \to U | M \\ U & \to T | a U b T | a U b c | a M b U \\ M & \to a M b M | c \\ T & \to a T | a c \end{aligned}

$\begin{aligned} S&\to U \;|\; M \\ U&\to T \;|\; a U b T \;|\; a U b c \;|\; a M b U \\ M&\to a M b M \;|\; c \\ T&\to a T \;|\; a c \\ \end{aligned}$

$S$ $M$ $U$ $a$ $T$ $a$ $T$ $T$ $U$ $U$ $T$

$U$ $U$ $S$ $M^* U$ $S$ $M$ $U$ $M$ $U$

Probablemente hay una mejor solución que la que elegí. Pero este parece funcionar, y funciona bien con el analizador GLR de Bison que solía probarlo; ese analizador se queja de análisis ambiguos a menos que escriba un código adicional para manejar la ambigüedad, y yo era demasiado vago para hacerlo. Lo probé con cadenas de hasta 20 abiertos + cierres, y parece haber producido un análisis inequívoco para cada secuencia anidada correctamente, sin producir análisis para secuencias anidadas incorrectamente.

rici
fuente

¡Felicitaciones por lograr lo que había concluido que probablemente era imposible! Verifiqué experimentalmente que para palabras de longitud ≤16 esta gramática es inequívoca y genera las mismas palabras que las de mi pregunta. ¡Ahora tengo que entender en detalle cómo funciona!

Gro-Tsen

S \to a S b T | a M b S

$S \to aSbT \;|\; aMbS$

M

$M$

T \to a T | c

$T\to aT\;|\;c$

U

$U$

0

Tome a + b + c + d + e y abcde. Hay dos formas obvias de cómo una gramática podría analizar esto, pero hay una forma en que la usamos.

En el caso del "colgar otra cosa", no es así como la gente lo mira. En cambio, la sintaxis se interpreta como "if", seguida de cero, uno o más "else if", seguido de un "else" opcional.

gnasher729
fuente

a c b a c b a c b c

$acbacbacbc$

¿Existe una resolución diferente del problema de "colgar más" además de "coincidencia más cercana"?

Respuestas: