[antlr/c++] Probleempje met treewalker

[MisterData]

Ik ben bezig mezelf ANTLR te leren, en dat gaat tot dusver heel erg goed. Nu zit ik echter met een probleem. Stel, ik heb het volgende in m'n grammar-file staan:

code:

class ExpressionParser extends Parser;
/* knip */
funcExpr : FUNCNAME LPAREN! parameterList RPAREN!;
protected parameterList: ((INT COMMA)* INT);

/* knip*/

class ExpressionLexer extends Lexer;
/* hele zooi tokens */

class ExpressionTreeWalker extends TreeParser;

expr returns [double r] { double a,b; r=0; ExpressionParameterList pl; }:
 /* hele zooi rules voor expr */
;

parameterList returns [ExpressionParameterList l] {double a; }:
    (a=expr) {
        ExpressionVariable v(a);
        l.Add(v); 
    };

Zoals je ziet parsed de onderste treewalk-rule alleen maar de eerste 'expr' in de parameterList (die er uiteindelijk dus zo uitziet : (1,2,3,4,5) ). Nu krijg ik alleen maar een lijst met alleen een '1', terug. Hoe zorg ik ervoor dat de anderen ook worden geAdd aan de lijst?

[MisterData]

Ik heb het nu op deze manier opgelost:

code:

parameterList returns [ExpressionParameterList l] {double abc; }:
    abcd:INT {
        abc = (double)atof(abcd->getText().c_str());
        ExpressionVariable v(abc);
        l.Add(v); 
    
        // kijken of er nog meer zijn
        bool flag = true;
        while(flag) {
            abcd = abcd->getNextSibling();
            if(abcd!=NULL) {
                abc = (double)atof(abcd->getText().c_str());
                ExpressionVariable v(abc);
                l.Add(v); 
            }
            else {
                flag = false;
            }
        }
    };

Toch zou ik graag van wat andere mensen horen hoe zij dit zouden oplossen, ik vind het zo niet echt netjes namelijk....

[marcusk]

Ik heb dat gedeelte van m'n antlr treewalker zelf nog niet helemaal af, maar uit m'n hoofd kun je het ongeveer zo doen:

code:

paramList returns [ExprList p = new ExprList()]
    :   #(PARAMS (e=expression {p.add(e);} )*)
    ;

expression returns [Expression e ...]
...

Met in de parser:

code:

paramList
    :   expressionList
        { ## = #([PARAMS,"params"], ##); }
    ;
expressionList
    :   expression ( COMMA! expression )*
    ;

[ Voor 8% gewijzigd door marcusk op 01-02-2004 21:55 ]

[MisterData]

Bedankt, het werkt als een trein nu Weet jij trouwens of er ergens een methode verstopt zit om een tree als deze:

code:

     +
    /  \
   /    \
  5     4

zo op het scherm te krijgen uit een AST?

[Alarmnummer]

ANTLR is imho een zwaar achterhaald stuk software. Je zit continue met syntactische predikaten te prutsen bij ambiguiteiten, bij een LR grammatica heb je hier veel minder last mee (in tegenstelling tot een LL) omdat je beslissing tot een veel later tijdstip mag uitstellen. Verder genereerd het ook geen databindingframework, dus je krijgt generieke nodes en je kan die tree ook zwaar verneuken als je transformaties erop wilt uitvoeren. Verder is het gewoon een zwaar verouderd kreng, kijk anders een naar SableCC (ook met c++/c#) backend tegenwoordig. Voor al mijn projecten gebruik ik het en vanaf 3.0 heeft het zelfs ingebouwde CST/AST transformatie... dus smullen maar.

[edit]
En dan nog een keer dat gestuntel met die treewalker. Bij SableCC krijg je depthfirst/reversed depth first visitor guides automagisch erbij. Schrijven van parsers is nog nooit zo makkelijk geweest

[ Voor 14% gewijzigd door Alarmnummer op 02-02-2004 10:32 ]

[mbravenboer]

Alarmnummer: Schrijven van parsers is nog nooit zo makkelijk geweest

Je kan te ver gaan . SableCC is relatief een stuk beter, maar het kan nog steeds niet op tegen (Scannerless) Generalized LR .

[Alarmnummer]

mbravenboer schreef op 02 februari 2004 @ 10:41:
[...]

Je kan te ver gaan . SableCC is relatief een stuk beter, maar het kan nog steeds niet op tegen (Scannerless)

SableCC is een scannerless parser generator.

[mbravenboer]

Alarmnummer: SableCC is een scannerless parser generator.

Ik kan me vergissen, maar volgens mij heeft SableCC heeft wel degelijk een gescheiden lexicale analyse. Deze gescheiden lexicale analyse zorgt ervoor dat de input opgedeelt wordt in tokens op een wijze die niet afhankelijk kunnen zijn van de context. Een concreet voorbeeld : a -- b zal nooit als a - (- b)) geparseerd kunnen worden als er zowel een -- als een - token in de taal zit.

[Alarmnummer]

mbravenboer schreef op 02 februari 2004 @ 11:29:
[...]

Ik kan me vergissen, maar volgens mij heeft SableCC heeft wel degelijk een gescheiden lexicale analyse. Deze gescheiden lexicale analyse zorgt ervoor dat de input opgedeelt wordt in tokens op een wijze die niet afhankelijk kunnen zijn van de context. Een concreet voorbeeld : a -- b zal nooit als a - (- b)) geparseerd kunnen worden als er zowel een -- als een - token in de taal zit.

Ik heb even op die link gekeken, en ik zie dat het verschil tussen de lexer en parser heel klein is (en bij SableCC zit er een wereld van verschil tussen). Bij SableCC heb je dus beide aparte onderdeel bij elkaar staan (en dat wordt gewoonlijk een scannerless parser genoemt).

[mbravenboer]

Alarmnummer: Bij SableCC heb je dus beide aparte onderdeel bij elkaar staan (en dat wordt gewoonlijk een scannerless parser genoemt).

Tja, das op zich handig, maar het voegt qua uitdrukkingskracht niets toe. Het punt van scannerless GLR is juist dat de lexiciale analyse niet gescheiden is en dus op basis van de context kan plaatsvinden. Er is dus eigenlijk helemaal geen gescheiden lexicale analyse: elk karakter is een token op zich. GLR in het algemeen zorgt ervoor dat grammaticas modulair kunnen zijn en je je synax definitie niet hoeft te verbouwen om prioriteiten en dergelijke af te handelen.

[Alarmnummer]

mbravenboer schreef op 02 februari 2004 @ 11:45:
[...]

Tja, das op zich handig, maar het voegt qua uitdrukkingskracht niets toe.

Tja.. ik heb de naam niet bedacht

Het punt van scannerless GLR is juist dat de lexiciale analyse niet gescheiden is en dus op basis van de context kan plaatsvinden. Er is dus eigenlijk helemaal geen gescheiden lexicale analyse: elk karakter is een token op zich. GLR in het algemeen zorgt ervoor dat grammaticas modulair kunnen zijn en je je synax definitie niet hoeft te verbouwen om prioriteiten en dergelijke af te handelen.

Wanneer komt er nou eens een 100% java versie?

[mbravenboer]

Alarmnummer: Tja.. ik heb de naam niet bedacht

En het is eigenlijk ook geen trademark van ons idd .

Wanneer komt er nou eens een 100% java versie?

(S)GLR moeten we helaas aan anderen overlaten, maar ik kan je wel verklappen dat we binnenkort met nieuwe JJForester achtige tools komen. We gaan werken aan de embedding van concrete object syntax in Java en de generatie van klasse structuren voor object talen. We zullen hierbij ook externe parsers gebruiken, zodat de toepassing van de transformatie/generatie geen dependency heeft op SGLR. Alleen het genereren van de AST, traversals en transformaties zal dan een dependency hebben op SGLR en Stratego. Als je nog wensen hebt, hoor ik ze graag .

Ik ben eigenlijk nog op zoek naar de meest standaard AST representatie voor Java. Helaas is die zoektocht nog niet zo succesvol . Overzichtje van wat ik tot nu toe heb: Java abstract syntax

[Alarmnummer]

mbravenboer schreef op 02 februari 2004 @ 11:55:
(S)GLR moeten we helaas aan anderen overlaten, maar ik kan je wel verklappen dat we binnenkort met nieuwe JJForester achtige tools komen.

Oeh.. dat is goed nieuws. Ik erger me aan SableCC omdat grammatica`s niet modulair zijn opgezet. Hierdoor krijg je veel ctrl c/ ctrl v zaken en herbruik je dus niet veel. Verder is het aanroepen van willekeurige producties ook niet mogelijk (zonder noodgrepen), en met een modulaire syntax kan gemakkelijker van alles parsen.

We gaan werken aan de embedding van concrete object syntax in Java en de generatie van klasse structuren voor object talen. We zullen hierbij ook externe parsers gebruiken, zodat de toepassing van de transformatie/generatie geen dependency heeft op SGLR. Alleen het genereren van de AST, traversals en transformaties zal dan een dependency hebben op SGLR en Stratego. Als je nog wensen hebt, hoor ik ze graag .

Ik denk dat ik al heel blij ben met de functionaliteit die ze nu aanbieden. Het moet verder wel makkelijk te installeren/deployen zijn. Niet dat je tig andere tools moet installeren om het aan de praat te krijgen.

[marcusk]

MisterData schreef op 02 februari 2004 @ 08:12:
Bedankt, het werkt als een trein nu Weet jij trouwens of er ergens een methode verstopt zit om een tree als deze:
[...]
zo op het scherm te krijgen uit een AST?

In de C# en Java versies kan dat zo:

code:

AST ast1 = m_parser.getAST();
ASTFrame frame1 = new ASTFrame("AST Viewer", ast1);
frame1.ShowDialog();

Er is ook nog toStringList methode van AST die een ASCII-art tree geeft.

(ANTLR is idd niet echt ideaal, maar ik heb zelf helaas geen keuze )

[MisterData]

Als je wil vechten over welke parser het beste is, doe dat dan ergens anders... totaal offtopic (en daarnaast is ANTLR voor wat ik doe geschikt)

[Alarmnummer]

MisterData schreef op 02 februari 2004 @ 17:04:
Als je wil vechten over welke parser het beste is, doe dat dan ergens anders... totaal offtopic (en daarnaast is ANTLR voor wat ik doe geschikt)

Ach tja.. ik zal mijn tips bij je volgende keer voor me houden..

*heeft ANTLR vroeger ook gebruikt.. dus weet exact wat voor tool het is*

[ Voor 11% gewijzigd door Alarmnummer op 02-02-2004 17:12 ]

[marcusk]

MisterData schreef op 02 februari 2004 @ 17:04:
Als je wil vechten over welke parser het beste is, doe dat dan ergens anders... totaal offtopic (en daarnaast is ANTLR voor wat ik doe geschikt)

Pff.. gezien de weinige vertalerbouw-achtige threads op GoT mag er toch best wel eens semi-offtopic geblaat worden over iets interessants wat mij betreft Weer eens wat anders dan al die PHP onzin

[MisterData]

marcusk schreef op 02 februari 2004 @ 17:13:
[...]
Pff.. gezien de weinige vertalerbouw-achtige threads op GoT mag er toch best wel eens semi-offtopic geblaat worden over iets interessants wat mij betreft Weer eens wat anders dan al die PHP onzin

daar heb je wel gelijk in