Gramática de precedencia simple

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda

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[editar]

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 univocamente inversible, es decir, no tiene dos reglas con el mismo lado derecho

Ejemplos[editar]

Ejemplo 1[editar]

S \to aSSb

S \to c

tabla de precedencia:

S a b c
S \dot = \lessdot \dot = \lessdot
a \dot = \lessdot \lessdot
b \gtrdot \gtrdot \gtrdot \gtrdot
c \gtrdot \gtrdot \gtrdot \gtrdot