Linksrekursion beseitigen für Dummies

Ethon

Hoi,
ich versuche gerade mich in Compilerbau einzuarbeiten.

Habe es mir mal als Testaufgabe gesetzt einen kleinen Interpreter zu schreiben, der C-Style Arithmetik beherrscht. Das möchte ich mit einem Recursive-Descent Parser tun.

Nur scheine ich ernsthaft zu dumm zum Beseitigen von Linksrekursionen zu sein. Gibt es denn nicht irgendwo im Netz ein konkretes Beispiel, wie das zu machen ist, ohne dass das Beispiel zu trivial ist? Mathematische Notation schön und gut, nur macht das den Knoten im Hirn gerade nur größer, wenn man gerade nix peilt ...

Falls jemandem langweilig ist, wie könnte denn eine Grammatik aussehen, die frei von Linksrekursionen ist und das hier korrekt parsen könnte?

-(abc++ - --bcd) - 12 * 3;

Danke & Grüße,
Ethon

Shade Of Mine

Womit hast du denn Probleme?

Fertige Syntaxdefinitionen gibt es fuer so ziemlich alles.

Ethon

Ich glaube ich habe Probleme das zu formulieren weil ich das gerade selbst nicht weiß. Denke ich muss erstmal schlafen.

Ist es in der Praxis vernünftig möglich, bei einer Sprache wie C mit 15 Operatorenprioritätsklassen die ganze Prioritätensache über die Grammatik abzuregeln?

Shade Of Mine

Ethon schrieb:

Ist es in der Praxis vernünftig möglich, bei einer Sprache wie C mit 15 Operatorenprioritätsklassen die ganze Prioritätensache über die Grammatik abzuregeln?

Wie wuerdest du es sonst machen, wenn nicht ueber die Grammatik?

Bassmaster

Hoi ist hier vielleicht was bei? http://www.c-plusplus.net/forum/201764

Th69

Hallo Ethon,

unter Extended Backus-Naur-Form (EBNF)-Parser habe ich auch eine EBNF-Definition für die Sprache "C" hinterlegt. Darfst du dir gerne als Vorlage benutzen.

Bashar

Shade Of Mine schrieb:

Ethon schrieb:

Ist es in der Praxis vernünftig möglich, bei einer Sprache wie C mit 15 Operatorenprioritätsklassen die ganze Prioritätensache über die Grammatik abzuregeln?

Wie wuerdest du es sonst machen, wenn nicht ueber die Grammatik?

http://en.wikipedia.org/wiki/Operator-precedence_parser

Th69 schrieb:

Hallo Ethon,

unter Extended Backus-Naur-Form (EBNF)-Parser habe ich auch eine EBNF-Definition für die Sprache "C" hinterlegt. Darfst du dir gerne als Vorlage benutzen.

Hi Th69,

dein Parser löst "nur" das Wortproblem, ist aber nicht in der Lage einen Syntaxbaum zu generieren, richtig?

Hintergrund:
Ich habe kürzlich auch einen Bottom-Up Parsergenerator für allgemeine Kontextfreie Grammatiken geschrieben. Der Parser ist auch in der Lage an den richtigen Stellen ein Callback aufzurufen, welches als Factory für Knoten in einem Syntaxbaum dient und vom Benutzer bereit gestellt wird. Genaugenommen zwei Callbacks, einmal für Terminale (Blätter im baum) und einmal für Nichtterminale (Innere Knoten).

Als Anwendung des Generators habe ich einen EBNF-Parser geschrieben.
D.h.: EBNF mit einer Grammatik definiert und den EBNF-Parser generieren lassen.
Eine Eingabedatei für den generierten Parser (in EBNF-Syntax) wird dann umgewandelt in eine Kontextfreie Grammatik, woraus der Generator wiederum einen Parser bauen kann.

Beispiel: Die EBNF Eingabe (beliebig viele wiederholungen des Terminals "a")

#Parser
{
	1: A =  {"a"};

}

wird umgewandelt in (mit neuem Nichtterminal C1)

A ::= C1;
C1 ::= 'a' C1;
C1 ::= <EPS>;

und kann somit direkt durch den Parsergenerator geschickt werden.
Die anderen EBNF-Operatoren werden ähnlich umgewandelt und es werden neue Produktionen geniert.

Mein Problem: Ich verliere die Möglichkeit, das Callback zu implementieren. Normalerweise kann der User mit einer ID wissen, welches Nichtterminal oder Terminal zum jeweiligen Zeitpunkt auf dem Stack liegt und weiß somit welcher Knotentyp erstellt werden muss. Durch die automatische Einführung neuer Produktionen und Nichtterminale im Zuge der Umwandlung (EBNF->Grammatik) geht diese Möglichkeit verloren.

Hast Du dafür eine Lösung? Oder sonst wer?

Hier noch ein komplexeres Beispiel, welches das Problem verdeutlicht.
EBNF-Eingabe (die Labels am Zeilenanfang sind IDs der Nichtterminale für das Callback):

10: Ausdruck =EinfacherAusdruck [RelOp EinfacherAusdruck] ;
20: EinfacherAusdruck = [AddOp] Term { AddOp Term } ;
30: Term = [ "NOT"] Faktor { MulOp Faktor } ;
40: Faktor =Variable | "(" Ausdruck ")" ;
50: Variable = "a" | "b" | "c" | "d" | "e" | "f" ;
60: AddOp="+" | "-";
70: MulOp="*" | "/" | "DIV" | "MOD" ;
80: RelOp="=" | "<>" | "<" | "<=" | ">" | ">=";

Umwandlung in eine Gramamtik:

Ausdruck ::= EinfacherAusdruck S1;
S1 ::= RelOp EinfacherAusdruck;
S1 ::= <EPS>;
EinfacherAusdruck ::= S2 Term C1;
S2 ::= AddOp;
S2 ::= <EPS>;
C1 ::= AddOp Term C1;
C1 ::= <EPS>;
Term ::= S3 Faktor C2;
S3 ::= 'NOT';
S3 ::= <EPS>;
C2 ::= MulOp Faktor C2;
C2 ::= <EPS>;
Faktor ::= A1;
A1 ::= Variable;
A1 ::= '(' Ausdruck ')';
Variable ::= A6;
A2 ::= 'a';
A2 ::= 'b';
A3 ::= A2;
A3 ::= 'c';
A4 ::= A3;
A4 ::= 'd';
A5 ::= A4;
A5 ::= 'e';
A6 ::= A5;
A6 ::= 'f';
AddOp ::= A7;
A7 ::= '+';
A7 ::= '-';
MulOp ::= A10;
A8 ::= '*';
A8 ::= '/';
A9 ::= A8;
A9 ::= 'DIV';
A10 ::= A9;
A10 ::= 'MOD';
RelOp ::= A15;
A11 ::= '=';
A11 ::= '<>';
A12 ::= A11;
A12 ::= '<';
A13 ::= A12;
A13 ::= '<=';
A14 ::= A13;
A14 ::= '>';
A15 ::= A14;
A15 ::= '>=';

Ethon

Danke für die Antworten, werde sie mal der Reihe nach durchsehen.

Hab mal etwas rumprobiert, so ist mein Ansatz ... hänge gerade bei den Postfix-Ausdrücken und weiß nicht genau wo ich am Besten Klammerung / Literale / Variablen hinpacke.

Expression =            CommaExpression
CommaExpression =       AssignmentExpression, { Comma, AssignmentExpression }
AssignmentExpression =  TernaryCondExpression, { AssignmentOperator, TernaryCondExpression }
TernaryCondExpression = LogicalOrExpression, { LogicalOrExpression, QuestionMark, LogicalOrExpression, Colon, LogicalOrExpression }
LogicalOrExpression =   LogicalAndExpression, { DoubleOr, LogicalAndExpression }
LogicalAndExpression =  BitOrExpression, { DoubleAnd, BitOrExpression }
BitOrExpression =       BitXorExpression, { Or, BitXorExpression }
BitXorExpression =      BitAndExpression, { Xor, BitAndExpression }
BitAndExpression =      CompExpression, { And, CompExpression }
RelEqualExpression =    RelGreaterExpression, { RelEqualOperator, RelGreaterExpression }
RelGreaterExpression =  RelLesserExpression, { RelGreaterOperator, RelLesserExpression }
RelLesserExpression =   BitShiftExpression, { RelLesserOperator, BitShiftExpression }
BitShiftExpression =    AddSubExpression, { BitShiftOperator, AddSubExpression }
AddSubExpression =      MulDivModExpression, { AddSubOperator, MulDivModExpression }
MulDivModExpression =   UnaryPrefixExpression, { MulDivModOperator, UnaryPrefixExpression }
UnaryPrefixExpression = ???????????????
UnaryPostfixExpression = ???????????????

AssignmentOperator   =  Assign | PlusAssign | MinusAssign | MulAssign | DivAssign |
                        ModAssign | AndAssign | XorAssign | OrAssign |
                        LShiftAssign | RShiftAssign
RelEqualOperator     =  Equal | NotEqual
RelGreaterOperator   =  Greater | GreaterEqual
RelLesserOperator    =  Lesser | LesserEqual
BitShiftOperator     =  LShift | RShift
AddSubOperator       =  Plus | Minus
MulDivModOperator    =  Mul | Div | Mod
UnaryPrefixOperator  =  DoublePlus | DoubleMinus | Not | Invert | TypeCast |
                        Mul | And | Plus | Minus

TypeCast             =  LParen, Identifier, RParen
SizeOfExpression     =  SizeOf, (LParen), UnaryPostfixExpression, (RParen)

SimpleExpression  = Ident | StringLiteral | IntLiteral | CharLiteral | FloatLiteral

Th69

Hallo µ,

sorry, hatte deine Frage zwar gestern gelesen, aber dann doch keine Zeit zu antworten und hätte es wohl auch vergessen (wenn du mir nicht die PM geschickt hättest)...

Ja, der EBNF-Parser erzeugt intern keinen Syntax-Baum, sondern dient nur dazu die syntaktische Korrektheit eines Textes (Code) anhand einer gegebenen EBNF-Definition zu überprüfen (d.h. er wandert intern einfach über die EBNF-Definition bis er entweder einen Fehler entdeckt oder aber das Ende der Definition erreicht hat).

Aber dein Parsergenerator hört sich sehr interessant an, denn so etwas wollte ich auch schon immer mal programmieren.
Ich hätte dies dann sogar ex3emplarisch für C++ machen wollen, um darauf aufbauend dann verschiedene Programme entwickeln zu können.

Bei weiteren Fragen melde ich mich später noch mal, ich muß jetzt ersteinmal Path of Exile (PoE) zocken: HC Party Event.

Th69 schrieb:

Aber dein Parsergenerator hört sich sehr interessant an, denn so etwas wollte ich auch schon immer mal programmieren.

Danke für Deine Antwort.
Nach längerem Nachdenken fällt mir nur die Möglichkeit ein, vom Benutzer weitere IDs in den EBNF-Code an kritischen Stellen einstreuen zu lassen. Eben so, dass er auch in der Lage ist, in der Factory die "richtigen" Knoten des Syntaxbaums zu generieren, gemäß der jeweiligen ID.
Syntaxgerichtete Übersetzungen sind in Parsergeneratoren sehr verbreitet. Aber mir gefällt das Konzept nicht, in eine externen Datei Quellcode der Programmiersprache einzustreuen, in der der Parser ausgeführt werden soll. Ich möchte also die Kopplung zwischen Parserdefiniton und Aktionen soweit es geht entfernen. Die Aktionen sind dabei an erster Stelle der Aufbau des Syntaxbaumes.

In den nächsten 2-3 Wochen bin ich nicht in der Nähe eines Compilers, aber das Projekt werde ich nächstes Jahr Hobbymäßig weiterführen. Dabei hätte ich Interesse an einem Mitstreiter mit ein wenig Vorerfahrung. Wenn Interesse besteht, melde dich einfach.

An einen Wechsel auf C++ habe ich auch gedacht aber wieder verworfen.
Das Projekt muss vielleicht überarbeitet werden, aber von C# möchte ich mich dabei nicht abwenden. Dafür ist die Sprache zu gut und zielführend. C++ ist mir dafür zu krank.

Th69

Hallo µ,

ich meinte bei "C++" die Sprache für den ich die EBNF-Syntax entwickeln wollte, nicht die Implementierungssprache (wobei ich damals hauptsächlich selber noch in C++ programmiert hatte, aber jetzt bevorzuge ich auch C# ;-).

Also ansehen würde ich mir dein Projekt schon mal gerne. :xmas1: