Then you can additionally store for each hash the order in which its keys are in:

# ...
push @grammar_keys, $1 unless exists $grammar{$1};
$grammar{$1} = $2;
# ...
print "$k\n" for my $k (@grammar_keys);
[download]

(I've also taken the liberty of using lowercase variable names; you should probably use all-uppercase names only for special global variables).

Or you can use a module like Tie::IxHash, which implements hashes with ordered keys just like you want.