linguagens formais e automatos

Prévia do material em texto

Por exemplo, uma expressão aritmética que são compostas de sub expressões que são elas próprias expressões aritméticas. Em termos de gramáticas formais isto é exatamente o que as regras E -> E + E; E -> E x E e E -> (E) dizem. A regra E -> a | b, por sua vez, se encarrega de indicar quais são as expressões mais simples. Vimos que a gramática livre de contexto tem poder de expressão suficiente para formalizar este mecanismo de alinhamento. As Arvores de derivação foram introduzidas como uma forma estática de exibir a hierarquia induzida por uma derivação. Por exemplo: uma derivação de a x (a + b) necessariamente começa por E -> E x E e somente depois pode-se usar a regra E -> (E), colocando a soma de expressões como sub-expressão. Isso já indica como a gramatica impas a precedência de operações derivada do uso de parênteses. Outros exemplos são de palíndromos, que nada mais são que alinhamento de palíndromos, como é dito pela regra S -> aSa | bSb, com a regra S -> λ indicando palíndromos de tamanho par. 
Discorra sobre como as linguagens livres de contexto permitem a ambiguidade sintática. Indique como e porque os AP’s têm capacidade para dar conta do alinhamento característico de linguagens livres de contexto. Aborde também o problema da não equivalência das versões determinísticas e não-determinísticas de APs. Tente indicar como APs são utilizados em compiladores e porque estes devem ser determinísticos neste caso. 
Na teoria dos autômatos, um autômato com pilha determinístico (APD) é uma variante de autômato com pilha . O APD aceita as linguagens livres de contexto determinísticas,um subconjunto próprio de linguagens livres de contexto.[1]
As transições da máquina são baseadas no estado atual e no símbolo de entrada, e também do símbolo mais alto na pilha. Os símbolos mais inferiores na pilha não estão visíveis e não provocam efeitos imediatos. As ações da máquina incluem colocar símbolo na pilha, retirá-lo da pilha ou susbtituir o topo da pilha. Um autômato com pilha determinístico tem no máximo uma transição possível para uma mesma combinação de símbolo de entrada, estado e símbolo no topo da pilha. Isto é o que o difere de um autômato com pilha não determinístico
Geraud Senizergues (1997) provou que o problema de equivalência para autômatos com pilha determinísticos (isto é, dados dois APDs A e B, L(A)=L(B)?) é decidível.[5] Esta prova rendeu-lhe em 2002 um Gödel Prize. Para AP não determinísticos, o problema de equivalência é indecidível.
Analises- Léxicas sintáticas e semânticas e Sínteses: Geração do código 
intermediário (cod. baixo/nível de instrução), otimização do código 
intermediário e geração do código objeto. 
 Atualmente, um compilador pode ser construído em po ucos dias, caso a 
linguagem fonte não seja m uito comp lexa e várias fases da compilação podem 
ser geradas automaticamente através da utilização de program as geradores, 
para a análise léxica e sintática, respectivamente.