Construção de compiladores/Análise sintática

Exemplo da análise sintática de uma expressão matemática. O resultado é uma árvore da expressão

Análise sintática (também conhecido pelo termo em inglês parsing) é o processo de analisar uma sequência de entrada (lida de um arquivo de computador ou do teclado, por exemplo) para determinar sua estrutura gramatical segundo uma determinada gramática formal. Essa análise faz parte de um compilador, junto com a análise léxica e análise semântica. A análise sintática, ou análise gramatical é o processo de se determinar se uma cadeia de símbolos léxicos pode ser gerada por uma gramática.

A análise sintática transforma um texto na entrada em uma estrutura de dados, em geral uma árvore, o que é conveniente para processamento posterior e captura a hierarquia implícita desta entrada. Através da análise léxica é obtido um grupo de tokens, para que o analisador sintático use um conjunto de regras para construir uma árvore sintática da estrutura.

Em termos práticos, pode também ser usada para decompor um texto em unidades estruturais para serem organizadas dentro de um bloco, por exemplo.

A vasta maioria dos analisadores sintáticos implementados em compiladores aceitam alguma linguagem livres de contexto para fazer a análise. Estes analisadores podem ser de vários tipos, como o LL, LR e SLR.

Tipos de analisadores sintáticos

A tarefa do analisador sintático (um algoritmo, programa de computador ou componente de software que se preze a realizar uma análise sintática) é essencialmente a de determinar se uma entrada de dados pode ser derivada de um símbolo inicial com as regras de uma gramática formal. Isso pode ser feito de duas maneiras:

• Descendente (top-down) - um analisador pode iniciar com o símbolo inicial e tentar transformá-lo na entrada de dados. Intuitivamente, o analisador inicia dos maiores elementos e os quebra em elementos menores. Exemplo: analisador sintático LL.
• Ascendente (bottom-up) - um analisador pode iniciar com um entrada de dados e tentar reescrevê-la até o símbolo inicial. Intuitivamente, o analisador tentar localizar os elementos mais básicos, e então elementos maiores que contêm os elementos mais básicos, e assim por diante. Exemplo: analisador sintático LR.

Determinismo

Analisadores sintáticos são determinísticos se sempre souberem que ação tomar independentemente da entrada de texto. Este comportamento é desejado e esperado na compilação de uma linguagem de programação. No campo de processamento de linguagem natural, pensava-se que essa a análise sintática determinística era impossível devido à ambiguidade inerente das linguagens naturais, em que diversas sentenças possuem mais de uma possível interpretação. Entretanto, Mitch Marcus propôs em 1978 o analisador sintático Parsifal, que consegue lidar com ambiguidades ainda que mantendo o comportamento determinístico.

Funcionamento

Um analisador sintático para uma gramática G é um programa que aceita como entrada uma sentença (uma lista de símbolos S) e constrói para a sentença sua árvore gramatical (ou equivalentemente uma seqüência de derivação) ou, caso a sentença não pertença à linguagem descrita por G, uma indicação de erro.

Duas técnicas básicas para a construção de analisadores sintáticos são a construção ascendente ou a construção descendente. Na construção ascendente (bottom-up), o analisador sintático varre a sentença buscando aplicar produções que permitam substituir seqüências de símbolos da sentença pelo lado esquerdo das produções, até alcançar como único símbolo restante o símbolo inicial da gramática.

O Algoritmo a seguir ilustra a estratégia de reconhecimento de sentença baseado em construção ascendente da árvore sintática. Esse algoritmo recebe como entrada uma representação da gramática G e a lista S de símbolos terminais que compõem a sentença. A saída é uma indicação se a sentença S pertence (true) ou não (false) à gramática G. Para a descrição desse algoritmo, as seguintes funções são definidas:

$\Sigma$ que recebe uma gramática G como argumento e retorna o seu símbolo sentencial; e

MATCH(G,$\alpha$) retorna uma nova lista de símbolos gerada a partir da aplicação de alguma regra de G à sentença S. Para tanto, esse procedimento analisa se para a sentença S, composta pela seqüência de símbolos $\beta$x1x2...xn$\upsilon$(onde eventualmente $\beta$ e $\upsilon$ podem ser a cadeia vazia), há na gramática alguma produção aplicável $x$ $\rightarrow$ x1x2...xn. Se houver, o valor de retorno do procedimento é a lista $\beta$ $x$$\upsilon$; caso contrário, o procedimento retorna uma lista vazia.

Na construção descendente (top-down), o objetivo é iniciar a análise com uma lista que contém inicialmente apenas o símbolo sentencial; a partir da análise dos símbolos presentes na sentença, busca-se aplicar regras que permitam expandir os símbolos na lista até alcançar a sentença desejada.

Na construção descendente, o objetivo é obter uma derivação mais à esquerda para uma sentença. Em termos de árvores gramaticais, a construção descendente busca a construção de uma árvore a partir da raiz usando pré-ordem para definir o próximo símbolo não-terminal que deve ser considerado para análise e expansão.

Pela forma como a técnica de construção descendente opera, ela não pode ser aplicada a gramáticas com produções recursivas à esquerda, ou seja, que contenham regras da forma:

A $\rightarrow$ A$\beta$

A limitação é que a análise descendente de tal tipo de produção poderia levar a uma recursão infinita na análise pela tentativa de expandir sempre a mesma regra sem consumir símbolo algum da entrada.

É possível transformar uma produção recursiva à esquerda em uma recursiva à direita que descreve as mesmas sentenças através da seguinte técnica. Sejam $\beta$ e $\delta$ duas seqüências de símbolos que não sejam iniciadas pelo símbolo não-terminal A e sejam as produções para A:

A $\rightarrow$ A$\beta$ A $\rightarrow$$\delta$

Através da introdução de um novo símbolo não-terminal A’, as mesmas sentenças descritas pelas produções acima podem ser descritas pelas produções recursivas à direita:

A $\rightarrow$$\delta$A’

A’ $\rightarrow$$\beta$ A’

A’ $\rightarrow$$\varepsilon$

Nos dois casos, as sentenças são formadas por uma ocorrência de $\delta$ no início seguida por zero ou mais ocorrências de $\beta$.

Os primeiros compiladores usavam essencialmente dois tipos de analisadores sintáticos. Analisadores baseados em precedência de operadores utilizam a técnica de construção ascendente combinada com informação sobre a precedência e associatividade de operadores da linguagem para guiar suas ações, sendo adequados à análise de expressões aritméticas. Analisadores do tipo descendentes recursivos implementam a técnica de construção descendente através de um conjunto de rotinas mutuamente recursivas para realizar a análise, sendo normalmente utilizados para outros comandos que não expressões aritméticas.

Analisador sintático preditivo

Esta seção descreve a construção de um analisador sintático baseado na técnica de construção descendente. Este programa, que realiza a análise sintática preditiva não recursiva, recebe como argumentos uma descrição da gramática G e a sentença S, expressa na forma de uma lista de símbolos terminada com um símbolo delimitador $, não-pertencente aos símbolos da gramática.

O ponto crítico nesse procedimento é saber escolher, dado um símbolo não-terminal que pode ser expandido e os próximos símbolos da sentença, qual deve ser a produção da gramática que deve ser aplicada na expansão. A tabela sintática para a gramática, cuja construção é descrita na seqüência, contém essa informação essencial à execução do algoritmo.

Construção da tabela sintática

A tabela sintática é a estrutura de apoio ao reconhecimento de sentenças pela técnica de construção descendente que tem como chave um par de símbolos. O primeiro componente da chave é um símbolo não-terminal, que corresponde ao símbolo que estará sendo analisado pelo algoritmo de reconhecimento da sentença. O segundo componente da chave é um símbolo da sentença, ou seja, um símbolo terminal ou o delimitador de fim de seqüência $. O valor associado a esse par de símbolos é a produção da gramática a ser aplicada para prosseguir com o reconhecimento da sentença.

Para construir a tabela sintática para uma gramática qualquer G, deve-se analisar cada uma das produções A $\rightarrow$ $\alpha$ de G. Inicialmente, deve-se obter o conjunto de símbolos terminais que podem iniciar uma cadeia a partir de S. Se S for um símbolo terminal, então esse conjunto é composto apenas por esse próprio símbolo. Caso contrário, as possíveis expansões de S devem ser analisadas até que os símbolos terminais ou a string vazia sejam alcançados.

Caso símbolos terminais sejam alcançados, a tabela sintática recebe a entrada com o valor A $\rightarrow$ $\alpha$ para cada chave A,t onde t é cada um dos símbolos terminais que podem ser alcançados desde S. Caso a string vazia seja um dos resultados possíveis para a expansão de S, é preciso analisar também as possíveis expansões dos símbolos à direita do símbolo corrente na produção.

O cômputo de STF pode também ser aplicado a uma cadeia de símbolos, sendo que neste caso o valor resultante é o primeiro cômputo de STF aplicado a cada símbolo da seqüência tal que o resultado não tenha sido $\varepsilon$. Caso o cômputo de STF para todos os símbolos da cadeia resulte em $\varepsilon$, este também será o resultado final.

O outro procedimento auxiliar deve computar, para cada símbolo não-terminal da gramática G, o conjunto de símbolos terminais que podem estar imediatamente à direita do símbolo especificado em alguma forma sentencial. Essa informação é mantida em uma lista seguinte($\alpha$), onde S é o símbolo de interesse. Para construir essas listas, as seguintes regras devem ser aplicadas até que se esgotem as possibilidades de acrescentar algo às listas:

Regra 1: O símbolo sentencial da gramática pode ter como próximo símbolo o delimitador de fim de sentença; insira o símbolo $ na lista seguinte($\sigma$(G)).

Regra 2: Se existir uma produção em G da forma A $\rightarrow \alpha$B$\beta$, então todos os símbolos terminais que podem iniciar a expansão de $\beta$ podem aparecer após B; insira em seguinte(B) o conteúdo de STF($\beta$) sem incluir $\varepsilon$, se estiver presente.

Regra 3: Se existir uma produção em G da forma A $\rightarrow$ $\alpha$B, então B termina a expansão de A. O mesmo pode ocorrer para uma produção da forma A $\rightarrow$ $\alpha$B$\beta$ onde a expansão de $\beta$ pode levar à string vazia $\varepsilon$. Em qualquer um desses casos, tudo que está em seguinte(A) deve ser incluído em seguinte(B).

Com esses procedimentos, a construção da tabela sintática para uma gramática G procede como se segue. Para cada produção A $\rightarrow$ $x$ em G:

1. Compute STF(G,$x$). Para cada símbolo x dessa lista, acrescente a produção A $x$ $x$ como o valor da tabela para o par de chaves [A,x].

2. Caso STF(G,$x$) contenha $\varepsilon$, acrescente a produção A $\rightarrow x$ à tabela para o par de chaves [A,y] para cada y em seguinte(A).

Como exemplo, considere a construção do analisador sintático preditivo para a gramática vista anteriormente. Como essa gramática é recursiva à esquerda, o primeiro passo nessa construção é construir a gramática equivalente sem esse tipo de recursão. O resultado da aplicação da técnica para eliminar a recursão à esquerda resulta na seguinte gramática:

E $\rightarrow$ TE'

E' $\rightarrow$ +TE'

E' $\rightarrow$ $\varepsilon$

T $\rightarrow$ FT'

T' $\rightarrow$ xFT'

T' $\rightarrow$ $\varepsilon$

F $\rightarrow$ (E)

F $\rightarrow$ id

Para esta gramática, o cômputo de STF() para cada um dos símbolos não-terminais resulta em:

STF(E) = STF (T) = STF (F) = (,ID

STF (E') = +,$\varepsilon$

STF (T') = $,$\varepsilon$

Como STF() para um símbolo terminal é o próprio símbolo, esses valores não são aqui apresentados.

A aplicação das regras para a construção das listas seguinte() resulta, para cada símbolo não-terminal:

seguinte(E) = seguinte(E') =$,)

seguinte(T) = seguinte(T') = +,$,)

seguinte(F) = x,+,$,)

A construção da tabela sintática para essa gramática analisa cada uma das suas produções:

P1. E $\rightarrow$ TE'

Para essa produção, STF(TE')= STF(T), que resulta na lista com os símbolos ( e id. Portanto, na tabela sintática as entradas [E,(] e [E,id] farão referência à produção P1.

P2. E' $\rightarrow$ +TE'

O cômputo de STF(+TE') resulta em +, ou seja, haverá uma referência para P2 na entrada [E',+] da tabela sintática.

P3. E' $\rightarrow$ $\varepsilon$

STF($\varepsilon$)= $\varepsilon$; portanto, a segunda regra para a construção da tabela deve ser aplicada. Como seguinte(E')=$,), as entradas correspondentes à [E',$] e [E',)] farão referência à produção P3.

P4. T $\rightarrow$ FT'

Como STF(FT')= STF(F)=(,id, as entradas para [T,(] e [T,id] farão referência à P4.

P5. T' $\rightarrow$ xFT'

Neste caso, STF(xFT')=x. Portanto, a entrada [T',x] terá a referência para P5.

P6. T' $\rightarrow$ $\varepsilon$

Novamente a segunda regra deve ser aplicada. Como seguinte(T')=+,$,), as entradas com referência à P6 na tabela serão [T',+], [T',$] e [T',)].

P7. F $\rightarrow$ (E)

Apenas a entrada [F,(] fará referência a esta produção, pois STF((E))= (.

P8. F $\rightarrow$ id

Apenas a entrada [F,id] fará referência a esta produção, pois STF(id)= id.

Para algumas gramáticas, pode ser que a tabela sintática apresente mais que uma produção por chave, o que reduz a aplicabilidade desse tipo de analisador –– seria necessário manter um registro do estado do analisador em pontos de múltipla escolha para eventualmente retornar a esse estado e tentar a outra alternativa, em caso de insucesso na escolha anterior. Gramáticas ambíguas e gramáticas recursivas à esquerda são exemplos de gramáticas que produziriam tabelas sintáticas com múltiplas produções para uma chave de par de símbolos.

Gramáticas com tabelas sintáticas sem múltiplas definições são denominadas gramáticas LL(1), indicando que a varredura da sentença ocorre da esquerda para a direita (Left-to-right) e que é utilizada a derivação canônica mais à esquerda (Leftmost derivation). O número entre parênteses indica quantos símbolos da sentença precisam ser analisados (lookahead) para a tomada de decisão no processo de reconhecimento.

Uma gramática com duas produções A $\rightarrow$$\alpha$ e A $\rightarrow$ $\beta$ é LL(1) se apresentar as seguintes propriedades:

1. S e $\beta$ não podem derivar ao mesmo tempo seqüências que tenham início pelo mesmo símbolo terminal; 2. Apenas um dos dois, S ou $\beta$, podem derivar $\varepsilon$; e 3. Se uma das produções deriva $\varepsilon$, a outra não pode derivar qualquer seqüência de símbolos que tenha início com um símbolo presente em seguinte(A).

Geradores de analisadores sintáticos

Como ocorre na construção de analisadores léxicos, a construção de programas analisadores sintáticos é usualmente suportada por ferramentas para a geração automática de programas a partir de uma especificação.

Uma tradicional ferramenta de criação de analisadores sintáticos é o yacc (Yet Another Compiler-Compiler), oriunda do ambiente de desenvolvimento de software do sistema operacional Unix. Assim como a ferramenta lex, yacc recebe como entrada um arquivo de especificação de uma gramática e gera como saída um módulo com código-fonte em C contendo uma rotina que realiza o reconhecimento de sentenças segundo essa gramática.

Especificação da gramática

O arquivo de entrada para o yacc, que por convenção recebe a extensão .y, é estruturado em três seções. Como na definição de arquivos lex, essas três seções –– definições, regras da gramática e código do usuário –– são separadas pelos símbolos %%.

A especificação das regras da gramática utiliza uma notação próxima de BNF. A notação BNF (Backus-Naur Form) introduz uma forma de representação textual para descrever gramáticas livres de contexto. BNF foi inicialmente desenvolvida para especificar a linguagem Algol 60.

O principal operador dessa linguagem é o operador binário ::=, que permite descrever as produções da gramática. O operando do lado esquerdo do operador é o símbolo não-terminal; do lado direito, a sua expansão, que pode conter símbolos terminais e não-terminais.

Na notação BNF, os símbolos não-terminais são delimitados por colchetes angulares, < e >. Por exemplo, a regra

<expr> ::= (<expr>)

define que uma expressão entre parênteses (o lado direito do operador) pode ser reduzido simplesmente a uma expressão (o símbolo não-terminal do lado esquerdo).

A notação BNF também introduz um conjunto de operadores destinados a simplificar a representação das regras da gramática, assim como lex introduz operadores para facilitar a especificação de expressões regulares.

O operador | (ou) permite expressar em uma mesma regra produções alternativas. Por exemplo, a regra

(S) ::= A|B

equivale às duas regras

(S) ::= A (S) ::= B

O operador [ ] (opcional) permite expressar zero ou uma ocorrência do símbolo especificado. Por exemplo, a regra

(S) ::= [a]

equivale a

(S) ::= $\varepsilon$ (S) ::= a

O operador ( | ) (fatoração) permite expressar a combinação de símbolos alternativos, como em

(S) ::= a(b|c)d

que equivale a

(S) ::= abd (S) ::= acd

O operador * (repetição), assim como para expressões regulares, expressa 0 ou mais ocorrências do símbolo. Por exemplo, a regra

(S) ::= a*

equivale a

(S) ::= $\varepsilon$ (S) ::= a(S)

Assim, a ocorrência do padrão no lado direito de uma produção equivale a

$\varepsilon$|a|aa|aaa|aaaa|..... O operador {||}* (concatenação) permite expressar a repetição múltipla de símbolos concatenados. Por exemplo, a regra

(S) ::= {A||B}*

equivale a

(S) ::= A(t) (t) ::= $\varepsilon$ (t) ::= BA(t)

Cada produção no yacc é expressa na forma:

simb  : exp  ;

onde simb é um símbolo não terminal e exp é a sua expansão em termos de outros símbolos da gramática. A expansão pode conter símbolos terminais e não-terminais, que por convenção são representados usando letras maiúsculas e minúsculas, respectivamente.

Pelas características de gramáticas livres de contexto, a expansão pode ser recursiva, isto é, conter o próprio símbolo que está sendo definido, como em

expr : expr '+' expr ;

Porém, pelo menos uma expansão para esse símbolo deve ser não-recursiva:

expr : IDENT ;

Em caso de definição recursiva, pelas características do analisador gerado (LR(1)) recomenda-se optar quando possível pela recursão à esquerda.

Produções para um mesmo símbolo podem ser agrupadas usando o símbolo '|',

 expr  :  expr + expr
       |  IDENT
       ;

Expansões para a cadeia vazia podem ser definidas; por convenção e para tornar mais clara a definição, essa expansão é destacada na forma de um comentário C:

 retv  :  /* empty */
       |  expr
       ;

O símbolo sentencial da gramática pode ser estabelecido na seção de definições através da declaração start, como em

 %start  expr

Na ausência dessa declaração, o símbolo não-terminal cuja expansão é definida na primeira produção da seção de regras da gramática é assumido ser o símbolo sentencial.

Outros tipos de declaração que podem estar presentes na primeira seção são declarações em C, colocadas entre os símbolos %{ e %}, e a definição dos nomes de tipos de tokens, os quais serão usados posteriormente nas expansões das produções.

Tokens que são representados por um único caractere, como '+' ou ';', não precisam ser declarados e podem ser usados dessa forma (como constantes do tipo caractere em C) nas expansões; os demais tokens precisam ser explicitamente declarados. Para tanto, a declaração token pode ser utilizada, como em

 %token IDENT

Alternativamente, tokens para operadores podem ser definidos com uma especificação de associatividade usando, ao invés de token, as declarações left, right ou nonassoc. Uma declaração

 %left OP

determina que uma expressão A OP B OP C será interpretada como (A OP B) OP C, enquanto que se a declaração tivesse sido

 %right OP

a interpretação seria A OP (B OP C). A declaração

 %nonassoc OP

determinaria que a expressão A OP B OP C estaria incorreta, pois o operador não é associativo.

A precedência dos operadores também é definida através dessas declarações. Operadores definidos através da mesma linha de declaração, como

 %left OP1 OP2	

têm a mesma precedência. Para aqueles definidos em linhas distintas, as últimas declarações têm maior precedência.

O símbolo terminal error é pré-definido, podendo ser utilizado como a última expansão de um símbolo caso a aplicação deseje determinar um curso de ação específico em uma situação de não-reconhecimento de uma sentença a partir das expansõbix previamente definidas para o símbolo.

Manipulação das sentenças reconhecidas

Reconhecer que uma seqüência de símbolos é uma sentença válida em uma gramática, é parte essencial do processo de compilação, porém pouco uso seria se simplesmente uma indicação de validade fosse retornada sem nenhuma possibilidade de manipulação adicional das expressões. No caso do yacc, essa possibilidade está associada à definição de ações semânticas.

Uma ação semântica em yacc é definida através de um bloco de expressões em C associado à definição de produções para um símbolo não-terminal:

 symb  :  expansão    { ação }  ;

A definição do corpo da ação pode conter referências aos valores semânticos de cada um dos símbolos da produção. O valor semântico de um token está associado a um valor associado ao símbolo, que pode ser por exemplo um valor numérico de uma constante ou a string associada a um identificador.

O valor semântico do token pode ser referenciado na expressão C através de pseudo-variáveis com nome $i, onde i determina a posição do token na expansão. A variável $$ referencia o valor semântico resultante para o símbolo sendo definido. Por exemplo:

 expr  :  expr '+' expr
          { $$ = $1 + $3 }
       ;

atribui à expressão reduzida o valor semântico que é a soma dos valores semânticos do primeiro e do terceiro componente da expansão, que estão separados pelo segundo componente, '+'.

Se nenhuma ação for definida para uma produção, a ação semântica padrão -- { $$ = $1; } é assumida.

O tipo associado a valores semânticos é definido pela macro YYSTYPE, que é inicialmente definida como int. Para modificar esse padrão, pode-se modificar essa definição através de uma declaração C na primeira seção do arquivo que define a gramática. Por exemplo:

 %{
  #define  YYSTYPE  double
 %}

Em aplicações que necessitem manipular tokens com diferentes tipos de valores semânticos, a declaração union deve ser utilizada para definir quais são os tipos de valores possíveis. Por exemplo, em uma aplicação que manipula valores inteiros e reais a seguinte declaração estaria presente:

 %union {
    int    ival;
    double fval;
 }

Essa declaração determina que a coleção de tipos de valores permitidos é composta por valores com nome ival ou fval, respectivamente para valores inteiros e reais –– no código C, uma união será criada. Esses mesmos nomes são utilizados para qualificar a definição de tokens da gramática, como em

 %token <ival>  INTEGER
 %token <fval>  REAL

Quando uma coleção de tipos de valores é utilizada, é preciso determinar também qual o tipo para o símbolo não-terminal para o qual a expressão está sendo reduzida. Para esse fim, yacc define a declaração type:

 %type <fval> expr