Gramática de análise sintática de expressão

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 e_S 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:

1. 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 ε.
2. Dadas quaisquer expressões de análise sintática e, e₁, e e₂ existentes, uma nova expressão de análise sintática pode ser construída usando os seguintes operadores:
   • Sequencia: e₁ e₂
   • Escolha ordenada: e₁ / e₂
   • 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 e₁e₂ primeiro invoca e₁, e se e₁ for bem-sucedido, posteriormente invoca e₂ no restante da cadeia de entrada restante consumida por e₁, e retorna o resultado. Se qualquer e₁ ou e₂ falhar, então a sequência de expressão e₁e₂ falhar.

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

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 S ← 'a' S? 'b' descreve a "linguagem de correspondência" livre de contexto simples $\{a^{n}b^{n}:n\geq 1\}$. A seguinte expressão de gramática de análise sintática descreve a linguagem não-livre de contexto clássica $\{a^{n}b^{n}c^{n}:n\geq 1\}$:

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.

Analisadores para linguagens expressas como uma GLC, tais como analisadores LR, exigem um passo tokenization separado para ser feito primeiro, o que quebra a entrada com base na localização de espaços, pontuação, etc O uso de token é necessário por causa da forma como estes analisadores usam lookahead para analisar GLCs que atendam a determinados requisitos em tempo linear. GASEs não requerem tokenization para ser uma etapa separada, e as regras de tokenization podem ser escritas da mesma forma como qualquer outra regra gramatical.

Muitas GLCs contem ambiguidades, mesmo quando elas estão destinadas a descrever linguagens inequívocas. O problema do "else pendente" em C, C ++, e Java é um exemplo. Estes problemas são frequentemente resolvidos através da aplicação de uma regra de fora da gramática. Em uma GASE, essas ambiguidades nunca surgem, por causa da priorização.

Desvantagens

Consumo de memória

A análise sintática de GASE é tipicamente realizada através de análise packrat, que utiliza memoization para eliminar passos de análise redundantes. Analisador packrat requer armazenamento proporcional ao tamanho total de entrada, em vez da profundidade da árvore de análise sintática como os analisadores com LR. Esta é uma diferença significativa em vários domínios: por exemplo, o código fonte escrito à mão tem uma efetiva profundidade de aninhamento de expressão constante independente da duração do programa—expressões aninhadas para além de uma certa profundidade tendem a ser reformuladas.

Para algumas gramáticas e algumas entradas, a profundidade da árvore de análise pode ser proporcional ao tamanho da entrada, assim tanto um analisador LR e um analisador packrat parecerão ter o mesmo desempenho de pior caso assintótico. Uma análise mais precisa levaria a profundidade da árvore de análise sintática em conta separadamente a partir do tamanho da entrada. Isto é semelhante a uma situação que surge em algoritmos de grafos: o algoritmo de Bellman-Ford e algoritmo de Floyd-Warshall parecem ter o mesmo tempo de execução ($O(|V|^{3})$) se e somente se o número de vértices é considerado. No entanto, uma análise mais precisa que representa o número de arestas como um parâmetro separado atribui o algoritmo de Bellman-Ford uma complexidade de tempo de $O(|V|*|E|)$, a qual só é quadrática no tamanho da entrada (em vez de cúbica).

Recursão indireta à esquerda

GASEs não podem expressar regras de esquerda-recursiva, quando uma regra refere-se a si mesma, sem avançar na seqüência. Por exemplo, na gramática aritmética acima, seria tentador mover algumas regras em torno de modo que a ordem de precedência dos produtos e somas pudesse ser expresso em uma linha:

Value   ← [0-9.]+ / '(' Expr ')'
Product ← Expr (('*' / '/') Expr)*
Sum     ← Expr (('+' / '-') Expr)*
Expr    ← Product / Sum / Value

Nesta nova gramática correspondendo um Expr requer testar se um Product corresponde enquanto corresponder um Product necessita testar se uma Expr corresponde. Esta definição circular não pode ser resolvida. Contudo, as regras da esquerda recursiva sempre podem ser reescritas para eliminar recursão à esquerda. Por exemplo, a regra GLC seguinte recursiva à esquerda:

string-of-a ← string-of-a 'a' | 'a'

pode ser reescrita em uma GASE usando um operador '+':

string-of-a ← 'a'+

O processo de reescrever as regras da esquerda indiretamente recursiva é complexa em alguns analisadores packrat, especialmente quando as ações semânticas estão envolvidas.

Com algumas modificações, análise sintática packrat tradicional pode suportar recursão esquerda direta, mas isso resulta em uma perda da propriedade da análise sintática em tempo linear que geralmente é a justificativa para o uso de GASEs e análise sintática packrat em primeiro lugar. Somente o algoritmo de análise Ometa suporta completamente recursão direta e indireta à esquerda sem complexidade de atendimento adicional (mas, novamente, com uma perda da complexidade de tempo linear), enquanto todos os analisadores GLR apoiarem recursão à esquerda.

Poder expressivo

Analisadores sintáticos packrat de GASE não podem reconhecer algumas regras GLC não determinísticas inequívocas, como a seguinte:

S ← 'x' S 'x' | 'x'

Nem algoritmos de análise LL (k) nem algoritmos de análise LR (k) são capazes de reconhecer este exemplo. No entanto, esta linguagem é analisável por um analisador sintático geral GLC como o algoritmo CYK.

Ver também

• Gramática Formal
• Expressão Regular
• Gramática Livre de Contexto

Referências

• Medeiros, Sérgio; Ierusalimschy, Roberto (2008). «A parsing machine for PEGs». Proc. of the 2008 symposium on Dynamic languages. ACM. pp. article #2. ISBN 978-1-60558-270-2. doi:10.1145/1408681.1408683 

Ligações externas

• Parsing Expression Grammars: A Recognition-Based Syntactic Foundation (PDF slides)
• Converting a string expression into a lambda expression using an expression parser
• The Packrat Parsing and Parsing Expression Grammars Page
• Packrat Parsing: a Practical Linear-Time Algorithm with Backtracking
• The constructed language Lojban has a fairly large PEG grammar allowing unambiguous parsing of Lojban text.