ANALISE SINTÁTICA aula-07-analise-sintática.pdf TERMOS UTILIZADOS EM LINGUAGEM DE PROGRAMAÇÃO • Símbolo: são os elementos mínimos que compõe uma linguagem. Na linguagem humana são as letras. • Sentença: É um conjunto ordenado de símbolos que forma uma cadeia ou string. Na linguagem humana são as frases. • Alfabeto: É um conjunto de símbolos. Na linguagem humana é o conjunto de letras {a, b, c, d, ...} • Linguagem: É o conjunto de sentenças, Na linguagem humana são os conjuntos de palavras {compiladores, linguagem, ...} • Gramática: É uma forma de representar as regras para formação de uma linguagem. ANALISE SINTÁTICA • O que é sintaxe? Parte da gramática que estuda a disposição das palavras na frase e das frases no discurso, bem como a relação lógica das frases entre si. (AURELIO, 2004). • É a segunda fazer do processo de compilação e sua função é verificar se as construções utilizadas no programa estão gramaticalmente corretas. • As estruturas sintáticas ou gramaticais podem ser especificadas através das Gramaticas Livres de Contexto -GLC. ANALISE SINTÁTICA • Dada uma GLC “G” e uma sentença “s” o objetivo do analisador sintático é verificar se a sentença “s” pertence a linguagem “G”. • O analisador sintático também é conhecido como parser e recebe do analisador léxico a sequência de tokens que constitui a sentença “s” • A analise sintática produz uma árvore de derivação se a sentença é válida ou emite um erro sintático. • O analisador sintático deve ser projetado para que a análise seja feita até o fim do programa mesmo que encontre erros no texto do programa fonte. ANALISE SINTÁTICA • Duas estratégias para implementar a analise sintática. • Top-down ou descendente: constrói a árvore de derivação a partir do símbolo inicial da gramatica fazendo a árvore crescer até as suas folhas. • Bottom-up ou ascendente: Faz a análise no sentido inverso, ou seja, constrói a árvore de derivação das folhas até o símbolo inicial da gramatica. ANALISE SINTÁTICA - PROCESSO • O analisador léxico é desenvolvido para reconhecer os tokens fazendo uma leitura dos caracteres e obtendo sequencia de tokens. • O analisador léxico vê o texto como uma sequência de palavras de uma linguagem regular e reconhece ele através de um autômato finito ou expressão regular. • Já o analisador sintático vê o mesmo texto como uma sequência de sentenças que deve satisfazer as regras gramaticais. • É através da gramatica que podemos validar expressões criadas na linguagem de programação. • O analisador sintático agrupa os tokens em frases gramaticais usadas pelo compilador com o objetivo de criar uma saída que é uma estrutura de dados que possui a hierarquia da entrada a árvore de derivação. ANALISE SINTÁTICA - PROCESSO • Exemplo de uma árvore de derivação. ANALISE SINTÁTICA - PROCESSO • Estrutura sintática de um código fonte ANALISE SINTÁTICA - PROCESSO • Entende-se por regras gramaticas as formas como podemos descrever a estrutura sintática do programa. • No modelo de compilador que está sendo estudado o analisador sintático recebe do analisador léxico uma cadeia de tokens representado o programa fonte. • O analisador sintático verifica se essas cadeias pertencem a linguagem definhada pela gramatica. Veja um exemplo no diagrama abaixo demostrando esse processo. ANALISE SINTÁTICA - PROCESSO ANALISE SINTÁTICA - PROCESSO ANALISE SINTÁTICA - PROCESSO • Descubra os erros sintáticos da seguinte expressão 01 02 03 04 05 06 07 private static Integer maior(Integer numero01 Integer numero02) { if (numero01 > numero02) { return numero01 } else { return numero02; } GRAMATICA LIVRE DE CONTEXTO • A Gramatica Livre de Contexto ajuda a especificar a sintaxe de uma linguagem. • A GLC é a base para a análise sintática das linguagens de programação e permitem descrever a maioria das linguagens de programação usadas atualmente. • Uma gramatica descreve naturalmente como é possível fazer construções em linguagem de programação. • Veja o exemplo de um comando if-else em Pascal que deve ter a seguinte forma if (expressão) then declaração else declaracao ; GRAMATICA LIVRE DE CONTEXTO • Essa mesma forma em uma Gramatica Livre de Contexto pode ser expressada da seguinte maneira: declaracao → if ( expressao ) then declaracao else declaracao; expressao → id > id declaracao → ... ... GRAMATICA LIVRE DE CONTEXTO • As linguagens regulares podem ser reconhecidas através de expressões regulares criando um analisador léxico (exemplo JFlex). • Uma linguagem livre de contexto pode ser reconhecida autômatos de pilha que a descrevem a forma como podemos criar analisadores sintáticos (exemplo JCUP). GRAMATICA LIVRE DE CONTEXTO • A definição de uma gramatica livre de contexto pode ser representada da seguinte forma: G = (N, T, P, S) • Onde: • N – Conjunto finito de símbolos não terminais. • T – Conjunto finito de símbolos terminais. • P – Conjunto de regras de produções. • S – Símbolo inicial da gramatica GRAMATICA LIVRE DE CONTEXTO • Terminologias: • Símbolos terminais: símbolos básicos que formas as cadeias, são os tokens da linguagem de programação. • Símbolos não terminais: variáveis sintáticas utilizadas para auxiliar a definição da linguagem, são compostas de símbolos terminas e pelos próprios símbolos não terminais. • Regras de produções: regras sintáticas que indicam como símbolos terminais e não terminais podem ser combinados. • Símbolo inicial: Inicio da validação da produção representado por um símbolo não terminal. GRAMATICA LIVRE DE CONTEXTO • Derivações: É a substituição das setnteças iniciando pelo símbolo inicial substituindo os símbolos não terminais pelos símbolos terminais. • Tipos de derivação: • Mais à esquerda: trocamos os símbolos não terminais mais à esquerda. • Mais à direita: trocamos os símbolos não terminais mais a direita • Derivações: É a substituição das setnteças iniciando pelo símbolo inicial substituindo os símbolos não terminais pelos símbolos terminais. • Tipos de derivação: • Mais à esquerda: trocamos os símbolos não terminais mais à esquerda. • Mais à direita: trocamos os símbolos não terminais mais a direita EXEMPLOS Definindo a gramatica da linguagem G = ( {LITERAL}, {a, b}, PALAVRA, LITERAL ) Definindo a regra de produção PALAVRA { LITERAL → aLITERALb | Ø } Identificando as terminologias Símbolos terminais Símbolos não terminais: Símbolo inicial: Regra de produção: aeb LITERAL LITERAL PALAVRA Derivação a direita para saber se aabb fazer parte da linguagem LITERAL → aLITERALb LITERAL → aaLITERALbb LITERAL → aaØbb Com a gramática acima é possível dizer que palavra aab da linguagem? LINGUAGEM DE PROGRAMAÇÃO AB Definindo a gramatica da linguagem G = ( {EXP }, { +, *, (, ), x }, OPR, EXP) Definindo a regra de produção OPR { EXP → EXP + EXP | EXP * EXP | (EXP) | x } Identificando as terminologias Símbolos terminais Símbolos não terminais: Símbolo inicial: Regra de produção: + , *, (, ), x EXP EXP OPR EXPRESSÕES MATEMÁTICAS SOMA E MULTIPLICAÇÃO Derivação a direita para saber se a expressão (x + x) * x fazer parte da linguagem EXP → EXP * EXP EXP → (EXP) * EXP EXP → (EXP + EXP) * EXP EXP → (x + EXP) * EXP EXP → (x + x) * EXP EXP → (x + x) * x OPR { EXP → EXP + EXP | EXP * EXP | (EXP) | x } Com a gramática acima é possível dizer que x - x é uma expressão valida? EXPRESSÕES MATEMÁTICAS SOMA E MULTIPLICAÇÃO Definindo a gramatica da linguagem G = ({EXP, OP}, {+, *, +, -, (, ), id, numero}, OPR, EXP) Definindo a regra de produção OPR { EXP → EXP OP EXP | (EXP) | -EXP | id | numero OP → + | - | * | / } Identificando as terminologias Símbolos terminais Símbolos não terminais: Símbolo inicial: Regra de produção: + , *, (, ), x, +, -, id, numero EXP, OP EXP OPR EXPRESSÕES MATEMÁTICAS SOMA E MULTIPLICAÇÃO COMPLETO Derivação a direita para saber se a expressão a + b fazer parte da linguagem EXP → EXP OP EXP EXP → EXP OP id EXP → EXP + id EXP → id OP id EXP → id + id OPR { EXP → EXP OP EXP | (EXP) | -EXP | id | numero OP → + | - | * | / } Com a gramática acima é possível dizer que qualquer expressão matemática é uma expressão valida? EXPRESSÕES MATEMÁTICAS SOMA E MULTIPLICAÇÃO COMPLETO Derivação a direita para saber se a expressão -1 fazer parte da linguagem EXP → OP EXP EXP → OP numero EXP → - numero OPR { EXP → EXP OP EXP | (EXP) | -EXP | id | numero OP → + | - | * | / } Com a gramática acima é possível dizer que qualquer expressão matemática é uma expressão valida? EXPRESSÕES MATEMÁTICAS SOMA E MULTIPLICAÇÃO COMPLETO DICAS PARA CRIAR UMA GRAMATICA LIVRE DE CONTEXTO • Conhecer todos os tokens. • Criar a regra de produção. • Especificar a gramatica. • Ex: G = ( {A, B, C}, {int, id, numero, +, -}, P, A ) • Fazer a derivação. EXERCÍCIOS SEÇÃO 5