Buffer voor een recursieve backtracking parser?

[ValHallASW]

Op het moment ben ik bezig met het schrijven met een parser voor wikitext (in dit geval de mediawikiversie. Ja, daar bestaat al een parser voor, maar die is ontworpen door een stel techies die wel regexps konden maar verder niets van formele talen wisten. Do the maths.). Dit is dan ook geen simpele taal om systematischer te parsen - ik heb er dan ook voor gekozen een parser van de grond af te bouwen. Wellicht niet de meest efficiente methode (maar dat geldt ook voor het in python bouwen), maar ik ben niet veel verder gekomen dan de eerste hoofdstukken van the dragon book

De structuur is op het moment als volgt:
* Een lexer die een stroom van tokens uitstuurt die voor de parser logisch zijn
* een buffered reader die deze stroom buffert, zodat het mogelijk is te backtracken en te peek()en
* een recursive backtracking parser die uit deze stroom leest

Het recursieve van deze parser levert echter een probleem op: hoe kan ik de reader laten backtracken in een recursieve aanroep. Stel ik heb de volgende tekst:

[[link|met {{net-geen-template} in de beschrijving]]

wanneer openende {'s worden gevonden dan probeert de parser 'm eerst als parameter ( {{{1}}} ) te parsen, vervolgens als template( {{template}} ), en als laatste als tekst. Voordat de tekst hier gekozen wordt wordt dus twee keer een backtrackactie uitgevoerd - waarbij de input stream natuurlijk ook een eind terug moet.
De reader heeft echter nog een functie die nodig is: het toevoegen van tokens aan de stroom. Neem als voorbeeld:

[[plaatje|met in de beschrijving een [[link]]]]

De vier ]]]]'s worden in eerste instantie als één token gezien (met lengte 4), geparsed als een wikilink, waarna een token met lengte 2 weer de stroom in wordt gestuurd. Het toevoegen van tokens geeft een extra 'dimensie' aan het probleem, omdat deze bij een eventuele backtrack weer weggegooid moeten worden.

Om zo'n de reader recursive-compatible te maken heb ik een paar manieren bedacht, maar die hebben allemaal een aantal nadelen:

* een nieuwe reader maken die de oude inleest heeft twee nadelen. De peek() leest een extra token in (maar dat is vrij makkelijk te fixxen door van de parent ook de peek() te gebruiken, mits die bestaat) - maar belangrijker: tokens die zijn toegevoegd worden niet ook aan de parent toegevoegd, waardoor de hierboven beschreven ]]'s nooit aankomen bij de parser van de buitenste wikilink

* bijhouden waar een bepaalde parser begonnen is met lezen. Dit lost het peek() en het probleem van het toevoegen van ]]'s op - maar hoe gooi je die ooit weer uit de stream? Op het onderste niveau is dat simpel: een backup houden van de input stream en die uitlezen in plaats van je buffer met toegevoegde tokens, maar hoe kom je te weten op welk punt in je buffer die toegevoegde tekens zijn gebleven, of hoever je buffer is opgeschoven?

* voor iedere parser een eigen buffer bijhouden. In feite is dit optie 1, maar dan zonder de peek()-problemen. Wel heb je hier óf problemen met het toevoegen van tokens, óf met het weghalen van tokens.


Doe ik te moeilijk, moet ik 'gewoon' een parser generator gebruiken (welke dan?) of heeft iemand gewoon een goed idee?

Source > http://svn.wikimedia.org/...pedia/trunk/pywikiparser/ (Lexer.py, BufferedReader.py en Parser.py; in ObjectTree/ staat een simpele object tree omdat ik niet tevreden was met de bestaande )

[Laurens-R]

Wat voor datastructure gebruik je?

Een tree lijkt me hier nogal voorhanden liggen

Kwestie van bij elk '[' een nieuwe child branche te maken.

Als je een ']' tegenkomt weer 1 level omhoog gaan in je tree (dus weer terug van child naar parent).

Natuurlijk ook het noodzakelijk parsen tussen de brackets, maar die tree zou je wel door de basis van het parsen moeten helpen.

Zodoende kan je later via de bekende tree traversal algoritmen de tree doorlopen mbv recursieve functies.

meer info over trees: http://en.wikipedia.org/wiki/Tree_%28data_structure%29

Aangezien Python een object georienteerde taal is, zou het moeten kunnen. Maar eerlijk gezegd heb ik nog nooit wat gedaan in Python (alleen in VB, PHP, C#, C(++) en Java)

[ Voor 52% gewijzigd door Laurens-R op 31-07-2007 23:35 ]

[ValHallASW]

Het kan zijn dat ik je niet goed begrijp, maar als ik het goed begrijp dan is je vraag hoe de lexer de data aanlevert. Dat is op dit moment een simpele array van tokens.
Een tree zou kunnen, ware het niet dat een tekst als

[[blablabla\n\n

ook legaal is, maar geen wikilink is: dit moet gewoon als tekst worden gezien. Bij een boomstructuur is dat lastig te implementeren.

De uitvoer van de parser is wel een boomstructuur (a la <wikilink><title>titel</title><parameter><template><title>template:test</title></template></parameter></wikilink>)


En ja, trees in python kunnen heel goed

[Laurens-R]

Ja ik bedoelde idd de manier waarop de elementen in het geheugen stonden

mmmm ja dan zou ik toch naar regex gaan kijken .... maar jah ... als ik het goed heb gelezen vermeed je die liever toch?

Ik denk dat het wel mogelijk is met een tree, je moet alleen op een andere manier parsen wat een "node" specificeert (dus niet genoegen nemen met alleen een '[' maar een bepaald patroon... maar dat klinkt al weer heel erg als een soort van eigen regex implementatie )

Zelf zou ik die tree er wel in houden voor de opslag van wiki elementen (voor zover nodig), omdat me dit gewoon redelijk gemakkelijk lijkt voor eventuele toekomstige uitbreiding en voor je output.

edit: er schiet me iets te binnen in de vorm van een stack oplossing, maar ik moet het nog even uitdokteren... het is een vaag vermoeden nog op dit moment

[ Voor 10% gewijzigd door Laurens-R op 31-07-2007 23:59 ]

[Verwijderd]

ValHallASW schreef op dinsdag 31 juli 2007 @ 23:04:
[[plaatje|met in de beschrijving een [[link]]]]

Is in zo'n geval een stack based parser niet handiger?. '[' gevonden, zoek de bijbehorende ']' (op 't zelfde niveau), en parse de tekst tussen die markers. Idem voor de tekst binnen markers die net op de stack gezet zijn, etc.
Lijkt me een wat praktischer benadering dan eerst ']]]]' als marker te zien, en van daaraf te gaan backtracken. Want op dat moment heb je eigenlijk al je levels langsgelopen (je weet dat 4 blokhaken het einde aanduiden), dus het tussenliggende stuk kun je net zo goed dan ook meteen al verwerken.

[Soultaker]

Het opsplitsen van tokens is waanzin. Het hele punt van tokenizen is dat je grammatica gedefinieert is over tokens en dat je de invoer dus inleest als serie tokens; die moet je dan niet meer gaan veranderen of opsplitsen. Kortom: je moet elke losse '[' en ']' als een afzonderlijke token zien, en daar in je grammatica rekening mee houden:

code:

parameter :- '[' '[' '[' value ']' ']' ']'
link :- '[' [' wikiword ']' ']'
.. etc ..

Je het dan wat ambiguïteit in je grammatica, maar dat geeft niet als je met een lookahead gaat parsen (wat je toch gaat doen).

Overigens vraag ik me af of er veel te tokenizen valt, als alle tokens effectief één karakter zijn. Sowieso is tokenizen (aka scannen of lexen) min of meer een optimalisatie, die niet essentieel is voor het proces. Traditioneel tokenize je om met een beperkte look-ahead (in het ideale geval 1) te kunnen parsen ook al delen bepaalde bepaalde tokens eenzelfde prefix. (De tokenizer kan dat wél efficiënt doen, omdat 'ie alleen tokens hoeft te herkennen en nog geen grammatica hoeft te volgen.) Als de uitvoer van je tokenizer moeilijker te parsen is dan de oorspronkelijke invoer doe je dus iets verkeerd.

Sowieso zou je moeten weten dat reguliere expressies geen matching braces kunnen parsen, dus daar los je het ook niet mee op. @Afterlife: is een stack based parser niet gewoon een soort LR-parser?

[ Voor 3% gewijzigd door Soultaker op 01-08-2007 00:56 ]

[ValHallASW]

Dat kan in principe wel, maar het is lastig om op een 'domme' manier te bepalen hoeveel open- en sluithaken er zijn geweest. Neem bijvoorbeeld:

[[plaatje|met {{template|parameter met ]]}}]]

wat geparsed moet worden als

<wikilink>
  <title>plaatje</title>
  <parameter>
    <template>
      <title>template</title>
      <parameter>met ]]</parameter>
    </template>
  </parameter>
</wikilink>

en niet als:

<wikilink>
  <title>plaatje</title>
  <parameter>{{template|parameter met</parameter>
</wikilink>
}}]]

maar als je daar ook nog een goed idee voor hebt

@Soultaker:
Hmm. Good point. Oftewel voor die tekens steeds een token maken voor één teken maar wel de tokens voor tekst, whitespace, nieuwe paragrafen, wikitable ( {| ) etc, behouden? Dat zou inderdaad betekenen dat er niets meer teruggegooid hoeft te worden en dat de stream bijhouden simpel wordt. En twee keer een expect(SQRE_OPEN) ipv checken of 'ie wel uit twee chars bestaat maakt natuurlijk ook geen ruk uit

[ Voor 25% gewijzigd door ValHallASW op 01-08-2007 01:05 ]

[Verwijderd]

@Afterlife: is een stack based parser niet gewoon een soort LR-parser?

Natuurlijk is 't dat. Had niet goed gelezen en werd afgeleid door de regex-referenties (die zijn per definitie plat en niet stack based of recursief). My bad, sorry.

[Infinitive]

Schrijf eerst maar eens een context-vrije grammatica voor wikitext en ga daarna maar eens nadenken wat voor parser je wilt gebruiken. Zaken als gebalanceerde brackets kan je prima uitdrukken in een context-vrije grammatica. Dan zul je ook zien wat nuttige tokens gaan zijn: misschien wel elk character een losse token, of misschien wel complete woorden en leestekens als tokens.