Hoe parse je boolean expressions

[Juup]

Om parsing te leren ben ik bezig met het schrijven van een (custom) parser.
Fragment uit de broncode:

code:

if a == 4 and (b == 5 or c == 8)

Ik heb ook een tokenizer die deze string ophakt in een stream van tokens, en elk token heeft een type (bv identifier, number, booloperator etc.

Hoe kan ik van deze lineaire stream van tokens nu een parsetree bouwen, iets als dit:

code:

.
     if
      |
     and
   /     \
 ==        or
/  \     /    \
a  4    ==    ==
       /  \  /  \
      b    5 c  8

Is daar informatie over te vinden?
Alles wat google me levert gaat over parser generators en BNF enzovoorts.

[Koppensneller]

Bijvoorbeeld door een Wikipedia: Shift-reduce parser te implementeren

[MartenBE]

Koppensneller schreef op vrijdag 03 oktober 2014 @ 14:53:
Bijvoorbeeld door een Wikipedia: Shift-reduce parser te implementeren

LR parsers met de hand maken is gekkenwerk. Ik denk dat het mogelijk moet zijn om met een LL parser te werken. Dat is wel nog haalbaar met de hand.

[Juup]

Bedankt voor jullie input.
Misschien moet ik dit toch niet met de hand willen doen.

[Soultaker]

Als je wil leren parsen, is het juist wel nuttig om parsers met de hand te schrijven. Voor het parsen van expressies, zie: Wikipedia: Shunting-yard algorithm

[vandeGerrit]

In de C# (.Net) hebben we 'Expression Trees'. Ik weet niet in welke taal je dit schrijft, maar ik denk dat je de concepten ervan wel kan gebruiken.

[KopjeThee]

Voor dit probleem lijkt mij een eenvoudige recursive descent parser te voldoen. Zie bijvoorbeeld deze opdracht. http://web.cse.ohio-state...expression-evaluator.html
Wat je daar ook al kunt lezen, is dat het van belang is om eerste even de grammatica op te schrijven van hetgeen je wilt parseren.

[M-ThijZ]

Als je hier meer over wilt leren kan ik je de Stanford Compiler course op Coursera ook van harte aanbevelen: https://www.coursera.org/course/compilers

[Ghostbird]

Is het je te doen om te leren een parser te schrijven? Of hoe parsen werkt?

Wij leerden (University of Twente Compiler Construction) een grammaticale definitie te schrijven in een mix van EBNF, ANTLR (een compiler compiler) en Java (ook C++ mogelijk AFAIK).

EBNF is een ISO standaard om grammaticale definities te noteren.¹
ANTLR is een compiler compiler die automatisch compilers kan genereren.
Java was de taal waarin we onze compiler moesten schrijven, ANTLR kan een compiler geschreven in Java genereren.
Deze compiler compileerde dan onze zelfgemaakte programmeertaal naar TASM (Triangle ASseMbly)
Met behulp van de TAM.Assembler werd de TASM code naar TAM (Triangle Abstract Machine) bytecode geassembleerd.
De TAM implementatie was geschreven in Java en draait dus zelf weer op de JVM (Java Virtual Machine).
En die is weer geschreven in C++ ofzo en gecompileerd naar native machinecode.
(Tenzij je het hele zootje in een Virtual Machine draait op een andere architectuur omdat je moeilijk wilt doen uiteraard.)

Het was dus een belachelijke complexiteit en overhead, maar het was dan ook puur academisch en om van te leren.

Je schrijft dan (in ons geval) drie definities in files die bestaan uit EBNF met ANTLR instructies en wat Java.
Een grammaticale definitie voor de Lexer en Parser (dat is wat jij wilt), deze levert een AST (Abstract Syntax Tree, een boom-model van de geparseerde input).

Dan een Contextual Analyser deze doorloopt de AST (niet meer de ongeparseerde input) en controleert onder andere of variabelen en constanten gedeclareerd zijn voordat ze gebruikt zijn, implementeert een stack voor variabele herdeclaraties in functies, doet typechecking etc. De resultaten worden opgeslagen in de AST, zodat de codegeneratie ze kan hergebruiken.

Dan een Code Generator deze doorloopt opnieuw de AST en genereert code voor elke node in de AST. Hij maakt onder andere gebruik van de type-data die de Contextual Analyser heeft weten te achterhalen, bijvoorbeeld om te bepalen of een + als string concatenatie of als optellen uitgevoerd moet worden. Als je het goed hebt uitgevoerd is de codegeneratie vrij simpel aangezien er maar 1 of 2 regels gegenereerd worden per node. De enige extra complexiteit is code die afhankelijk is van types en het backpatchen van jump instructies.
De instructies voor het genereren van de code zijn dus in Java, en de code die gegenereerd wordt zijn dus Java Strings die TASM code zijn.

Om een lang en nodeloos complex verhaal kort te maken.
Als je serieus een parser wilt maken om te leren hoe parsen werkt en niet om te leren hoe je een parser programmeert, dan kun je overwegen om de ANTLR tool te downloaden.

1) De EBNF ISO standaard is gedefinieerd in ISO EBNF en is dus zelf-gedefinieerd. Die lui die dat schreven waren echte meta-nerds.

[.oisyn]

^^ TL;DR

Soultaker schreef op vrijdag 03 oktober 2014 @ 22:30:
Als je wil leren parsen, is het juist wel nuttig om parsers met de hand te schrijven. Voor het parsen van expressies, zie: Wikipedia: Shunting-yard algorithm

'Nuff said . Je moet een probleem niet complexer maken dan het is.

[ Voor 7% gewijzigd door .oisyn op 06-10-2014 11:17 ]