Pregunta originalmente respondida: ¿Qué significa shift / reduce en el análisis?
Analizar es el proceso de reconocer la estructura gramatical de alguna oración en algún idioma de acuerdo con alguna gramática.
Entonces, por ejemplo, consideremos como oración de entrada: “ El leñador corta madera ” en un idioma similar al inglés de acuerdo con la siguiente gramática (incompleta):
- ¿Necesitaríamos resolver P vs. NP como prerrequisito en el diseño de inteligencia general artificial?
- No pude escribir el programa Fibonacci. ¿Cómo puedo desarrollar mis habilidades matemáticas?
- ¿Qué es la criptografía de clave pública en términos simples? ¿Cómo se relaciona con los números primos?
- ¿Debo continuar las matemáticas con la ciencia actuarial o cambiar a la informática y por qué?
- ¿Cuál es el significado del teorema de Shamir?
- [matemáticas] :: = \ cdots | | cdots [/ math]
- [matemáticas] \ cdots [/ matemáticas]
- [matemáticas] :: = \ cdots | | | \ cdots [/ math]
- [matemáticas] :: = \ cdots | | \ cdots [/ math]
- [matemáticas] \ cdots [/ matemáticas]
- [matemáticas] :: = \ cdots | El | \ cdots [/ math]
- [matemáticas] :: = \ cdots | leñador | madera | \ cdots [/ math]
- [matemáticas] \ cdots [/ matemáticas]
- [matemáticas] :: = \ cdots | chuletas | \ cdots [/ math]
- [matemáticas] \ cdots [/ matemáticas]
Ahora esto se analiza como:
[matemáticas] [/ matemáticas]
- [matemáticas] [/ matemáticas]
- [matemáticas] [/ matemáticas] El
- [matemática] [/ matemática] leñador
- [matemáticas] [/ matemáticas]
- [matemáticas] [/ matemáticas] chuletas
- [matemáticas] [/ matemáticas]
- [matemáticas] [/ matemáticas] madera
Este análisis se puede descubrir fácilmente mediante prueba y error y se puede verificar fácilmente mediante inspección visual.
Por supuesto, las gramáticas realistas pueden estar mucho más involucradas con una gran cantidad de categorías sintácticas y reglas de producción. Y surge la pregunta, ¿existe un procedimiento sistemático que permita encontrar todos los análisis válidos de una oración de entrada arbitraria que se ajuste a una gramática dada.
En general, dicho algoritmo no puede existir, pero existe una clase de gramáticas, las llamadas gramáticas libres de contexto, para las cuales existe dicho algoritmo.
Ahora, en general, cuando se nos da una oración de entrada, podemos intentar encontrar un análisis válido, es decir, descubrir un árbol de análisis válido de dos maneras distintas. Nosotros podemos
- intente construir el árbol de análisis de arriba hacia abajo comenzando desde la raíz y luego examinando la entrada para ver qué producciones podrían aplicarse y luego verifique cada posibilidad exactamente de la misma manera, es decir, de forma recursiva. Este es el llamado enfoque de arriba hacia abajo. O podemos
- intente mirar directamente la entrada y ver si podemos construir el árbol de abajo hacia arriba, reconociendo las piezas de la entrada como una instancia de alguna regla de producción y construyendo un pequeño árbol de análisis a partir de eso. Luego podemos combinar estos pequeños subárboles en árboles progresivamente más grandes hasta que alcancemos la producción de raíces. Este es el enfoque de abajo hacia arriba.
Por supuesto, también se puede usar alguna combinación de las dos técnicas, a menudo llamada análisis de la esquina izquierda.
Ahora su pregunta se refiere al análisis de reducción de turnos, que es una instancia particular de la técnica de análisis general ascendente. El algoritmo, dejando de lado muchos detalles, funciona de la siguiente manera.
Comenzamos con una configuración con una pila vacía en un lado (la pila de reducción) y la cadena de entrada como una pila de tokens en el otro.
Algo como esto:
[matemáticas] []: [El, leñador, chuletas, madera] [/ matemáticas]
Primero cambiamos el primer token de la pila de entrada a la pila de reducción que nos da:
[matemáticas] [El]: [leñador, chuletas, madera] [/ matemáticas]
Luego verificamos la pila de reducción para ver si las pocas entradas superiores pueden reconocerse como resultado de aplicar alguna regla gramatical. En este caso, por ejemplo, reconoceríamos que el token ‘ The ‘ es un [math] Determiner [/ math] de acuerdo con la gramática. Luego reducimos la parte superior de la pila de reducción a la gramática identificada no terminal, dándonos:
[matemáticas] [Determinador]: [leñador, chuletas, madera] [/ matemáticas]. Seguimos reduciendo hasta que ya no es posible.
Luego simplemente enjuagamos y repetimos siempre que podamos:
Shift ‘ leñador ‘: [matemáticas] [Determinador, leñador]: [chuletas, madera] [/ matemáticas].
Reducir ‘ leñador ‘: [matemática] [Determinador, Sustantivo]: [chuletas, madera] [/ matemática].
Reducir [matemática] [Determinador, sustantivo] [/ matemática]: [matemática] [Frase sustantiva]: [chuletas, madera] [/ matemática].
Shift ‘ chops ‘: [math] [NounPhrase, chops]: [wood] [/ math].
Reduzca ‘ chuletas ‘: [matemática] [Frase sustantiva, verbo]: [madera] [/ matemática].
Shift ‘ wood ‘: [math] [NounPhrase, Verb, wood]: [] [/ math].
Reduce ‘ wood ‘: [math] [NounPhrase, Verb, Noun]: [] [/ math].
Reducir [matemática] [Sustantivo] [/ matemática]: [matemática] [NounPhrase, Verb, NounPhrase]: [] [/ math].
Reduzca [math] [Verb, NounPhrase] [/ math]: [math] [NounPhrase, VerbPhrase]: [] [/ math].
Reduce [math] [NounPhrase, VerbPhrase] [/ math]: [math] [Sentencia]: [] [/ math].
Espero que esta explicación haya sido algo clara y que te sirva de ayuda. Si no es así, no dude en preguntar en los comentarios y podemos ir un poco más profundo si lo desea.
