Revision as of 16:43, 26 June 2010

Problem (in Portuguese)

(appeared in Teste 2 2009/2010)

Considere uma linguagem constituída por uma sequência, não vazia, de linhas. Cada linha é constituída por uma sequência, possivelmente vazia, de caracteres. Pretende-se determinar o número de controlo de erro (CRC) de cada linha de texto. Para tal, o analisador lexical produz dois tipos de lexemas: CHR (número inteiro que representa o código do carácter lido); EOL (fim de linha). Escreva um programa que imprima, após o fim de cada linha (EOL), o correspondente CRC (iniciado a 0 em cada linha, é calculado através de um “ou exclusivo” com o valor inteiro do carácter lido).

1. Identifique uma gramática que reconheça a linguagem descrita.
2. Determine os atributos de cada símbolo e indique, justificadamente, o tipo de gramática obtida.
3. Represente a árvore decorada para a frase seguinte, indicando a sequência de valores impressos no seu processamento.
   CHR.i=12 CHR.i=7 CHR.i=9 EOL EOL CHR.i=92 EOL
4. Escreva uma especificação YACC que realize a solução do problema acima. A gramática não deve ter conflitos.

Solution

The problem has a simple solution, with just two non-terminal symbols: one to account for multiple lines (lines), and another to account for multiple characters in a line (line) (a line can be empty, i.e., it may not have any characters).

lines  -> line EOL        { printf("%d\n", line.crc); }
lines  -> lines line EOL  { printf("%d\n", line.crc); }

line  ->                 { line.crc = 0; }
line0 -> line1 CHR        { line0.crc = line1.crc ^ CHR.i; }

All attributes are synthesized (S-attributed grammar): crc encodes a line's CRC.

The following is the annotated tree.

A YACC specification can be obtained by adapting the grammar above: <text>

%union { int i; }
%token CHR
%token EOL
%type<i> line
%%
lines : line EOL        { printf("%d\n", $1); }
lines : lines line EOL  { printf("%d\n", $2); } 
line  : /* empty */     { $$ = 0; }
line  : line CHR        { $$ = $1 ^ $2; }
%%

</text>