Wiki**3

Problema

Uma máquina reconhece os símbolos de 0 a 9, ~ e !. Os símbolos de 0 a 9 são organizados em sequências possivelmente delimitadas por !. Se a sequência numérica não estiver delimitada, então o seu valor é simplesmente o do seu maior dígito (em base 10). Sequências delimitadas indicam o número correspondente aos dígitos em base 10. O operador ~ calcula o valor da soma dos seus argumentos (este operador é associativo à esquerda).

Exemplo: à sequência 1934~!26!~12 corresponde ao valor 9+26+2=37.

1. Identifique a gramática atributiva correspondente ao problema, descrevendo o significado de todos os atributos, assim como os respectivos tipos. Que tipo de gramática obteve?
2. Identifique a árvore de sintaxe decorada e o grafo de dependências para a frase 123~!123! (valor 126).
3. Escreva uma especificação YACC que implemente a gramática descrita em 1. Codifique toda a especificação (incluindo as zonas de declarações e de regras) e todas as funções auxiliares. Não utilizar variáveis globais.

Gramática Atributiva

E representa uma expressão; N representa um número; S representa uma sequência de dígitos não delimitada; e D representa uma sequência de dígitos delimitada. O atributo booleano v representa o valor associado a cada símbolo.

Como se pode ver pelas acções semânticas associadas à gramática, todos os atributos são sintetizados, pelo que a gramática é do tipo S.

Árvore Sintáctica Decorada e Grafo de Dependências

Especificação YACC (versão directa a partir da gramática acima)

Considerando que a gramática acima é do tipo S, a realização em YACC é trivial e deixa-se como exercício para o leitor.