Gramática de movimento literal

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

Gramáticas de movimento literal (LMGs do inglês Literal movement grammar) vem de um formalismo introduzido por Groenink em 1995. Destina-se a caracterização de fênomenos de extraposição da linguagem natural, como topicalização e cross-serial. LMGs estendem da classe das gramáticas livres de contexto (GLCs), introduzido semântica reescrita na forma de função de correspondência de padrões, bem como operações de união e eliminação de uma variável.

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

A operação de escrita de uma LMG é muito semelhante a de uma GLC, com a adição de "argumentos" para os símbolos não-terminais. Enquanto a gramática livre de contexto obedece como regra geral S → α, ou seja, cada não terminal S gera algum terminal α ou uma nova variável com um terminal, uma regra LMG obedece o esquema geral X(x1,...,xn) → α onde X é um não terminal de aridade n (chamado de predicado na terminologia do LMG), e α é uma palavra de “itens” (definido posteriormente). Os argumentos xi são sequências de símbolos terminais e/ou variáveis que definem o padrão. No caso em que um padrão possui múltiplas variáveis de adjacências, corresponderá a quaisquer partições de mesmo valor. Assim, se o predicado é f (x, y) e o padrão real é f (ab), há três resultados válidos: x = ε, y = ab; x = a, y = b; x = ab, y = ε. Desta forma uma única regra é um conjunto de possibilidades. Um “item” em gramática de momvimento literal é da forma

  • , um predicado de aridade n
  • , uma variável x ligada com a palavra produzida por
  • , uma remoção de por uma palavra de terminais/ou variáveis a

Em uma regra onde f(x1,...,xm) → α y:g(z1,...,zn)β, a variável y é ligada com qualquer símbolo terminal produzido pelo predicado g, e em α e β, todas as ocorrências de y são substituídas por palavras, e em α e β são produzidas como se símbolos terminais ali estivessem. Um item , onde x é algo que produz uma string terminal (tanto por ela mesma como por algum predicado), e y é uma palavra de terminais e/ou variáveis, é escrita como uma palavra vazia (ε) se e somente se , caso contrário, não pode ser escrita.

Exemplo[editar | editar código-fonte]

LMGs são caracterizadas de  linguagens, não-livre de contexto como segue:

   S() → x: A() B(x)
   S() → a A()
   A() → ε
   B(xy) → a/x b B(y)c
   B(ε) → ε 

A derivação para aabbcc, usando parêntesis para indicar agrupamento é

   S() → x:A() B(x) → x:(a A()) B(x) → x:(aa A()) B(x) → x:aa B(x) → aa B(aa)
   → aa a/a b B(a) c → aab B(a) c → aab a/a b B() cc → aabb B() cc → aabbcc

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

A operação de escrita de uma LMG é muito semelhante a de uma GLC, com a adição de "argumentos" para os símbolos não-terminais. Enquanto a gramática livre de contexto obedece como regra geral S → α, ou seja, cada não terminal S gera algum terminal α ou uma nova variável com um terminal, uma regra LMG obedece o esquema geral X(x1,...,xn) → α onde X é um não terminal de aridade n (chamado de predicado na terminologia do LMG), e α é uma palavra de “itens” (definido posteriormente). Os argumentos xi são sequências de símbolos terminais e/ou variáveis que definem o padrão. No caso em que um padrão possui múltiplas variáveis de adjacências, corresponderá a quaisquer partições de mesmo valor. Assim, se o predicado é f (x, y) e o padrão real é f (ab), há três resultados válidos:


Poder Computacional[editar | editar código-fonte]

Linguagens geradas por esta gramática contem as linguagens livres de contexto como subconjunto, como cada CFG é um LMG, onde todos os predicados têm aridade 0 e nenhuma regra de produção contém ligações entre variáveis ou exclusões.

Referências

  1. Groenink, Annius V. 1995. Literal Movement Grammars. In Proceedings of the 7th EACL Conference.