Trabalho de compiladores

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ímbolos nã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ímbolos retirados 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 indicar