[Vertalers] LR(1) Item sets

[Verwijderd]

Hoe bepaal je precies een lr(1) item set?
ik heb bijvoorbeeld deze grammatica

(0) Z’ -> Z
(1) Z -> F
(2) F -> a F b
(3) F -> G
(4) G -> G b
(5) G -> b

waarbij de kleine letters de terminals zijn en de hoofdletters de non-terminals.
bij ontleding krijg ik de volgende states. hoe kan ik hier bijvoorbeeld nu de afsluitings items bepalen?

0) Z’ -> . Z, #
Z -> . F, #
F -> . a F b,
F -> . G,
G -> . G b,
G -> . b,

1) Z’ -> Z .,

2) Z -> F .,

3) F -> a . F b,
F -> . a F b,
F -> . G,
G -> . G b,
G -> . b,

4) F -> G .,
G -> G . b,

5) G -> b .,

6) F -> a F . b,

7) G -> G b .,

F -> a F b .,

[Zoijar]

Je hebt een set S van data items van de vorm N -> a . b{f}.

Als S een item van de vorm P -> a . Nb{f} bevat, dan voor elke regel N->y in je gramatica, moet S ook de regel N->.y{t} bevatten waar t=FIRST(b{f}).

En verder staat FIRST(b{f}) voor de FIRST set van b, en als 'b' epsilon kan produceren nog verenigd met set f.

Waarom wil je dit eigenlijk weten? Je vraag klinkt namelijk alsof je niet precies weet waarover het gaat, terwijl je toch een vrij specialistische vraag stelt. Als je zelf een parser generator wilt schrijven raad ik je aan een goed compiler/parser boek erbij te pakken waar dit soort dingen zeker in staan.

edit:
Als die states zijn al closures. Je begint met de start state, bepaald daar de closure van, en dan voor elk symbol waar de dot voor staat maak je een pijl naar een nieuwe state die begint met de desbetrefende regel, de dot naar voren geplaatst, en bepaal je weer de closure enz

[ Voor 60% gewijzigd door Zoijar op 18-01-2003 19:07 ]