Gramàtica lliure de context determinista

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