Aula04 GLC

Gramáticas Livres de Contexto
Marcelo Johann
INF01033 - Compiladores B - Marcelo Johann - 2020/1 1

Conteúdo da aula
• Motivação
• Hierarquia de Chomsky
• GLCs
– Gramática, produção, derivações, árvores
– Ambíguas, sem ciclos, ε-livres, fatoradas à
esquerda, recursivas à esquerda, simplificadas
• Transformações
– Eliminação de produções vazias,
– Eliminação de recursividade à esquerda
(direta, indireta),
– Fatoração
Usando Gramáticas para definir a sintaxe
• Muitas construções de linguagens de programação são

recursivas
– Expressões Regulares não podem reconhecer tais construções.
• Exemplo de definição recursiva:

– se S1 e S2 são enunciados e E é uma expressão,
então “if E then S1 else S2” é um enunciado
• Exemplo de definição com uma gramática:

cmd → if expr then cmd else cmd
expr → ( bool ) | expr && expr | expr || expr
bool → true | false
Símbolo “→" indica produção, ou regra de substituição

Hierarquia de Linguagens de Chomsky
recursively enumerable
context-sensitive
context-free
regular

Hierarquia de Linguagens de Chomsky
Linguagem Produções Máquina
Qqr u → v
Recursivamente
Tipo 0 desde que u Máquina de Turing
Enumerável
não seja vazio
wAz → wvz Máq Turing não
Sensível ao
Tipo 1 (w,z são o determinística
Contexto
contexto) linearmente limitada
A→v
Livre de Máquina de Pilha
Tipo 2 (um símbolo à
Contexto não determinística
esquerda)
Tipo 3 Regular A → a | aB | 𝜀 Autômato Finito

Definições
• Gramáticas
• Produção
• Derivações
• Árvores de Derivação

Gramáticas formais: Notações e Definições
• Uma Gramática Formal é um conjunto de 4 elementos:
– G := {S, P, N, T}
• S: o Símbolo Inicial (S ∈ N)
• P: Conjunto de regras de produções do tipo
u→v
• T: conjunto de símbolos terminais
– Palavras ou tokens da linguagem
• N: conjunto de símbolos não terminais

– Símbolos que podem ser substituídos pelas produções
• Vocabulário e notações:
– V: alfabeto
V = N ∪ T (N ∩ T = ∅)
– u ou 𝛂: string pertencente a V
Derivações
• Seja:
– um não-terminal A ∈ N,
– uma regra de produção p = { A → v } ∈ P, e
– w, z dois strings quaisquer.
A transformação:
wAz ⇒ wvz
É chamada “derivação em um passo usando p”
• Se w1 ⇒ w2 ⇒ w3 … ⇒ wn então podemos dizer
w1 ⇒* wn
– “derivação em múltiplos (0 ou mais) passos”;
– também ⇒+ (um ou mais)

Definição da Linguagem Gerada
• A linguagem gerada G (notada L(G)) é:
– O conjunto formado por todos os strings de símbolos
terminais deriváveis a partir do símbolo inicial S
– L(G) = {s | s é um elemento de T* e S ⇒+ s}
• Equivalência:
– G1 e G2 são equivalentes se L(G1) = L(G2)
⇒ Todos strings gerados estão em L
⇐ Todos strings w ∈ L podem ser gerados
• Convenções
– Símbolos que representam terminais em minúsculos:
• u, v, x, y, ...
– Símbolos que representam não-terminais em maiúsculos:
• X, Y, TERM, S,...
– Símbolos que representam formas sentenciais (seqüências
de terminais e não-terminais): letras gregas ou sublinhadas:
• α, β, ω, w, z

Caso particular:
Gramática Regular
• Gramática regular:
– produções exclusivamente da forma:
• A → wB
• A → w,
• onde w ∈ T* e A, B ∈ N (gramática linear à direita)
– A linguagem gerada por uma gramática
regular é regular.
– Pode-se gerar os mesmos strings através de
uma expressão regular.

Exemplo G={N,T,P,S}
N = {S, B, C, D}
T = {0, 1}
S -> 0B | 1C
B -> 1S
C -> 0C | 0D | 1
D -> 0
Exercício: fornecer expressão regular equivalente à

gramática acima.
Árvore de derivação (Parse Tree)
• Árvore de derivação:
– representação gráfica da derivação de uma
sentença (string)
– estrutura hierárquica que originou a sentença
• A raiz da árvore representa o símbolo inicial
• Os vértices interiores são não-terminais
• Os símbolos terminais e a palavra vazia são folhas

Árvore de derivação – exemplo 1
• Gramática G = (
{NUMERO, NUM, DIGITO},
NUMERO
{0,1,2,...,9},
P, NUM
NUMERO )
• P (regras de produção) =
NUMERO → NUM NUM DIGITO
NUM → NUM DIGITO | DIGITO
DIGITO → 0|1|...|9 DIGITO 5
4
Árvore de derivação para
a sentença 45

Derivação mais à esquerda
e mais à direita
• Derivação mais à esquerda de uma
sentença:
– seqüência de formas sentenciais que se
obtém derivando sempre o símbolo não-
terminal mais à esquerda.
• Derivação mais à direita de uma sentença:

– seqüência de formas sentenciais que se
obtém derivando sempre o símbolo não-
terminal mais à direita.

Árvore de derivação – exemplo 2
Gramática G = ({E}, {+, -, *, /, (, ), x}, P, E) sendo
E
P = {E → E + E | E –E| E*E | E/E | (E) | x}
E + E
A mesma árvore pode
representar mais de uma derivação
x E * E
para uma mesma sentença
x x
Possíveis derivações para a árvore:
E⇒E+E⇒x+E⇒x+E*E⇒x+x*E⇒x+x*x
E⇒E+E⇒E+E*E⇒E+E*x⇒E+x*x⇒x+x*x
E⇒E+E⇒E+E*E⇒x+E*E⇒x+x*E⇒x+x*x
Isso não é problema…. MAS….

Gramática Ambígua
Quando há mais de uma
E → E OP E | “(“ E “)” | x árvore de derivação
para uma mesma
OP → “*” | “/” | “+” | “-”
sentença
• Considere 5 – 3 * 2
E E
E - E E
E * E
5 E * E E - E 2
3 2 5 3

Tipos ou Características
• Gramáticas Ambíguas
• Gramáticas sem ciclos
• Gramáticas ε-livres
• Gramáticas fatoradas à esquerda
• Gramáticas recursivas à esquerda
• Gramáticas simplificadas

Outras Classificações de Gramáticas
• Gramática sem ciclos:
– Uma gramática sem ciclos é uma GLC que não
possui derivações da forma
A ⇒+ A para algum A ∈ N
• Gramática ε-livre :
– GLC que não possui produções vazias do tipo
A→ε
exceto a produção S → ε (S é o símbolo inicial).

• Gramática fatorada à esquerda:
– GLC que não possui produções do tipo A → αβ1| αβ2
para alguma forma sentencial α.
• Gramática recursiva à esquerda:

– GLC que permite a derivação
A ⇒+ Aα para algum A ∈ N
O não terminal A deriva ele mesmo, de forma direta ou indireta, como
símbolo mais à esquerda de uma subpalavra gerada.
OBS: RECONHECEDOR TOP-DOWN não aceita gramáticas
recursivas à esquerda

• Gramática Simplificada:
– GLC que:
– não possui símbolos inúteis;
– não possui produções vazias;
– não possui produções do tipo A → B;

Transformações de GLCs
• (A) Eliminação de produções vazias
• (B) Eliminação de recursividade à esquerda:

– recursão direta
– recursão indireta
• (C) Fatoração de uma gramática

Eliminação de Produções Vazias
• Objetivo:
– Criar GLC equivalente sem produções tipo A → 𝜀;
• Algoritmo: Seja G = (N,T,P,S) uma GLC

Etapa 1:
– Construir N𝜀, conjunto de não-terminais que geram a
palavra vazia
– N𝜀 = {A | A→𝜀};
Repita:
N𝜀 = N𝜀 ∪ {X| X→X1…Xn e X1…Xn ∈ N𝜀}
até que o tamanho de N𝜀 não aumente.

Etapa 2:
– Construir o novo conjunto de produções sem produções
vazias, ou seja,
– gerar G1 onde P1 é definido desta forma:
– P1 = {A→𝛼 | 𝛼 ≠ 𝜀};
Repita:
Para toda produção A→𝛼 ∈ P1 e X ∈ N𝜀 tal que
𝛼 = 𝛼1X𝛼2, se 𝛼1𝛼2 ≠ 𝜀 então faça:
P1 = P1 ∪ {A → 𝛼1𝛼2}
até que o tamanho de P1 não aumente.

Etapa 3:
– Incluir a palavra vazia na linguagem, se necessário:
– Se a palavra vazia pertence à linguagem, então a

gramática resultante é:
G2 = (N,T,P2,S);
Onde:
P2 = P1 ∪ {S → 𝜀}

(B) Eliminação de recursividade à esquerda
• Exemplo de GLC recursiva à esquerda:

A → Aa | b
Linguagem =
{ b, ba, baa, baaa, baaaa, baaaaa, … }
• É equivalente a dizer:
b seguido de uma repetição de zero ou mais ‘a’s à
direita
(B) Eliminação de recursividade à esquerda
• Exemplo de GLC recursiva à esquerda:

A → Aa | b
• Gramáticas transformadas equivalentes:
Com a palavra vazia Sem a palavra vazia

A → bX A → b | bX
X → aX |ε X → a | aX
Obs: pode ainda haver recursão indireta!

(B) Outro exemplo de recursividade
• E → E+T | T
• T → T*F | F
• F → (E)| Id
A regra E → E+T | T se torna:
E →TE’
E’ → +TE’| ε
A regra T → T*F | F se torna:

T → FT’
T’→*FT’ | ε

(C) Fatoração de uma gramática
• Elimina a indecisão de qual produção

aplicar quando duas ou mais produções
iniciam com a mesma forma sentencial
A → αβ1 | αβ2
Se torna:
A → αX
X → β1 |β2

(C) Exemplo de Fatoração a Esquerda
Cmd → if Expr then Cmd else Cmd

Cmd → if Expr then Cmd
Cmd → Outro
• Fatorando a esquerda:
Cmd → if Expr then Cmd ElseOpc
Cmd → Outro
ElseOpc → else Cmd | ε

Leituras e Tarefas
Em material separado

Aula04 GLC

Enviado por

Direitos autorais:

Formatos disponíveis

Aula04 GLC

Enviado por

Dados do documento

Título original

Direitos autorais

Formatos disponíveis

Compartilhar este documento

Compartilhar ou incorporar documento

Opções de compartilhamento

Você considera este documento útil?

Este conteúdo é inapropriado?

Direitos autorais:

Formatos disponíveis

Aula04 GLC

Enviado por

Direitos autorais:

Formatos disponíveis

Gramáticas Livres de Contexto

INF01033 - Compiladores B - Marcelo Johann - 2020/1 1

• Muitas construções de linguagens de programação são

• Exemplo de definição recursiva:

• Exemplo de definição com uma gramática:

Símbolo “→" indica produção, ou regra de substituição

INF01033 - Compiladores B - Marcelo Johann - 2020/1 4

Tipo 3 Regular A → a | aB | 𝜀 Autômato Finito

INF01033 - Compiladores B - Marcelo Johann - 2020/1 5

INF01033 - Compiladores B - Marcelo Johann - 2013/1 6

• N: conjunto de símbolos não terminais

INF01033 - Compiladores B - Marcelo Johann - 2013/1 8

INF01033 - Compiladores B - Marcelo Johann - 2013/1 9

INF01033 - Compiladores B - Marcelo Johann - 2013/1 10

Exercício: fornecer expressão regular equivalente à

INF01033 - Compiladores B - Marcelo Johann - 2013/1 12

INF01033 - Compiladores B - Marcelo Johann - 2013/1 13

• Derivação mais à direita de uma sentença:

INF01033 - Compiladores B - Marcelo Johann - 2013/1 14

Isso não é problema…. MAS….

INF01033 - Compiladores B - Marcelo Johann - 2013/1 16

INF01033 - Compiladores B - Marcelo Johann - 2013/1 17

INF01033 - Compiladores B - Marcelo Johann - 2013/1 18

• Gramática recursiva à esquerda:

INF01033 - Compiladores B - Marcelo Johann - 2013/1 19

INF01033 - Compiladores B - Marcelo Johann - 2020/1 20

• (B) Eliminação de recursividade à esquerda:

• (C) Fatoração de uma gramática

INF01033 - Compiladores B - Marcelo Johann - 2013/1 21

• Algoritmo: Seja G = (N,T,P,S) uma GLC

INF01033 - Compiladores B - Marcelo Johann - 2020/1 22

INF01033 - Compiladores B - Marcelo Johann - 2020/1 23

– Se a palavra vazia pertence à linguagem, então a

INF01033 - Compiladores B - Marcelo Johann - 2020/1 24

• Exemplo de GLC recursiva à esquerda:

• Exemplo de GLC recursiva à esquerda:

• Gramáticas transformadas equivalentes:

Com a palavra vazia Sem a palavra vazia

Obs: pode ainda haver recursão indireta!

A regra T → T*F | F se torna:

INF01033 - Compiladores B - Marcelo Johann - 2020/1 27

• Elimina a indecisão de qual produção

INF01033 - Compiladores B - Marcelo Johann - 2013/1 28

Cmd → if Expr then Cmd else Cmd

INF01033 - Compiladores B - Marcelo Johann - 2013/1 29

INF01033 - Compiladores B - Marcelo Johann - 2020/1 30

Você também pode gostar