Quais modelos de computação podem ser expressos através de gramáticas?

18

Esta é uma reformulação dos programas de gramática São? solicitado anteriormente por Vag e com muitas sugestões dos comentaristas.

De que maneira uma gramática pode ser vista como especificando um modelo de computação? Se, por exemplo, usarmos uma gramática simples, livre de contexto, como

G ::= '1' -> '0' '+' '1'
      '1' -> '1' '+' '0'
      '2' -> '2' '+' '0'
      '2' -> '1' '+' '1'
      '2' -> '0' '+' '2'
      '3' -> '3' '+' '0'
      '3' -> '2' '+' '1'
      '3' -> '1' '+' '2'
      '3' -> '1' '+' '2'

Assumindo que o analisador não diferenciar entre terminais e não terminais símbolos como tenho demonstrado aqui, então é possível realizar operações aritméticas simples para números até 3.

Por exemplo, pegue a string

"2 + 0 + 1"

A execução de um analisador LR (1) nessa cadeia de caracteres deve fornecer a seguinte árvore de sintaxe concreta, na qual o resultado da computação é armazenado na raiz da árvore:

           '3'
         /  |  \
        /   |   \
      '2'  '+'  '1'
     / | \
    /  |  \
  '2' '+' '0' 

Assim, se considerarmos uma gramática um programa e um gerador de analisador um compilador , poderemos ver a linguagem de especificação gramatical como uma linguagem de programação ?

Além disso, poderíamos criar programas completos de Turing especificando gramáticas semelhantes a como você pode criar programas completos de turing com autômatos celulares ou o cálculo lambda ?

Em outras palavras, sabe-se que, no sentido de reconhecer uma linguagem, linguagens regulares correspondem a autômatos de estados finitos , linguagens livres de contexto correspondem a autômatos push-down e linguagens sensíveis a contexto correspondem a autômatos limitados lineares . No entanto, se considerarmos as gramáticas como dispositivos computacionais (ou seja, programas no sentido do exemplo acima), como classificamos a força computacional de cada classe de gramática na hierarquia de Chomsky?

Além disso, que tal as subclasses menos conhecidas de gramáticas, como

EDIT: A propósito, este é um detalhe na minha própria pergunta, mas eu não mencionei que não dei nenhum símbolo inicial para a gramática de exemplo e acenei com a mão na necessidade de distinguir entre terminais e não terminais. Tecnicamente ou tradicionalmente, acho que a gramática provavelmente teria que ser escrita de uma forma mais complicada como esta (onde S é o símbolo inicial e $ representa o terminal de final de fluxo):

G ::= S -> R0 '$'
      S -> R1 '$'
      S -> R2 '$'
      R0 -> '0'
      R0 -> R0 '+' '0'
      R1 -> '1'
      R1 -> R0 '+' '1'
      R1 -> '1' '+' R0
      R1 -> R0 '+' '1' '+' R0
      R2 -> '2'
      R2 -> R0 '+' '2'
      R2 -> '2' '+' R0
      R2 -> R0 '+' '2' '+' R0
      R2 -> R1 '+' '1'
      R2 -> R1 '+' '1' '+' R0

... não que isso realmente mude alguma coisa, mas achei que deveria mencionar.

Edição: Outra coisa que me veio à mente quando li a resposta de Gasche é que cada ramo da árvore no meu exemplo representa uma sub-computação. Se você observar cada regra de produção como uma função em que o LHS representa o resultado e o RHS representa seus argumentos, a estrutura da gramática determina como as funções são compostas.

Em outras palavras, o contexto do analisador, juntamente com seu mecanismo de orientação, ajuda a determinar não apenas quais funções aplicar ('como' um polimorfismo paramétrico), mas como elas devem ser compostas para formar novas funções.

Pelo menos, eu acho que você poderia olhar desta maneira para CFGs inequívocos, para outras gramáticas a ginástica mental é um pouco demais para mim agora.

Rehno Lindeque
fonte
3
Você esqueceu de mencionar o Viston Pushdown Automaton (palavras aninhadas), um dispositivo adorável e promissor! É importante porque parece haver uma melhoria mínima em relação aos regexps para poder analisar programas escritos em linguagens de programação populares. ( cis.upenn.edu/~alur/nw.html )
Vag
1
Obrigado, isso é muito interessante, eu não procurei! Há outras que também pulei como deterministas, livres de contexto, adjacentes a árvores, indexadas e assim por diante. Apenas pensei que poderia ser um pouco demais para uma pergunta ... Mas talvez eu as adicione
Rehno Lindeque
1
@imz Quero dizer gramáticas, pois são formalmente definidas na hierarquia chomsky (ou seja, como conjuntos de produções). Como estou reivindicando exatamente o que você está dizendo: que gramáticas são programas, significa apenas a classe de programas representável por gramáticas (que é a questão).
Rehno Lindeque
1
@ imz Para ser honesto, não estou realmente familiarizado com gramáticas indexadas, apenas as adicionei como uma reflexão tardia.
Rehno Lindeque
1
Estou começando a pensar que pode ter sido uma boa ideia postar esta pergunta no fórum do LtU, em vez de examinar as discussões interessantes: P. Entre @imz, talvez seja melhor ler a pergunta como "quais classes de gramática correspondem a quais classes de programas no sentido 'funcional' descrito por Jukka na resposta de Marc Hamman". Talvez eu deveria fazer isso, porém mais claro ...
Rehno Lindeque

Respostas:

10

Existe uma correspondência individual entre as gramáticas Chomsky Tipo 0 e as máquinas de Turing.

Isso é explorado na linguagem de programação Thue, que permite escrever programas completos de Turing especificados por uma string inicial e um conjunto de regras de reescrita de strings (uma gramática semi-Thue , que é equivalente a uma gramática tipo 0).

ATUALIZAR:

Além de linguagens esotéricas de "Turing tar-pit" como Thue, várias linguagens de uso geral que permitem ao programador estender sua própria sintaxe podem ser usadas para executar o cálculo completo de Turing durante o estágio de análise-compilação.

Os idiomas da família Lisp , em particular o Common Lisp , são provavelmente os exemplos mais óbvios, mas também, de maneira geral, idiomas com verificação estática de tipo que nem sempre precisam ser interrompidos, como C ++ com modelos , Scala e Qi .

Antonio Valério Miceli-Barone
fonte
Mas a questão é sobre coisas que funcionam ao contrário: deve-se chegar ao resultado não reescrevendo uma sequência inicial de símbolos de acordo com as regras, mas o "resultado" da computação definida por uma gramática nesta pergunta é uma inicial símbolo que pode produzir a sequência de "entrada" de acordo com as regras da gramática.
imz - Ivan Zakharyaschev
2
concumat(qvocêote(Eun),ovocêt)TM(Eun)=ovocêt
Concordo que a correspondência entre gramáticas do Tipo 0 e TMs é uma resposta válida para a pergunta (especialmente, se restrita à computação de funções sim / não). A sugestão adicional de modelar uma MT arbitrária com uma gramática, introduzindo alguma convenção sobre como representar os pares de entrada e saída, parece-me não corresponder ao interesse pretendido da pergunta original: (a ser continuado)
imz - Ivan Zakharyaschev
Entendo-o como uma questão para explorar exatamente as estruturas gramaticais existentes e os analisadores correspondentes para realizar cálculos, ou seja, a forma permitida da tradução entre uma função f e uma gramática pode ser apenas: uma entrada que eu fui analisada como S significa f ( I) = S.
imz - Ivan Zakharyaschev
1
Superficialmente, a linguagem de programação Thue não parece se encaixar nesse tipo de estrutura gramatical: embora tenha reescrevendo regras como uma gramática, o cálculo de um resultado de uma entrada vai na direção das regras, não no sentido inverso. direção, como Rehno quer. (Mas talvez seja apenas uma questão de mudar a direção das setas nas produções: traduzir uma gramática "computação como analisador" no sentido deste Q para Thue poderia ser apenas mudar as direções das regras, então o programa Thue chegará aos símbolos iniciais como os resultados, não é mesmo? ..)
imz - Ivan Zakharyaschev
6

Minha resposta não tem a intenção de ser formal, precisa e absolutamente in-topic. Acho que a resposta de Marc Hamman é sólida, mas sua pergunta me fez pensar em um tópico relacionado.

As gramáticas podem ser consideradas casos especiais de sistemas dedutivos: a entrada é um julgamento e a árvore de análise é uma derivação do julgamento, ou prova de que o julgamento é válido de acordo com as regras (gramaticais).

Nesse sentido, sua pergunta pode estar relacionada à abordagem de alguma parte da comunidade de programação lógica / pesquisa de prova (estou pensando em Dale Miller, por exemplo), que é que a pesquisa de prova tem conteúdo computacional, em oposição ao mais clássico ponto de vista da teoria do tipo / prova em que o cálculo é a normalização da prova .

Observação: relendo minha resposta, acho que a idéia de que "a construção de árvore de análise é prova de pesquisa" é um pouco exagerada aqui. A pesquisa de provas flui na outra direção: uma parte de um julgamento bastante complexo e, pelo uso repetido de regras de inferência que trabalham na estrutura da prova, esperamos alcançar axiomas mais simples que não precisam ser mais provados. Portanto, seria mais natural ver, em termos gramaticais, julgamentos complexos como não terminais, átomos como terminais e a pesquisa de provas como um problema de geração de palavras ou teste de não-vazio.

gasche
fonte
Comentários muito interessantes. Meu cérebro é um pouco cansado demais para dar uma boa resposta agora, no entanto, em meu exemplo os ramos da árvore representam essencialmente sub-computações que são compostas em conjunto de acordo com as regras de análise ...
Rehno Lindeque
6

Além disso, poderíamos criar programas completos de Turing especificando gramáticas ...?

Não sei se entendi corretamente sua pergunta, mas se você estiver procurando por uma linguagem de programação baseada em um tipo de sistema de reescrita de strings, provavelmente estará interessado em Refal , que é baseado no formalismo do algoritmo Markov (um método de Turing- formalismo completo, que também é um sistema de reescrita de sequências gramaticais).

Artem Pelenitsyn
fonte
1
Entendi a pergunta da seguinte maneira: Rehno está interessado no processo de análise de inicialização (definido por uma gramática) para ser visto como uma computação do resultado. A computação deve construir o resultado das partes que vão na direção oposta às regras de produção da gramática. As regras de reescrita de Refal (IIUC, semelhante à linguagem de programação Thue mencionada acima) iriam na outra direção (da entrada ao resultado).
imz - Ivan Zakharyaschev
Agora que penso nisso, as gramáticas sensíveis ao contexto têm mais de um símbolo no LHS das regras de produção. Então, acho que não há diferença prática real. Um analisador para uma linguagem sensível ao contexto seria um sistema de reescrita de cadeias, não importa como você a veja, certo?
Rehno Lindeque
@imz obrigado pelo esclarecimento sobre a pergunta de Rehno. @Rehno “Um analisador para uma linguagem sensível ao contexto seria um sistema de reescrita de strings, não importa como você a veja, certo?” - provavelmente faz sentido, sim.
Artem Pelenitsyn
Mas as regras de reescrita de Refal são tratadas de maneira não determinística? (Ou, de outra forma: Refal fará o retrocesso na busca de um caminho de reescrita funcional?) Se queremos modelar essa abordagem de "análise como computação" com regras de reescrita na direção inversa, precisamos de regras não determinísticas; considere uma gramática parecida S -> A a; S -> B b; A -> 0; B -> 0. Se programarmos isso revertendo as regras, precisaremos escolher regras diferentes para o processamento 0em tempo de execução para avaliar "0a" ou "0b" como S.
imz - Ivan Zakharyaschev
6

(Apenas algumas considerações triviais. Pode ser um comentário, mas muito longo.)

De fato, o que você descreve parece ser a visão muito natural sobre o que é uma língua (no entendimento humano da "linguagem", seu objetivo) e como a gramática define uma linguagem.

Uma linguagem compreende (infinitamente muitas) formas sintáticas corretas que são interpretadas para fornecer os valores semânticos .

Se a interpretação for computável, as formas sintáticas de uma linguagem podem ser vistas como programas que calculam os valores semânticos.

Se assumirmos que uma linguagem é implementada como um dispositivo finito, podemos chamar essa representação finita de uma linguagem de "gramática". De acordo com esse entendimento, uma gramática se preocupa com a sintaxe, mas também com a semântica, ou seja, como calcular o valor semântico de uma expressão inteira a partir dos valores de suas partes (as partes atômicas e seus valores são armazenados em um "léxico") .

Algumas teorias da linguagem natural têm essa forma (a forma que é consistente com as considerações acima; já foi mencionada na resposta de @ gasche aqui): um sistema dedutivo que busca uma derivação da entrada (juntamente com o cálculo da semântica valor ou a construção do termo de prova; cf. correspondência de Curry-Horward). Portanto, se olharmos para sistemas como esse e os considerarmos gramáticas, sua pergunta será trivial : esses sistemas são exatamente criados para realizar cálculos da maneira que você descreve.

fGEu f(Eu)=SEuSG

(De fato, os compiladores reais para linguagens de programação se parecem mais com um sistema com sintaxe e semântica: eles transformam a forma sintática de um programa em um executável, que é o significado semântico do programa, e não apenas em um símbolo inicial da gramática.)

imz - Ivan Zakharyaschev
fonte
4

Apenas para adicionar:

Um programa de lógica pura possui leitura declarativa e leitura processual. Este relatório discute a ideia de que estes podem ser complementados por uma leitura gramatical, onde as cláusulas são consideradas como reescrevendo regras de uma gramática. O objetivo é mostrar que esse ponto de vista facilita a transferência de conhecimentos da programação lógica para outras pesquisas em linguagens de programação e vice-versa. Alguns exemplos dessa transferência são discutidos. Por outro lado, a visão gramatical apresentada justifica algumas extensões ad hoc à programação lógica pura e facilita o desenvolvimento de fundamentos teóricos para tais extensões.

Uma visão gramatical da programação lógica por Pierre Deransart e Jan Maluszynski.

Vag
fonte
Aparentemente, o Prolog surgiu das gramáticas de atributos; portanto, é essa visão que inicia a programação lógica.
Reinierpost
1

Que tal algo como números Peano:

S    -> int
int  -> zero
int  -> succ
zero -> "0"
succ -> "#" int

ele reconhecerá qualquer string (número) deste formulário:

0   // zero
#0  // one
##0 // two

e deve retornar uma estrutura aninhada, com a profundidade sendo o número.

Mas começa a ficar complicado quando se quer implementos, basta dizer adição:

S    -> int
int  -> sum
int  -> zero
int  -> succ
zero -> "0"
succ -> "#" int
sum  -> int "+" int

Faz todo sentido, pois reconhecerá apenas ints bem formados como este:

#####0 + ####0

Mas essa gramática introduz uma divisão na árvore de análise sempre que houver uma soma. Portanto, em vez de termos uma árvore ramificada agradável, que mapeia diretamente para um número, temos a estrutura da expressão, ainda a alguns cálculos da efetiva valor. Portanto, nenhum cálculo é feito, apenas reconhecimento. O problema pode não ser a gramática, mas o analisador. Em vez disso, pode-se usar outra coisa, idk ... Outro ponto que vem à mente é a adequação do formalismo gramatical para expressar a computação. Quando você olha o axioma de um Peano (em notação semelhante a Haskell):

1) Nat = Zero
2) Nat = Succ Nat
3) Sum ( Succ X ) ( Y ) = Succ ( X + Y )
4) Sum Zero X = X

A terceira regra declara explicitamente uma transformação. Alguém poderia imaginar ter a mesma quantidade de significado em uma regra gramatical livre de contexto. E se sim, como!?

pai
fonte