parsing - sintactico - parser ll 1 ejercicios

¿Ejemplos de las gramáticas LL(1), LR(1), LR(0), LALR(1)?

Question

¿Existe un buen recurso en línea con una colección de gramáticas para algunos de los principales algoritmos de análisis sintáctico (LL (1), LR (1), LR (0), LALR (1))? He encontrado muchas gramáticas individuales que pertenecen a estas familias, pero no conozco ningún recurso bueno en el que alguien haya escrito un gran conjunto de gramáticas de ejemplo.

¿Alguien sabe de tal recurso?

Answer 1

Ejemplos de wikipedia

LL(1)

gramática

S -> F
S -> ( S + F )
F -> a

entrada

( a + a )

pasos de análisis

S -> "(" S "+" F ")"
  -> ( "F" + F ) 
  -> ( "a" + F ) 
  -> ( a + "a" )       

LR(0)

gramática

(1) E → E * B
(2) E → E + B
(3) E → B
(4) B → 0
(5) B → 1 

entrada

1 + 1

pasos de análisis

need to build a parser table and traverse through states.

LR(1)

gramática

S’ -> S S 
S  -> C C 
C  -> c C | d

entrada

cd

pasos de análisis

large table

LALR

gramática

A -> C x A | ε
B -> x C y | x C
C -> x B x | z

entrada

xxzxx

pasos de análisis

traverse large parser table

Es posible que también desee echarle un vistazo a

• Herramienta Simulador de análisis
• antlr funciona - >download<
• Generación de tabla de analizador desde ocw mit
• Del análisis al código genration ocw mit
• ejemplos adicionales

Answer 2

No esperaría que encontraras una gran colección de gramáticas organizadas de esa manera a propósito. ¿Qué obtendría el organizador a cambio?

Lo que podría tener la oportunidad de hacer, es encontrar generadores de analizadores que correspondan a cada familia (p. Ej., LL (1)), e ir a buscar instancias de entradas para ese generador de analizadores sintácticos, todo lo cual será LL (1) por definición. Por ejemplo, las gramáticas de ANTLR son todas varias versiones de LL (k) dependiendo de qué versión de ANTLR elija (la descripción de la versión ANTLR indicará qué k acepta); Las gramáticas de Bison son todas LALR (1) [ignorando la opción GLR reciente]. Si vas a mi sitio web (ver biografía), ves una lista de gramáticas que están prácticamente libres de contexto (es decir, no en ninguna de las clases que describes).

EDITAR: Tenga en cuenta la aclaración de @Bart Kier de que ANTLR puede marcar explícitamente una gramática como LL (k) para k específica.

Answer 3

Técnicas de análisis: una guía práctica tiene varios ejemplos (es decir, probablemente media docena más o menos por tipo) de casi cualquier tipo de gramática. Puede comprar el libro de la 2ª edición, aunque la 1ª edición está disponible de forma gratuita en el website del autor en formato PDF (al final del enlace).

El autor también tiene algunas gramáticas de prueba que incluye con ejemplos de código de la segunda edición, que se pueden encontrar here .

Nota: todas estas gramáticas son pequeñas (menos de un par de docenas de reglas), debido a que obviamente es un libro publicado.