Question

As linguagens livres de contexto possuem estrutura que possibilita o alinhamento sintático de seus componentes. 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 aninhamento 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.

Answer 1

nao compreendi o raciocínio