[Compilers] Korte vraag mbt LR(0) Parse table gen.

[Verwijderd]

Voor een general purpose parser unit ben ik nu bezig met een LR(0) parse table generator die de parse table voor mn LR(0) parser gaat aanleveren. (Ik gebruik geen generators/parsers die beschikbaar zijn omdat mn lexical analyzer nogal uitgebreid is en daardoor bestaande parsers/tablegenerators niet voldoen).

Om de Item List generator te testen gebruik ik de simpele grammatica van: http://www.wikipedia.org/wiki/LR_parser , een goede page waar ook het algoritme voor de LR(0) parse table generation is uitgelegd. Om niet teveel tijd kwijt te zijn aan het checken van andere resultaten dan die op deze page zijn vermeld, wil ik mn algoritme iig gelijk houden aan wat op die page is uitgelegd, echter is zie een rariteit op die page waar volgens mij geen basis voor is:

Bij het genereren van de vervolg item sets op set 0, wordt eerst gekeken naar de terminals die volgen op de dot, en daarna pas naar de non-terminals. In Aho-Sethi-Ullman kon ik ook niets vinden waaruit zal blijken dat men eerst de terminals moet bekijken en daarna de non-terminals, echter deze volgorde heeft wel gevolgen voor de volgorde van de sets en dus voor de uiteindelijke action/goto table. Ik vermoed dat die volgorde niets uitmaakt, maar weet dat niet zeker.

Mijn vraag is dus: maakt het uit of je bij het genereren van vervolgsets eerst begint met de terminals of niet? .

Bvd.

ps: ik ben niet wetenschappelijk bezig met talen en vertalers, dus mocht je links hebben naar wellicht tot op de vezel correct zijnde wetenschappelijke artikelen: bedankt, maar dat kost me teveel tijd om te doorgronden (terwijl de algo's in feite bar simpel zijn, zie de wikipedia pages).

[Scare360]

Literatuur: Aho, Sethi, Ullmann
Compilers Principles, Techniques and Tools.
ISBN 0 201 10088 6

[ Voor 232% gewijzigd door Scare360 op 01-12-2002 23:03 ]

[.oisyn]

wat offtopic reacties verwijderd

[Verwijderd]

paulgielens schreef op 01 December 2002 @ 22:31:
Literatuur: Aho, Sethi, Ullmann
Compilers Principles, Techniques and Tools.
ISBN 0 201 10088 6

Die heeft ie al....

[mbravenboer]

Ik ben niet zo goed in thuis in LR parsers en LR parse table constructie, omdat ik dat vreemd genoeg tot nu toe nooit heb moeten leren en ik altijd werk met een parser generator die de volledige klasse van context vrije grammatica's ondersteunt, maar ik zal een poging wagen. Ik zou me maar niet al te veel vertrouwen in dit geval .

De volgorde van de item-sets/state wordt toch helemaal niet gebruikt in het algoritme van een LR parser? Waarom zou de volgorde van deze item-sets dan uitmaken?

Ik zie in het boek van Aho inderdaad ook geen volgorde gespecificeerd staan, dus ik denk dat de gekozen volgorde op de Wiki pagina slechts bedoeld is om duidelijk te maken waarover er gesproken wordt en niet direct om onderscheid te maken tussen terminals en non-terminals. Je moet tenslotte toch wat kiezen .

[mbravenboer]

Otis: Ik gebruik geen generators/parsers die beschikbaar zijn omdat mn lexical analyzer nogal uitgebreid is en daardoor bestaande parsers/tablegenerators niet voldoen.

Ik ben trouwens wel benieuwd wat er zo uitgebereid aan is dat je geen bestaande tools kan gebruiken?

[Verwijderd]

mbravenboer schreef op 02 December 2002 @ 07:34:
De volgorde van de item-sets/state wordt toch helemaal niet gebruikt in het algoritme van een LR parser? Waarom zou de volgorde van deze item-sets dan uitmaken?

Nee, in 1e instantie leek me dat ook geen bezwaar, maar het levert wel een state machine op met andere state-chains, dus of het algoritme nog klopt dat je gebruikt om die state machine te construeren is dan de vraag. En aangezien de uitkomst van dit algoritme weer wordt gebruikt voor het testen van de volgende stap, de LR(0) parser, is het natuurlijk wel zaak dat die tabel correct is

Ik zie in het boek van Aho inderdaad ook geen volgorde gespecificeerd staan, dus ik denk dat de gekozen volgorde op de Wiki pagina slechts bedoeld is om duidelijk te maken waarover er gesproken wordt en niet direct om onderscheid te maken tussen terminals en non-terminals. Je moet tenslotte toch wat kiezen .

Ja dat was mn vermoeden ook, ik twijfelde alleen even omdat je normaliter, kijkende naar Item set 0, zou starten met non-terminal E en daarna non-terminal B, niet met terminal 0. Naja, ik ga het wel first come first served implementeren

Ik ben trouwens wel benieuwd wat er zo uitgebereid aan is dat je geen bestaande tools kan gebruiken?

Ik wil de parser o.a. gebruiken voor een tekst template taal voor een forum en een CMS, plus voor templates in mn generator. Hierdoor heb je dus te maken met text die er niet toe doet en text die daartussen staat maar er wel toe doet, bv urls of andere dingen. Om dat goed te tokenizen zit je eigenlijk tegen tokens aan te kijken die bestaan uit regular expressions, dus niet fixed ( en dan met 1 variabel token, de identifier ). Ik heb dus mbv de regular expression engine van .NET een lexical analyzer gebouwd die regular expressions matched (die ook op zich NFA's zijn in .NET) met de aangeboden brontext. Die zet ik om in tokens. Overlap kan worden uitgesloten of niet (dus een quoted string met text die matcht met tokens bv kun je uitsluiten). Ik heb geen parser generator voor .net gevonden die louter regex tokens vrat, veelal zijn het fixed text tokens, wat dus niet de bedoeling is.

De complete tokenizer is dan erg klein:

C++:

// walk all token definitions. Match all regular expressions with the string to 
// tokenize. All matches are tokenized into tokens belonging with the token  
// definition. All tokens are then added to the sorted list with the index as the key
foreach(ITokenDefinition tdCurrent in m_alTokenDefinitions)
{
    if(tdCurrent.TokenID==(int)BuildInTokenID.UntokenizedLiteralString)
    {
        // skip this token definition
        continue;
    }
    
    MatchCollection mcMatchesFound = 
                        tdCurrent.MatchingRegularExpression.Matches(m_sToTokenize);
    if(mcMatchesFound.Count > 0)
    {
        // found matches, convert the matches to tokens
        foreach(Match mMatchedSnippet in mcMatchesFound)
        {
            // create a token using the factory object. TokenID 
            // and RelatedTokenDefinition are already filled in.
            IToken toToAdd = tdCurrent.CreateTokenFromDefinition();
            toToAdd.LiteralMatchedTokenText = mMatchedSnippet.Value;
            toToAdd.StartIndexInInputStream = mMatchedSnippet.Index;
            // add to sorted list
            slTokensFound.Add(mMatchedSnippet.Index, toToAdd);
        }
    }
}

Hierna vang ik de non-tokenized text op in untokenizedliteralstring tokens en alle textdelen zijn getokenized. Wellicht niet de rapste lexical analyzer, maar wel een van de flexibelste

[Scare360]

Inderdaad een mooie oplossing.

[Verwijderd]

Nou hij werkt

Ter test heb ik de grammatica iets aangepast:
(1) E -> E * B
(2) E -> E + B
(3) E -> B
(4) B -> 2
(5) B -> 1

om de test wat interessanter te maken.

Ik heb een generator gebouwd voor de parsetables, de parsetables toont ie hier:


(beetje ingekort aan de rechterkant, was toch leeg)

Daarna heb ik een derived class gemaakt van mn LR(0) generalparser class. Deze derived class, een 'specializedparser', bevatte callbacks voor elke rule die in de grammatica zit. Deze callbacks, gebouwd mbv delegates, ontvangen alle righthandside stackitems die van de stack zijn gepopt in een list en kunnen, omdat ze weten dat de rule correct is, meteen beginnen met interpreteren ervan. In de test heb ik de rulecallbacks als een interpreter de boel laten uitrekenen.

Bij het parsen van de string: '2*1+2+1' kwam er '5' uit, hetgeen klopt. Hieronder een screenshot van de parsertester applicatie die een instance van de specialized parser aanroept en de string voert.



Error recovery zit er nog niet in, dat ga ik nu inbouwen, maar de LR(0) parser plus de parse-table generator werkt iig naar behoren Omdat de generator niet met een gui is uitgerust is het niet echt nuttig deze te releasen, wellicht maak ik er nog een artikeltje van voor codeproject.com.

[mbravenboer]

Hum, ziet er goed uit . Die GUI zou wellicht nog leuk zijn voor mensen die willen leren hoe LR parsing werkt. Het zou dan helemaal geinig zijn als je tijdens het parsen het proces ook kan volgen oid ... Hum ik draaf door .

Bij het parsen van de string: '2*1+2+1' kwam er '5' uit, hetgeen klopt.

Ik hoop dat je nog meer deed dan parsen .

[Verwijderd]

mbravenboer schreef op 09 December 2002 @ 15:40:
Hum, ziet er goed uit . Die GUI zou wellicht nog leuk zijn voor mensen die willen leren hoe LR parsing werkt. Het zou dan helemaal geinig zijn als je tijdens het parsen het proces ook kan volgen oid ... Hum ik draaf door .

Allereerst is het al geinig om te zien hoe de sets tot stand komen tijdens het tablegeneration process. Die output ik nu gewoon in de console. Hij is best rap, de gehele table genereert hij in een paar tienden van een seconde, maar het is ook maar een klein tabelletje en een paar states. Ik heb geen grammar invoer routine, en daardoor is een gui-tje wat lastig, want je wilt natuurlijk ook je eigen grammatica's ermee laten werken, geen idee of ik daar ooit tijd voor heb

[...]
Ik hoop dat je nog meer deed dan parsen .

heh, err, ja Wat vind je trouwens van mn lexical analyzer truukje hierboven? niet 1 van de efficienste wellicht maar wel makkelijk te bouwen

[mbravenboer]

Het probleem is dat ik ontzettend verwend ben. Ik werk altijd met SDF/SGLR en meer kan je eigenlijk niet wensen. Het support de volledige klasse van context-vrije grammatica's en lexicale syntax en context vrije syntax worden er gezamenlijk gedefinieerd. Het gebruik van Scannerless Generalized LR parsers zocht ervoor dat scanners en parsers samenwerken om zo ambiguiteiten ook samen op te kunnen lossen. Bij een strict gescheiden proces ontstaan er problemen: ambiguiteiten moeten opgelost worden door de scanner alleen. Bij SGLR zijn de scanner en parser samengevoegd en kan er dus met ambiguiteiten op lexicaal niveau worden gewerkt.

Als ik problemen zie, denk ik dus aan oplossingen in SGLR. Daar is alles goed op te lossen, dus zie ik niet zo snel een probleem .

Maar goed, als ik me even beperk tot klassieke lexicale analyse en parsers zie ik je probleem eerlijk gezegd nog steeds niet . In normale talen heb je toch ook bijvoorbeeld String literals waarin whitespace juist wel relevant is, een identifier geen identifier is en dergelijke? Als ik je goed begrijp zit hier bij jou ook het probleem? Of is er juist geen duidelijk scheiding tussen het gebied waarin identifiers wel en niet identifiers zijn?

Ik zie het probleem dus niet zo, maar dit ligt ongetwijfeld aan mijn beperkte werkervaring met deze tools. Kan je misschien een voorbeeldje van je template taal geven waaruit ik het probleem wel kan begrijpen?

De code op zich (zonder de noodzaak daarvan te begrijpen) lijkt mij een uitstekende stress-test voor de reguliere expressies implementatie van .NET . Ik begreep overigens dat die at runtime code genereert (optioneel?) voor de reguliere expressie, wat een acceptabele performance zou kunnen verklaren.

[Verwijderd]

Het probleem is o.a. dat tokens als emailadressen en urls, zijn niet mbv een normale string te beschrijven. Je zit dus aan een regular expression vast voor dit soort tokens. De generators die ik gezien heb voor .net ondersteunden dit niet. Het resultaat hiervan is dan dat je handmatig tekst moet gaan zitten nascannen, en dat is vervelend, want kan tot gevolg hebben dat je tokens die gescanned zijn meeneemt, of overslaat of wat dan ook. Een regular expression based tokenizer is dan dus de oplossing.

Ik heb bv nu deze regular expression voor urls en emailaddresses:

code:

URL: (http://www.|http://|www.)([\w-]+\.)+[\w-]+(/[\w-./?%&~=]*)?
Emailadres: \w+([-+.]\w+)*@\w+([-.]\w+)*\.\w+([-.]\w+)*

Deze regular expressions zorgen ervoor dat urls en emailadressen perfect worden gescanned en getokenized, zodat mn general LR(0) parser ze mee kan nemen met de parsing van de inputstream.

Verder heb je soms wel en soms niet 'identifiers', bv bij UBB heb je geen identifiers, alle text die geen token is, is platte tekst die je 1:1 moet overnemen. Regular expressions hebben verder het voordeel dat je bv een token kunt opnemen voor een quoted string:

code:

(\".*?\")

en je dus geen problemen hebt met whitespace in een string etc. Dit is ook anders op te lossen natuurlijk, met losse tokens voor de quotes en losse tekst, maar dat hoeft dus niet.

Wanneer heb je btw de lexical analyzer nodig voor ambiguiteitsproblemen? Ik kan daar 1 2 3 geen voorbeeld van bedenken.

De gecompileerde regular expression definities zijn idd supersnel. Wanneer ik de parsing van een redelijk grote file nog eens uitvoer is hij beduidend sneller klaar. Nadeel is dat de NFA's niet threadsafe zijn (logisch) en je dus bij bv een website die een stukje tekst moet parsen (forum bv) je toch vast zit aan het telkens opnieuw instantieren van de regular expressions.

[ Voor 13% gewijzigd door Verwijderd op 09-12-2002 16:54 ]

[mbravenboer]

Otis: De generators die ik gezien heb voor .net ondersteunden dit niet.

Ah ok... Dat is wel matig zou je zeggen, want zelfs voor bijvoorbeeld float literals heb je toch al vrij vergelijkbare kracht nodig? Het lijkt mij dat er in lexical analyzers die al wat langer op de markt zijn niet echt een probleem is, dus laten we hopen dat de .NET tools zichzelf ook verbeteren . In SDF is het natuurlijk ook geen enkel probleem, maar dat is niet zo verwonderlijk ...

Verder heb je soms wel en soms niet 'identifiers', bv bij UBB heb je geen identifiers, alle text die geen token is, is platte tekst die je 1:1 moet overnemen.

Is dat niet precies ook de functie van een String literal? Zulke functionaliteit zou je toch ook verwachten in een beetje bruikbaar tool ...

Overigens werkt je oplossing natuurlijk fantastisch, dus daar is zeker geen commentaar op te leveren .

Wanneer heb je btw de lexical analyzer nodig voor ambiguiteitsproblemen? Ik kan daar 1 2 3 geen voorbeeld van bedenken.

In de meeste programmeertalen is er ook geen probleem omdat ze via extra regels ambiguiteiten uitsluiten. Hierdoor kan code worden afgewezen terwijl het in principe best kan voldoen aan de grammatica. Neem bijvoorbeeld de expressie a--b. Dit zou aan een grammatica kunnen voldoen als je het zo ziet: a - ( - b ). Vrij merkwaardig natuurlijk, maar het kan wel. Er dus een mogelijke parse-tree voor deze string maar toch staat (bijvoorbeeld) Java dit niet toe: -- wordt de lexical analyzer zonder verdere discussie als het token van de -- operator bestempeld (zonder dus kennis te hebben van de context waarin dit token voorkomt). Hierdoor is a -- b geen geldige expressie meer.

Met SGLR kan dit anders: omdat de scanner en parser gecombineerd zijn kunnen ook andere mogelijkheden nagegaan worden. In principe is een expressie als a--b dus toegestaan als je met een SGLR parser gaat parsen. Omdat dit echter niet aan de standaard voldoet, moet je dit toch afwijzen. Hiervoor (onder andere) zijn er disambiguation filters. Via een follow restriction kan je bijvoorbeeld aangeven dat een "-" nooit mag worden gevolgd door een "-". Hierdoor kan een "--" dus alleen een "--" zijn.

Nu is dit natuurlijk een beetje een raar voorbeeld omdat je toch wel kan aanvoeren dat het goed is dat -- wordt afgewezen. Ik kon zo echter geen eenvoudig voorbeeld bedenken wat makkelijk uit te leggen is en goed in bestaande en bekende talen past. Vrijwel allemaal zijn ze zo gemaakt dat lexical ambiguiteiten ook direct vreemd overkomende constructies zijn.

Er bestaan echter wel degelijk goede voorbeelden .

Stel dat je bijvoorbeeld SQL gaat embedden in een taal als Java of Cobol. Je hebt dan een probleem met de keywords van Java of Cobol. In deze talen mogen keywords niet gebruikt worden als identifier. Identifiers in embedded SQL die een keyword zijn in omringende taal zullen door de lexical analyzer nu echter direct worden afgewezen als identifier, terwijl ze in SQL best een identifier kunnen zijn.

Vanwege scannerless parsing en de ondersteuning van de volledige klasse van context-vrije grammatica's is SDF/SGLR subliem in het combineren van talen. Re-engineering, reverse engineering en language prototyping vereisen dit eigenlijk en SDF/SGLR (of een gelijkwaardig alternatief) is daarom in vele gevallen daar eigenlijk de beste oplossing. Voor gewone, veel gebruikte programmeertalen kan je natuurlijk wel discussieren of je voor het parsen SDF/SGLR moet gaan gebruiken of toch echt moet kiezen voor een klassieke parsing techniek met een zeer goede performance.

Veel meer uitleg en voorbeelden kan je lezen in het paper "Disambiguation Filters for Scannerless Generalized LR Parsers". Deze filters worden bijvoorbeeld ook gebruikt om de prioriteit en associativiteit van expressies te regelen. Dit werkt erg fraai: in mijn Java grammatica kan je in de Expressies module een voorbeeld vinden. Het artikel is redelijk toegankelijk als je een klein beetje in de grammatica's en parsers zit, dus het is voor jou denk ik zeer goed te volgen.

[Alarmnummer]

[heeft niet het hele topic doorgelezen mode[
SableCC komt binnenkort trouwens ook met een c# parser generator. De schrijver is weer bezig met ontwikkeling en het gaat eenvoudiger worden om een andere backend erachter te plaatsen zodat ook andere talen ermee gegenereerd kunnen worden. En verder is er ook al een c# versie van ANTLR.

[Verwijderd]

mbravenboer schreef op 09 December 2002 @ 18:34:
[...]
Ah ok... Dat is wel matig zou je zeggen, want zelfs voor bijvoorbeeld float literals heb je toch al vrij vergelijkbare kracht nodig? Het lijkt mij dat er in lexical analyzers die al wat langer op de markt zijn niet echt een probleem is, dus laten we hopen dat de .NET tools zichzelf ook verbeteren . In SDF is het natuurlijk ook geen enkel probleem, maar dat is niet zo verwonderlijk ...

Ik kon geen goede vinden die flexibel met tokens om kon gaan. Er zijn wel een aantal parser generators maar je bent er niet natuurlijk, wanneer je een parser hebt, je moet ook code genereren/het geparste interpreteren. Veel waren gewoon te wazig daarvoor.

[...]
In de meeste programmeertalen is er ook geen probleem omdat ze via extra regels ambiguiteiten uitsluiten. Hierdoor kan code worden afgewezen terwijl het in principe best kan voldoen aan de grammatica. Neem bijvoorbeeld de expressie a--b. Dit zou aan een grammatica kunnen voldoen als je het zo ziet: a - ( - b ). Vrij merkwaardig natuurlijk, maar het kan wel. Er dus een mogelijke parse-tree voor deze string maar toch staat (bijvoorbeeld) Java dit niet toe: -- wordt de lexical analyzer zonder verdere discussie als het token van de -- operator bestempeld (zonder dus kennis te hebben van de context waarin dit token voorkomt). Hierdoor is a -- b geen geldige expressie meer.

Net ff geprobeerd, in C# ook niet.

Wel een amazing voorbeeld, want je zou echt verwachten dat het correct zou zijn. (nu is a - -b natuurlijk gelijk aan a+b, dus een gemiddelde programmeur zou hier nooit over vallen, maar toch) Wat me wel fascineerde was het volgende:

Met SGLR kan dit anders: omdat de scanner en parser gecombineerd zijn kunnen ook andere mogelijkheden nagegaan worden. In principe is een expressie als a--b dus toegestaan als je met een SGLR parser gaat parsen. Omdat dit echter niet aan de standaard voldoet, moet je dit toch afwijzen. Hiervoor (onder andere) zijn er disambiguation filters. Via een follow restriction kan je bijvoorbeeld aangeven dat een "-" nooit mag worden gevolgd door een "-". Hierdoor kan een "--" dus alleen een "--" zijn.

Maar... dan zijn de gevolgen dus gelijk, terwijl je met SGLR toch zou verwachten dat hij de expressie WEL zou goedkeuren . Maar ik begrijp wat je bedoelt.

[goed verhaal verder]

Bedankt voor de heldere uitleg! Ik zal zien of ik dat paper te pakken kan krijgen (en ik hoop dat er niet teveel alpha en beta's in staan, want je vraagt je soms af of ze uberhaupt wel willen dat iemand het begrijpt )

[mbravenboer]

Otis: Maar... dan zijn de gevolgen dus gelijk, terwijl je met SGLR toch zou verwachten dat hij de expressie WEL zou goedkeuren . Maar ik begrijp wat je bedoelt.

Hehe . Eerlijk gezegd keurde mijn grammatica voor Java het eerst ook wel goed. Ik had dit conflict met de standaard over het hoofd gezien. Ik ging toen echter de gigantische testsuite van Jikes (die Jacks heet) toepassen en toen vond ik deze fout. Via het toevoegen van een extra regel kan ik hetzelfde gedrag bereiken als opgelegd wordt in de language reference.

Ik zal zien of ik dat paper te pakken kan krijgen (en ik hoop dat er niet teveel alpha en beta's in staan, want je vraagt je soms af of ze uberhaupt wel willen dat iemand het begrijpt )

Hum . Dit paper valt erg mee. Als je naar papers over Stratego/SDF/SGLR kijkt staan alleen papers over semantiek vol met logica. Gelukkig gaan de meeste papers echter niet over semantiek .

Hier staat het artikel:
http://www.stratego-langu...rlessGeneralizedLRParsers