Trabalho de compiladores

Disponível somente no TrabalhosFeitos
  • Páginas : 7 (1692 palavras )
  • Download(s) : 0
  • Publicado : 29 de agosto de 2012
Ler documento completo
Amostra do texto
TRABALHO DE COMPILADORES


1) Defina e de exemplo de:

a)Gramática.

Uma gramática G é uma construção matemática usada para definir uma
linguagem em um alfabeto , e é definida através de quatro componentes:
G = < , , P, S >. Temos:

• um alfabeto de símbolos terminais, ou simplesmente terminais: os símbolos
que compõem as cadeias da linguagem.
• um alfabeto de símbolosnão terminais, ou simplesmente não - terminais.
Os não - terminais são símbolos auxiliares, que não podem fazer parte das
cadeias da linguagem definida pela gramática, que são compostas apenas de
terminais.
• um conjunto P de regras de re-escrita (ou regras de produção) da forma,
que indicam que a cadeia pode ser substituída, onde ocorrer, pela
cadeia . No caso mais geral,as cadeias e podem ser compostas de
terminais e não-terminais, em qualquer número, exigindo-se apenas que
contenha pelo menos um não-terminal.
• m não-terminal especial S, o símbolo inicial.

Formalmente, a linguagem da gramática G é o conjunto
L(G) = { x * | S * x },

onde * representa o conjunto das cadeias em , ou seja todas as cadeias compostas de
zero ou mais símbolosretirados do alfabeto.

b)Gramática Livre de Contexto.

Descreve uma linguagem e regras de cálculo que permitem calcular valores.

Numa gramática livre de contexto as regras de reescrita têm a forma A B com apenas um símbolo A, sempre um não-terminal, do lado esquerdo.

O nome livre de contexto faz referência ao fato de que, onde quer que apareça,
A pode ser substituído por b,independentemente do contexto à sua volta. Por oposição,
γAδ→γβδ, , que permite substituir A por β apenas no contexto “γ antes, δ depois” é uma
A, que permite substituir A por apenas no contexto “ antes, depois” é uma
sensível ao contexto permite regras α→β quaisquer, com a única restrição de que o
comprimento de β seja maior ou igual ao comprimento de α.


Na prática, não é necessário indicarexplicitamente os quatro componentes de

uma gramática livre de contexto, bastando apresentar as regras, seguindo as seguintes
convenções:

os símbolos que aparecem à esquerda nas regras são os nãoterminais, em geral
representados por letras latinas maiúsculas (S, A, B, ...).
• os demais símbolos são os terminais, em geral representados por letras latinas
minúsculas ou outros símbolos (a, b,c, ..., 0, 1, +, #, ...).
• o símbolo inicial é o que aparece no lado esquerdo da primeira regra.
• várias regras (A → β1, A → β2, ..., A → βn), com um mesmo nãoterminal A
do lado esquerdo podem ser reunidas: A → β1 | β2 | ... βn.
• cadeias com terminais e nãoterminais são representadas por letras gregas
minúsculas (α, β, γ, ...).
• cadeias só de terminais são representadas por letras latinas(x, y, z, ...).
• um símbolo qualquer, que pode ser terminal ou nãoterminal, é representado
por uma letra latina maiúscula (X, Y, ...).


c)Linguagem gerada por uma gramática livre de contexto

Uma das gramáticas mais freqüentemente usadas como exemplo em cursos
de linguagens e de compiladores é a gramática G0, dada por suas regras:

E → E + T | T
T → T ∗ F | F
F → ( E ) | a

Pelasconvenções vistas, temos para G0 :
símbolos terminais: { +, ∗, (, ), a }
símbolos não terminais: { E, T, F }
símbolo inicial: E
regras: { E→E+T, E→T, T→T∗F, T→F,
F→(E), F→a }

Por exemplo, a cadeia a+a∗a pertence à linguagem da gramática, por causa da
derivação
(1) E ⇒ E+T ⇒ T+T ⇒ a+T ⇒ a+T∗F ⇒ a+F∗F ⇒ a+a∗F
⇒ a+a∗a
Note que outras derivações sãopossíveis para a mesma cadeia. Por exemplo, temos
(2) E ⇒ E+T ⇒ E+T∗F ⇒ E+T∗a ⇒ E+F∗a ⇒ E+a∗a ⇒ T+a∗a
⇒ F+a∗a ⇒ a+a∗a
(3) E ⇒ E+T ⇒ E+T∗F ⇒ E+F∗F ⇒ E+a∗F ⇒ T+a∗F
⇒ T+a∗a ⇒ F+a∗a ⇒ a+a∗a

As derivações (1), (2) e (3) acima são equivalentes, no sentido de que ambas geram a
cadeia da mesma maneira, aplicando as mesmas regras aos mesmos símbolos, e se
diferenciam apenas pela ordem em que as...
tracking img