Re: Formelparser

Dave wrote:

> > Die für Dich relevanten Begriffe sind Lexer (auch
> > Scanner oder Tokenizer genannt), Recursive Descent Parser (RDP),
> > Abstract Syntax Tree (AST) und Expression Parsing.
>
> Die Begriffe sind mir ein Begriff

Gute Ausgangslage :-)

> > Vereinfacht gesagt brauchst Du zunächst zwei Klassen. Eine zerlegt
> > die Eingabe in Wörter (Tokens).
>
> Hier beginnts: Ich entwerfe gerade ein Interface für diese Tokens ->
> Stichwort Abflussbaum... Gehe ich den richtigen Weg???

Abflussbaum? Klingt eher nach einem Fall für den Klempner ;-)

Den Begriff kenn ich aus dem Compilerbau so nicht; meinst Du vielleicht
einen Kontrollflussbaum (Control Flow Tree, Control Flow Graph) oder
doch den AST? Der Control Flow Graph wäre eher im Bereich des Emittens
und dient dem Erzeugen von optimierten Zwischencode (SSA etc). Daher
nehme ich einfach mal an, dass Du den AST meinst.

Der Begriff Token ist leider auch im Compilerbau relativ überladen.
Normalerweise wird er nur im Bereich der lexikalischen Analayse
verwendent. In .NET wird mit Token aber z.B. auch eine Metadaten Token
bezeichnet.

Wenn es Dir nur um das Design von Tokens im Bereich der lexikalischen
Analyse geht, hat es mit dem AST aber eigentlich gar nichts mehr zu
tun. Ein Token ist ein Wort in der Eingabe, dem vom Lexer in der Regel
eine Klasse (Literal, Bezeichner, Operator, Schlüsselwort, etc) und
einen Wert (z.B. der Name des Bezeichnes) zugeordnet bekommt.

Das schaut dann in etwa so aus:

enum TokenId
{
Eof,
Identifier,
IntegerLiteral,
DoubleLiteral,
If,
Then,
Else,
End
}

class Token
{
public TokenId TokenId;
public string Text;
}

Für komplexere Sprachen (C#, VB) wird häufig der Text selbst nicht im
Token gespeichert, sondern das Token enthält nur Referenzen auf das
Dokument. Das verhindert das (häufig unnütze) Erzeugen von tausenden
von Strings. Für Formeln wäre das aber Overkill.

Für besseres Error Reporting wird i.d.R. noch der Source Context
(Datei, Zeile, Spalte) im Token gespeichert.

Im AST werden i.d.R. keinen Tokens mehr referenziert, da sie dort keine
Bedeutung mehr haben. Da die meisten Sprachen aber auf Grund des Error
Reportings oder eine besonders intelligenten IDE Integration auch einen
Source Context im AST brauchen, wird machnmal Start- und Endeindex der
abgedeckten Tokens an den Knoten gespeichert (was natürlich voraussetzt
das man die Liste der Tokens vom Lexer über einen Index adressieren
kann).

> > Die andere Klasse kombiniert die Wörter dann zu Sätzen. Diese Klasse
> > wird nahezu immer Parser gennant. Der Parser produziert i.d.R. einen
> > Baum (Abstract Syntax Tree, AST), der den Ausdruck bzw. die
> > Anweisung, Deklaration o.ä. representiert.
>
> Okay - kenn ich bereits von meinem BF Interpreter (der am ende sogar
> ASM Code generiert hat stolz)

BrainF***? *vbg* Wollte ich auch schon mal gemacht haben, aber
irgendwie habe ich keine Lust Code in BF zu schreiben ;-)

--
Immo Landwerth - Visual Studio 2003 - C# - XanaNews 1.17.6.6
.

Relevant Pages

  • Re: Get line numbers with Antlr parser
    ... I need to extract the line numbers from the parser. ... You will have to build an AST class to be used by antlr for that, ... in one part of the parser it works, but in the tree parser ... That way, antlr will build the tree using MyAST nodes, which store the ...
    (comp.compilers)
  • Re: [ANTLR] Zeile und Spalte bei Fehler in Treeparser ermitteln
    ... > Peter Rill schrieb: ... >> Leider ist ja die Javadoc zu ANTLR auch sehr lückenhaft und viele Methoden ... > public void initialize(AST ast) { ... Man muss void initialize(Token token) ...
    (de.comp.lang.java)
  • Re: Formelparser
    ... Ich meine den Baum der die Tokens miteinander verbindet (ein Knoten ... > im Token gespeichert. ... > Im AST werden i.d.R. keinen Tokens mehr referenziert, ...
    (microsoft.public.de.german.entwickler.dotnet.csharp)
  • Re: [ANTLR] Zeile und Spalte bei Fehler in Treeparser ermitteln
    ... public void initialize(final Token token) ... nur, wenn man den AST von ANTLR slebst bauen will, aber mit ... unterstützung von ANTLR... ... Gruss theo ...
    (de.comp.lang.java)
  • Re: Highspeed parsen - aber wie?
    ... AST) erzeugen sollte. ... Vergleiche das am besten mit SAX und DOM. ... der Parser Elemente und Attribute findet, ...
    (de.comp.lang.java)