Gramática de precedencia simple

Una gramática de precedencia simple es un tipo de Gramática libre de contexto que puede ser reconocida por un Analizador sintáctico de precedencia simple.

Definición formal

G = (N, Σ, P, S) es una gramática de precedencia simple si todas las producciones en P tienen las siguientes características:

• No hay reglas borradoras (producciones ε)
• No hay reglas inútiles (símbolos inalcanzables o reglas improductivas)
• Para cada par de símbolosX, Y (X, Y $\in$ (N ∪ Σ)) sólo hay una Relación de precedencia Wirth-Weber.
• G es unívocamente inversible, es decir, no tiene dos reglas con el mismo lado derecho

Ejemplo 1

$S\to aSSb$

$S\to c$

tabla de precedencia:

	S	a	b	c
S	$\dot{=}$	$⋖$	$\dot{=}$	$⋖$
a	$\dot{=}$	$⋖$		$⋖$
b	$⋗$	$⋗$	$⋗$	$⋗$
c	$⋗$	$⋗$	$⋗$	$⋗$