¿Ayuda a entender los analizadores LR (1), generación de tablas? ¿Algún otro recurso?

Question

Actualmente estoy tomando una clase de compiladores y estoy teniendo dificultades para entender los algoritmos de análisis LR (1) usando la tabla de acción/goto y también cómo generar estas tablas a mano. En este momento estamos utilizando Engineering a Compiler de Cooper y Torczon como nuestro libro de texto de clase y también he leído las páginas de wikipedia sobre generación de tablas, pero todavía no entiendo los conceptos. Si es posible, ¿alguien puede recomendar otro libro que explique bien el análisis o un recurso en línea? Creo que muchas universidades tendrían buenos recursos/diapositivas en línea sobre el tema, pero no tengo idea de dónde empezar a buscar. ¡Gracias!

Answer 1

algunas notas dignas de conferencias ...

http://cs.oberlin.edu/~jdonalds/331/lecture14.html

comprensión y escritura compiladores tiene una sección, cuáles son las ventajas verdaderas de LR (1) Análisis?

http://www.amazon.com/Understanding-Writing-Compilers-Yourself-Macmillan/dp/0333217322

(también disponible libremente en línea)

Aquí hay un enlace a un resumen decente, aunque la explicación es insuficiente.

http://arantxa.ii.uam.es/~modonnel/Compilers/LR1Summary.pdf

más notas de clase ...

http://www.cs.umd.edu/class/spring2011/cmsc430/lectures/lec07.pdf

y notas aquí ...

http://cobweb.ecn.purdue.edu/~smidkiff/ece495S/files/handouts/w3w4bBW.pdf

(incluyendo tablas Goto y de acción)

Lo siento, no puedo explicarlo personalmente, no estoy muy seguro de mí mismo. Tal vez encuentres un alma amable y más conocedora.

Answer 2

Los libros son siempre difíciles de leer debido a los detalles del algoritmo. Los símbolos griegos y las operaciones abstractas son difíciles de interpretar a menos que ya sepas lo que significan.

La forma en que aprendí cómo hacer esto, era escribir una pequeña gramática (expresión simple, instrucción de asignación, si entonces declaración, secuencia de instrucciones), y luego mano simular el algoritmo. Consigue una gran hoja de papel. Dibuja el estado de configuración de inicio con solo el símbolo de objetivo y el punto [G = DOT RHS1 ... RHSM]. Luego procese los estados no procesados, siguiendo el algoritmo en detalle; escriba lo que representa cada símbolo griego en ese momento. A medida que ganes confianza, obtendrás una mejor sensación y será más rápida.

Esencialmente lo que vas a hacer es, para cada artículo que

[LHS RHS1 DOT RHS2 RHS3 ... RHSN] 

en un estado, pulse el punto de partida un lugar a la derecha para producir un nuevo elemento

[LHS RHS1 RHS2 DOT RHS3 ... RHSN ] 

sorteo un nuevo estado en su nuevo estado en papel con ese artículo como la semilla, complete el núcleo del artículo con los conjuntos de anticipación basados ​​en PRIMERO (RHS3), expanda el estado y repita.

Esto le llevará varias horas la primera vez que lo prueba. Vale la pena cada segundo. ¡Usa un lápiz!