Na ciência da computação, uma gramática de análise sintática de expressão, ou GASE, é um tipo de gramática formal analítica, ou seja, ela descreve uma linguagem formal em termos de um conjunto de regras para o reconhecimento de cadeias na linguagem. O formalismo foi introduzido por Bryan Ford em 2004 e está intimamente relacionado com a família de linguagens analíticas de cima para baixo (em inglês, top-down) introduzidas no início de 1970. Sintaticamente, GASEs também são semelhantes a gramáticas livres de contexto (GLCs), mas elas têm uma interpretação diferente: o operador escolha seleciona o primeiro jogo em GASE, enquanto é ambígua na GLC. Isto está mais próximo de como o reconhecimento de uma cadeia tende a ser feito na prática, por exemplo, por um analisador recursivo de descida.

Ao contrário das GLCs, GASEs não podem ser ambíguas; Se uma cadeia é analisada sintaticamente, então ela tem exatamente um árvore de análise sintática válida. Conjectura-se que existem linguagens livres de contexto que não pode ser analisadas sintaticamente por uma GASE, mas isso ainda não está comprovado.  GASEs são bem adaptadas para analisar linguagens de computador, mas não as linguagens naturais, onde seu desempenho é comparável ao de algoritmos gerais de GLC, como o algoritmo de Earley.

Definição

Sintaxe Formalmente, uma gramática de análise sintática de expressão consiste em:

Um conjunto finito N de símbolos não-terminais. Um conjunto finito Σ de símbolos terminais que é disjunto em relação a N. Um conjunto finito P de regras de análise sintática. Uma expressão eS denominada de expressão inicial.

Cada regra de análise sintática em P tem a forma A ← e, em que A é um símbolo não-terminal e e é uma expressão de análise sintática. Uma expressão de análise sintática é uma expressão hierárquica semelhante a uma expressão regular, a qual é construída da seguinte forma:

Uma expressão de análise sintática atômica consiste de: qualquer símbolo terminal, qualquer símbolo não-terminal, ou a cadeia vazia ε. Dadas quaisquer expressões de análise sintática e, e1, e e2 existentes, uma nova expressão de análise sintática pode ser construída usando os seguintes operadores: Sequencia: e1 e2 Escolha ordenada: e1 / e2 Zero-ou-mais: e* Um-ou-mais: e+ Opcional: e? Predicado-E: &e Predicado-Não: !e

Semânticas

A diferença fundamental entre gramáticas livres de contexto e gramáticas de análise sintática de expressão é que o operador de escolha da GASE é ordenado. Se a primeira alternativa for bem-sucedida, a segunda alternativa é ignorada. Assim escolha ordenada não é comutativa, ao contrário de escolha não ordenada como em gramáticas livres de contexto. Escolha ordenada é análoga aos operadores de corte macio disponíveis em algumas linguagens de programação lógica.

A conseqüência é que, se uma GLC é transliterada diretamente a uma GASE, qualquer ambiguidade na antiga é resolvida escolhendo uma árvore de análise sintática deterministicamente a partir das possíveis análises sintáticas. Escolhendo cuidadosamente a ordem em que as alternativas da gramática são especificadas, um programador tem um grande controle sobre qual árvore de análise sintática é selecionada.

Como gramáticas livres de contexto booleanas, gramáticas de análise sintática de expressão também adicionam os predicados sintáticos 'E'- e 'NÃO'-. Por eles poderem usar uma sub-expressão complexa arbitrariamente para "olhar a frente" na cadeia de entrada sem realmente consumi-la, eles fornecem um poderoso "olhar para frente"(em inglês, lookahead) sintático e instalação de não-ambiguidade, em particular quando a reordenação das alternativas não pode especificar a árvore de análise sintática exata desejada.

Interpretação operacional de expressões de análise sintática Cada não-terminal em uma gramática de análise sintática de expressão representa, essencialmente, uma função de análise em um analisador recursivo de descida, e a expressão de análise sintática correspondente representa o "código" que compreende a função. Cada função de análise sintática conceitualmente toma uma cadeia de entrada como seu argumento, e produz um dos seguintes resultados:

sucesso, em que a função pode opcionalmente avançar ou consumir um ou mais caracteres da cadeia de entrada fornecida a ele, ou falha, no caso em que nenhuma entrada é consumida.

Uma expressão de análise sintática atômica consistindo de um único terminal (ou seja literal) será bem-sucedida se o primeiro caractere da cadeia de entrada corresponde ao terminal, e nesse caso consome o caractere de entrada; caso contrário, a expressão produz um resultado de falha. Uma expressão de análise atômica que consiste na seqüência vazia sempre trivialmente é bem-sucedida sem consumir qualquer entrada.

Uma expressão de análise sintática atômica consistindo de um não-terminal A representa uma chamada recursiva para a função-não-terminal A. A não-terminal pode ter sucesso sem realmente consumir qualquer entrada, e isso é considerado um resultado distinto do fracasso.

O operador sequência e1e2 primeiro invoca e1, e se e1 for bem-sucedido, posteriormente invoca e2 no restante da cadeia de entrada restante consumida por e1, e retorna o resultado. Se qualquer e1 ou e2 falhar, então a sequência de expressão e1e2 falhar.

O operador escolha e1 / e2 invoca primeiro e1, e se e1 for bem-sucedido, retorna seu resultado imediatamente. Caso contrário, se e1 falhar, então o operador escolha recua para a posição de entrada original em que foi invocado e1, mas, em seguida, chama e2 em vez de e1, retornando o resultado de e2.

Os operadores de zero-ou-mais, de um-ou-mais, e opcional consumem zero ou mais, uma ou mais, ou zero ou uma repetições consecutivas de sua sub-expressão e,respectivamente. Ao contrário de gramáticas livres de contexto e expressões regulares, no entanto, esses operadores sempre se comportam com avidez, consumindo o máximo de informação possível e nunca recuando. (Verificadores de igualdade de expressão regular podem começar combinando com avidez, mas, em seguida, voltam atrás e tentam caminhos mais curtos, se eles não conseguem corresponder.) Por exemplo, a expressão a* sempre consume tantos a's quanto forem consecutivamente disponíveis na seqüência de entrada, e a expressão (a* a) sempre falhará porque a primeira parte (a*) nunca vai deixar qualquer 'a' para a segunda parte para corresponder.

A expressão predicado E- &e invoca a sub-expressão e, em seguida, se e for bem-sucedido, é bem-sucedido e falha se e falhar, mas em qualquer caso nunca consome qualquer entrada.

A expressão predicado NÃO- !e é bem-sucedido se e falha e falha se e for bem-sucedido, mais uma vez consumindo sem entrada em ambos os casos.

Exemplos Esta é uma GASE que reconhece fórmulas matemáticas que aplicam as quatro operações básicas a inteiros não negativos. Expr ← Sum Sum ← Product (('+' / '-') Product)* Product ← Value (('*' / '/') Value)* Value ← [0-9]+ / '(' Expr ')' No exemplo acima, os símbolos terminais são caracteres de texto, representados por caracteres entre aspas simples, como '(' e ')'. O intervalo [0-9] é também um atalho para dez caracteres, indicando qualquer um dos dígitos de 0 a 9 (Esta sintaxe de alcance é a mesma que a sintaxe utilizada por expressões regulares.) Os símbolos não-terminais são os que se expandem para outras regras: Value, Product, Sum, and Expr.

A expressão de análise sintática ('a'/'b')* corresponde e consume uma sequência de tamanho arbitrário de a's e b's. A regra de produção descreve a "linguagem de correspondência" livre de contexto simples . A seguinte expressão de gramática de análise sintática descreve a linguagem não-livre de contexto clássica : S ← &(A 'c') 'a'+ B !('a'/'b'/'c') A ← 'a' A? 'b' B ← 'b' B? 'c' A regra recursiva a seguir corresponde o estilo C padrão declarações if/then/else de tal forma que a cláusula opcional "else" sempre se liga ao "if" mais interno, por causa da priorização implícita do operador '/'. (Em uma gramática livre de contexto, essa construção produz a clássica ambiguidade pendente.) S ← 'if' C 'then' S 'else' S / 'if' C 'then' S A expressão de análise sintática foo &(bar) corresponde e consome o texto "foo", mas apenas se for seguido pelo texto "bar". A expressão de análise sintática foo !(bar)) coincide com o texto "foo", mas somente se ele não é seguido pelo texto "bar". A expressão !(a+ b) a, corresponde a um único "a", mas apenas se não é parte de uma sequência arbitrariamente longa de a's seguida por um b.

A regra recursiva a seguir corresponde a comentário aninhado da sintaxe do estilo Pascal, (* que pode (* ser aninhado *) como este *). Os símbolos de comentário aparecem entre aspas simples para distingui-las das operadoras de GASE. Begin ← '(*' End ← '*)' C ← Begin N* End N ← C / (!Begin !End Z) Z ← any single character

Implementando analisadores de gramáticas de análise sintática de expressão Qualquer gramática de análise sintática de expressão pode ser convertida diretamente em um analisador sintático recursivo de descida. Devido à capacidade de "olhar para frente" (em inglês, lookahead) ilimitado que o formalismo gramatical prevê, no entanto, o analisador resultante pode apresentar um desempenho de tempo exponencial no pior caso.

É possível obter melhor desempenho para qualquer gramática de análise sintática de expressão através da conversão de seu analisador sintático recursivo de descida em um analisador sintático packrat, que sempre é executado em tempo linear, ao custo de requisitos substancialmente maiores de espaço de armazenamento. Um analisador sintático packrat é uma forma de analisador sintático semelhante a um analisador sintático recursivo de descida na construção, exceto que durante o processo de análise ele memoiza (em inglês, memoizes) os resultados intermediários de todas as invocações das funções de análise mutuamente recursivas, garantindo que cada função de análise sintática só é invocada no máximo uma vez em uma determinada posição da entrada. Devido a essa memoização, um analisador sintático packrat tem a capacidade de analisar muitas gramáticas livres de contexto e de qualquer gramática de análise sintática de expressão (incluindo algumas que não representam linguagens livres de contexto) em tempo linear. Exemplos de analisadores sintáticos recursivos de descida memoizados são conhecidos a partir de, pelo menos, tão cedo quanto 1993. Note que esta análise do desempenho de um analisador packrat assume que há memória suficiente para armazenar todos os resultados memoizados; na prática, se não houvesse memória suficiente, algumas funções de análise podem ter que ser chamadas mais de uma vez na mesma posição de entrada e, conseqüentemente, o analisador pode demorar mais do que o tempo linear.

Também é possível construir analisadores LL e analisadores LR de gramáticas de análise sintática de expressão, com melhor desempenho de pior caso de um analisador recursivo de descida, mas a capacidade de lookahead ilimitada do formalismo da gramática é então perdida. Portanto, nem todas as linguagens que podem ser expressas utilizando gramáticas de análise sintática de expressão podem ser analisadas por analisadores LL ou LR.

Vantagens Comparado com expressões regulares puras (ou seja, sem referências anteriores), GASEs são estritamente mais poderosas, mas requerem muito mais memória. Por exemplo, uma expressão regular inerentemente não consegue encontrar um número arbitrário de pares de parênteses, porque não é recursiva, mas uma GASE pode. No entanto, uma GASE necessitará de uma quantidade de memória proporcional ao comprimento da entrada, enquanto uma gramática de expressões regulares irá exigir apenas uma quantidade constante de memória.

Qualquer GASE pode ser analisada em tempo linear, utilizando um analisador packrat, como descrito acima.