El lenguaje de análisis de arriba hacia abajo (TDPL) es un tipo de gramática formal analítica desarrollada por Alexander Birman a principios de la década de 1970 para estudiar formalmente el comportamiento de una clase común de analizadores de análisis de arriba hacia abajo prácticos que apoyan una forma limitada de retroceso . Birman originalmente nombró a su formalismo TMG Schema (TS), después de TMG , uno de los primeros generadores de analizadores sintácticos , pero luego Aho y Ullman le dieron el nombre TDPL en su antología clásica The Theory of Parsing, Translation and Compiling .
Definición de una gramática TDPL
Formalmente, una gramática TDPL G es una tupla que consta de los siguientes componentes:
- Un conjunto finito N de símbolos no terminales .
- Un conjunto Σ finito de símbolos terminales que es disjunta de N .
- Un conjunto P finito de reglas de producción , donde una regla tiene una de las siguientes formas:
- A ← ε, donde A es un no terminal y ε es la cadena vacía.
- A ← f , donde f es un símbolo distinguido que representa una falla incondicional .
- A ← a , donde a es cualquier símbolo terminal.
- A ← BC / D , donde B , C y D son no terminales.
Interpretación de una gramática
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 a reconocer y produce uno de dos resultados posibles:
- éxito , en cuyo caso la función puede avanzar opcionalmente o consumir uno o más caracteres de la cadena de entrada que se le proporciona, o
- falla , en cuyo caso no se consume ninguna entrada.
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 carácter siguiente), el no terminal falla.
Un no terminal A definido por una regla de la forma A ← BC / D primero invoca recursivamente al no terminal B , y si B tiene éxito, invoca a C en el resto de la cadena de entrada que B no consumió . Si tanto B como C tienen éxito, entonces A a su vez tiene éxito y consume el mismo número total de caracteres de entrada que B y C juntos. Sin embargo, si B o C fallan, entonces A retrocede al punto original en la cadena de entrada donde se invocó por primera vez, y luego invoca a D en esa cadena de entrada original, devolviendo cualquier resultado que D produzca.
Ejemplos de
La siguiente gramática TDPL describe el lenguaje regular que consta de una secuencia de longitud arbitraria de a y b:
S ← AS / T
T ← BS / E
A ← a
B ← b
E ← ε
La siguiente gramática describe el lenguaje de paréntesis de lenguaje libre de contexto que consiste en cadenas de llaves coincidentes de longitud arbitraria, como '{}', '{{} {{}}}', etc .:
S ← OT / E
T ← SU / F
U ← CS / F
O ← {
C ←}
E ← ε
F ← f
Los ejemplos anteriores se pueden representar de manera equivalente pero mucho más sucinta al analizar la notación gramatical de expresiones como S ← (a / b) * y S ← ({S}) *, respectivamente.
TDPL generalizado
Una ligera variación de TDPL, conocida como TDPL generalizada 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 , usamos la forma de regla alternativa A ← B [C, D] , que se interpreta de la siguiente manera. Cuando no terminal A se invoca en alguna cadena de entrada, primero se invoca recursivamente B . Si B tiene éxito, entonces A invoca posteriormente a C en el resto de la entrada que B no consumió , y devuelve el resultado de C al llamador original. Si B falla, por otro lado, entonces A invoca a D en la cadena de entrada original y devuelve el resultado a la persona que llama.
La diferencia importante entre esta forma de reglas y el A ← BC / D forma regla utilizada en TDPL es que C y D no son tanto invocan en la misma llamada a A : es decir, la regla GTDPL actúa más como un "puro" si / entonces / else construye usando B como condición.
En GTDPL es sencillo expresar lenguajes interesantes no 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 idioma, aunque el proceso no es sencillo y puede aumentar considerablemente el número de reglas requeridas. [1] Además, tanto TDPL como GTDPL pueden verse como formas muy restringidas de analizar gramáticas de expresión , todas las cuales representan la misma clase de gramáticas. [1]