(1) E DEL

DE B (2) E → 1

y analizar la entrada siguiente: del 1 + 1 del

La acción y la tabla indicada

Las dos 0) tablas de análisis sintáctico de LR (para esta gramática miran como sigue:

Procedimiento del análisis

La tabla abajo ilustra cada paso en el proceso. Aquí el estado refiere al elemento en la tapa del apilado (el elemento de derecha), y la acción siguiente es determinada refiriendo a la tabla de la acción arriba. También observar que un $ está añadido a la secuencia de la entrada para denotar el extremo de la corriente.

Recorrido

El programa de análisis comienza con el apilado que contiene apenas el estado inicial (“0”):

l

El primer símbolo de la secuencia de la entrada que el programa de análisis considera es “1”. Para descubrir cuál es la acción siguiente (el cambio, reduce, acepta o el error), la tabla de la acción se pone en un índice con el estado actual (recordar que el " state" actual; es apenas lo que está en la tapa del apilado), que en este caso es 0, y el símbolo actual de la entrada, que es “1”. La tabla de la acción especifica un cambio para indicar 2, y así que el estado 2 se empuja sobre el apilado (otra vez, recordar que toda la información de estado está en el apilado, tan " desplazamiento para indicar 2" está la misma cosa que empujando 2 sobre el apilado). El apilado resultante es

l “1” ''' del ''' 2

donde está 2. la tapa del apilado por la explicación también demostramos el símbolo (e., “1”, B) que causó la transición al estado siguiente, aunque en realidad no sea parte del apilado.

En el estado que 2 la tabla de la acción dice que sin importar qué terminal vemos en el flujo de entradas, nosotros debe hacer una reducción con la regla 5. Si la tabla está correcta, ésta significa que el programa de análisis acaba de reconocer el lado derecho de la regla 5, que es de hecho el caso. En este caso escribimos 5 a la corriente de salida, hacemos estallar un estado del apilado (puesto que el lado derecho de la regla tiene un símbolo), y empujamos en el apilado el estado de la célula en la tabla indicada para el estado 0 y B, es decir, estado 4. El apilado resultante es: ''' del ''' 4 del

B del

Sin embargo, en el estado 4 la tabla de la acción dice que debemos ahora hacer una reducción con la regla 3. Escribimos tan 3 a la corriente de salida, hacemos estallar un estado del apilado, y encontramos el nuevo estado en la tabla indicada para el estado 0 y E, que es el estado 3. El apilado resultante: ''' del ''' 3 del

E del

El terminal siguiente que el programa de análisis considera es “+” y según la tabla de la acción debe entonces ir a indicar 6: ''' del ''' 3 del

E del “+” ''' del ''' 6

Observar que el apilado resultante se puede interpretar como la historia de un autómata finito del estado que acaba de leer una E no terminal seguida por un terminal “+”. La tabla de transición de este autómata es definida por las acciones del cambio en la tabla de la acción y las acciones indicadas en la tabla indicada.

El terminal siguiente ahora es “1” y éste significa que realizamos un cambio y vamos a indicar 2: ''' del ''' 3 del

E del “+” ''' del ''' 6 “1” ''' del ''' 2

Apenas como el “1 anterior” éste se reduce a B que da el apilado siguiente: ''' DEL ''' 8 DEL ''' DEL ''' 3 DEL

E DEL

“+” DEL ''' B DEL ''' 6

Observar otra vez que el apilado corresponde con una lista de estados de un autómata finito que ha leído una E no terminal, seguida por “+” y entonces un B. En el estado 8 realizamos siempre una reducción con la regla 2. Observar que los 3 estados superiores en el apilado corresponden con los 3 símbolos en el lado derecho de la regla 2. ''' del ''' 3 del

E del

Finalmente, leemos un “$” del flujo de entradas que significa que según la tabla de la acción (el estado actual es 3) el programa de análisis acepta la secuencia de la entrada. Los números de la regla que entonces habrán sido escritos a la corriente de salida serán 3, 5, 2 que es de hecho una derivación de derecha del " de la secuencia; 1 + 1" en revés.

Construir las tablas de análisis sintáctico (0) de LR

¡Artículos

Construcción de estas tablas de análisis sintáctico se basa en la noción de los artículos de LR del (la 0) (simplemente llamados los artículos del aquí) que son reglas de la gramática con un punto especial agregado en alguna parte en el lado derecho. Por ejemplo el → de la regla E E + B tiene los cuatro artículos correspondientes siguientes: → del
E del
• → E DEL

E DE E + DE B • + → DEL

E DE B E + • → DEL

E DE B E + B • Las reglas del ε del → del A de la forma tienen solamente un solo → del A del artículo •. Estas reglas serán utilizadas para denotar ese estado del programa de análisis. El → E del artículo E • + B, por ejemplo, indica que el programa de análisis ha reconocido una secuencia que correspondía con E en el flujo de entradas y ahora la espera leer “+” seguido por otra secuencia que corresponde con el B.

Sistemas del artículo

No es generalmente posible caracterizar el estado del programa de análisis con un solo artículo porque puede no saber que por adelantado que gobiernan va a utilizar para la reducción. Por ejemplo si hay también un → E * B de la regla E entonces el → E de los artículos E • + → E de B y de E • * B ambos se aplicará después de que una secuencia que correspondía con E se haya leído. Por lo tanto caracterizaremos el estado del programa de análisis por un sistema de artículos, en este caso el sistema {→ E de E • + B, → E DE E • * b}.

Encierro de los sistemas del artículo

Un artículo con un punto delante de un no terminal, tal como → de E E + • B, indica que el programa de análisis espera analizar el B no terminal después. Para asegurar el sistema del artículo contiene todas las reglas posibles que el programa de análisis puede estar en el medio del análisis, él debe incluir todos los artículos que describen cómo B sí mismo será analizado. Esto significa que si hay reglas tales como → 1 de B y el → 0 de B entonces el sistema del artículo debe también incluir el → de los artículos B • 1 y → de B • 0. En general esto puede ser formulada como sigue:

l si hay un artículo del v del → del A de la forma • El Bw del en un artículo fijado y en la gramática allí es una regla del w → del B de la forma entonces el → del B del artículo • el w del debe también estar en el artículo fijado.

Cualesquiera fijan de artículos pueden ser extendidos tales que satisfacen esta regla: continuar simplemente agregando los artículos apropiados hasta que todos los nonterminals precedidos por los puntos se expliquen. La extensión mínima se llama el encierro del de un artículo fijado y escrito como clos ( I ) del donde está un sistema el I del artículo. Es éstas los sistemas cerrados del artículo que tomaremos como los estados del programa de análisis, aunque solamente los que son realmente accesibles del estado del comenzar sean incluidos en las tablas.

La gramática aumentada

Antes de que comencemos a determinar las transiciones entre los diversos estados, la gramática se aumenta siempre con una regla adicional → E

DEL

(0) S

donde está un nuevos símbolo de inicio y E S el viejo símbolo de inicio. El programa de análisis utilizará esta regla para la reducción exactamente cuando ha aceptado la secuencia de la entrada.

Por nuestro ejemplo tomaremos la misma gramática que antes y la aumentaremos: → E * → DEL

DEL → E DEL

DEL

DEL

(0) S (1) E DEL

DE B (2) E → 1

DEL

DEL → 0 DEL

DEL → B DEL

DE E + DE B (3) E (4) B (5) B

Es para esta gramática aumentada que determinaremos los sistemas del artículo y las transiciones entre ellas.

Construcción de la tabla

Encontrar los sistemas accesibles del artículo y las transiciones entre ellas

El primer paso de construir las tablas consiste en el determinar de las transiciones entre los sistemas cerrados del artículo. Estas transiciones serán resueltas como si estemos considerando un autómata finito que pueda leer los terminales así como nonterminals. El estado del comenzar de este autómata es siempre el encierro del primer artículo de la regla agregada: → de S • E: el artículo del del

l fijó 0 → del
S de • DEL

DE E + → DE E • E * DEL

DE B + → DE E • DEL

DE E + DE B + → DE E • DEL

DE B + → DE B • 0 del
+ → de B • 1

El " marcado en negrita ; + " de ; delante de un artículo indica los artículos que fueron agregados para el encierro (no ser confundido con el matemático “+” el operador que es un terminal). Los artículos originales sin un " + " de ; se llaman el núcleo sistema del artículo.

El comenzar en el estado del comenzar (S0) ahora determinaremos todos los estados que se pueden alcanzar de este estado. Las transiciones posibles para un sistema del artículo pueden ser encontradas mirando los símbolos (los terminales y los nonterminals) que encontramos a la derecha después de los puntos; en el caso del artículo fijado 0 éstos son los terminales “0” y “1” y la E y el B. Para encontrar el artículo fijó que un x del símbolo lleva a nosotros sigue el procedimiento siguiente: Tomar el sistema, S, de todos los artículos en el artículo actual fijado donde hay un punto delante de un cierto x del símbolo.

Para cada artículo en el S, mover el punto a la derecha del x .

Cerrar el sistema resultante de artículos.

Para el terminal “0” esto da lugar a: el artículo del del

l fijó 1 → 0 del
B de •

y para el terminal “1” en: el artículo del del

l fijó el → 1 del
B de 2 •

y para la E no terminal en: el artículo del del

l fijó el → E del
S de 3 • → E DEL

E • * → E DEL

E DE B • + B

y para el B no terminal en: el artículo del del

l fijó el → B del
E de 4 •

Observar que el encierro no agrega nuevos artículos en todos los casos. Continuamos este proceso hasta que se encuentren no más de nuevos sistemas del artículo. Para los sistemas 1, 2, y 4 del artículo no habrá transiciones puesto que el punto no está delante de ningún símbolo. Para el artículo fijado 3 vemos que el punto está delante de los terminales “*” y “+”. Para “*” la transición va: el artículo del del

l fijó el → E del
E de 5 * •

DE B + → DE B • 0
+ → de B • 1

y para “+” la transición va: el artículo del del

l fijó el → del
E de 6 E + •

DE B + → DE B • 0
+ → de B • 1

Para el artículo fijado 5 tenemos que considerar los terminales “0” y “1” y el B. Para los terminales vemos que el resultar cerró sistemas del artículo es igual a los sistemas ya encontrados 1 y 2 del artículo, respectivamente. Para el B no terminal la transición va: el artículo del del

l fijó el → E * B del
E de 7 •

Para el artículo fijado 6 también tenemos que considerar el terminal “0” y “1” y el B. Como antes, los sistemas resultantes del artículo para los terminales son iguales a los sistemas ya encontrados 1 y 2. Para el B nontermal la transición va: el artículo del del

l fijó el → del
E de 8 E + B •

Estos sistemas finales del artículo no tienen ningún símbolo más allá de sus puntos así que se agregan no más de nuevos sistemas del artículo y somos finished. La tabla de transición para el autómata ahora mira como sigue:

Construir la acción y la tabla indicada

De esta tabla y de los sistemas encontrados del artículo construimos la acción y la tabla indicada como sigue: las columnas para los nonterminals se copian al

indicado de la tabla las columnas para los terminales se copian a la tabla de la acción como

de las acciones del cambio una columna adicional para “$” (extremo de la entrada) se agrega a la tabla de la acción que contiene a CRNA del para cada artículo fijado que contenga el → E de S •.

si un determinado i del artículo contiene un artículo del w del → del A de la forma • y el w del → del A es el m de la regla con el > del m ; 0 entonces la fila para el i del estado en la tabla de la acción se llena totalmente del m de la acción r de la reducción. El lector puede verificar que éste dé lugar de hecho a la acción y a la tabla indicada que fueron presentadas anterior encendido.

Una nota sobre LR (0) contra SLR y LALR que analizan

Observar que solamente el paso 4 del procedimiento antedicho produce reduce acciones, y así que todo reduce acciones debe ocupar una fila entera de la tabla, haciendo la reducción ocurrir sin importar el símbolo siguiente en el flujo de entradas. Esta es la razón por la cual éstos son 0) de LR (analizan las tablas : no hacen ningún lookahead (es decir, anticipan los símbolos cero) antes de decidir a qué reducción a realizarse. Una gramática que necesita el lookahead quitar ambigüedades de reducciones requeriría contener de la fila de la tabla del análisis diferente reduce acciones en diversas columnas, y el procedimiento antedicho no es capaz de crear tales filas.

Los refinamientos procedimientos de la construcción de la tabla de LR a los 0) ((tal como SLR y LALR ) son capaces de construir reducen las acciones que no ocupan filas enteras. Por lo tanto, son capaces de analizar más gramáticas que programas de análisis de LR (0).

Conflictos en las tablas construidas

Se construye el autómata de una manera tal que se garantice para ser determinista. Sin embargo, cuando reducir las acciones se agregan a la tabla de la acción que puede suceder que la misma célula está llenada de una acción de la reducción y una acción del cambio (un cambiar de puesto-reduce el conflicto ) o con dos diferentes reducir las acciones (un reducir-reduce el conflicto ). Sin embargo, puede ser demostrado que cuando sucede ésta la gramática no es 0) gramáticas de LR (.

Un pequeño ejemplo (de las 0) gramáticas no-LR con un conflicto de la cambiar de puesto-reducción es: → 1

DEL

(1) E (2) E

Uno del artículo nos fija entonces encuentra es: el artículo del del

l fijó 1 → 1 del
E de • → 1 DEL

E DE E •
+ → de E • 1

DE E + → DE E • 1

Hay un conflicto de la cambiar de puesto-reducción en este artículo fijado porque en la célula en la tabla de la acción para este sistema y el terminal “1” del artículo habrá una acción del cambio para indicar 1 y una acción de la reducción con la regla 2.

Un pequeño ejemplo (de las 0) gramáticas no-LR con un conflicto de la reducir-reducción es:

DEL → B 2 DEL

DEL → A 1 DEL

DEL

DEL

(1) E (2) E (3) UN → 1

DEL

DEL → 1 (4) B

En este caso obtenemos el punto siguiente fijado: el artículo del del

l fijó 1 → 1 del
A de • → 1 del
B •

Hay un conflicto de la reducir-reducción en este artículo fijado porque en las células en la tabla de la acción para este artículo fijado habrá una acción de la reducción para la regla 3 y una para la regla 4.

Ambos ejemplos antedichos pueden ser solucionados dejando el uso del programa de análisis el sistema del siguiente (véase el programa de análisis LL) de un no terminal A de decidir a si va a utilizar uno del A s gobierna para una reducción; utilizará solamente el w del → del A de la regla para una reducción si el símbolo siguiente en el flujo de entradas está en el sistema del siguiente del A . Esta solución da lugar a los programas de análisis simples de LR supuesto

.

Zenithic

Eight model plays

Random links:

1745 en Canadá | Lythe | El Talua | Terapia de la oscuridad | Subiaco, Italia