Construção de compiladores
34 pág.

Construção de compiladores


DisciplinaConstrução de Compilares3 materiais14 seguidores
Pré-visualização10 páginas
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:
\u2022 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.
\u2022 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.
Análise sintática 11
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:
que recebe uma gramática G como argumento e retorna o seu símbolo sentencial; e
MATCH(G, ) 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 x1x2...xn 
(onde eventualmente e podem ser a cadeia vazia), há na gramática alguma produção aplicável 
x1x2...xn. Se houver, o valor de retorno do procedimento é a lista ; 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 A 
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 e 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 A A 
Através da introdução de um novo símbolo não-terminal A\u2019, as mesmas sentenças descritas pelas produções acima
podem ser descritas pelas produções recursivas à direita:
A A\u2019
A\u2019 A\u2019
A\u2019 
Nos dois casos, as sentenças são formadas por uma ocorrência de no início seguida por zero ou mais ocorrências
de .
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
Análise sintática 12
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 
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 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 . Caso o
cômputo de STF para todos os símbolos da cadeia resulte em , 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( ), onde S é o