Derivación
El
concepto de derivación trata a las producciones como reglas
donde el no terminal de la izquierda se sustituye por la cadena del
lado derecho de la producción.
Informalmente
el proceso de derivación consta de los siguientes pasos:
Comenzar
con el símbolo inicial de la gramática como cadena de
entrada.
Seleccionar
un símbolo no terminal N en la cadena y una
producción N→S1…Sk
y cambiar la N
por los
S1…Sk en la cadena.
Repetir el
paso 2, hasta que se tenga una cadena formada únicamente por
símbolos terminales.
Si
realizando este proceso, a partir del símbolo inicial se
consigue obtener la cadena que se está evaluando, esta cadena
pertenece al lenguaje definido por la gramática.
Si el
símbolo que se elige en el paso “b” para la
sustitución, es el símbolo que está más a
la izquierda, entonces la derivación se llama derivación
más a la izquierda.
Por
ejemplo, en la gramática anterior se puede comprobar que “5
- 1 + 3” puede ser generada por la gramática, como se
puede ver a continuación:
lista
lista + digito
lista + 3
lista – digito + 3
lista – 1 + 3
digito – 1 + 3
5 - 1 + 3
|
