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