Videoaula 8 - Gramáticas

Prévia do material em texto

Gramáticas
COMPILADORES
• Definição de uma Gramática
• Constituição de uma Gramática
• Gramática Regular
• Gramática Livre de Contexto
• Diferenças entre as Gramáticas
ROTEIRO 
● Uma gramática 'G' pode ser formalmente descrita 
usando quatro tuplas como G = (V, T, S, P) onde,
● V = Conjunto de Variáveis ​​ou Símbolos 
Não-Terminais
● = Conjunto de Símbolos Terminais
● S = Símbolo inicial
● P = Regras de Produção para Terminais e 
Não-Terminais
DEFINIÇÃO DE UMA GRAMÁTICA 
● Uma regra de produção tem a forma 𝛂→𝛃 onde 𝛂 e 𝛃
são cadeias em V ⋃ T, e pelo menos um símbolo de 𝛂
pertence a V.
Exemplo: G = ({S, A, B}, {a, b}, S, {S→AB, A→a, B→b})
● Noam Chomsky apresentou um modelo matemático 
de gramática que é eficaz para linguagens de 
computador.
● De acordo com Chomsky, há quatro tipos de 
Gramática e a Gramática Tipo 3 é a Gramática 
Regular que aceita Linguagens Regulares.
CONSTITUIÇÃO DE UMA GRAMÁTICA
https://www.geeksforgeeks.org/chomsky-hierarchy-in-theory-of-computation/
● A Gramática Regular é a gramática Tipo 3 de 
acordo com a Hierarquia de Chomsky. 
● Apresenta um único símbolo não-terminal do lado 
esquerdo, um único terminal do lado direito, ou 
um único terminal seguido por um não-terminal.
● A Gramática Regular aceita e gera linguagens 
regulares.
● Todas as produções deverão ser no formato de:
A –> xB
A –> x
A –> Bx
onde A, B ∈ V (Conjunto de Variáveis), ex ∈ T*, 
ou seja, a sequência de terminais.
GRAMÁTICA REGULAR
● Tipos
● A gramática regular pode ser dividida em dois tipos:
● Gramática Linear Esquerda (LLG)
● Uma gramática é considerada Linear Esquerda se 
todas as produções forem da forma:
● A –> Bx
● A –> x
● onde A, B ∈ V (símbolos não-terminais) e x ∈ T*, ou 
seja, a sequência de terminais.
● Na LLG, o símbolo não-terminal fica à esquerda do 
símbolo terminal.
GRAMÁTICA REGULAR
● Tipos (Cont.)
● A gramática regular pode ser dividida em dois tipos:
● Gramática Linear Esquerda (LLG)
● Uma gramática é considerada Linear Direita se 
todas as produções forem da forma:
● A –> xB
● A –> x
● onde A, B ∈ V (símbolos não-terminais) e x ∈ T*, ou 
seja, a sequência de terminais.
● No RLG, o símbolo não-terminal fica à direita do 
símbolo terminal.
GRAMÁTICA REGULAR
● Uma gramática livre de contexto (GLC) é definida 
por um conjunto de regras de produção que 
descrevem como as sentenças de uma linguagem 
podem ser geradas. 
● Cada regra de produção consiste em um símbolo 
não-terminal que é substituído por uma sequência 
de símbolos terminais e não-terminais. 
GRAMÁTICA LIVRE DE CONTEXTO
● A gramática livre de contexto pode ser definida 
usando quatro tuplas V, T, P e S.
● G= (V, T, P, S) 
● G significa a gramática 
● T contém um conjunto finito de símbolos 
chamados Terminais.
● V contém um conjunto finito de símbolos que 
não são terminais
● S denota o símbolo inicial. 
GRAMÁTICA LIVRE DE CONTEXTO
● Continuação
● Uma linguagem é definida sobre algum alfabeto, 
por exemplo, o conjunto de tokens produzidos 
por um lexer, ou o conjunto de caracteres 
alfanuméricos. Esses símbolos do alfabeto são 
chamados de terminais. 
● O símbolo inicial é usado para derivar uma 
string. Pode-se derivar uma string substituindo, 
repetidamente, um não-terminal do lado direito 
da produção até que todos os não-terminais 
tenham sido substituídos por símbolos 
terminais.
GRAMÁTICA LIVRE DE CONTEXTO
● Suponha que temos os seguintes conjuntos
● Conjunto de Símbolos Terminais (T): {a, b}
● Conjunto de Símbolos Não-Terminais (N): {S, A, B}
● Símbolo Inicial (S): S
● Algumas regras de produção para a gramática 
● Regra de Produção S:
● S → aA
● Isso significa que o símbolo não-terminal S pode 
ser substituído pela sequência "aA".
GRAMÁTICA LIVRE DE CONTEXTO
● Algumas regras de produção para a gramática (cont.)
● Regra de Produção A:
● A → aA
● A → bB
● A → ε
● Isso significa que o símbolo não-terminal A pode 
ser substituído por "aA", "bB" ou ε (a cadeia 
vazia).
GRAMÁTICA LIVRE DE CONTEXTO
● Algumas regras de produção para a gramática (cont.)
● Regra de Produção B:
● A → bB
● B → ε
● Isso significa que o símbolo não-terminal B pode 
ser substituído por "bB" ou ε.
GRAMÁTICA LIVRE DE CONTEXTO
● Essas regras de produção permitem gerar sequências 
de símbolos terminais e não-terminais. O processo de 
aplicar essas regras começa com o símbolo inicial (S) 
e, em seguida, as regras são usadas iterativamente 
para expandir os não-terminais até que não haja mais 
não-terminais na sequência.
GRAMÁTICA LIVRE DE CONTEXTO
● Por exemplo, usando as regras anteriores, podemos gerar a 
sequência "aabb" da seguinte forma:
S (inicial)
aA (aplicando a regra de produção S)
aabB (aplicando a regra de produção A)
aabb (aplicando a regra de produção B)
● Assim, a gramática livre de contexto permite descrever 
estruturas complexas em linguagens de programação e é 
amplamente utilizada na análise sintática de compiladores.
GRAMÁTICA LIVRE DE CONTEXTO
● Comparativo entre as gramáticas
DIFERENÇAS ENTRE AS GRAMÁTICAS
1.Compiladores: princípios, técnicas e ferramentas
2.Compiladores: princípios e práticas
3.https://www.geeksforgeeks.org/difference-between-context-free-grammar-
and-regular-grammar/
4.https://www.geeksforgeeks.org/chomsky-hierarchy-in-theory-of-computation/
REFERÊNCIAS
https://plataforma.bvirtual.com.br/Acervo/Publicacao/280
https://integrada.minhabiblioteca.com.br/reader/books/9788522128532/pageid/0
https://www.geeksforgeeks.org/difference-between-context-free-grammar-and-regular-grammar/
https://www.geeksforgeeks.org/chomsky-hierarchy-in-theory-of-computation/