Como devo especificar uma gramática para um analisador?

Estou programando há muitos anos, mas uma tarefa que ainda me leva excessivamente longa é especificar uma gramática para um analisador e, mesmo após esse esforço excessivo, nunca tenho certeza de que a gramática que eu for apresentada seja boa ( por qualquer medida razoável de "bom").

Não espero que exista um algoritmo para automatizar o processo de especificação de uma gramática, mas espero que haja maneiras de estruturar o problema que elimine grande parte das suposições e tentativas e erros da minha abordagem atual.

Meu primeiro pensamento foi ler sobre analisadores, e já fiz um pouco disso, mas tudo o que li sobre esse assunto toma a gramática como um dado (ou trivial o suficiente para que você possa especificá-la por inspeção), e se concentra em o problema de traduzir essa gramática em um analisador. Estou interessado no problema imediatamente antes: como especificar a gramática em primeiro lugar.

Estou interessado principalmente no problema de especificar uma gramática que represente formalmente uma coleção de exemplos concretos (positivos e negativos). Isso é diferente do problema de criar uma nova sintaxe . Agradecemos a Macneil por apontar essa distinção.

Eu realmente nunca apreciei a distinção entre gramática e sintaxe, mas agora que estou começando a vê-la, pude aprimorar meu primeiro esclarecimento dizendo que estou interessado principalmente no problema de especificar uma gramática que imporá uma sintaxe predefinida: acontece que, no meu caso, a base dessa sintaxe geralmente é uma coleção de exemplos positivos e negativos.

Como a gramática é especificada para um analisador? Existe um livro ou referência lá fora, que é o padrão de fato para descrever práticas recomendadas, metodologias de design e outras informações úteis sobre a especificação de uma gramática para um analisador? Em que pontos, ao ler sobre a gramática do analisador, devo me concentrar?

Nos arquivos de amostra, você precisará tomar decisões com base em quanto deseja generalizar a partir desses exemplos. Suponha que você tenha os três exemplos a seguir: (cada um é um arquivo separado)

f() {}
f(a,b) {b+a}
int x = 5;

Você pode especificar trivialmente duas gramáticas que aceitarão essas amostras:

Gramática trivial 1:

start ::= f() {} | f(a,b) {b+a} | int x = 5;

Gramática trivial dois:

start ::= tokens
tokens ::= token tokens | <empty>
token ::= identifier | literal | { | } | ( | ) | , | + | = | ;

O primeiro é trivial porque aceita apenas as três amostras. O segundo é trivial porque aceita tudo o que poderia usar esses tipos de token. [Para esta discussão, vou assumir que você não está muito preocupado com o design do tokenizer: é simples assumir identificadores, números e pontuação como seus tokens, e você pode emprestar qualquer conjunto de tokens de qualquer linguagem de script que desejar. de qualquer maneira.]

Portanto, o procedimento que você precisará seguir é começar no nível mais alto e decidir "quantas de cada instância eu quero permitir?" Se uma construção sintática puder fazer sentido repetir inúmeras vezes, como methods em uma classe, você desejará uma regra com este formulário:

methods ::= method methods | empty

O que é melhor indicado no EBNF como:

methods ::= {method}

Provavelmente será óbvio quando você deseja apenas zero ou uma instância (o que significa que a construção é opcional, como na extendscláusula para uma classe Java), ou quando você deseja permitir uma ou mais instâncias (como em um inicializador de variável em uma declaração ) Você precisará estar atento a questões como exigir um separador entre elementos (como ,em uma lista de argumentos), exigir um terminador após cada elemento (como nas ;instruções para separar) ou não exigir separador ou terminador (como o caso com métodos em uma classe).

Se seu idioma usa expressões aritméticas, seria fácil copiar das regras de precedência de um idioma existente. É melhor seguir algo bem conhecido, como as regras de expressão de C, do que procurar algo exótico, mas apenas desde que tudo o resto seja igual.

Além dos problemas de precedência (o que é analisado um ao outro) e de repetição (quantos de cada elemento devem ocorrer, como eles são separados?), Você também precisará pensar em ordem: algo sempre deve aparecer antes de outro? Se uma coisa está incluída, outra deve ser excluída?

Nesse ponto, você pode ficar tentado a aplicar gramaticalmente algumas regras, uma regra como se a Personidade de uma pessoa for especificada e você não desejar permitir que a data de nascimento também seja especificada. Embora você possa construir sua gramática para fazer isso, talvez seja mais fácil aplicá-lo com um passe de "verificação semântica" depois que tudo for analisado. Isso mantém a gramática mais simples e, na minha opinião, gera melhores mensagens de erro para quando a regra é violada.

Onde posso aprender como especificar a gramática de um analisador?

Para a maioria dos geradores de analisador, é geralmente alguma variante de Backus-Naur 's <nonterminal> ::= expressionformato. Eu vou assumir que você está usando algo assim e não está tentando criar seus analisadores manualmente. Se você pode produzir um analisador para um formato em que recebeu a sintaxe (incluímos um exemplo de problema abaixo), especificar gramáticas não é problema seu.

O que eu acho que você está enfrentando é separar a sintaxe de um conjunto de amostras, que é realmente mais reconhecimento de padrões do que analisando. Se você está tendo que recorrer a isso, significa que quem está fornecendo seus dados não pode fornecer sua sintaxe, porque eles não têm um bom controle sobre seu formato. Se você tiver a opção de recuar e pedir a eles para fornecer uma definição formal, faça-o. Não é justo que eles ofereçam um problema vago se você puder ser responsabilizado pelas consequências de um analisador com base em uma sintaxe deduzida que aceita entradas ruins ou rejeita entradas boas.

... nunca tenho certeza de que a gramática apresentada seja boa (por qualquer medida razoável de "boa").

"Bom" na sua situação teria que significar "analisa os pontos positivos e rejeita os negativos". Sem nenhuma outra especificação formal da sintaxe do seu arquivo de entrada, as amostras são seus únicos casos de teste e você não pode fazer nada melhor do que isso. Você pode colocar o pé no chão e dizer que apenas os exemplos positivos são bons e rejeitar qualquer outra coisa, mas isso provavelmente não está no espírito do que você está tentando realizar.

Sob circunstâncias mais saudáveis, testar uma gramática é como testar qualquer outra coisa: você precisa criar casos de teste suficientes para exercitar todas as variantes dos não terminais (e terminais, se estiverem sendo gerados por um lexer).

Problema de exemplo

Escreva uma gramática que analise os arquivos de texto que contêm uma lista, conforme definido pelas regras abaixo:

• Uma lista consiste em zero ou mais coisas .
• Uma coisa consiste em um identificador , uma chave aberta, uma lista de itens e uma chave de fechamento.
• Uma _item_list_ consiste em zero ou mais itens .
• Um item consiste em um identificador , um sinal de igual, outro identificador e um ponto e vírgula.
• Um identificador é uma sequência de um ou mais dos caracteres AZ, az, 0-9 ou o sublinhado.
• Espaço em branco é ignorado.

Exemplo de entrada (todos válidos):

clank { foo = bar; baz = bear; }
clunk {
    quux =bletch;
    281_apple = OU812;
    He_Eats=Asparagus ; }

As respostas de Macneil e Blrfl são ótimas. Eu só quero adicionar alguns comentários sobre o início do processo.

Uma sintaxe é apenas uma maneira de representar um programa . Portanto, a sintaxe do seu idioma deve ser determinada pela sua resposta a esta pergunta: O que é um programa?

Você pode dizer que um programa é uma coleção de classes. Ok, isso nos dá

program ::= class*

como ponto de partida. Ou você pode ter que escrever

program ::= ε
         |  class program

Agora, o que é uma aula? Tem um nome; uma especificação opcional de superclasse; e várias declarações de construtor, método e campo. Além disso, você precisa de uma maneira de agrupar uma classe em uma única unidade (não ambígua), e isso deve envolver algumas concessões à usabilidade (por exemplo, marque-a com a palavra reservada class). OK:

class ::= "class" identifier extends-clause? "{" class-member-decl * "}"

Essa é uma notação ("sintaxe concreta") que você pode escolher. Ou você pode facilmente decidir sobre isso:

class ::= "(" "class" identifier extends-clause "(" class-member-decl* ")" ")"

ou

class ::= "class" identifier "=" "CLASS" extends-clause? class-member-decl* "END"

Você provavelmente já tomou essa decisão implicitamente, especialmente se você tiver exemplos, mas eu só quero reforçar o ponto: A estrutura da sintaxe é determinada pela estrutura dos programas que ela representa. É isso que faz você passar pelas "gramáticas triviais" da resposta de Macneil. Programas de exemplo ainda são muito importantes, no entanto. Eles servem a dois propósitos. Primeiro, eles ajudam a descobrir, no nível abstrato, o que é um programa. Segundo, eles ajudam a decidir qual sintaxe concreta você deve usar para representar a estrutura da sua linguagem.

Depois que a estrutura estiver desativada, você deve voltar e lidar com questões como permitir espaços em branco e comentários, corrigir ambiguidades etc. Isso é importante, mas é secundário ao design geral e depende muito do tecnologia de análise que você está usando.

Por fim, não tente representar tudo sobre o seu idioma na gramática. Por exemplo, convém proibir certos tipos de código inacessível (por exemplo, uma declaração após a return, como em Java). Você provavelmente não deve tentar incluir isso na gramática, porque ou sentirá falta de coisas (gritos, e se returnestiver entre chaves, ou se os dois ramos de uma ifdeclaração retornarem?) Ou tornará sua gramática muito complicada gerenciar. É uma restrição sensível ao contexto ; escreva-o como um passe separado. Outro exemplo muito comum de uma restrição sensível ao contexto é um sistema de tipos. Você poderia rejeitar expressões como 1 + "a"na gramática, se trabalhasse bastante, mas não poderia rejeitar 1 + x(onde xtem o tipo string). assimevite restrições pela metade na gramática e faça-as corretamente como um passe separado.