## c't-Projekte - Mailinglisten

[Voriger (Datum)] [Nächster (Datum)] [Voriger (Thread)] [Nächster (Thread)]
[Nach Datum][Nach Thread]

### Re: [ct-bot] Updates

Absender: Timo Sandmann
Datum: Mo, 11.07.2011 23:40:16
In-reply-to: <3fa2a0ffcb971c3ba20ff2956901265e.squirrel@xxxxxxxxxxxxxxxxxxx>
References: <06FDD79E-4108-46F2-9912-C51255355A81@xxxxxxxxxxxxxxx> <486F950B-9CD1-476A-AD42-EB734AFCB1EC@xxxxxxxxxxxxxxx> <3fa2a0ffcb971c3ba20ff2956901265e.squirrel@xxxxxxxxxxxxxxxxxxx>

    Hallo Uwe,

    vielen Dank für die ausführlichen Erklärungen.

    Mir sind noch zwei Dinge aufgefallen, auf die ich dich hinweisen möchte, weil sie vermutlich so nicht beabsichtigt sind:
    1.) Bei fast allen Dateien in avr_basic und doku ist das executable-Flag (x) gesetzt.
    2.) Die Sourcecode Dateien haben unterschiedliche Zeilenumbruch-Zeichen, teilweise CRLF ("Windows-Mode") und teilweise LF ("Unix-Mode"). Das ist insbesondere dann nervig, wenn man alle Änderungen in einen Patch packen möchte, dann gibt es innerhalb der Patchdatei unterschiedliche Zeilenende-Zeichen.

    Beides nur als Hinweis, es ist natürlich nicht so tragisch.

    Grüße,
    Timo

    Am 08.07.2011 um 09:37 schrieb Uwe Berger:
    > MoinMoin,
    >
    > Am Do, 7.07.2011, 23:29, schrieb Timo Sandmann:
    >> auch uBasic ist jetzt wieder aktuell (rev. 60).
    >> Die Option "TOKENIZER_FASTPARSER" habe ich ausgeschaltet, weil ich keine
    >> Ahnung habe, was genau sie tut bzw. welche Auswirkungen sie hat... (sieht
    >> irgendwie nach Suchbaum für die Schlüsselwörter aus oder so etwas in der
    >> Art?).
    >>
    > korrekt, es handelt sich um ein beschleunigtes Suchverfahren nach
    > Schlüsselwörtern im BASIC-Quelltext und deren "Tokenizierung" in einem
    > Binärbaum.
    >
    > Das bisherige Verfahren, einschaltbar via TOKENIZER_STANDARD in
    > ubasic_config.h, beruht auf einer Liste aller gültigen Schlüsselwörter und
    > deren Zuordnung zu einem Token. Bei der Analyse wird diese Liste vom
    > Anfang bis zum gesuchten Schlüsselwort elementeweise durchgescannt.
    > Nachteile:
    > * die Liste wird immer von Anfang an gelesen, ist das gesuchte
    >  Schlüsselwort sehr weit hinten, muss auch entsprechend lange gesucht
    >  werden
    > * es werden String-Vergleiche verwendet, die auch nicht gerade schnell sind
    >
    > Das neue Verfahren, einschaltbar via TOKENIZER_FASTPARSER in
    > ubasic_config.h, verwendet einen Binärbaum zur Suche/Umsetzung der
    > Schlüsselwörter in Token. Der erste Buchstabe des zu suchenden Wortes wird
    > als Einsprung in den Baum verwendet, danach hangelt sich der Parser
    > buchstabenweise durch den Baum bis er auf ein entsprechendes Blatt trifft,
    > in dem das entsprechende Token kodiert ist. Vorteile:
    > * die Suche ist effizienter, da keine Liste durchgescannt werden muss,
    >  sondern zielgerichtet gesucht wird --> die Anzahl der Zugriffe verringert
    >  sich im Durchschnitt
    > * es werden nur Byte-Vergleiche verwendet
    > * lustigerweise scheint der generierte Code incl. Binärbaum platzsparender
    >  zu sein (habe ich zumindestens bei der Übersetzung des Interpreters
    >  unter Linux festgestellt). U.a. fällt dabei auch die Funktion singlechar()
    >  in tokenizer.c weg, weil auch diese Zeichen im Binärbaum abgebildet sind.
    >
    > Durch dieses Suchverfahren verbessert sich die Geschwindigkeit des
    > Interpreters teilweise erheblich (je nach Umfang des BASIC-Programmes).
    > Einige Tests mit unterschiedlichen BASIC-Programmen ergaben einen
    > durchschnittlichen Faktor von 1:4!
    >
    > Einziger (derzeitiger) Nachteil ist, dass zur Generierung des Binärbaums
    > ein Programm notwendig ist, welches noch nicht veröffentlicht wurde.
    > Grund: Rene (der Entwickler dieses Algorithmus) hat mich darum gebeten mit
    > der Freigabe des Build-Tolls noch ein wenig zu warten, bis er mit einem
    > paralellen Projekt, welches ebenfalls diesen Parser benutzt, fertig ist.
    > Bis dahin bin ich aber gern bereit, bei individuellen Erweiterungen des
    > BASIC-Sprachumfangs, den Binärbaum zu generieren, wenn ich entsprechende
    > Anfragen via Mail bekomme. Der derzeitige Sprachumfang (Revision 60 im SVN
    > auf mikrocontroller.net) ist im derzeitig veröffenlichten Binärbaum
    > enthalten.
    >
    >> String-Support lässt sich in ubasic_config.h aktivieren, falls gewünscht.
    >>
    > jupp, seit ein paar Versionen des Interpreters gibt es einige
    > BASIC-Elemente, die die Verarbeitung von Zeichenketten, inclusive
    > Zeichenketten-Felder, ermöglichen. Dabei muss man sich aber bewußt sein,
    > dass dies teilweise sehr viel dynamischen RAM zur Laufzeit (Speicherplatz
    > für Zeichenkettenvariable werden erst dann reserviert, wenn diese
    > angesprochen werden...) benötigt, was auf einer MCU tötlich sein könnte.
    > Also man sollte diese Option nur dann einschalten wenn man wirklich
    > Zeichenketten in BASIC verarbeiten möchte, ...und dies dann wirklich
    > wohlbedacht dosiert.
    >
    > Ich habe Zeichenkettenverarbeitung in den Interpreter reingenommen, weil
    > er nicht nur für ressourcenarme MCUs gedacht ist. So teste ich z.B.
    > Weiterentwicklungen des Interpreters gar nicht auf eine MCU, sondern unter
    > Linux. Erst ganz zum Schluss, kurz vor Veröffentlichung, flashe ich das
    > Zeugs mal auf ein Arduino-Board (mit einem Mega328p) und einem
    > SD-Card-Shield (von dem die BASIC-Programme eingelesen werden), um zu
    > sehen, ob auch dort alles funktioniert.
    >
    > Grüße Uwe

- Antworten:
  - Re: [ct-bot] Updates
    - From: Uwe Berger

- Referenzen:
  - [ct-bot] Updates
    - From: Timo Sandmann
  - Re: [ct-bot] Updates
    - From: Timo Sandmann
  - Re: [ct-bot] Updates
    - From: Uwe Berger

- Voriger (Datum): Re: [ct-bot] Updates, Uwe Berger
- Nächster (Datum): [ct-bot] Wiki Update (AVR Toolchain), Timo Sandmann
- Voriger (Thread): Re: [ct-bot] Updates, Uwe Berger
- Nächster (Thread): Re: [ct-bot] Updates, Uwe Berger
- Indizes:
  - Datum
  - Thread