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

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Wikitext.svg
Esta página ou seção precisa ser wikificada (desde agosto de 2014).
Por favor ajude a formatar esta página de acordo com as diretrizes estabelecidas.

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[1] 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. [1] 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.[2]

Definição[editar | editar código-fonte]

Sintaxe[editar | editar código-fonte]

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:

  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, 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[editar | editar código-fonte]

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[editar | editar código-fonte]

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[editar | editar código-fonte]

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 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[editar | editar código-fonte]

Qualquer gramática de análise sintática de expressão pode ser convertida diretamente em um analisador sintático recursivo de descida.[3] 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 [3] é 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.[4] 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[editar | editar código-fonte]

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[editar | editar código-fonte]

Consumo de memória[editar | editar código-fonte]

A análise sintática de GASE é tipicamente realizada através de análise packrat, que utiliza memoization[5][6] 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,[5] 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 () 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 , a qual só é quadrática no tamanho da entrada (em vez de cúbica).

Recursão indireta à esquerda[editar | editar código-fonte]

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,[3][6][7] mas isso resulta em uma perda da propriedade da análise sintática em tempo linear[6] 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[8] 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[editar | editar código-fonte]

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

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[editar | editar código-fonte]

Referências[editar | editar código-fonte]

  1. a b Ford, Bryan p (2004). «Parsing Expression Grammars: A Recognition Based Syntactic Foundation». Proceedings of the 31st ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. ACM. ISBN 1-58113-729-X. doi:10.1145/964001.964011. Consultado em 30 de julho de 2010 
  2. a b Bryan Ford (2002). «Functional Pearl: Packrat Parsing: Simple, Powerful, Lazy, Linear Time» (PDF) 
  3. a b c Ford, Bryan (setembro de 2002). «Packrat Parsing: a Practical Linear-Time Algorithm with Backtracking». Massachusetts Institute of Technology. Consultado em 27 de julho de 2007 
  4. Merritt, Doug (novembro de 1993). «Transparent Recursive Descent». Usenet group comp.compilers. Consultado em 4 de setembro de 2009 
  5. a b for example, the LISP expression (x (x (x (x ....))))
  6. a b c Alessandro Warth, James R. Douglass, Todd Millstein (janeiro de 2008). «Packrat Parsers Can Support Left Recursion» (PDF). Viewpoints Research Institute. Consultado em 2 de outubro de 2008 
  7. Ruedi Steinmann (março de 2009). «Handling Left Recursion in Packrat Parsers» (PDF) 
  8. «Packrat Parsers Can Support Left Recursion» (PDF). PEPM '08. Janeiro de 2008. Consultado em 4 de agosto de 2009 

Ligações externas[editar | editar código-fonte]

Predefinição:External links