El lenguaje de análisis descendente (TDPL) es un tipo de gramática formal analítica desarrollada por Alexander Birman a principios de la década de 1970 [1] [2] [3] con el fin de estudiar formalmente el comportamiento de una clase común de analizadores descendentes prácticos que admitan una forma limitada de retroceso . Birman originalmente denominó a su formalismo Esquema TMG (TS), en honor a TMG , uno de los primeros generadores de analizadores sintácticos , pero más tarde Aho y Ullman le dieron el nombre de TDPL en su antología clásica The Theory of Parsing, Translation and Compiling . [4]
Formalmente, una gramática TDPL G es una cuádruple que consta de los siguientes componentes:
Una gramática TDPL puede verse como una representación formal extremadamente minimalista de un analizador sintáctico descendente recursivo , en el que cada uno de los no terminales representa esquemáticamente una función de análisis sintáctico . Cada una de estas funciones no terminales toma como argumento de entrada una cadena que se debe reconocer y produce uno de dos resultados posibles:
Tenga en cuenta que una función no terminal puede tener éxito sin consumir realmente ninguna entrada, y esto se considera un resultado distinto del fracaso.
Un no terminal A definido por una regla de la forma A → ε siempre tiene éxito sin consumir ninguna entrada, independientemente de la cadena de entrada proporcionada. Por el contrario, una regla de la forma A → f siempre falla independientemente de la entrada. Una regla de la forma A → a tiene éxito si el siguiente carácter en la cadena de entrada es el terminal a , en cuyo caso el no terminal tiene éxito y consume ese terminal; si el siguiente carácter de entrada no coincide (o no hay un siguiente carácter), entonces el no terminal falla.
Una A no terminal definida por una regla de la forma A → BC/D primero invoca recursivamente a la B no terminal y, si B tiene éxito, invoca a C en el resto de la cadena de entrada que no ha sido consumida por B. Si tanto B como C tienen éxito, entonces A a su vez tiene éxito y consume la misma cantidad total de caracteres de entrada que consumieron B y C juntos. Sin embargo, si B o C fallan, entonces A retrocede al punto original en la cadena de entrada donde fue invocada por primera vez y luego invoca a D en esa cadena de entrada original, devolviendo cualquier resultado que D produzca.
La siguiente gramática TDPL describe el lenguaje regular que consiste en una secuencia de longitud arbitraria de a y b:
La siguiente gramática describe el lenguaje Dyck libre de contexto que consiste en cadenas de llaves de longitud arbitraria coincidentes, como '{}', '{{}{{}}}', etc.:
Los ejemplos anteriores se pueden representar de forma equivalente pero mucho más sucinta en la notación gramatical de expresión de análisis como y , respectivamente.S ← (a/b)*S ← ({S})*
Una ligera variación de TDPL, conocida como TDPL generalizado o GTDPL, aumenta en gran medida la expresividad aparente de TDPL mientras conserva el mismo enfoque minimalista (aunque en realidad son equivalentes). En GTDPL, en lugar de la forma de regla recursiva de TDPL A → BC/D , se utiliza la forma de regla A → B[C,D] . Esta regla se interpreta de la siguiente manera: cuando se invoca A no terminal en alguna cadena de entrada, primero invoca recursivamente B . Si B tiene éxito, entonces A invoca posteriormente C en el resto de la entrada que no ha sido consumida por B y devuelve el resultado de C al llamador original. Si B falla, por otro lado, entonces A invoca D en la cadena de entrada original y pasa el resultado de vuelta al llamador.
La diferencia importante entre esta forma de regla y la forma de regla A → BC/D utilizada en TDPL es que C y D nunca se invocan en la misma llamada a A : es decir, la regla GTDPL actúa más como una construcción if/then/else "pura" que utiliza B como condición.
En GTDPL es sencillo expresar lenguajes interesantes que no son libres de contexto, como el ejemplo clásico {a n b n c n }.
Una gramática GTDPL se puede reducir a una gramática TDPL equivalente que reconoce el mismo lenguaje, aunque el proceso no es sencillo y puede aumentar en gran medida la cantidad de reglas necesarias. [5] Además, tanto TDPL como GTDPL pueden verse como formas muy restringidas de análisis de gramáticas de expresión , todas las cuales representan la misma clase de gramáticas. [5]