Análise sintática sem varredura

Análise sintática sem varredura é uma técnica de análise sintática que não utiliza um componente de varredura (Scanner) para traduzir uma cadeia de caracteres em marcas. O termo análise sintática sem varredura foi inicialmente utilizado por Salomon^[1] e Cormack.^[2] Como conseqüência do uso desta técnica é que a linguagem definida será descrita por uma única gramática unificada(definida por exemplo através do formalismo Syntax Definition Formalism) ao invés de ser descrita por uma gramática livre de contexto e uma gramática regular.

Processo

O processo de análise sintática utilizando esta técnica pode ser dividido em duas partes.

Na primeira fase é feita a combinação da parte da gramática livre de contexto com a gramática regular que define as marcas da linguagem. Esta combinação é feita da seguinte forma:

Todas as marcas do lado esquerdo de cada regra de produção devem ser separados por marcas de formatação (Layout).
Todos os símbolos contidos na gramática devem ser renomeados da seguinte forma:
- Símbolos da sintaxe léxica devem ser renomeados para terminarem com -LEX (sigla para o inglês Lexical)
- Símbolos livres de contexto devem ser renomeados para terminarem com -CF (sigla para o inglês Context-Free)

Agora na segunda fase a gramática alterada é utilizada para o processo de análise sintática tradicional. Como resultado será gerada uma árvore sintática, onde esta terá as folhas como caracteres contidos na expressão avaliada e as marcas serão sub-árvores da mesma.

Vantagens

As principais vantagens levantadas por Visser^[3] são:

Ausência de um componente de varredura. Uma vantagem obvia desta técnica é não ter o esforço da implementação de um analisador léxico. Além disso, também são eliminadas as complicações inerentes ao processo de integração entre o analisador léxico e o analisador sintático.
Formalismo uniforme e integrado para definição de gramáticas. A linguagem é toda definida em função de uma única gramática expressa através de um único formalismo. Passando assim a não existir necessidade do uso de uma linguagens regulares para definição dos padrões léxicos da linguagem. Desta forma, simplificando o uso e a implementação do formalismo utilizado.
Desambiguação por contexto. Por conta da integração das duas gramáticas, o processo de análise léxica é guiado pela definição da parte da gramática livre de contexto. Desta forma, problemas clássicos que existiam no contexto do analisador léxico passam a não existir mais.
Conservação da estrutura léxica. Geralmente analisadores léxicos não mantém a estrutura das frases nas marcas que são gerados por eles.
Conservação da formatação. Os analisadores léxicos abrem mão das marcas de formatação encontradas nas frases analisadas. Porém em alguns casos o programa original ainda deve ser mantido no nível da análise sintática.
Sintaxe léxica expressável. Gramáticas livres de contexto fornecem um formalismo para definição da sintaxe léxica mais expressivo do que as linguagens regulares que são tradicionalmente utilizadas nos analisadores léxicos.

Desvantagens

Existem algumas desvantagens associadas ao o uso da técnica de análise sintática sem varredura.^[3] São elas:

Limitação das técnicas de análise sintática. Este é o principal problema com o analisador sintático sem varredura. Quando um componente de varredura é utilizado no processo de análise sintática este componente é utilizado para fazer leituras prévias de marcas. Porém, no caso de não existir um componente de varredura a leitura prévia será feita por caractere, o que não é suficiente para alguns tipos de gramáticas. Para resolver esse problema algumas implementações adotam um algoritmo de leitura prévia variável.
Tamanho da gramática. Como no processo existe apenas uma gramática para definir a linguagem esta gramática tende a ser maior que cada uma das gramáticas isoladas. Este problema pode ser tratado utilizando técnicas de normalização para gramáticas, assim reduzindo o tamanho destas.
Desambiguação léxica. Apesar de vários dos problemas de ambigüidade serem resolvidos pela unificação das gramáticas, ainda existem certos tipo de ambigüidades que devem ser tratadas. Duas construções de desambiguação são tratadas por Visser.^[3]
Interpretação das regras de desambiguação. Apesar de existirem regras para desambiguação estas ainda são passivas de interpretação de acordo com a implementação.
Eficiência. Como um componente de varredura é facilmente modelado através de um autômato finito os analisadores sintáticos sem varredura devem ser implementados por autômatos à pilha que em geral tem um custo maior de execução.

Implementações

«dparser». gera código ANSI C de um analisador sintático GLR sem varredura.
O componente denominado SGLR da ferramenta ASF+SDF gera e interpreta tabelas sintáticas para gramáticas sem varredura.
SGLR também é utilizado na ferramenta de transformação de sistemas Stratego/XT.
Spirit permite definir o processo de análise sintática com ou sem o uso de varredura.
SBP é um analisador sintático sem varredura para Gramáticas Booleanas. Este é escrito na linguagem Java.

Exemplo

O exemplo abaixo define uma linguagem simples para expressões da lógica proposicional utilizando Syntax Definition Formalism (SDF):

module basic/Booleans                                         %% Declaração do nome do módulo

exports
  sorts Boolean                                               %% Definindo o tipo Boolean
  context-free start-symbols Boolean                          %% Declarando símbolo inicial da gramática

context-free syntax
   "true"                     → Boolean                     %% Constante que representa o valor verdadeiro
   "false"                    → Boolean                     %% Constante que representa o valor falso
   lhs:Boolean "|" rhs:Boolean→ Boolean {left}              %% Definição do operador lógico "ou". Operador associativo à esquerda.

lhs:Boolean "&" rhs:Boolean→ Boolean {left} %% Definição do operador lógico "e". Operador associativo à esquerda.

   "not" "(" Boolean ")"      → Boolean                     %% Definição do operador lógico de negação de um sentença
   "(" Boolean ")"            → Boolean                     %% Definição de suporte a parênteses como expressões Boolean

 context-free priorities                                      %% Declaração de ordem de precedência entre operadores lógicos
   Boolean "&" Boolean→ Boolean >
   Boolean "|" Boolean→ Boolean

Referências

↑ Salomon, D. J. and Cormack, G. V. (1989). Scannerless NSLR(1) parsing of programming language. SIGPLAN Notices, 24(7), 170-178.
↑ Salomon, D. J. and Cormack, G. V. (1995). The disambiguation and scannerless parsing of complete character-level grammars for programming languages. Technical Report 95/06, Department of Computer Science, University of Mantioba, Winnipeg, Canada.
↑ ^a ^b ^c Visser, Eelco. (1997). Scannerless generalized-lr parsing. Technical Report P9707, University of Amsterdam, Amesterdam, Países Baixos.

Outras Referências

Lounden, Kenneth C (2004). Compiladores. princípios e práticas. São Paulo, Brasil: Pioneira Thomson Learning. ISBN 85-221-0422-0
«The Syntax Definition Formalism». Consultado em 15 de Outubro de 2008. Arquivado do original em 9 de outubro de 2008

[1] Salomon, D. J. and Cormack, G. V. (1989). Scannerless NSLR(1) parsing of programming language. SIGPLAN Notices, 24(7), 170-178.

[2] Salomon, D. J. and Cormack, G. V. (1995). The disambiguation and scannerless parsing of complete character-level grammars for programming languages. Technical Report 95/06, Department of Computer Science, University of Mantioba, Winnipeg, Canada.

[Visser1997-3] Visser, Eelco. (1997). Scannerless generalized-lr parsing. Technical Report P9707, University of Amsterdam, Amesterdam, Países Baixos.

[1]

[2]

[3]