O que você obteria se adicionasse parâmetros às gramáticas livres de contexto?

13

Eu estava pensando em gramáticas para linguagens sensíveis a indendências e parece que as gramáticas CF fariam o truque se combinadas com parâmetros. Como exemplo, considere este fragmento para gramática simplificada do Python no formato ANTLR:

// on top-level the statements have empty indent
program  
    : statement('')+
    ;

// let's consider only one compound statement and one simple statement for now
statement(indent) 
    : ifStatement(indent)
    | passStatement(indent)
    ;

passStatement(indent)
    : indent 'pass' NEWLINE
    ;

// statements under if must have current indent plus 4 spaces
ifStatement(indent)
    : indent 'if' expression ':' NEWLINE (statement(indent '    ')+)
    ;

Minha pergunta: esse tipo de gramática (CFG com parâmetros) tem um nome?

Parece que não seria difícil escrever um analisador de descida recursiva para esta gramática (os parâmetros devem ser basicamente analisadores). Quais poderiam ser as dificuldades com essa abordagem?

A adição de parâmetros eleva a classe de idioma suportada acima de livre de contexto?

Aivar
fonte
1
Se o conjunto de valores que os parâmetros podem assumir for finito, será trivialmente livre de contexto (você poderá iterar sobre todos os valores e escrever tudo).
catraca aberração
1
Vale ressaltar que sua proposta é para idiomas sensíveis ao recuo com recuo fixo. Python (e outras linguagens) não são restritas dessa maneira; eles aceitam o recuo que o usuário deseja. Isso não afeta a analisabilidade (exceto para manipular caracteres de tabulação), mas seria difícil expressar sua proposta, pelo menos como eu a entendo.
rici
@HendrikJan, gramáticas de atributos são uma maneira de anotar gramática com ação semântica, elas não controlam a análise.
precisa saber é o seguinte
1
Se o objetivo é manipular o recuo, isso é mais adequado para o tokenizer do que para o analisador. Faça com que o tokenizador emita tokens INDENT e UNINDENT virtuais quando o nível de indentação for alterado. Então não há necessidade de aumentar a gramática do idioma com informações sobre recuo.
John Kugelman

Respostas:

14

As gramáticas de afixo ( gramáticas parametrizadas e livres de contexto) foram estudadas extensivamente pelo eminente cientista da computação holandês Cornelis HA Koster , começando com seu artigo de 1962 "Basic English, uma gramática generativa para uma parte do inglês", co-escrito com LGLT Meertens. Em 1970, ele produziu um formalismo do conceito; uma visão geral útil está disponível em seu artigo de 1971, "Affix Grammars for Programming Languages", cuja versão encontrei no Citeseer .

Nesse artigo, Koster compara seu formalismo (e outro semelhante) com gramáticas de dois níveis de Van Wijngaarden e as considera muito semelhantes.

A bibliografia anotada inestimável de Dick Grune sobre técnicas de análise inclui um grande número de outras referências úteis para gramáticas de afixação e outros formalismos não-Chomskyianos. (Consulte a seção 18.2.6 da bibliografia, embora existam artigos úteis em outras seções.) Grune aborda gramáticas de afixos brevemente no §15.3.2 da segunda edição de Técnicas de análise: um guia prático (e ainda mais brevemente na primeira edição). , disponível on-line) mencionando o fato de que é fácil adaptar as técnicas de análise de cima para baixo (e outras).

umanbncn

Koster, que também foi editor do relatório Algol 68, foi o desenvolvedor original da Compiler Description Language (CDL) , com base em suas idéias sobre gramáticas de afixação. Este kit de ferramentas e seus derivados posteriores foram utilizados na produção por muitos anos. Esta página , que encontrei com uma pesquisa no Google e cuja permanência não posso garantir, possui links para o manual e o site de download do CDL3.

rici
fonte
Eu sinto que as linguagens CDL são mais como gramáticas de atributos : os valores dos atributos podem ser calculados por funções definidas externamente. Eu reservaria a gramática de afixo de nome para os casos em que os relacionamentos entre os valores dos afixos (atributos) são definidos dentro do formalismo, como nas Gramáticas de afixo estendido .
Reinierpost
@reinierpost: é claro que você tem direito à sua própria terminologia; o privilégio não se restringe aos ovos antropomórficos. No entanto, o próprio manual da CDL afirma que "CDL3 é uma linguagem de implementação baseada em gramáticas de afixos", que eu acho que deve ser levada em consideração. (Manual disponível em ftp.cs.kun.nl/pub/cdl3/cdl3-manual-1.2.7.pdf ). Foi o que afirmei na minha resposta: que o CDL se baseava no trabalho de Koster sobre gramáticas de afixação. Como Grune aponta, a diferença entre gramáticas de afixo e atributo é pequena; sua distinção é se os afixos são usados ​​para decidir a validade sintática.
rici
(A citação é da primeira página do manual.)
rici
Eu sei ... e você está certo. Meu comentário não foi feito para contradizê-lo.
Reinierpost
6

Tome o lema de bombeamento para CFGs :

Pegue a gramática

S -> A("")
A(p) -> p 
      | p '\n' A(p"*") '\n' p 

Isso descreve um triângulo estelar:

*
**
***
**
*

Não há como dividir um triângulo estelar em 5 partes vocêvWxy de tal modo que {vocêvnWxny|n>0 0} também é um triângulo estelar (com vx não vazio).

Isso significa que o triângulo estelar não é uma linguagem livre de contexto.

Ou um exemplo mais simples:

S-> B("")
B(p)-> p 'a' p 'a' p
     | B(p 'b')

Isso descreve o idioma {bnumabnumabn|n0 0} que não é livre de contexto.

catraca arrepiante
fonte
3

Eu nunca vi esse formalismo apresentado (mesmo em algo como as Técnicas de Análise de Grune ), dependendo dos detalhes de como você define exatamente "os parâmetros devem ser basicamente analisadores", parece mapeado para van Wijngaarden duas gramáticas de nível, que têm o mesmo poder que gramática irrestrita da estrutura de fase (ou seja, mais poderosa que sensível ao contexto, você pode escrever uma gramática VW que fornece todos os programas de interrupção).

AProgrammer
fonte
Koster e seu grupo estudaram dois tipos de gramáticas de afixo, até onde sei: 1) formas restritas de gramáticas de Van Wijngaarden, destinadas a permitir um reconhecimento mais fácil; 2) as linguagens CDL, linguagens práticas de descrição do compilador sem manipulação explícita de valor de afixo, mas com a opção de definir regras na linguagem de destino (por exemplo, assembler), tornando-as completas em Turing.
Reinierpost