Mostrar código-fonte de Gramática de análise sintática de expressão

{{Wikificação|data=agosto de 2014}}
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<ref name="For04">{{citar conferência
| ref = "pegs"
|primeiro = Bryan p
|último = Ford
|título= Parsing Expression Grammars: A Recognition Based Syntactic Foundation
|títulolivro= Proceedings of the 31st ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages
|páginas=
|publicado= [[Association for Computing Machinery|ACM]]
|ano= 2004
| url = http://portal.acm.org/citation.cfm?id=964001.964011
| doi = 10.1145/964001.964011
| isbn = 1-58113-729-X
|acessodata= 2010-07-30
}}</ref> 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. <ref name="For04" /> 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.<ref name="pegs">
{{citar periódico
|autor = Bryan Ford
|título= Functional Pearl: Packrat Parsing: Simple, Powerful, Lazy, Linear Time
|ano= 2002
| url = http://pdos.csail.mit.edu/~baford/packrat/icfp02/packrat-icfp02.pdf
|formato= [[Portable Document Format|PDF]]}}
</ref>

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

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

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.
<pre>
Expr    &larr; Sum
Sum     &larr; Product (('+' / '-') Product)*
Product &larr; Value (('*' / '/') Value)*
Value   &larr; [0-9]+ / '(' Expr ')'
</pre>
No exemplo acima, os símbolos terminais são caracteres de texto, representados por caracteres entre aspas simples, como <code>'('</code> e <code>')'</code>. O intervalo '''<code>[0-9]</code>''' é 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 {{nowrap|'''''S'' ← 'a' ''S''? 'b''''}} descreve a "linguagem de correspondência" livre de contexto simples <math> \{ a^n b^n : n \ge 1 \} </math>.  A seguinte expressão de gramática de análise sintática descreve a linguagem não-livre de contexto clássica <math> \{ a^n b^n c^n : n \ge 1 \} </math>:
<pre>
S &larr; &(A 'c') 'a'+ B !('a'/'b'/'c')
A &larr; 'a' A? 'b'
B &larr; 'b' B? 'c'
</pre>
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.)
<pre>
S &larr; 'if' C 'then' S 'else' S / 'if' C 'then' S
</pre>
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.
<pre>
Begin &larr; '(*'
End   &larr; '*)'
C     &larr; Begin N* End
N     &larr; C / (!Begin !End Z)
Z     &larr; any single character
</pre>

== 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.<ref name="ford02">{{citar web
|url = http://pdos.csail.mit.edu/~baford/packrat/thesis|título= Packrat Parsing: a Practical Linear-Time Algorithm with Backtracking|acessodata= 2007-07-27|último = Ford|primeiro = Bryan|data=setembro de 2002|publicado= Massachusetts Institute of Technology}}
<!-- I'm not sure how to incorporate all the info from this old ref into the new one above.  If you can do so, or can verify that it has already been done, please delete this.  --~~~~

Ford, Bryan, ''Packrat Parsing: a Practical Linear-Time Algorithm with Backtracking'', Master’s thesis, Massachusetts Institute of Technology, September, 2002, http://pdos.csail.mit.edu/~baford/packrat/thesis/

-->
</ref>  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 <ref name="ford02" /> é 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.<ref name="merritt01">
{{citar web
|url=http://compilers.iecc.com/comparch/article/93-11-012
|título=Transparent Recursive Descent
|acessodata=2009-09-04
|último =Merritt
|primeiro =Doug
|data=novembro de 1993
|publicado=Usenet group comp.compilers
}}
</ref> 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<ref name=":0" /><ref name="warth08" /> 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,<ref name=":0">for example, the LISP expression (x (x (x (x ....))))</ref> 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 (<math>O(|V|^3)</math>) 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 <math>O(|V|*|E|)</math>, 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:

<pre>
Value   &larr; [0-9.]+ / '(' Expr ')'
Product &larr; Expr (('*' / '/') Expr)*
Sum     &larr; Expr (('+' / '-') Expr)*
Expr    &larr; Product / Sum / Value
</pre>

Nesta nova gramática correspondendo um <tt>Expr</tt> requer testar se um <tt>Product</tt> corresponde enquanto corresponder um <tt>Product</tt> necessita testar se uma <tt>Expr</tt> 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:

<pre>
string-of-a &larr; string-of-a 'a' | 'a'
</pre>

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

<pre>
string-of-a &larr; 'a'+
</pre>

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,<ref name="ford02"/><ref name="warth08">
{{citar periódico
|autor = Alessandro Warth, James R. Douglass, Todd Millstein
|título= Packrat Parsers Can Support Left Recursion
|data=janeiro de 2008
| url = http://www.vpri.org/pdf/tr2007002_packrat.pdf
|formato= [[Portable Document Format|PDF]]
|publicado= Viewpoints Research Institute
|acessodata= 2008-10-02 }}
</ref><ref name="ruediste09">
{{citar periódico
 |autor       = Ruedi Steinmann
 |título     = Handling Left Recursion in Packrat Parsers
 |data        = março de 2009
 |url         = http://n.ethz.ch/~ruediste/packrat.pdf
 |formato     = [[Portable Document Format|PDF]]
 |jornal      = 
 |acessodata  = 2014-08-09
 |arquivourl  = https://web.archive.org/web/20110706232049/http://n.ethz.ch/~ruediste/packrat.pdf
 |arquivodata = 2011-07-06
 |urlmorta    = yes
}}
</ref> mas isso resulta em uma perda da propriedade da análise sintática em tempo linear<ref name="warth08"/> 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<ref name="ometa08">
{{citar web
|url=http://www.vpri.org/pdf/tr2007002_packrat.pdf
|título=Packrat Parsers Can Support Left Recursion
|acessodata=2009-08-04
|data=janeiro de 2008
|publicado=PEPM '08
}}
</ref> 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:<ref name="pegs"/>

<pre>
S &larr; 'x' S 'x' | 'x'
</pre>
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|Gramática Formal]]
* [[Expressão regular|Expressão Regular]]
* [[Gramática Livre de Contexto]]

== Referências ==
<references />
* {{citar conferência
|primeiro = Sérgio
|último = Medeiros
|autorlink =
|autor2 =Ierusalimschy, Roberto |authorlink2=Roberto Ierusalimschy
|título= A parsing machine for PEGs
|títulolivro= Proc. of the 2008 symposium on Dynamic languages
|páginas= article #2
|publicado= [[Association for Computing Machinery|ACM]]
|ano= 2008
| url =
| doi = 10.1145/1408681.1408683
| isbn = 978-1-60558-270-2
|acessodata=
}}

== Ligações externas ==
{{external links|date=September 2011}}
* [http://www.brynosaurus.com/pub/lang/peg-slides.pdf Parsing Expression Grammars: A Recognition-Based Syntactic Foundation] (PDF slides)
* [http://mathosproject.com/updates/convert-a-string-expression-into-a-lambda-expression/ Converting a string expression into a lambda expression using an expression parser]
* [http://bford.info/packrat/ The Packrat Parsing and Parsing Expression Grammars Page]
* [http://pdos.csail.mit.edu/~baford/packrat/thesis/ Packrat Parsing: a Practical Linear-Time Algorithm with Backtracking]
* The [[constructed language]] [[Lojban]] has a [http://www.digitalkingdom.org/~rlpowell/hobbies/lojban/grammar/ fairly large PEG grammar] allowing unambiguous parsing of Lojban text.

{{DEFAULTSORT:Parsing Expression Grammar}}
[[Categoria:Análise sintática (computação)]]