(→Solution) |
(→Solution) |
||
Line 18: | Line 18: | ||
line -> <amsmath>\epsilon</amsmath> { <font color="blue">line.crc = 0;</font> } | line -> <amsmath>\epsilon</amsmath> { <font color="blue">line.crc = 0;</font> } | ||
− | line<sub>0</sub> -> line<sub>1</sub> '''CHR''' { <font color="blue">line<sub>0</sub>.crc = line<sub>1</sub>.crc | + | line<sub>0</sub> -> line<sub>1</sub> '''CHR''' { <font color="blue">line<sub>0</sub>.crc = line<sub>1</sub>.crc <amsmath>\oplus</amsmath> CHR.i;</font> } |
All attributes are synthesized (S-attributed grammar): '''crc''' encodes a line's CRC. | All attributes are synthesized (S-attributed grammar): '''crc''' encodes a line's CRC. |
(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).
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 for CHR.i=12 CHR.i=7 CHR.i=9 EOL EOL CHR.i=92 EOL. The green boxes represent print operations (of the displayed value).
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>