Programmeren: Rekenen

[Verwijderd]

Wel ik ben bezig met een parser en nu moet hij ook bijvoorbeeld kunnen rekenen. {$variable = 2 + 3 * 3} of {$variable = 10 % 2 * 3} etc. Nu kan ik me herinneren dat vermenigvuldigen en delen voorang hebben op optellen en aftrekken wat dus inhoud bij het eerste voorbeeld: 2 + (3 * 3) is 11. Mijn parser doet het 1 voor 1 van links naar rechts en rekent op dit moment de diepste sets eerst uit maar houdt nog geen rekening met het fenomeen dat vermenigvuldigen en delen hebben. Ik zat er aan te denken omdat mijn parser toch al eerst de diepste sets uit rekent, wat volgens mij ook zo moet. Om vermenigvuldigen en delen een extra set mee te geven voordat mijn parser deze gaat uitrekenen. Hierdoor rekent hij deze eerder uit dan plus en min. Kan dit zo of moet dit anders?

Daarnaast kan ik mij de modulo omtrend dit fenomeen niet herrinneren. Valt de modulo berekening onder optellen / aftrekken of onder vermenigvuldigen / delen ?

[Juup]

Zie https://en.wikipedia.org/wiki/Order_of_operations:

1 () [] -> . :: Function call, scope, array/member access
2 ! ~ - + * & sizeof type cast ++ -- (most) unary operators, sizeof and type casts (right to left)
3 * / % MOD Multiplication, division, modulo
4 + - Addition and subtraction

[CurlyMo]

Voor het schrijven van je eigen parser zijn niet zoveel manieren die echt werken. Het wiel opnieuw uitvinden heeft dus weinig zin.

Toen ik mijn eigen parser en lexer begon te maken heb ik veel gehad aan deze blog:
https://ruslanspivak.com/lsbasi-part1/

Het is weliswaar een pascal parser in python, maar de blog beschrijft (vind ik) vrij duidelijk de theorieën erachter.

Daarnaast zijn de steekwoorden die je kan zoeken / lezen:
- Recursive decent parser
- Shunting Yard algoritme
- Operator precendence parser
- Abstract Syntax Tree

De termen die de volgordelijkheid van operatoren beschrijven zijn precedence en associativity

Als laatste nog de opmerking dat het maken van een parser vrij complex is voor een beginner zoals je zelf aangeeft te zijn. Begin eerst eens met een beetje leren te programmeren voordat je zelf een programmeertaal probeert te maken.

[ Voor 17% gewijzigd door CurlyMo op 28-04-2019 15:48 ]

[Verwijderd]

toch blij ff gevraagd te hebben, met de code van Wikipedia: Operator-precedence parser heb ik een goede basis, ff modulo toevoegen.

De c code functie daar is een goed voorbeeld en is anders hoe ik het in eerste instantie bedacht. mijn idee zette alleen extra haakjes om vermenigvuldigen terwijl het c voorbeeld echt met lagen werkt.

Betreft beginner, nee dat ben ik niet en mn parser, ach, nu bezig met versie 3 en nadat ik de if, elseif, else, foreach & while erin had zitten, de for getest. Hij parsed al redelijk snel maar ben er toch achter gekomen om de boel maar naar php te converteren voordat ik hem uitvoer, hij deed namelijk 2msec per { for} iteratie met een variable assignment erin en een if statement met een variable en integer om te breaken. oftewel leuk voor 100 iteraties (200ms) maarja dat doet php toch vele malen sneller...

Waarom ik vraag: ik kon geen zekerheid voor de modulo vinden, daarnaast de logica achter het extra complex maken van wiskundige berekeningen, onderscheid maken hierin, daarnaast is echte wiskunde minstens zo'n 20 jaar geleden geweest en ben nu te weten gekomen dat er onderscheid gemaakt wordt tussen programmeertalen hierin.

ach en daarnaast programmeer ik al best lang en complexe berekeningen is voor mij ook 4 werkgevers terug. En met materie is het bij mij zo, als je er niet echt meer in zit, maar een vermoeden hebt, dan kun je beter even vragen aan de kenners...

Maar waarom noem jij het een lexer (ik noem het Token::all() en heb jij je parser ook op github staan, mag ik een kijkje nemen ?

Wat voor een bron bestanden kan je parser aan, kan die ook overweg met methoden, multiline methoden, assignments, class definities, functie definities ? Ik bedoel daar moet je parser waarschijnlijk ook in groeien...

Zo maak ik gretig gebruik van json, maar ook van variabelen, methode aanroepen in die json, dus parse ik json bestanden, maar ook html, maar in principe tot aan binaire bestanden toe straks.

Nog een tip; indien je in php parsed zou ik het afraden om de token_get_all() functie te gebruiken. Het idee is leuk, je zult waarschijnlijk hetzelfde moeten doen, maar deze functie wijkt waarschijnlijk per php versie af en voordat je al die edge cases gedetecteerd hebt of er bij een versie update (anders wellicht iets kapot kan gaan) zou ik die zelf maken.

[ Voor 178% gewijzigd door Verwijderd op 29-04-2019 23:42 . Reden: betere reactie ]

[Verwijderd]

Juup schreef op zondag 28 april 2019 @ 15:26:
Zie https://en.wikipedia.org/wiki/Order_of_operations:

1 () [] -> . :: Function call, scope, array/member access
2 ! ~ - + * & sizeof type cast ++ -- (most) unary operators, sizeof and type casts (right to left)
3 * / % MOD Multiplication, division, modulo
4 + - Addition and subtraction

bedankt !

2 doe ik in principe al voor de tijd, ik heb een left en een right in de operator array / object. Ik parse left & right op variablen, methodes, casts en exclamation (moet nog ~ (not), & ) en voer dan de operator uit. wat betekent die * daar bij 2, waar staat ie voor zoals *20 ? Daarnaast het fenomeen rtl / ltr (direction) kan het voorkomen in een voorbeeld dat deze beide moeten worden uitgevoerd ? welke gaan dan eerst, die met rtl of ltr, of hebben de invloeden altijd dezelfde richting en komt gemengd (rtl + ltr) niet in dezelfde stap voor.

[CurlyMo]

Verwijderd schreef op zondag 28 april 2019 @ 16:03:
Betreft beginner, nee dat ben ik niet en mn parser, ach, nu bezig met versie 3 en nadat ik de if, elseif, else, foreach & while erin had zitten, de for getest. Hij parsed al redelijk snel maar ben er toch achter gekomen om de boel maar naar php te converteren voordat ik hem uitvoer, hij deed namelijk 2msec per { for} iteratie met een variable assignment erin en een if statement met een variable en integer om te breaken. oftewel leuk voor 100 iteraties (200ms) maarja dat doet php toch vele malen sneller...

Bouw je nu wel een AST op?

Waarom ik vraag: ik kon geen zekerheid voor de modulo vinden, daarnaast de logica achter het extra complex maken van wiskundige berekeningen, onderscheid maken hierin, daarnaast is echte wiskunde minstens zo'n 20 jaar geleden geweest en ben nu te weten gekomen dat er onderscheid gemaakt wordt tussen programmeertalen hierin.

Als het goed is kan je je operatoren modulair toevoegen aan je parser door ze simpelweg aan een lijstje toe te voegen met de juiste precendence en associativity. Zulke lijstjes zul je ook vaak tegenkomen in bestaande programmeertalen. Voor je parser maakt het dan niet meer uit hoe complex je berekening is, zolang je de juiste waarde aan je operator koppelt, moet die er gewoon uit kunnen komen.

Maar waarom noem jij het een lexer (ik noem het Token::all() en heb jij je parser ook op github staan, mag ik een kijkje nemen ?

Ik heb het niet bedacht Er zijn gewoon bestaande theorieën over.

Mijn implementatie:
https://github.com/piligh...s/pilight/events/events.c

Staat jouw uitwerking ook al ergens

Wat voor een bron bestanden kan je parser aan, kan die ook overweg met methoden, multiline methoden, assignments, class definities, functie definities ? Ik bedoel daar moet je parser waarschijnlijk ook in groeien...

Bijbehorende documentatie:
https://manual.pilight.org/eventing/index.html

[bwerg]

Verwijderd schreef op zondag 28 april 2019 @ 16:03:
Maar waarom noem jij het een lexer (ik noem het Token::all() en heb jij je parser ook op github staan, mag ik een kijkje nemen ?

Omdat het zo heet.

Een tokenizer/lexer (zijn synoniemen van elkaar) is puur om stukjes tekst te groeperen als een rijtje tokens, waar je parser dan iets mee kan. Zo is de expressie "42*(123 + bla)" te groeperen als "42", "*", "(", "123", "+", "bla", ")", waarbij de lexer ook meteen een soort type kan toekennen aan de tokens. Een lexer maakt vaak gebruik van een simpele klasse van grammatica's zoals regexen (die niet krachtig genoeg zijn om een hele parser van te bouwen). Zo'n rijtje maakt het gemakkelijker om daarna te parsen, dat hoeft dan niet met platte tekst te werken.

Je noemt ook methoden en assignments uitvoeren en de snelheid daarvan. Dat is geen parser meer, dat is een hele compiler/interpreter van een taal met een semantiek. Een parser parsed, dus dat is alleen het inlezen van tekst volgens een grammatica.

Verder heb je het over performance, maar als je een efficiënte parser wil maken lijkt PHP me sowieso niet de voorkeurskeuze (ook al is mijn PHP-kennis zeer beperkt). Nou bepaal je zelf het doel van het project maar mij lijkt een elegante, nette oplossing leerzamer dan een hacky oplossing om het sneller te maken. Netjes de theorie volgen (lexer --tokens--> parser --AST--> code-uitvoer) lijkt me vooral nuttig.

[ Voor 4% gewijzigd door bwerg op 30-04-2019 09:13 ]

[CurlyMo]

De lexer zal dan ook bepalen dat afhankelijk van de context een komma de ene keer de argumenten van een functie scheid, terwijl het de andere keer een decimaal teken is. Die regels bepaal je allemaal zelf. Je lexer zorgt alleen dat je combinaties van characters tot tokens worden omgezet met een bepaalde functie.

[bwerg]

CurlyMo schreef op dinsdag 30 april 2019 @ 09:14:
De lexer zal dan ook bepalen dat afhankelijk van de context een komma de ene keer de argumenten van een functie scheid, terwijl het de andere keer een decimaal teken is. Die regels bepaal je allemaal zelf.

Met de belangrijke beperking dat die regels wel regulier moeten zijn. Als je lexer aan de hand van de context gaat bekijken elke variabelen in scope zijn, ben je geen lexer meer aan het bouwen maar een volledige parser. "Afhankelijk van de context" is dan ook een beetje een gevaarlijke omschrijving, want regexen zijn in beginsel niet context-afhankelijk. Je lexer ziet dat de expressie "42,42 + 123" met de regex "[0-9]*,[0-9]*" begint en eet dan het matchende stukje tekst ("42,42") op, waarna hij weer zonder verdere context met de rest (" + 123") verder gaat.

[mcdronkz]

't Is ook nog een idee om van infix-notatie af te stappen, dan speelt bewerkingsvolgorde geen rol meer.

Stukje LISP:

Common Lisp:

(+ 3 (+ 8 (/ 10 2) 2) 3 (* 5 2) 5)

[CurlyMo]

bwerg schreef op dinsdag 30 april 2019 @ 12:06:
[...]

Met de belangrijke beperking dat die regels wel regulier moeten zijn. Als je lexer aan de hand van de context gaat bekijken elke variabelen in scope zijn, ben je geen lexer meer aan het bouwen maar een volledige parser. "Afhankelijk van de context" is dan ook een beetje een gevaarlijke omschrijving, want regexen zijn in beginsel niet context-afhankelijk. Je lexer ziet dat de expressie "42,42 + 123" met de regex "[0-9]*,[0-9]*" begint en eet dan het matchende stukje tekst ("42,42") op, waarna hij weer zonder verdere context met de rest (" + 123") verder gaat.

Waar ik op doelde is dit (ruw voorbeeld):

function(foo, bar)

geeft:

"function" (type functie) "foo" (type argument) "bar" (type argument)


Terwijl:

123,12 + 123

geeft:

"123,12" (type getal) "+" (type operator) "123" (type getal)

De komma heeft dus twee verschillende betekenissen.

Parser knoopt de eindjes aan elkaar.

[bwerg]

CurlyMo schreef op dinsdag 30 april 2019 @ 12:50:
[...]

Waar ik op doelde is dit (ruw voorbeeld):

function(foo, bar)

geeft:

"function" (type functie) "foo" (type argument) "bar" (type argument)

Met "ruw voorbeeld" bedoel je hopelijk ook dat een echte lexer ook de haakjes en de komma netjes als tokens teruggeeft. Witruimte weggooien mag wel, maar de betekenis van losse haakjes en komma's is context-afhankelijk (en om verwarring te voorkomen: formeel niet context-afhankelijk, maar context-vrij) en is dus werk voor een parser.

Maar goed, voor meer informatie is wikipedia al best aardig over dit onderwerp.

[ Voor 19% gewijzigd door bwerg op 30-04-2019 13:42 ]

[CurlyMo]

bwerg schreef op dinsdag 30 april 2019 @ 13:27:
[...]

Met "ruw voorbeeld" bedoel je hopelijk ook dat een echte lexer ook de haakjes en de komma netjes als tokens teruggeeft. Witruimte weggooien mag wel, maar de betekenis van losse haakjes en komma's is context-afhankelijk en is dus werk voor een parser.

Maar goed, voor meer informatie is wikipedia al best aardig over dit onderwerp.

Laten we het niet beter proberen uit te leggen dan Wikipedia.

Enige wat blijft staan is de vraag of de lexer bepaald dat 123,12 één getal is met de komma als decimaal teken of twee getallen met één komma als delimiter en dat de parser bepaald dat het een getal is met decimalen.

[Verwijderd]

Wat betreft de keuze dat ik het in php doe, daar schrijf ik al jaren in, nooit fan geweest van, java, c, c++.

Betreft een AST. Mijn tokenizer class maakt van een string een array met tokens, elk token is een bepaald type, string, int, float, boolean, array, object, variable assignment, variable met modifier, variable zonder modifier, methode of multiline methode. Oftewel dit is mijn structuur. Deze structuur werd vervolgens uitgevoerd. Wat ik nu toevoeg is een compiler die alles uitschrijft in php code, vergelijkbaar met Smarty. Indien die dit geschreven heeft zet ik de filemtime gelijk met de source van het bestand zodat straks die uitschrijfcode alleen update indien de source veranderd. Die uitschrijfcode wordt een class die de parser mee krijgt als argument, alle data is aanwezig in de parser. Ik denk dat het parsen dan in totaal niet zoveel tijd kost. In cli op het moment dat ik een command uitvoer: 75 ms framework time tot de controller, dan wil hij naar de view, de view wordt geparsed door mijn parser en momenteel kost 225 ms om te komen tot de uitschrijfcode inclusief framework time. Dus van request tot view. Ik denk dat een andere hd (naar ssd) die 225 ms / 4 doet en resulteerd in +/- 60 msec. Indien de uitschrijfcode beschikbaar is, komt die class die de view uitvoerd er nog bij, dus 70 msec met php dan. Aanname dat for loops nu goed gaan, doe ik dat uitschrijfbestand niet en heb er een for loop van 10.000 iteraties inzitten, 10.000 x 2 msec, tsja daar wordt je niet vrolijk van, maar goed daar heb ik nu 10 msec van gemaakt hopelijk.

Code is te vinden hier: https://github.com/like-it/Priya/tree/develop/Module/Parse

[CurlyMo]

Verwijderd schreef op dinsdag 30 april 2019 @ 15:56:
Code is te vinden hier: https://github.com/like-it/Priya/tree/develop/Module/Parse

Wat is uiteindelijk je doel? Een nieuwe template engine bouwen? Wat parsed je parser? Oftewel, kan je een voorbeeld geven van de input?

[ANdrode]

Verwijderd schreef op zondag 28 april 2019 @ 16:03:
toch blij ff gevraagd te hebben, met de code van Wikipedia: Operator-precedence parser heb ik een goede basis, ff modulo toevoegen.

Het Shunting-yard algorithm (rangeer)algoritme is hiervoor ook een goede keuze als alternatief voor een complete parser

[CurlyMo]

ANdrode schreef op dinsdag 30 april 2019 @ 17:03:
[...]


Het Shunting-yard algorithm (rangeer)algoritme is hiervoor ook een goede keuze als alternatief voor een complete parser

Behalve als je toch wel een complete parser aan het bouwen bent.

[Verwijderd]

CurlyMo schreef op dinsdag 30 april 2019 @ 16:08:
[...]

Wat is uiteindelijk je doel? Een nieuwe template engine bouwen? Wat parsed je parser? Oftewel, kan je een voorbeeld geven van de input?

sorry, zover ben ik nog niet, maar hierbij een voorbeeldje:

code:

{ $variable = 1 + 2 * 4 } //assignment
{ $string = 'test123' } //assignment
{ $string | string.uppercase.first } //weergave met modifier, past $string niet aan, alleen weergave


//if statement
{ if ($a == $b) }

{ elseif ( $c > $d ) }

{ else }

{ /if }

// for each statement
{ for.each($data as $attribute => $value) }

{ /for.each }

//while statement
{ while ( true ) }

{ /while }

// variable assigment met cast & method
{ $method = (string) string.uppercase.first( $string) }

{ echo (1+2) }

Daarnaast in json bestanden:
// variabelen / functies

code:

{
    "url" : "{$priya.dir.module | dir.name }Parse/Modifier/"
}

{ literal } { /literal } // wordt niet geparsed

{ rem } { /rem } // hier kun je straks code kloppen zonder "{}" om code en zonder ";" (is de bedoeling, werkt nog niet)

[CurlyMo]

Verwijderd schreef op dinsdag 30 april 2019 @ 22:03:
[...]


sorry, zover ben ik nog niet, maar hierbij een voorbeeldje:

Klopt het dan dus dat je een template engine aan het bouwen bent?

[Verwijderd]

CurlyMo schreef op dinsdag 30 april 2019 @ 22:24:
[...]

Klopt het dan dus dat je een template engine aan het bouwen bent?

ja en nee, initieel begonnen om mijn json config files te voorzien van variabelen en handige methodes, later uitgebreid zodat ie templates aankan. Met de toen aanwezige template engines kon ik niet goed json er doorheen krijgen, dus ben ik hobbymatig begonnen met het zelf ontwikkelen. Templates kan de parser dus straks ook, maar heel veel php functies kan deze straks ook en je zou er complete code in kunnen schrijven, echter voor nu nog geen functie declaratie en class declaraties, functie declaraties gaan momenteel via functies geschreven in php.

via { import.function( $dir || $url ) } kun je eventueel aangeven waar die moet gaan zoeken naar functies. Dit kunnen dan ook custom functies zijn, met een default dir en veel php standaard functies beschikbaar.

code:

{
    "menu" :
    {
        "20" : {
            "jid" : "20",
            "name" : "Home",
            "title" : "{$menu.20.name}",
            "ctime": 1486915209,
            "mtime": 1492381674,
            "sort": 1,
            "target" : "section[name='page']",
            "method" : "replace-with",
            "node" : {
                "tag" : "li",
                "content" : "{$menu.20.title}",
                "route": "{route('priya-software-page', \"{$menu.20.name}\")}",
                "class" : "menu-item-{$menu.20.name | string.lowercase}",
                "data" : {
                    "target" : "{$menu.20.target}",
                    "method" : "{$menu.20.method}"
                }
            }
        }
    }
}

Waarbij die $menu.20.name uit hetzelfde bestand komt, nou moet ik nog iets verzinnen voor die $menu.20 te veranderen in this.parent('name') bijvoorbeeld.

[ Voor 33% gewijzigd door Verwijderd op 01-05-2019 14:44 ]

[CurlyMo]

Heb je al wel eens conceptueel nagedacht of JSON het juiste formaat voor je doel is en er misschien niet al een formaat bestaat dat doet wat je wil? Ik weet niet of het er is, misschien wel.