(→Solution) |
|||
Line 17: | Line 17: | ||
lines -> lines line '''EOL''' { printf("%d\n", <font color="blue">line.crc</font>); } | lines -> lines line '''EOL''' { printf("%d\n", <font color="blue">line.crc</font>); } | ||
− | line -> < | + | line -> <math>\epsilon</math> { <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 <math>\oplus</math> 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 -> [math]\epsilon[/math] { line.crc = 0; } line0 -> line1 CHR { line0.crc = line1.crc [math]\oplus[/math] 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>