Gramáticas atributivas

 

  1. Pretende-se controlar um semáforo de 3 estados: Encarnado, Amarelo e Verde, representados pelos valores numéricos 2, 1 e 0, respectivamente. O semáforo pode ser controlado por um temporizador que emite, regularmente, o   token   NEXT que faz o semáforo evoluir para o estado seguinte, na sequência: Encarnado, Verde, Amarelo e novamente Encarnado. Além disso, existe um botão de pânico que gera o   token   PANIC e coloca o semáforo no estado Encarnado, independentemente do estado anterior. O estado inicial do sistema é Encarnado.
    a.
    Construa a gramática atributiva que permite controlar o estado do semáforo (considere apenas os 2 tokens indicados).  
    Indique que tipo de gramática atributiva que obteve.
    b.
    Realize a árvore semântica anotada (decorada) para a entrada:   NEXT,   NEXT,   PANIC e   NEXT.
  2. Considere a seguinte gramática atributiva:
    s->symbol   1   #   symbol   2{ 
        s.   val =   symbol   1.   val +   symbol   2.   val
        symbol   1.   x = 1
        symbol   2.   x = 1
       } 
    symbol   1->symbol   2   dig{ 
        symbol   2.   x =   symbol   1.   x * 5
        symbol   1.val = symbol   2.val +   dig.val * symbol   1.x
       } 
    symbol->dig{ 
        symbol.val =   dig.val * symbol.x
       } 

    O elemento lexical   dig representa um dígito de   0 a   9, e o seu atributo   val representa o valor numérico correspondente.

    1. Represente a àrvore semântica para a entrada   328#37.
    2. Apresente uma gramática atributiva equivalente que apenas contenha atributos sintetizados.
  3. A gramática seguinte admite atribuições dentro de expressões.
    S->E
    E->E   + E | E   := E |   ( E   ) |   id

    Quando uma expressão está a ser analisada é necessário diferenciar os casos onde a expressão está à direita, daqueles onde a expressão está à esquerda, do sinal de atribuição. Note que não é possível atribuir um valor a uma expressão. Por exemplo a expressão   id + id := id é ilegal. No entanto, as expressões   id := ( id + id ), quer   id := ( id := id ), ou ainda   ( id ) := ( id := ( id + id ) ) são autorizadas.  
    Considere que o operador ':=' é menos prioritário que o operador '+', além de associativo à direita, enquanto o operador '+' é associativo à esquerda.

    Escreva um esquema de tradução que usa um atributo herdado ( e nenhum sintetizado ) chamado  ladoassociado ao símbolo   E, e que determina se a expressão corrente está à direita ou à esquerda da atribuição. O código associado à gramática emitirá uma mensagem de erro caso a expressão seja ilegal.