Árbol de sintaxis

Un árbol de sintaxis , derivación o análisis es un término de la informática teórica y la lingüística . Describe una representación jerárquica del desglose de un texto. Los árboles de sintaxis se utilizan como ayuda para la visualización gráfica del desglose y, en forma de estructura de datos , para mostrar este desglose para el procesamiento de la máquina, p. B. en un compilador o traductor .

Los diversos términos no se utilizan de manera uniforme en la literatura. Sólo el término árbol de derivación , que se basa en el término derivación, está formalmente definido con precisión . Otros nombres para diferentes tipos de árboles se pueden definir técnicamente con más detalle, como se describe a continuación, si es necesario.

A diferencia de la informática, en la que los lenguajes también se pueden definir según las posibilidades técnicas, la lingüística encuentra requisitos previos más difíciles cuando se trata de lenguajes naturales , principalmente porque el orden de los componentes de una oración puede variar.

Introducción

Representación de un árbol de derivación

En el análisis (mecánico) de oraciones en lenguaje natural o textos formales (por ejemplo, programas de computadora), el análisis léxico (el desglose en tokens o símbolos ) a menudo va seguido de un resumen jerárquico de los símbolos en partes relacionadas de oraciones ( constituyentes ) o secciones. del Texto formal en su lugar. Por el contrario, esto también puede entenderse como una disección del texto. El resultado es un árbol como el que se muestra a la derecha. Además de la forma gráfica, las representaciones entre corchetes también se utilizan para árboles de sintaxis:${\ Displaystyle [_ {S} \ [_ {\ mathit {NP}} \ John] \ [_ {\ mathit {VP}} \ [_ {V} \ hit] \ [_ {\ mathit {NP}} \ [_ {\ mathit {Det}} \ the] \ [_ {N} \ ball]]]].}$

Técnicamente, el árbol de la izquierda también se denomina árbol de derivación concreto , ya que muestra la estructura resultante utilizando exactamente el texto concreto. En lingüística, sin embargo, también son comunes los modelos que proporcionan varias capas de representación (por ejemplo, estructura de superficie y profundidad ).

A menudo, los nodos del árbol están enriquecidos con atributos (en lingüística, estos son principalmente categorías morfológicas ). Esto le proporciona un árbol de sintaxis atribuido con la gramática atribuida asociada . Si bien se usa una gramática libre de contexto en las dos primeras representaciones de árbol , la dependencia del contexto entra en juego en la última . Estas diferencias se reflejan en la jerarquía de Chomsky . En tales casos, el término análisis semántico se utiliza en la construcción de compiladores .

Árboles de derivación

Considere una gramática libre de contexto . Un árbol de derivación para esto es un árbol cuyos nodos están etiquetados con símbolos de (es decir, símbolos terminales y no terminales y la palabra vacía ). El árbol está ordenado , i. H. los hijos de cada nodo tienen un orden fijo, y lo siguiente se aplica al etiquetado: ${\ Displaystyle G = \ left (N, \ Sigma, P, S \ right)}$${\ Displaystyle \ Sigma \ cup N \ cup \ {\ varepsilon \}}$

• La raíz está etiquetada con el símbolo de inicio . Esta propiedad a veces no es necesaria. Un árbol que los satisface se llama árbol de derivación completo .${\ Displaystyle S}$
• Si los hijos de un nodo interno etiquetado con están etiquetados con los símbolos (en ese orden), la gramática debe contener la regla .${\ Displaystyle A}$${\ Displaystyle z_ {1}, \ ldots, z_ {m}}$${\ Displaystyle A \ a z_ {1} \ ldots z_ {m}}$
• Las hojas del árbol están etiquetadas con símbolos .${\ Displaystyle \ Sigma \ cup \ {\ varepsilon \}}$
• Si una hoja está marcada con , es el único sucesor de su nodo predecesor.${\ Displaystyle \ varepsilon}$

Solo los símbolos no terminales se pueden usar como nodos internos, y solo los símbolos terminales o la palabra vacía para las hojas.

Construcción de árboles de derivación

Los posibles árboles / diagramas de sintaxis a menudo se pueden crear fácilmente para textos cortos siguiendo las reglas de producción. Hay muchos métodos mecánicos disponibles para textos más extensos .

Por ejemplo, el diagrama de sintaxis que se muestra en la introducción incluye, entre otras cosas. se basan en las siguientes reglas:

${\ displaystyle {\ begin {array} {lll} S & \ rightarrow & NP \ VP \\ NP & \ rightarrow & {\ mathtt {John}} \\ NP & \ rightarrow & Det \ N \\ VP & \ rightarrow & V \ NP \\\ end {matriz}} \ quad \ quad {\ begin {matriz} {lll} V & \ rightarrow & {\ mathtt {hit}} \\ Det & \ rightarrow & {\ mathtt {the} } \\ N & \ rightarrow & {\ mathtt {ball}} \ end {array}}}$

Para generar un árbol de derivación, las reglas se pueden aplicar paso a paso desde la raíz reemplazando sistemáticamente un no terminal en el lado izquierdo de la regla con los símbolos en el lado derecho hasta que solo queden terminales:

${\ Displaystyle S \ \ Rightarrow \ NP \ VP \ \ Rightarrow \ {\ mathtt {John}} \ VP \ \ Rightarrow \ {\ mathtt {John}} \ V \ NP \ \ Rightarrow \ {\ mathtt {John \ hit }} \ NP \ \ Rightarrow \ {\ mathtt {John \ hit}} \ Det \ N \ Rightarrow \ {\ mathtt {John \ hit \ the}} \ N \ Rightarrow \ {\ mathtt {John \ hit \ the \ pelota}}}$

Con cada uno de los pasos, dibuja una parte del árbol de sintaxis de arriba a abajo. Pero también puede aplicar las reglas al revés y comenzar con la oración escrita y luego construir el árbol paso a paso de abajo hacia arriba.

Árboles de derivación para gramáticas ambiguas e inequívocas

Si hay más de un árbol de derivación para una palabra en el lenguaje de una gramática, se habla de una gramática ambigua , de lo contrario, de una inequívoca. Por ejemplo, la siguiente gramática es ambigua

${\ displaystyle {\ begin {array} {lll} S & \ rightarrow & S \ S \\ S & \ rightarrow & a \ end {array}}}$

porque "aa a" se puede dividir en dos formas diferentes: "[aa] a" y "a [aa]". Sin embargo, solo una clasificación posible permite la siguiente gramática

${\ displaystyle {\ begin {array} {lll} S & \ rightarrow & a \ S \\ S & \ rightarrow & a \ end {array}}}$

En el caso de gramáticas ambiguas, el número de posibles árboles de derivación para una misma palabra puede aumentar considerablemente con la longitud de la palabra. En este caso, los árboles de derivación ya no son una representación adecuada para la totalidad de las posibles derivaciones. En el caso de los lenguajes formales, la gramática concreta (superficial) suele formularse sin ambigüedades. Las gramáticas abstractas, por otro lado, son a menudo ambiguas, por lo que la unicidad del árbol de derivación abstracto resulta de lo concreto a lo largo del curso del análisis.

Árboles de sintaxis abstracta

Para la representación de árboles de sintaxis como una estructura de datos en una computadora, la designación de árbol de sintaxis abstracta (AST) se usa ahora de manera bastante uniforme. B. También de árboles de derivación abstractos , árboles operador o similares. se puede hablar. En la literatura se muestra una conexión exacta entre el árbol de sintaxis abstracta y el árbol de derivación concreto, p. T. indicado. Sin embargo, además de un engrosamiento del árbol de derivación, los requisitos para el procesamiento adicional también se incluyen en la estructura, de modo que, como resultado, una derivación formal directa de la gramática superficial suele ser insatisfactoria.

La gramática de superficie libre de contexto se opone entonces a una gramática abstracta , que en el sentido más estricto es principalmente un tipo de datos algebraicos . Los árboles de sintaxis se representan técnicamente como términos versátiles . El análisis está en la transición entre términos gramaticales y algebraico-lógicos, de modo que aquí se puede hablar con fluidez de no terminales y tipos o de árboles y términos.

ejemplo

Árbol de sintaxis concreto (izquierda) y abstracto (derecha) para la expresión ${\ Displaystyle a \ times (b + 3)}$

La ilustración de al lado muestra árboles de sintaxis concretos y abstractos para las siguientes gramáticas.

E :: E "+" T - expresión
  :: T
T :: T "*" Término F
  :: F
F :: V - factor
  :: N
  :: "(" E ")"
V - variable
N - número

E :: E "+" E
  :: E "*" E
  :: V
  :: N

tipo E = agregar (E, E);
        mul (E, E);
        var (V);
        num (N)

La gramática concreta de este ejemplo debe regular el orden en que se aplican los operadores a las expresiones (parciales), es decir, el punto antes del guión y las expresiones parciales de la misma prioridad deben agruparse de izquierda a derecha. También se ofrece la posibilidad de crear un resumen diferente con expresiones entre paréntesis. Junto con ciertos terminales (aquí "(", ")", "+", "*"), estas son simplemente propiedades de la superficie sintáctica que ya no juegan un papel en el análisis posterior y el procesamiento posterior. En particular, la distinción entre diferentes tipos de expresiones (aquí E, T y F) y las palabras clave se puede prescindir por completo, como se puede ver en el árbol de sintaxis abstracta, que también está mucho más cerca del "contenido" de la expresión. Además, debido a estos detalles de la superficie, los árboles de derivación de hormigón no solo se vuelven confusos rápidamente, sino que también ocupan más espacio de almacenamiento del necesario como estructura de datos en la computadora debido a sus detalles. Esto también se refleja en el tiempo de ejecución y la complejidad de los programas que luego procesarán el árbol de derivación. Por razones técnicas, el desglose de un texto fuente no suele estar representado por un árbol de derivación específico.

Representación de árboles de sintaxis abstracta

Además de la representación gráfica como árbol (operador) que se muestra en el ejemplo, los árboles de sintaxis abstracta también se indican técnicamente como términos , p. Ej. B.: mul(var('a'), add(var('b'), num(3))).

Gramática abstracta

Si bien los árboles de sintaxis abstracta son estructuras de datos y los tipos algebraicos asumen el papel de la gramática en ellos, en la literatura, especialmente en relación con los cálculos, a menudo solo se da una gramática burda y ambigua que, como se muestra en el ejemplo anterior, tiene la misma estructura que los términos, pero aún contienen palabras clave. Esta forma permite una escritura agradable de árboles de sintaxis abstracta, que a menudo es muy cercana a la fuente real. Por lo general, en la introducción se indica que se pueden usar corchetes para eliminar las ambigüedades. Un árbol de sintaxis abstracta para el ejemplo anterior se a * (b + 3)escribiría entonces como. En el contexto de esta literatura, sin embargo, el enfoque siempre está en el término.Como se mencionó, los límites entre la gramática y el álgebra se difuminan al jugar con la forma.

Un ejemplo típico son las expresiones en el cálculo lambda , cuya gramática abstracta a menudo solo se escribe como. La misma técnica también se utiliza para gramáticas extensas. ${\ Displaystyle E: = \ lambda VE \, | \, EE \, | \, V}$

literatura

• Ingo Wegener : Informática Teórica . Una introducción orientada a algoritmos. BG Teubner, Stuttgart, ISBN 3-519-02123-4 , 6.1 Ejemplos de árboles de sintaxis y lenguajes libres de contexto, p. 147-148 . 
• Uwe Schöning : Informática teórica, en pocas palabras . 5ª edición. Spektrum Akademischer Verlag, Heidelberg, ISBN 978-3-8274-1824-1 , 1.1.4 Árboles de sintaxis, p. 15-17 . 
• Juraj Hromkovič : Informática teórica . Lenguajes formales, predictibilidad, teoría de la complejidad, algoritmos, comunicación y criptografía. 3ª Edición. BG Teubner Verlag, Heidelberg, ISBN 978-3-8351-0043-5 , 10.4 Gramáticas libres de contexto y autómatas pulsadores, p. 378 . 
• Hans Zima: Compilador I . Análisis. Bibliographisches Institut, Mannheim / Viena / Zúrich 1982, ISBN 3-411-01644-2 , 4.3 Árboles abstractos y su atribución, p. 216-229 . 
• Stefan Müller : Teoría gramatical. De la gramática transformacional a los enfoques basados ​​en restricciones. 2ª Edición. Language Science Press, Berlín 2018, ISBN 978-3-96110-074-3 , cap. 2 ( langsci-press.org ). 

Evidencia individual

1. ↑ Müller (2018), p. 59 y siguientes.