Gramàtica lliure de context determinista

De Viquipèdia
Salta a la navegació Salta a la cerca

En la teoria dels llenguatges formals, la classe de gramàtiques lliures de context deterministes (DCFGs per les seves sigles en anglès) son un subconjunt propi de les gramàtiques lliures de context. Son el subconjunt de les gramàtiques lliures de context que es poden derivar d'un autòmat amb pila determinista i generen els llenguatges lliures de context deterministes. Aquestes gramàtiques son sempre no-ambigües.[1][2]

DCFGs son d'un gran interès pràctic, ja que poden es poden analitzar sintàcticament (parser) en temps lineal i de fet, es pot generar automàticament un parser a partir de la gramàtica amb un generador. Per aquest motiu s'han fet servir a bastament en computació, ja que formes més restrictives de DCFGs es poden analitzar sintàcticament per parsers força simples.

Referències[modifica]

  1. C., Martin, John. Introduction to languages and the theory of computation. 4th ed. New York, NY: McGraw-Hill, 2011. ISBN 9780073191461. 
  2. Michael., Sipser,. Introduction to the theory of computation. 3rd ed. Boston, MA: Cengage Learning, 2013. ISBN 9781133187790.