| View previous topic :: View next topic |
| Author |
Message |
Gekko
l33t
Joined: 29 Oct 2002
Posts: 773
|
 Posted: Tue Feb 28, 2006 10:04 am Post subject: [OT] Wie funktioniert Syntaxanalyse? |
 |
|
Hallo,
Ich habe z.B. folgende Strings (4 Grundrechnungsarten, Vorzeichen und Klammern):
| Code: | (1+3)*4-1
((1+3)*(-3/2))*4/(2-3) |
Wie könnte ich bei solchen Strings herausfinden, ob der "Syntax" richtig ist? Muss ich für diese (und ähnliche Dinge) einen Syntaxbaum auflösen? Kennt jemand Links zu Tutorials, wie man solche Dinge auf richtige Schreibweise überprüfen könnte? Ich möchte nicht gawk oder lexx und so Kram verwenden, sondern würde gerne wissen, wie man so etwas theroetisch selbst machen könnte. Ich möchte auch nicht in Ruby evaluieren und Fehler abfangen, sondern verstehen wie man so etwas macht.
Jeder Link oder Tipp wird dankend angenommen |
|
| Back to top |
|
 |
rukh
Apprentice
Joined: 17 Aug 2005
Posts: 177
Location: Sol 3
|
| Posted: Tue Feb 28, 2006 10:26 am Post subject: |
|
|
Also, zuerst musst Du Dich dann mit Grammatiken beschäftigen und so weiter und so fort. Im Endeffekt, musst Du Deinem Programm sagen können wo was zu stehen hat.
1. Deine Funktionen bestehen immer aus einem Operator und zwei Zahlen.
2. Ist daselbe wie oben, nur musst Du zuerst den Ausdruck in Klammern evaluieren und dann erst den ersten Operator veknüpfen. (Du kannst b + c ersetzen durch d, d.h. selbe Situation wie 1.)
Und so weiter und so fort. Such Dir per (bevorzugte Suchmaschine) oder in der Wikipedia einfach ein paar Themen zu Grammatiken und formale Sprachen.
Hoffe, dass ich Dir helfen konnte.
_________________
Prepare to meet your maker! -- Bereiten Sie vor sich, Ihren Hersteller zu treffen!
-- rukh.de, Noir (german) |
|
| Back to top |
|
|
Hilefoks
l33t
Joined: 29 Jan 2003
Posts: 849
Location: Emden / Deutschland
|
| Posted: Tue Feb 28, 2006 12:44 pm Post subject: |
|
|
Moin,
| Gekko wrote: | | Wie könnte ich bei solchen Strings herausfinden, ob der "Syntax" richtig ist? Muss ich für diese (und ähnliche Dinge) einen Syntaxbaum auflösen? |
Nein, für eine solch einfache Syntax ist es unnötig einen Syntaxbaum zu bauen. Das testen einer solchen Syntax erledigt auch ein regulärer Ausdruck oder aber eine einfache Schleife mit einigen if-Abfragen. Auch eine rekursive Funktion könnte dieses "Problem" lösen.
MfG Hilefoks |
|
| Back to top |
|
|
mrsteven
Veteran
Joined: 04 Jul 2003
Posts: 1939
|
| Posted: Tue Feb 28, 2006 12:51 pm Post subject: |
|
|
Also, das ganze läuft über Produktionsregeln. Schau dir auch mal den Wikipedia-Artikel über EBNF an. Eine einfache Grammatik, die nur mathematische Ausdrücke aus natürlichen Zahlen kennt, schaut damit z.B. so aus:
| Code: | Ausdruck ::= Summe.
Summe ::= Produkt {("+" | "-") Produkt}.
Produkt ::= Faktor {("*" | "/") Faktor}.
Faktor ::= Zahl | ("(" Summe ")").
Zahl ::= (Ziffer_a_Null {Ziffer}) | "0".
Ziffer_a_Null ::= "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9".
Ziffer ::= "0" | Ziffer_a_Null. |
Das heißt hier: Ein mathematischer Ausdruck ist eine Summe. Eine Summe besteht wiederum aus zwei Produkten mit einem Plus oder Minus zwischendrin usw. Die einzelnen Regeln werden dann verschachtelt und teilweise auch rekursiv angewendet.
Der Ausdruck 3*(2+4*9)-6 lässt sich dann so zerlegen:
- Das Ganze ist laut oben stehenden Produktionsregeln eine Summe, nämlich aus 3*(2+4*9) und 6.
- Wir machen weiter mit dem linken Summand, also 3*(2+4*9). Dieser ist ein Produkt aus 3 und (2+4*9).
- Die Zahl 3 ist ein Faktor, den wir wie eine Zahl behandeln dürfen.
- Als Zahl gilt alles, was entweder 0 ist, oder aus einer Ziffer ohne Null und beliebig vielen Ziffern (diesmal einschließlich der 0) besteht.
- Wir machen weiter mit dem Klammerausdruck (2+4*9), dieser ist eine Summe mit Klammern links und rechts.
- 2+4*9 ist eine Summe aus den Produkten 2 und 4*9.
- Die 2 ist ein Produkt aus einem Faktor, der 2.
- Die 2 dürfen wir wieder als Zahl behandeln, siehe 4.
- Das zweite Produkt aus 6. besteht aus den Faktoren 4 und 9.
- 4 und 9 sind wieder Zahlen, siehe 4. Nun sind wir fertig, da wir alle Nichtterminal-Symbole in Terminal-Symbole aufgelöst haben.
Die Unterscheidung zwischen Produkt, Summe und Faktor wird vor allem dann wichtig, wenn du wirklich einen Parser bauen willst, denn so stimmt dann die Reihenfolge, in der die einzelnen Teile ausgewertet werden, also Klammern zuerst, Punkt vor Strich usw.
Ich habe hier noch einen alten, einfachen Parser rumliegen, der die Grundrechenarten und Potenzieren mit Fließkommazahlen beherrscht. Kann ich dir bei Interesse mal schicken (melde dich am besten per PM).
Suche auch mal nach "rekursiver Abstieg", da findet man einiges.  |
|
| Back to top |
|
|
_hephaistos_
Advocate
Joined: 07 Apr 2004
Posts: 2694
Location: salzburg, austria
|
| Posted: Tue Feb 28, 2006 1:06 pm Post subject: |
|
|
hi,
jo, EBNF is cool
aber ein stack solltes auch tun...
da kannst dann poppen und pushen was das zeug hält
sofern das richtige "zeichen" kommt....
cheers
_________________
-l: signature: command not found |
|
| Back to top |
|
|
Gekko
l33t
Joined: 29 Oct 2002
Posts: 773
|
| Posted: Sat Jul 29, 2006 10:47 am Post subject: |
|
|
Danke für die Informationen Jungs,
ich habs jetzt mit nem Kellerautomaten (Stack) gelöst. |
|
| Back to top |
|
|
flash49
Apprentice
Joined: 12 Feb 2005
Posts: 233
|
| Posted: Sat Jul 29, 2006 2:35 pm Post subject: |
|
|
Ich habe hier noch ein altes Vorlesungsscript, falls du dich etwas mehr mit Compilerbau beschäftigen willst/mußt: http://wwwags.informatik.uni-kl.de/lehre/ss00/SystemSoftware/ Es ist eher praktisch orientiert und ganz hilfreich, falls du mal einen echten Compiler bauen willst. Wir hatten damals einen kleinen Compiler Pascal zu Mips-Assembler geschrieben.
| Gekko wrote: | Danke für die Informationen Jungs,
ich habs jetzt mit nem Kellerautomaten (Stack) gelöst. |
Das wäre dann im Prinzip ein LL(1) Parser (diesen schreibt man meistens, wenn man intuitiv an die Sache rangeht) oder ein LR(X) Parser für eine (vereinfachte) Variante der deterministisch kontextfreien Sprachen.
 Eine Anmerkung noch, bevor jemand es vergeblich versucht: Ein regulärer Ausdruck reicht nur für Typ3 Sprachen aus. Als Faustregel gilt, daß alles was nach einer Klammerstruktur z.B. (((()))(())), HTML, XML aussieht mindestens deterministisch kontextfrei ist und sich immer ein Beispiel konstruieren läst, das der RA nicht abdeckt. |
|
| Back to top |
|
|
Freiburg
Guru
Joined: 19 Jun 2004
Posts: 504
Location: Freiburg
|
|
| Back to top |
|
|
|
|
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
|
|
Deutsches Forum (German) 
