Parser / Recursive Descent Übersetzer

[xMänneken]

N`Abend,

bin auf der Suche nach einem einfachen Parser/Recursive Descent Übersetzer, also als C++ Code.

Habe schon das Netz durchsucht und zwar auch 1-2 Beispiele gefunden, die waren aber sehr umfangreich, also bin ich bei Euch gelandet
Suche also eher etwas einfaches als Anschauungsobjekt, damit ich da mal durchsteige

Nehme sonst auch gerne Pseudocode

Danke!!

[ronny]

boost::spirit ist eine möglichkeit - http://boost.org/libs/spirit/index.html

[xMänneken]

r0nny schrieb:

boost::spirit ist eine möglichkeit - http://boost.org/libs/spirit/index.html

Der sieht auch ganz schön mächtig aus
Würde ja gern mal selbst einen kleinen erstellen, für einfache mathematische Aufgaben oder so. Deshalb wäre ein einfacher, fertiger sehr hilfreich Könnte man die Funktionsweise genau erkennen.

[Konrad Rudolph]

Tip: Schau Dir mal ANTLR an, insbesondere die von ANTLR erstellten Codes, das sind wunderschöne Recursive Descent Parser. Schön ist auch die Einführung des Autors in die manuelle Konstruktion von Recursive Descent Parsern:

http://www.antlr.org/book/byhand.pdf

(Ist zwar alles Java, ist aber recht einfach nach C++ übertragbar.)

[xMänneken]

Moin,

so, habe mich nun mal rangemacht und probiert einen Parser zu schreiben, der einen Term - erlaubt sind Ziffern, + , -, *, ( und ) - in infix einliest und in postfix wieder ausgibt.

Soweit bin ich bisher gekommen...hoffe das ist soweit richtig, habe mich bemüht den Code zu erklären, hoffe jemand steigt durch
Für Verbesserungen bin ich jederzeit offen

Problem ist nun die Funktion stack.
Operanden werden ja sofort in den Postfix-String geschrieben. (Funktion push)
Diese Regeln soll der stack anwenden:
http://www.cz.j.th.schule.de/html_inc/schule/lehrer/privat/mirko_koenig/postfix/postfix.htm#in2post

Jemand eine Idee ? Wäre dufte Danke!

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include<iostream.h>
#include<string.h>

char	lookahead;		// nächstes Zeichen in expression
int     pos = 0;		// aktuelle Positon des Zeichens
char    expression[20]; // der zu parsende Ausdruck
int		fehler = 0;		// Fehler-Index
int		klammer = 0;	// Klammer-Fehler wenn am Ende !=0
int		stellepost = 0;	// Stelle im Postfix-String
int		stellestack = 0;// Stelle im Operanden Stack

char aktuell;
char postfix[20];	// Postfix-String
char operanden[10];	// Operanden-Stack

void push(char reindamit); // Schreibe Zahlen in Postfixstring
void stack(char aufnstack);// Stack für Operanden und Klammern

// Grammatik-Anfang
void expr();		// epxr -> term exprrest
void exprrest();	// exprrest -> + term exprrest | - term exprrest | NIX
void term();		// term -> factor termrest
void termrest();	// termrest -> * factor termrest | NIX
void factor();		// factor -> + factor | - factor | (expr) | number
void number();		// number -> 0.....9
// Grammatik-Ende

void consume(char); // aktuelles Zeichen abarbeiten, pos++
void error(int);	// werfe Fehler aus

// Fehler-Anfang
void error(int fehler)
{
	switch(fehler)
	{
	case 1: cout << "Fehler bei number()\n "; break;
	case 2: cout << "Fehler bei consume()\n"; break;
	case 3: cout << "Klammerfehler\n "; break;
	}

}
// Fehler-Ende

// Expr-Anfang
void expr()
{
	term();
	exprrest();
}
// Expr-Ende

// Epxrrest-Anfang
void exprrest()
{
	switch( lookahead ) 
	{
		case '+' : case '-':
		stack(lookahead);
		consume( lookahead );
		term();
		exprrest();
		break;
	}

	switch( lookahead ) 
	{
		case ')' : klammer--;
		stack(lookahead);
		consume( lookahead );
		break;
	}

}
// Epxrrest-Ende

// Term-Anfang
void term()
{
	factor();
	termrest();
}
// Term-Ende

// Termrest-Anfang
void termrest()
{
	switch( lookahead ) 
	{
		case '*' :
		stack(lookahead);
		consume( lookahead );
		factor();
		termrest();
		break;

		default:
        return;
	}
}
// Termrest-Ende

// Factor-Anfang
void factor()
{
	switch( lookahead ) 
	{
		case '+' : case '-':
		stack(lookahead);
		consume( lookahead );
		factor();
		break;
	}

	switch( lookahead ) 
	{
		case '(' : klammer++;
		stack(lookahead);
		consume(lookahead);
		expr();
		break;
	}

        number();	
}
// Factor-Ende

// Number-Anfang
void number()
{
	switch( lookahead ) 
		{
			case '0': case '1': case '2': case '3': case '4': case '5': case '6': case '7': case '8': case '9':
			push(lookahead);
			consume(lookahead);
			break;

			default:
			error(1);
			break;
			}
}
// Number-Ende

// consume-Anfang
void consume(char t) 
	{
		if(lookahead == t) 
			{
				//aktuell = lookahead;
				//stack(aktuell);
				pos++;
				lookahead = expression[pos];            
			}
		else
			error(2);
	}
// consume-Ende

// Push-Anfang
void push(char reindamit)
{

	postfix[stellepost]= reindamit;
	stellepost++;
}
// Push-Ende

//Stack-Anfang
void stack(char aufnstack)
{

}
//Stack-Ende

// Main-Anfang
void main()
{
	cout << "Bitte geben Sie einen Ausdruck in Infix-Notation ein:\n\n\t";
	gets( expression );

	lookahead = *expression;
	expr();

	// Klammer-Fehler
	if(klammer !=0)
		{
		error(3);
		}
	// Klammer-Fehler-Ende

	cout << pos;
	int i = 0;
	cout << "Ausgabe:  ";
	while(i <= pos)
		{
	  cout << postfix[i];
	  i++;
		}
}
// Main-Ende

[Konrad Rudolph]

xMänneken schrieb:

Jemand eine Idee ? Wäre dufte Danke!

Wo ist denn da Dein Problem? Die Regeln sind doch recht gut beschrieben. Das kann man mit nem Switch erschlagen.

void stack(char aufnstack)
{
    switch (aufnstack) {
       case '(': push('('); break;
       case ')':
           for (; ;) {
               char zeichen = pop();
               if (zeichen == '(') break;
               ausgabe(zeichen);
           }
           break;
       case '+', '-', '*', '/':
           // Als Übung Dir überlassen. ;-)
    }
}