[PHP] Stack-based Parsing

Pagina: 1
Acties:
  • 235 views sinds 30-01-2008
  • Reageer

Onderwerpen


Verwijderd

Topicstarter
K was op zoek naar info over Stack-based Parsen en dit is wat ik hier op het forum vond.
Een stack is een LIFO collectie. LIFO staat voor 'Last In First Out'.

Een andere vorm van collecties is een FIFO stucture (First In First Out), bijvoorbeeld Queues.

Een voorbeeld van een stack is een array in PHP waar je alleen een item afhaalt als dat als laatste is toegevoegd.

Met stack-based parsen wordt dan ook een manier van parsen bedoeld waarbij je gebruik maakt van een stack. Doorgaans wordt het subject (de string) van begin tot eind doorlopen en worden in de stack states opgeslagen.
Wanneer je bijvoorbeeld een openings- tegenkomt sla je die op in de stack (met een 'push' method). Hierna kun je natuurlijk alleen nieuwe openingstags tegenkomen, of een sluitings- tag. Iedere openingstag push je weer op de stack en bij een sluitingstag haal je weer een element van de stack af (en als het goed is, is dat altijd het bijbehorende element, je haalt ze weer in omgekeerde volgorde eraf). Een item van de stack halen doe je met een 'pop' method.
Heb je heel je string doorlopen, dan moet je stack weer leeg zijn.

De loop is dan de engine van je parser en de stack gebruik je om de state in op te slaan.
Je kunt zelf een LIFO stucture ontwerpen, maar je kunt ook gewoon een PHP array nemen en je bij het gebruik daarvan aan de regels houden die bij
een stack horen.
dus ben ik aan de gang gegaan, maar al vrij snel liep ik vast :X
ik stoote op de vraag : Hoe 'parse' je door je string heen?
ik had het al geprobeerd met preg_match maar dan krijg je alleen de eerste en heb je dus een probleempie als je er meerdere matches in je string heb zitten.

en hoe houd je je parsed data bij?!?
Zit er al een tijdje mee te dubben. heb ook al op googel gezocht en heb door de source van yapter gespit, maar daar werd ik niet veel wijzer van. ik begin er een beetje gek van te worden. 8)7

hopelijk kunnen jullie me helpen

Verwijderd

Kijk eens naar preg_split().

  • thomaske
  • Registratie: Juni 2000
  • Laatst online: 17-09 07:55

thomaske

» » » » » »

ik had het al geprobeerd met preg_match maar dan krijg je alleen de eerste en heb je dus een probleempie als je er meerdere matches in je string heb zitten
preg_match_all() ??

Brusselmans: "Continuïteit bestaat niet, tenzij in zinloze vorm. Iets wat continu is, is obsessief, dus ziekelijk, dus oninteressant, dus zinloos."


  • Janoz
  • Registratie: Oktober 2000
  • Laatst online: 16-09 09:15

Janoz

Moderator Devschuur®

!litemod

Ik weet niet precies wat je wilt parsen, maar vaak kun je gewoon met findfirst oid werken. Zeker waneer je alleen [ ] tags verwerkt kun je gewoon zoeken naar de eerste [ en kijken of het een bekende tag is. probeer het gebruik van reguliere expressies zoveel mogenlijk te vermijden, want in dat geval ben je redelijk dubbelop bezig (imho). Veel dingen kun je heel simpel zonder een regexp doen en is die regexp alleen maar overkill.

Ik weet niet in hoeverre je kennis reikt, maar bij iets ingewikkelere zaken kun je het beste een gramatica opstellen. Hieruit kun je precies de regels achterhalen voor het parsen.

Ken Thompson's famous line from V6 UNIX is equaly applicable to this post:
'You are not expected to understand this'


  • EfBe
  • Registratie: Januari 2000
  • Niet online
eerst tokens maken van je string, dus via regular expressions tokens matchen. Daarna die tokens parsen. Dit kun je doen met bv een LR(0) parser, of een LR(1) parser. Zie bv http://www.wikipedia.org/wiki/LR(0)_parser voor hoe je een LR(0) parser bouwt. Het punt is niet dat je tokens gaat herkennen, maar dat je je tokenstream toetst aan de grammatica die je hebt opgesteld. Het is geen simpele materie, dus maak je borst maar nat :)

[ Voor 3% gewijzigd door EfBe op 19-12-2002 15:50 ]

Creator of: LLBLGen Pro | Camera mods for games
Photography portfolio: https://fransbouma.com


  • brammetje
  • Registratie: Oktober 2000
  • Laatst online: 12-01 11:31
als je php gebruikt is het nuttig dit eens door te kijken. De bron is ook beschikbaar.

  • tomato
  • Registratie: November 1999
  • Niet online
Ik denk dat het opstellen van een grammatica iets te hoog gegrepen is voor een beginner en daarnaast helemaal niet nodig is voor wat hij wil.

Ga inderdaad te werk zoals Janoz voorstelt, ipv van een findfirst method kun je natuurlijk ook zelf teken voor teken de string aflopen en kijken of je een character tegenkomt waar je iets mee kunt. Regular expressions zou ik hierbij inderdaad niet gebruiken. Als je goed doorhebt hoe het werkt en je wilt ingewikkelder dingen doen kun je altijd kijken of je makkelijke truckjes ziet waarvoor je een regex kunt gebruiken.

Een simpele opzet in PHP:
PHP:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
$text = 'wat je wilt parsen';

$open_character = '[';
$close_character = ']';

$index = 0;

do {

    if ($text[$index] == $open_character) {

        // We zijn binnen een nieuwe tag beland
        // push() de stack

    } else if ($text[$index] == $close_character) {

        // We zijn nu de laatste tag weer uit
        // pop() de stack

    }

} while (++$index < strlen($text));


Dit is natuurlijk een wat versimpelde uitvoering, het gaat uit van genestte '[...]' structures, waarschijnlijk heb je langere open/close tokens.

Je kunt dit gemakkelijk uitbreiden met support voor het escapen van '[' en ']' dmv bijvoorbeeld een '\' teken en heel veel andere leuke dingen.

[ Voor 12% gewijzigd door tomato op 19-12-2002 16:36 . Reden: Verduidelijking ]


  • EfBe
  • Registratie: Januari 2000
  • Niet online
tomato: als er geen regels zijn dan kun je net zo goed bv '[' vervangen door '<' en ']' vervangen door '>', dat als XML inlezen in een XML DOM, daar een XSL tegenaanhouden en klaar. Echter de ellende begint bv wanneer je binnen bepaalde tags geen andere tags toestaat, bv geen quote tags binnen code tags, ik noem maar iets. Dan verzand je al snel in 'wat heb ik gezien' (oftewel in welke productionrule zit ik) en welke regels horen daarbij. Dat zal snel erg complex worden.

[ Voor 9% gewijzigd door EfBe op 19-12-2002 16:51 ]

Creator of: LLBLGen Pro | Camera mods for games
Photography portfolio: https://fransbouma.com


  • tomato
  • Registratie: November 1999
  • Niet online
EfBe schreef op 19 December 2002 @ 16:50:
tomato: als er geen regels zijn dan kun je net zo goed bv '[' vervangen door '<' en ']' vervangen door '>', dat als XML inlezen in een XML DOM, daar een XSL tegenaanhouden en klaar. Echter de ellende begint bv wanneer je binnen bepaalde tags geen andere tags toestaat, bv geen quote tags binnen code tags, ik noem maar iets. Dan verzand je al snel in 'wat heb ik gezien' (oftewel in welke productionrule zit ik) en welke regels horen daarbij. Dat zal snel erg complex worden.
Dat is waar, maar ik weet niet of het nou zo'n goed idee is direct met grammatica's te gaan gooien naar iemand die nog niet weet hoe hij zelf met een stack genestte structuren kan parseren.

Wat jij noemt is inderdaad vrij triviaal op te lossen met productieregels, maar ook met een stackparser is dat best te doen als je het jezelf niet te moeilijk maakt.

  • MisterData
  • Registratie: September 2001
  • Laatst online: 29-08 20:29
Ben je een (stackbased) template parser aan het schrijven? Heb ik ook es ooit gedaan (een maand of twee geleden denk ik :?) Bekijk hier een test-scherm, en mogelijke template-files :) Mijn aanpak:

• Array opbouwen dmv strtok, alle gewone tekst scheiden van tags
• Loopen door die array, met preg_match kijken of een stuk een tag is of een stuk tekst, en vervolgens een array elements en een array elementTypes bouwen.
• Vervolgens loopen door die array en met een stack checken of elke sluittag z'n begintag matched enz. :) 800 regels code ongeveer :7

[ Voor 43% gewijzigd door MisterData op 19-12-2002 17:34 ]


  • Nielsz
  • Registratie: Maart 2001
  • Niet online
MisterData schreef op 19 December 2002 @ 17:33:
Ben je een (stackbased) template parser aan het schrijven? Heb ik ook es ooit gedaan (een maand of twee geleden denk ik :?) Bekijk hier een test-scherm, en mogelijke template-files :) Mijn aanpak:

• Array opbouwen dmv strtok, alle gewone tekst scheiden van tags
• Loopen door die array, met preg_match kijken of een stuk een tag is of een stuk tekst, en vervolgens een array elements en een array elementTypes bouwen.
• Vervolgens loopen door die array en met een stack checken of elke sluittag z'n begintag matched enz. :) 800 regels code ongeveer :7
Ik heb een stackbased UBBparser geschreven :) Ongeveer dezelfde aanpak.
http://nielsz.servicez.org/parser/index.php
700 regels geloof ik :7

Verwijderd

Topicstarter
k heb het geprobeerd met preg_match_all() :
PHP:
1
2
3
4
5
6
7
8
#open tml file 
$filename='templates/main.tml'; 
$fp = fopen($filename,'r'); 
$tml = fread($fp, filesize($filename)); 
fclose ($fp); 
#start arsing 
$grammer = "/\\[(BLOCK|END)( [A-Za-z0-9_.\/]+)( (LOOP|IF_FOUND|INCLUDE|RE_USE) ([A-Za-z0-9_.\/]+))?]/";
preg_match_all($grammer, $tml, $backRef);

geeft :
PHP:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
Array
(
    [0] => Array
        (
            [0] => [BLOCK Main]
            [1] => [BLOCK news LOOP 3]
            [2] => [BLOCK msgHeader]
            [3] => [END msgHeader]
            [4] => [BLOCK msgBody INCLUDE newBody.tml]
            [5] => [END msgBody]
            [6] => [BLOCK msgFooter]
            [7] => [BLOCK 2emsgFooter]
            [8] => [END msgFooter]
            [9] => [END msgFooter]
            [10] => [END news]
            [11] => [BLOCK footer IF_FOUND foot]
            [12] => [END footer]
        )

    [1] => Array
        (
            [0] => BLOCK
            [1] => BLOCK
            [2] => BLOCK
            [3] => END
            [4] => BLOCK
            [5] => END
            [6] => BLOCK
            [7] => BLOCK
            [8] => END
            [9] => END
            [10] => END
            [11] => BLOCK
            [12] => END
        )

    [2] => Array
        (
            [0] =>  Main
            [1] =>  news
            [2] =>  msgHeader
            [3] =>  msgHeader
            [4] =>  msgBody
            [5] =>  msgBody
            [6] =>  msgFooter
            [7] =>  2emsgFooter
            [8] =>  msgFooter
            [9] =>  msgFooter
            [10] =>  news
            [11] =>  footer
            [12] =>  footer
        )

    [3] => Array
        (
            [0] => 
            [1] =>  LOOP 3
            [2] => 
            [3] => 
            [4] =>  INCLUDE newBody.tml
            [5] => 
            [6] => 
            [7] => 
            [8] => 
            [9] => 
            [10] => 
            [11] =>  IF_FOUND foot
            [12] => 
        )

    [4] => Array
        (
            [0] => 
            [1] => LOOP
            [2] => 
            [3] => 
            [4] => INCLUDE
            [5] => 
            [6] => 
            [7] => 
            [8] => 
            [9] => 
            [10] => 
            [11] => IF_FOUND
            [12] => 
        )

    [5] => Array
        (
            [0] => 
            [1] => 3
            [2] => 
            [3] => 
            [4] => newBody.tml
            [5] => 
            [6] => 
            [7] => 
            [8] => 
            [9] => 
            [10] => 
            [11] => foot
            [12] => 
        )

)

het leek me dat ik daar wel wat mee kan 8)
heeft volgens mij ongeveer hetzelfde ffect als strtok
want daarmee heb ik het volgende gedaan :
PHP:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
$iBlock = sizeof($backRef[1]);
$blocks=array();
$error=array();
while($i<$iBlock) {
    switch($backRef[1][$i]) {
        case 'BLOCK' :
            array_push($blocks,$backRef[2][$i]);
            $error[sizeof($error)] = 'pushed '.$backRef[2][$i];
        break;
        case 'END' :
            if($backRef[2][$i]==$blocks[sizeof($blocks)-1]) {
                switch ($backRef[4][$i-1]) {
                    case 'LOOP' :
                        
                        for($h=0;$h<$backRef[5][$i-1];$h++) {
                        
                        }
                    break;
                }
                $error[sizeof($error)] = 'parsed '.$backRef[2][$i];
                array_pop($blocks);
            }
                else {
                    $error[sizeof($error)] = $blocks[sizeof($blocks)-1].' wasn\'t closed properly.';
                    array_pop($blocks);
                }
            #de cases gaan ver met de vars die in de grammer worden opgezocht
        break;
    }
    $i++;
}

$blocks is dan mijn stack. en van hieruit kan ik den ik wel wat maken lijkt me.
ik vraag me alleen af, als het af is en netjes in een class staat en er een debug mode inzet etc., of het niet een enorme parsetime veroorzaakt?

  • .oisyn
  • Registratie: September 2000
  • Laatst online: 17-09 14:05

.oisyn

Moderator Devschuur®

Demotivational Speaker

EfBe schreef op 19 December 2002 @ 15:48:
eerst tokens maken van je string, dus via regular expressions tokens matchen. Daarna die tokens parsen. Dit kun je doen met bv een LR(0) parser, of een LR(1) parser. Zie bv http://www.wikipedia.org/wiki/LR(0)_parser voor hoe je een LR(0) parser bouwt. Het punt is niet dat je tokens gaat herkennen, maar dat je je tokenstream toetst aan de grammatica die je hebt opgesteld. Het is geen simpele materie, dus maak je borst maar nat :)


Voor een parser als dit is het een beetje onzin om een grammatica ervoor op te stellen. Je hebt namelijk een open-tag en een sluit-tag, die bovendien moeten matchen. Als je een grammatica opstelt bouw je slechts een superset van wat je wilt hebben; met de parser kun je niet controleren of de open en close tag bij elkaar horen, dat moet je dan weer in de semantic checker gaan doen. Dan kun je het beste gewoon die 2 dingen combineren en met de hand een parser bouwen, wat in dit geval echt totaal niet veel werk is

Give a man a game and he'll have fun for a day. Teach a man to make games and he'll never have fun again.


Verwijderd

Topicstarter
oke, mijn aanpak werkte dus niet, kom in nergens omdat ik het stuk tussen de open en close tags niet heb opgevraagd, als ik dat dan ook nog eens appart moet gaan doen, wordt de laadt tijd te groot.
dus ga ik maar is kijken naar doe strtok
guess you where right MrData. :)

  • EfBe
  • Registratie: Januari 2000
  • Niet online
.oisyn schreef op 19 December 2002 @ 19:50:
Voor een parser als dit is het een beetje onzin om een grammatica ervoor op te stellen. Je hebt namelijk een open-tag en een sluit-tag, die bovendien moeten matchen. Als je een grammatica opstelt bouw je slechts een superset van wat je wilt hebben; met de parser kun je niet controleren of de open en close tag bij elkaar horen, dat moet je dan weer in de semantic checker gaan doen.
Wellicht praten we over verschillende dingen :) Maar je hebt een lexical analyzer die tokens bakt en een parser die tokens scant om productieregels te verifieren. Wat ik parser noem noem jij semantic checker :)
Dan kun je het beste gewoon die 2 dingen combineren en met de hand een parser bouwen, wat in dit geval echt totaal niet veel werk is
In het geval van simpele tags als bold etc niet nee. Maar 'even' een parser met de hand maken voor een resiment uitzonderingen is niet 1 2 3 gedaan. Bv de UBB die op GoT wordt gebruikt bevat al aardig wat uitzonderingen, daar schrijf je niet 1 2 3 een 'parser' voor met de hand. Ik bedoel: stel je wilt binnen een bold tag geen quotes en binnen code geen quotes, maar 1 nestlevel diep quotetexts, etc. :) Dat wordt gauw complex :) (Als je de UBB syntax uitschrijft in BNF zit je zonder smileys al rond de 70 productieregels, dat doe je niet 1 2 3 met de hand)

Creator of: LLBLGen Pro | Camera mods for games
Photography portfolio: https://fransbouma.com


  • MisterData
  • Registratie: September 2001
  • Laatst online: 29-08 20:29
Nielsz schreef op 19 december 2002 @ 17:56:
[...]

Ik heb een stackbased UBBparser geschreven :) Ongeveer dezelfde aanpak.
http://nielsz.servicez.org/parser/index.php
700 regels geloof ik :7
Die van mij kan ook met UBB overweg (een klein beetje, is natuurlijk uitbreidbaar), en ik denk dat ik em nog ooit es vrijgeef op GoT ofzo :)

  • Tux
  • Registratie: Augustus 2001
  • Laatst online: 21:53

Tux

MisterData schreef op 19 December 2002 @ 21:05:
[...]


Die van mij kan ook met UBB overweg (een klein beetje, is natuurlijk uitbreidbaar), en ik denk dat ik em nog ooit es vrijgeef op GoT ofzo :)
Waarom niet nu ;) :P

The NS has launched a new space transportation service, using German trains which were upgraded into spaceships.


  • MisterData
  • Registratie: September 2001
  • Laatst online: 29-08 20:29
Ach waarom niet he ;) Licentie: gratis voor niet-commercieel gebruik. Wil je hem toch commercieel gebruiken, mail me dan even (in m'n profiel staat m'n mailadres).

http://quatro.ath.cx/meuk/misterdata-stackbased-tpl-1.0.zip

  • Tux
  • Registratie: Augustus 2001
  • Laatst online: 21:53

Tux

MisterData schreef op 19 december 2002 @ 21:44:
[...]


Ach waarom niet he ;) Licentie: gratis voor niet-commercieel gebruik. Wil je hem toch commercieel gebruiken, mail me dan even (in m'n profiel staat m'n mailadres).

http://quatro.ath.cx/meuk/misterdata-stackbased-tpl-1.0.zip
Ontzettend bedankt :)
Ik wil namelijk wat meer leren over stackbased parsing, dus ik ga die code eens bekijken :)

The NS has launched a new space transportation service, using German trains which were upgraded into spaceships.


  • MisterData
  • Registratie: September 2001
  • Laatst online: 29-08 20:29
Tux schreef op 19 December 2002 @ 21:53:
[...]


Ontzettend bedankt :)
Ik wil namelijk wat meer leren over stackbased parsing, dus ik ga die code eens bekijken :)
Bereid je dan maar voor op een 800-regels lange brij van code zonder commentaar :+

  • Nielsz
  • Registratie: Maart 2001
  • Niet online
MisterData schreef op 19 December 2002 @ 21:56:
[...]

Bereid je dan maar voor op een 800-regels lange brij van code zonder commentaar :+
offtopic:
Ik heb alleen regels code staan met commentaar als "Huh? Wat doet dit hier :o "

[ Voor 5% gewijzigd door Nielsz op 19-12-2002 22:10 ]


  • MisterData
  • Registratie: September 2001
  • Laatst online: 29-08 20:29
Nielsz schreef op 19 december 2002 @ 22:10:
[...]

offtopic:
Ik heb alleen regels code staan met commentaar als "Huh? Wat doet dit hier :o "
:D
offtopic:
mwah, als er een vrijwilliger is die het even wil documenteren....

  • whoami
  • Registratie: December 2000
  • Laatst online: 23:16
offtopic:
800 LOC is peanuts....

[ Voor 33% gewijzigd door whoami op 19-12-2002 22:18 ]

https://fgheysels.github.io/


  • Tux
  • Registratie: Augustus 2001
  • Laatst online: 21:53

Tux

MisterData schreef op 19 December 2002 @ 22:13:
[...]


:D
offtopic:
mwah, als er een vrijwilliger is die het even wil documenteren....
Ik heb vakantie en ik ben van plan om de source uit te pluizen ;)

Ik heb vanmiddag nog in mn hardcoded str_replace() parser voor mn forum (andere manier lastig omdat die bijna alles als template ophaalt en nogal wat specifieke functies nodig) helemaal zitten commenten :P

edit:
Zijn er maar 738 ;)

[ Voor 4% gewijzigd door Tux op 19-12-2002 22:26 ]

The NS has launched a new space transportation service, using German trains which were upgraded into spaceships.


  • Nielsz
  • Registratie: Maart 2001
  • Niet online
Tux schreef op 19 december 2002 @ 22:24:
[...]

edit:
Zijn er maar 738 ;)
offtopic:
550 :7


Ik ga die van mij ook nog wel eens releasen, zodra hij echt goed af is. Maarja, tijdgebrek enzo. Het is wel heel leerzaam. Maar hij's wel bagger geprogrammeerd :)

  • Tux
  • Registratie: Augustus 2001
  • Laatst online: 21:53

Tux

Nielsz schreef op 19 December 2002 @ 22:32:
[...]

[offtopic]550 :7 [/oftopic]

Ik ga die van mij ook nog wel eens releasen, zodra hij echt goed af is. Maarja, tijdgebrek enzo. Het is wel heel leerzaam. Maar hij's wel bagger geprogrammeerd :)
Heel leerzaam is het wel ja :P

Als je voor het eerst iets met stacks ziet dan denk je wel ff 'WTF', maar stukje bij beetje begint het helder te worden :P

The NS has launched a new space transportation service, using German trains which were upgraded into spaceships.


  • .oisyn
  • Registratie: September 2000
  • Laatst online: 17-09 14:05

.oisyn

Moderator Devschuur®

Demotivational Speaker

EfBe schreef op 19 december 2002 @ 20:36:
Wellicht praten we over verschillende dingen :) Maar je hebt een lexical analyzer die tokens bakt en een parser die tokens scant om productieregels te verifieren. Wat ik parser noem noem jij semantic checker :)
zeker niet, ik ben bezig met een eigen scripttaal voor games mbv flex en bison, dus ik weet wel min of meer waar het over gaat ;)

De grammatica voor een parser die hier bedoelt wordt is niet meer dan dit:

code:
1
2
text -> OPEN_TAG text CLOSE_TAG
text -> STRING


Daar heb je echt geen parser generator voor nodig om dat met de hand te coden hoor ;)
Bovendien, als een stuk geparsed is en er een abstract syntax tree van is gemaakt, dan moet je nog kijken of de close tag de open tag matcht (dan controleer je dus op semantics, niet op syntax)

Een optie is om de scanner (lexical analyser, tokenizer, whatever you want to call it) alleen close tags te herkennen als ze bij de open tag horen. Desalniettemin heb je nog steeds geen parser generator nodig om die 2 production rules in te bouwen
In het geval van simpele tags als bold etc niet nee. Maar 'even' een parser met de hand maken voor een resiment uitzonderingen is niet 1 2 3 gedaan. Bv de UBB die op GoT wordt gebruikt bevat al aardig wat uitzonderingen, daar schrijf je niet 1 2 3 een 'parser' voor met de hand. Ik bedoel: stel je wilt binnen een bold tag geen quotes en binnen code geen quotes, maar 1 nestlevel diep quotetexts, etc. :) Dat wordt gauw complex :) (Als je de UBB syntax uitschrijft in BNF zit je zonder smileys al rond de 70 productieregels, dat doe je niet 1 2 3 met de hand)


dat UBB op GoT heet RML ;) Maar dat even terzijde, je hoeft heus niet al je productieregels uit te schrijven voor elke tag. Je kunt simpelweg voldoen met een lijstje ondersteunde tags (en attributen), en vervolgens kun je in een tabel opzoeken welke tag in welke mogen. Met React (de forumsoftware hier op GoT) kun je die rechten (ik noem het maar even rechten) gewoon on the fly aanpassen, daar gaan de Parse lui echt niet de hele tijd nieuwe grammatica's voor zitten maken hoor :)

Give a man a game and he'll have fun for a day. Teach a man to make games and he'll never have fun again.


  • stekkel
  • Registratie: Augustus 2001
  • Laatst online: 17-09 08:05
ben zelf ook veel bezig met parsers.
Ik heb een o.a. een imap bodystructure parser geschreven wat gebruikt maakt van een recursive functie om een tree te vullen. Ik maak dus geen gebruik van een stack maar sla het gelijk op in een tree.

dingen zoals regex en pregmatch werken absoluut niet voor imap-parsers. Het probleem is namelijk dat je tokens ook in bijvoorbeeld quoted strings kunnen voorkomen en dan juist weer niet als erkende token behandeld mag worden. De oplossing was gewoon simpel left to right parsing en waar mogelijk findfirst achtige dingen gebruiken (strpos). Op deze manier parse je dus alles zonder dat je een stack nodig hebt om alles eerst in op te slaan.

Acties:
  • 0 Henk 'm!

  • EfBe
  • Registratie: Januari 2000
  • Niet online
.oisyn schreef op 19 December 2002 @ 22:58:
zeker niet, ik ben bezig met een eigen scripttaal voor games mbv flex en bison, dus ik weet wel min of meer waar het over gaat ;)

De grammatica voor een parser die hier bedoelt wordt is niet meer dan dit:

code:
1
2
text -> OPEN_TAG text CLOSE_TAG
text -> STRING


Daar heb je echt geen parser generator voor nodig om dat met de hand te coden hoor ;)
hehe nee inderdaad, met zo'n straffe taalsyntaxis heb je geen parser nodig. Ik begreep dat echter niet 1 2 3 uit topicstarters' text.
Bovendien, als een stuk geparsed is en er een abstract syntax tree van is gemaakt, dan moet je nog kijken of de close tag de open tag matcht (dan controleer je dus op semantics, niet op syntax)
Dit kun je doen door een gewone productionrule, wat gebeurt bij een shift-reduce parser (wat eigenlijk de naam is voor een stack-based parser)
Een optie is om de scanner (lexical analyser, tokenizer, whatever you want to call it) alleen close tags te herkennen als ze bij de open tag horen. Desalniettemin heb je nog steeds geen parser generator nodig om die 2 production rules in te bouwen
Met die 2 rules niet nee. :)
dat UBB op GoT heet RML ;) Maar dat even terzijde, je hoeft heus niet al je productieregels uit te schrijven voor elke tag. Je kunt simpelweg voldoen met een lijstje ondersteunde tags (en attributen), en vervolgens kun je in een tabel opzoeken welke tag in welke mogen. Met React (de forumsoftware hier op GoT) kun je die rechten (ik noem het maar even rechten) gewoon on the fly aanpassen, daar gaan de Parse lui echt niet de hele tijd nieuwe grammatica's voor zitten maken hoor :)
Maar dan heb je uiteindelijk weinig rules. Als je bv de bold tag neemt en je mag daarbinnen alle text constructies weer gebruiken (of beter: altijd mag binnen elke tag iedere textconstructie weer plaatsvinden, behalve quote in quote), dan heb je erg weinig rules en dus kun je volstaan met een tabel met tags die in welke tags mogen, maar dat wordt echt ellende, wanneer je het wat stricter definieert, immers waarom zou men anders in normale parsers niet gewoon hetzelfde doen: welke statements na/binnen welke andere mogen in een tabelletje en klaar ben je :P

Creator of: LLBLGen Pro | Camera mods for games
Photography portfolio: https://fransbouma.com


Acties:
  • 0 Henk 'm!

Verwijderd

Topicstarter
ik heb het voor elkaar gekregen 8)
als het helemaal af is post ik het nog wel in deze thread.
thnx voor de hulp
Greetzzz

Acties:
  • 0 Henk 'm!

  • Mithrandir
  • Registratie: Januari 2001
  • Laatst online: 23:25


Ehm, klein foutje, sorry :o

[ Voor 99% gewijzigd door Mithrandir op 23-01-2004 19:57 ]

Verbouwing


Acties:
  • 0 Henk 'm!

  • MSalters
  • Registratie: Juni 2001
  • Laatst online: 13-09 00:05
Maar is het al helemaal af? TS?

Man hopes. Genius creates. Ralph Waldo Emerson
Never worry about theory as long as the machinery does what it's supposed to do. R. A. Heinlein


Acties:
  • 0 Henk 'm!

  • Infinitive
  • Registratie: Maart 2001
  • Laatst online: 25-09-2023
Voor de geïnteresseerden is er het een en ander aan introductiemateriaal op het gebied van LR(1)-ontleden beschikbaar op de volgende website: http://www.cs.uu.nl/docs/vakken/gont/.

putStr $ map (x -> chr $ round $ 21/2 * x^3 - 92 * x^2 + 503/2 * x - 105) [1..4]


Acties:
  • 0 Henk 'm!

  • curry684
  • Registratie: Juni 2000
  • Laatst online: 06-09 00:37

curry684

left part of the evil twins

Mithrandir is een prutser ;) Maar daar TS nog actief is op het forum kan ie alsnog laten horen hoe het er mee staat als ie dit ziet :Y)

Professionele website nodig?

Pagina: 1