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

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

¿Alguien conoce tal recurso?

Author: Majid, 2011-06-26
Source

3 answers

Parsing Techniques-A Practical Guide tiene varios ejemplos (es decir, probablemente media docena por tipo) de casi todos los tipos de gramática. Puede comprar el libro de la 2a edición, aunque la 1a edición está disponible de forma gratuita en el sitio web del autor en formato PDF (cerca de la parte inferior del enlace).

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

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

 18
Author: Jason Moore,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2011-08-20 20:05:42

Ejemplos de wikipedia

CL(1)

Gramática

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

Entrada 

( a + a )

Parsing steps 

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

Parsing steps 

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

Análisis pasos

large table

LALR

Gramática

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

Entrada 

xxzxx

Parsing steps 

traverse large parser table

Es posible que también desee echar un vistazo a

 35
Author: Prashant Bhate,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2012-10-17 17:33:05

No esperaría que encontraras grandes colecciones de gramáticas organizadas de esa manera a propósito. ¿Qué ganaría el organizador a cambio?

Lo que podría tener una oportunidad de hacer, es encontrar generadores de analizador que correspondan a cada familia (por ejemplo, LL(1)), y buscar instancias de entradas para ese generador de analizador, todos los cuales serán LL(1) por definición. Por ejemplo, las gramáticas de ANTLR son todas varias versiones de LL (k) dependiendo de la versión de ANTLR que elija (el descripción de la versión ANTLR dirá lo que k acepta); Las gramáticas de Bison son todas LALR (1) [ignorando la reciente opción GLR]. Si vas a mi sitio web (ver biografía), verás 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ífico.

 2
Author: Ira Baxter,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2011-06-30 08:53:35