Árvore de sintaxe

Uma árvore de sintaxe , derivação ou análise sintática é um termo da ciência da computação teórica e linguística . Ele descreve uma representação hierárquica da divisão de um texto. As árvores de sintaxe são usadas como um auxílio para a visualização gráfica da divisão e, na forma de uma estrutura de dados , para exibir essa divisão para o processamento da máquina, por ex. B. em um compilador ou tradutor .

Os vários termos não são usados ​​uniformemente na literatura. Apenas o termo árvore de derivação , que é baseado no termo derivação, é formalmente definido com precisão . Outros nomes para diferentes tipos de árvores podem ser definidos tecnicamente com mais detalhes, conforme descrito abaixo, se necessário.

Ao contrário da informática, em que as línguas também podem ser definidas de acordo com as possibilidades técnicas, a lingüística encontra pré-requisitos mais difíceis ao lidar com as línguas naturais , principalmente porque a ordem dos componentes de uma frase pode variar.

introdução

Representação de uma árvore de derivação

Na análise (mecânica) de sentenças de linguagem natural ou textos formais (por exemplo, programas de computador), a análise lexical (a divisão em tokens ou símbolos ) é frequentemente seguida por um resumo hierárquico dos símbolos em partes relacionadas de sentenças ( constituintes ) ou seções do Texto formal em vez disso. Por outro lado, isso também pode ser entendido como uma dissecação do texto. O resultado é uma árvore como a mostrada à direita. Além da forma gráfica, as representações entre colchetes também são usadas para árvores de sintaxe:${\ displaystyle [_ {S} \ [_ {\ mathit {NP}} \ John] \ [_ {\ mathit {VP}} \ [_ {V} \ hit] \ [_ {\ mathit {NP}} \ [_ {\ mathit {Det}} \ the] \ [_ {N} \ ball]]]].}$

Tecnicamente, a árvore à esquerda também é chamada de árvore de derivação concreta , pois mostra a estrutura resultante exatamente usando o texto concreto. Em linguística, no entanto, os modelos também são comuns que fornecem várias camadas de representação (por exemplo, superfície e estrutura de profundidade ).

Freqüentemente, os nós da árvore são enriquecidos com atributos (em linguística, essas são categorias principalmente morfológicas ). Isso fornece uma árvore de sintaxe atribuída com a gramática atribuída associada . Enquanto uma gramática livre de contexto é usada nas duas primeiras representações de árvore , a dependência de contexto entra em jogo na última . Essas diferenças se refletem na hierarquia de Chomsky . Nesses casos, o termo análise semântica é usado na construção do compilador .

Árvores de derivação

Considere uma gramática livre de contexto . Uma árvore de derivação para isso é uma árvore cujos nós são rotulados com símbolos de (ou seja, símbolos terminais e não terminais e a palavra vazia ). A árvore está ordenada , i. H. os filhos de cada nó têm uma ordem fixa e o seguinte se aplica à rotulagem: ${\ displaystyle G = \ left (N, \ Sigma, P, S \ right)}$${\ displaystyle \ Sigma \ cup N \ cup \ {\ varepsilon \}}$

• A raiz é identificada com o símbolo de início . Esta propriedade às vezes não é necessária. Uma árvore que os satisfaça é chamada de árvore de derivação completa .${\ displaystyle S}$
• Se os filhos de um nó interno rotulado com são rotulados com os símbolos (nessa ordem), a gramática deve conter a regra .${\ displaystyle A}$${\ displaystyle z_ {1}, \ ldots, z_ {m}}$${\ displaystyle A \ to z_ {1} \ ldots z_ {m}}$
• As folhas da árvore são rotuladas com símbolos .${\ displaystyle \ Sigma \ cup \ {\ varepsilon \}}$
• Se uma folha estiver marcada com , ela será a única sucessora de seu nó predecessor.${\ displaystyle \ varepsilon}$

Apenas símbolos não terminais podem ser usados ​​como nós internos, e apenas os símbolos terminais ou a palavra vazia para as folhas.

Construção de árvores de derivação

As árvores / diagramas de sintaxe possíveis podem ser facilmente criados para textos curtos, seguindo as regras de produção. Muitos métodos mecânicos estão disponíveis para textos mais longos .

Por exemplo, o diagrama de sintaxe mostrado na introdução inclui, entre outras coisas. baseiam-se nas seguintes regras:

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

Para gerar uma árvore de derivação, as regras podem ser aplicadas passo a passo a partir da raiz, substituindo sistematicamente um não terminal no lado esquerdo da regra pelos símbolos no lado direito até que apenas os terminais sejam deixados:

${\ 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 \ bola}}}$

Com cada uma das etapas, você desenha uma parte da árvore da sintaxe de cima para baixo. Mas você também pode aplicar as regras ao contrário e começar com a frase escrita e então construir a árvore passo a passo de baixo para cima.

Árvores de derivação para gramáticas inequívocas e ambíguas

Se houver mais de uma árvore de derivação para uma palavra na linguagem de uma gramática, fala-se de uma gramática ambígua , caso contrário, de uma não ambígua. Por exemplo, a gramática a seguir é ambígua

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

porque "aa a" pode ser dividido de duas maneiras diferentes: "[aa] a" e "a [aa]". No entanto, apenas uma classificação possível permite a seguinte gramática

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

No caso de gramáticas ambíguas, o número de árvores de derivação possíveis para uma e a mesma palavra pode aumentar acentuadamente com o comprimento da palavra. Nesse caso, as árvores de derivação não são mais uma representação adequada para a totalidade das derivações possíveis. No caso das linguagens formais, a gramática concreta (de superfície) é geralmente formulada de forma inequívoca. As gramáticas abstratas, por outro lado, são freqüentemente ambíguas, em que a singularidade da árvore de derivação abstrata resulta do concreto ao longo do curso da análise.

Árvores de sintaxe abstrata

Para a representação de árvores sintáticas como uma estrutura de dados em um computador, a designação árvore sintática abstrata (AST) agora é usada de maneira bastante uniforme. B. também de árvores de derivação abstratas , árvores operador ou similares. pode ser falado. Uma conexão exata entre a árvore de sintaxe abstrata e a árvore de derivação concreta é mostrada na literatura, por exemplo, T. indicado. No entanto, além de um engrossamento da árvore de derivação, requisitos para processamento posterior também são incluídos na estrutura, de modo que uma derivação formal direta da gramática de superfície geralmente é insatisfatória como resultado.

A gramática de superfície livre de contexto é então oposta a uma gramática abstrata , que no sentido mais restrito é principalmente um tipo de dados algébrico . As árvores de sintaxe são então tecnicamente representadas como termos versáteis . A análise está na transição entre termos gramaticais e lógico-algébricos, para que se possa falar fluentemente aqui de não terminais e tipos ou de árvores e termos.

exemplo

Árvore de sintaxe concreta (esquerda) e abstrata (direita) para a expressão ${\ displaystyle a \ times (b + 3)}$

A ilustração ao lado mostra árvores de sintaxe concretas e abstratas para as gramáticas a seguir.

E :: E "+" T - expressão
  :: T
T :: T "*" termo F
  :: F
F :: V - fator
  :: N
  :: "(" E ")"
V - variável
N - número

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

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

A gramática concreta neste exemplo deve regular a ordem em que os operadores são aplicados às expressões (parciais) - isto é, ponto antes do traço e as expressões parciais da mesma prioridade devem ser agrupadas da esquerda para a direita. A possibilidade de criar um resumo diferente também é oferecida com expressões entre colchetes. Junto com certos terminais (aqui "(", ")", "+", "*") são apenas propriedades da superfície sintática que não mais desempenham um papel na análise posterior e no processamento posterior. Em particular, a distinção entre diferentes tipos de expressões (aqui E, T e F) e as palavras-chave podem ser completamente dispensadas, como pode ser visto na árvore de sintaxe abstrata, que também está muito mais próxima do "conteúdo" do expressão. Além disso, devido a esses detalhes de superfície, as árvores de derivação de concreto não apenas se tornam confusas rapidamente, mas também ocupam mais espaço de armazenamento do que o necessário como estrutura de dados no computador devido aos seus detalhes. Isso também se reflete no tempo de execução e na complexidade dos programas que, posteriormente, processarão a árvore de derivação. Por razões técnicas, a divisão de um texto fonte geralmente não é representada por uma árvore de derivação específica.

Representação de árvores de sintaxe abstrata

Além da representação gráfica como árvore (operador) mostrada no exemplo, as árvores de sintaxe abstratas também são tecnicamente indicadas como termos , por exemplo, B.: mul(var('a'), add(var('b'), num(3))).

Gramática abstrata

Enquanto as árvores de sintaxe abstratas são estruturas de dados e os tipos algébricos assumem o papel de gramática nelas, na literatura, especialmente em conexão com cálculos, muitas vezes apenas uma gramática grosseira e ambígua é dada, a qual, como mostrado no exemplo acima, tem o mesma estrutura dos termos, mas ainda contém palavras-chave. Esta forma permite uma escrita agradável de árvores de sintaxe abstratas, que geralmente estão muito próximas da fonte real. Normalmente é apontado na introdução que colchetes podem ser usados ​​para desambiguação. Uma árvore de sintaxe abstrata para o exemplo acima seria então realmente a * (b + 3)escrita como. No contexto desta literatura, entretanto, o foco está sempre no termo.Como mencionado, os limites entre gramática e álgebra são borrados pelo jogo com a forma.

Um exemplo típico são as expressões no cálculo lambda , cuja gramática abstrata geralmente é apenas escrita como. A mesma técnica também é usada para gramáticas extensas. ${\ displaystyle E: = \ lambda VE \, | \, EE \, | \, V}$

literatura

• Ingo Wegener : Ciência da Computação Teórica . Uma introdução orientada a algoritmos. BG Teubner, Stuttgart, ISBN 3-519-02123-4 , 6.1 Exemplos de linguagens livres de contexto e árvores de sintaxe, p. 147-148 . 
• Uwe Schöning : Ciência da Computação Teórica - em poucas palavras . 5ª edição. Spektrum Akademischer Verlag, Heidelberg, ISBN 978-3-8274-1824-1 , 1.1.4 Syntax trees, p. 15-17 . 
• Juraj Hromkovič : Ciência da Computação Teórica . Linguagens formais, previsibilidade, teoria da complexidade, algoritmos, comunicação e criptografia. 3ª Edição. BG Teubner Verlag, Heidelberg, ISBN 978-3-8351-0043-5 , 10.4 Gramáticas livres de contexto e autômatos de botão de pressão, p. 378 . 
• Hans Zima: Compiler I . Análise. Bibliographisches Institut, Mannheim / Vienna / Zurich 1982, ISBN 3-411-01644-2 , 4.3 Árvores abstratas e sua atribuição, p. 216-229 . 
• Stefan Müller : Teoria gramatical. De gramática transformacional a abordagens baseadas em restrições. 2ª Edição. Language Science Press, Berlin 2018, ISBN 978-3-96110-074-3 , cap. 2 ( langsci-press.org ). 

Evidência individual

1. ↑ Müller (2018), página 59f.