Gramática de árvore regular

Origem: Wikipédia, a enciclopédia livre.
Saltar para a navegação Saltar para a pesquisa

Em informática teórica e teoria das linguagens formais, uma gramática de árvore regular (RTG)[1] é uma gramática formal que descreve o conjunto de árvores direcionais, ou termos. A gramática regular pode ser vista como um tipo especial de gramática de árvore regular, descrevendo um conjunto de árvores de caminho único.

Definição[editar | editar código-fonte]

Uma gramática de árvore regular G é definida pela tupla

G = (N, Σ, Z, P),

onde

  • N é um conjunto de não-terminais,
  • Σ é o alfabeto ranqueado (i.e., um alfabeto cujos símbolos possuem uma aridade associada) disjunto de N,
  • Z é a variável não-terminal inicial, com ZN, e
  • P é o conjunto de produções da forma At, com AN, e tTΣ(N), onde TΣ(N) é o universo de Herbrand associado, i.e. o conjunto de todas as árvores compostas pelos símbolos em Σ ∪ N de acordo com suas aridades, onde não-terminais são considerados nulários.

Derivações de Árvores[editar | editar código-fonte]

A gramática G, implicitamente, define um conjunto de árvores onde qualquer árvore que possa ser derivada de Z usando o conjunto de regras P é dita como sendo gerada por G. Esse conjunto de árvores é conhecido como o conjunto de linguagens de G. Mais formalmente, a relação ⇒G no conjunto TΣ(N) é definida da seguinte forma:

Uma árvore t1TΣ(N) pode ser derivada em um único passo numa árvore t2TΣ(N) (resumindo: t1G t2), se existe um contexto S e uma produção (At) ∈ P como no exemplo:

  • t1 = S[A], e
  • t2 = S[t].

Aqui, um contexto significa uma árvore com exatamente uma lacuna; se S é esse contexto, S[t] denota o resultado de preencher a árvore t na lacuna de S.

A linguagem de árvores gerada por G é a linguagem L(G) = { tTΣ | ZG* t }.

Aqui, TΣ denota o conjunto de todas as árvores compostas de símbolos de Σ, enquanto ⇒G* denota aplicações sucessivas de ⇒G.

Uma linguagem gerada por uma gramática de árvore regular é uma linguagem de árvores regular.

Exemplos[editar | editar código-fonte]

Exemplo árvore de derivação G1 em notação linear (tabela no canto superior esquerdo) e gráfica (figura principal)

Seja G1 = (N11,Z1,P1), onde

  • N1 = {Bool, BList } é o nosso conjunto de não-terminais,
  • Σ1 = { true, false, nil, cons(.,.) } é o nosso alfabeto ranqueado, aridades indicados pelos argumentos (i.e. o símbolo cons tem peso 2),
  • Z1 = BList é o nosso não-terminal inicial, e
  • o conjunto P1 consiste nas seguintes produções:
    • Boolfalse
    • Booltrue
    • BListnil
    • BListcons(Bool,BList)

Um exemplo de derivação da gramática G1 é

BListcons(Bool,BList) ⇒ cons(false,cons(Bool,BList)) ⇒ cons(false,cons(true,nil)).

A imagem demonstra a árvore de derivação correspondente; ela é uma árvore de árvores (figura principal), enquanto que a árvore de derivação da gramática de termos é uma árvore de cadeias (tabela no canto superior esquerdo).

A árvore gerada por G1 é o conjunto de todas as listas finitas de valores booleanos L(G1), que é igual a TΣ1. A gramática G1 corresponde a declaração de tipos algébricos

  datatype Bool
    = false
    | true
  datatype BList
    = nil
    | cons of Bool * BList

na linguagem de programação Standard ML: todos os membros de L(G1) correspondem a um valor do tipo BList em Standard ML.

Em outro exemplo, seja G2 = (N11,BList1,P1P2), usando o conjunto de não-terminais e o alfabeto definidos no exemplo anterior, mas estendendo o conjunto de produções anterior com P2, consistindo das seguintes produções:

  • BList1cons(true,BList)
  • BList1cons(false,BList1)

A linguagem L(G2) é o conjunto de todas as listas finitas de valores booleanos que contém true em pelo menos um item. O conjunto L(G2) não possui tipo de dado equivalente em Standard ML, nem em nenhuma outra linguagem funcional. Ele um conjunto próprio de L(G1). O termo do exemplo acima por acaso está em L(G2), tambpem, como mostra a derivação a seguir:

BList1cons(false,BList1) ⇒ cons(false,cons(true,BList)) ⇒ cons(false,cons(true,nil)).

Propriedades da Linguagem[editar | editar código-fonte]

Se ambos L1, L2 são linguagens de árvores regulares, então os conjuntos de árvores L1L2, L1L2, e L1 \ L2 também são linguagens de árvores regulares, e é decidível tanto para L1L2, quanto para L1 = L2.

Caracterizações adicionais e relações com outras linguagens formais[editar | editar código-fonte]

Rajeev Alur e Parthasarathy Madhusudan[2][3] relacionaram uma subclasse de linguagens de árvores binárias regulares a palavras aninhadas e linguagens visivelmente com pilha.

As linguagens de árvores regulares também são[4] as linguagens reconhecidas por Autômatos de árvore ascendentes e autômatos de árvore não-derterminísticos descendentes.

Gramáticas de árvores regulares são generalizações de Gramáticas Regulares.

Ver também[editar | editar código-fonte]

Leitura adicional[editar | editar código-fonte]

  • Um livro dedicado a gramáticas de árvore: Nivat, Maurice; Podelski, Andreas (1992). Tree Automata and Languages. Col: Studies in Computer Science and Artificial Intelligence. 10. [S.l.]: North-Holland 
  • Gramáticas de árvores regulares já haviam sido descritas em 1968 por:
  • As aplicações de gramáticas de árvores regulares incluem:
    • Seleção de Instruções em geração de código de compiladores:Emmelmann, Helmut (1991). «Code Selection by Regularly Controlled Term Rewriting». Code Generation - Concepts, Tools, Techniques. Workshops in Computing. Springer. pp. 3–29 
    • Um Problema de decisão para a lógica de primeira ordem, teoria formal de fórmulas sobre equivalência equivalência (=) e pertinência em conjuntos (∈) como únicos predicados: Comon, Hubert (1990). «Equational Formulas in Order-Sorted Algebras». Proc. ICALP 
    • Resolver cláusulas sobre conjuntos: Gilleron, R.; Tison, S.; Tommasi, M. (1993). «Solving Systems of Set Constraints using Tree Automata». 10th Annual Symposium on Theoretical Aspects of Computer Science. LNCS. 665. Springer. pp. 505–514 
    • O conjunto de todas as verdades que podem ser expressas na lógica de primeira ordem sobre uma algebra finita é sempre uma gramática de árvore regular: Burghardt, Jochen (2002). «Axiomatization of Finite Algebras» (PDF). Advances in Artificial Intelligence. LNAI. 2479. Springer. pp. 222–234. ISBN 3-540-44185-9 
  • Algoritmos sobre gramáticas de árvore regular são discutidos a partir de uma visão orientada pela eficiência em: Aiken, A.; Murphy, B. (1991). «Implementing Regular Tree Expressions». ACM Conference on Functional Programming Languages and Computer Architecture. pp. 427–447 
  • Dado um mapeamento de árvores em pesos, a generalização de Knuth do algoritmo de Dijkstra para encontrar o menor caminho pode ser aplicada a uma gramática de árvore regular para computar, para cada não-terminal, o peso mínimo da sua árvore de derivação: Knuth, D.E. (1977). «A Generalization of Dijkstra's Algorithm». Information Processing Letters. 6 (1): 1–5. doi:10.1016/0020-0190(77)90002-3 . Baseado nessa informação, é fácil enumerar suas linguagens em ordem de peso crescente. Em particular, qualquer não-terminal com um peso mínimo infinito produz a linguagem vazia.
  • Autômatos de árvores regulares tem sido generalizados para admitir testes de equivalência entre nós irmãos em árvores: Bogaert, B.; Tison, Sophie (1992). «Equality and Disequality Constraints on Direct Subterms in Tree Automata». Proc. 9th STACS. LNCS. 577. Springer. pp. 161–172 
  • Permitir teste de equivalência entre nós mais profundos levam a indecidibilidade: Tommasi, M. (1991), Automates d'Arbres avec Tests d'Égalités entre Cousins Germains, LIFL-IT 

Referências[editar | editar código-fonte]

  1. «Regular tree grammars as a formalism for scope underspecification». Predefinição:Citeseerx 
  2. Alur, Rajeev; P. (1 de janeiro de 2004). «Visibly Pushdown Languages». New York, NY, USA: ACM. Proceedings of the Thirty-sixth Annual ACM Symposium on Theory of Computing: 202–211. doi:10.1145/1007352.1007390  Sect.4, Theorem 5.
  3. Alur, Rajeev; P. (1 de maio de 2009). «Adding Nesting Structure to Words». J. ACM. 56 (3): 16:1–16:43. ISSN 0004-5411. doi:10.1145/1516512.1516518  Sect.7
  4. Comon et al, Tree Automata Techniques and Applications, 1997

Ligações externas[editar | editar código-fonte]