Compiladores

Disponível somente no TrabalhosFeitos
  • Páginas : 17 (4177 palavras )
  • Download(s) : 0
  • Publicado : 6 de dezembro de 2012
Ler documento completo
Amostra do texto
COMPILADORES

3. ANÁLISE SINTÁTICA
INTRODUÇÃO Toda linguagem de programação tem regras que descrevem sua estrutura sintática (ou sintaxe). A sintaxe de uma LP pode ser descrita por uma gramática livre de contexto1 ou pela notação BNF. O uso de gramáticas traz vantagens para projetistas de linguagens e escritores de compiladores pelas seguintes razões:








uma gramática dá umaespecificação sintática precisa de uma LP (embora talvez menos clara que a notação BNF); para certas classes de gramáticas, pode-se automatizar o processo de construção do analisador sintático e o gerador automático pode revelar certas ambigüidades sintáticas da LP difíceis de serem detectadas pelo escritor do compilador; uma gramática bem projetada dá estrutura à uma LP, o que facilita acompilação e a detecção de erros de programas fonte; e novas construções sintáticas que surgem com a evolução de uma LP podem ser incorporadas mais facilmente à linguagem se seu compilador tem uma implementação baseada em uma descrição gramatical.

1Gramática

livre de contexto é aquela que tem regras do tipo A ::= α, com A ∈ VN e α ∈ V

*

© UFCG / DSC / PSN, 2005 – Parte 3: Análise Sintática –Pág. 1

COMPILADORES Dada uma gramática G(S), verificar se uma dada sentença w pertence ou não à L(G) é verificar se S =>+ w para alguma seqüência de derivação S => w1 => w2 => ... => wn => w (em outra palavras, é obter uma árvore de derivação sintática (ADS) para w). Nesse sentido, o analisador sintático de um compilador nada mais é do que um construtor de ADS. Quando ele consegue construir uma ADSpara uma sentença w (um programa), dizemos que w está sintaticamente correta. Em caso contrário, dizemos que w está sintaticamente incorreta. Os analisadores sintáticos podem ser classificados basicamente em dois grupos: descendentes e ascendentes.

© UFCG / DSC / PSN, 2005 – Parte 3: Análise Sintática – Pág. 2

COMPILADORES Um analisador sintático descendente tenta construir a ADS para umasentença w a partir do símbolo inicial S (raiz), aplicando regras de produção até produzir todos os símbolos (folhas) de w.

© UFCG / DSC / PSN, 2005 – Parte 3: Análise Sintática – Pág. 3

COMPILADORES Um analisador sintático ascendente tenta construir a ADS para uma sentença w a partir dos símbolos de w (folhas), fazendo reduções (substituir o lado direito de uma regra pelo seu lado esquerdo)até obter o símbolo inicial S (raiz).

© UFCG / DSC / PSN, 2005 – Parte 3: Análise Sintática – Pág. 4

COMPILADORES ANALISADOR SINTÁTICO DESCENDENTE Descendente com Backup O analisador sintático descendente com backup é o mais antigo método de construção de ADS. Usando tentativa-e-erro, tenta derivar uma sentença esgotando todas as possíveis opções de derivação (p.ex. várias regras com omesmo lado esquerdo, A ::= aB | aC | cD). Caso uma escolha tenha sido infeliz, é selecionada outra derivação e o processo continua. O retorno para os pontos com outras possibilidades de derivação é feito até que se tenha analisado a sentença inteira, ou até que seja encontrada uma folha que não seja reconhecida depois de esgotar-se todas as regras de produção da gramática.

© UFCG / DSC / PSN, 2005– Parte 3: Análise Sintática – Pág. 5

COMPILADORES O registro de que regra de produção foi adotada em determinado ponto da análise, que porção da sentença analisada já foi lida, etc. é mantido em uma estrutura tipo pilha para facilitar o mecanismo de tentativa-e-erro do método descendente com backup. Por gastar muita memória para registrar os passos que adota durante a análise de uma sentença,além de ser demorado, este método praticamente não é mais usado na construção de compiladores. Descendente Recursivo Para quem dispõe de uma linguagem com recursividade para a implementação de um compilador, este método é o mais indicado pois aproveita a estrutura da gramática de forma completa e não impõe restrições à ela (a única restrição é a de não haver recursividade a esquerda). O...
tracking img