Tool um Ausdrücke zu generieren

Real_PsychoDAD

Hallo,

kennt jemand von euch ein Programm/Skript, mit denen man alle nach einer formalen Grammatik (Chomsky) definierten Ausdrücke (einer best. Länge) generieren kann? Also z.B. schreibe ich in eine Datei

Expr -> (Expr)
Expr -> Expr + Expr
Expr -> C
C -> x
C -> 0
C -> 1
C -> 2

und das Programm generiert mir dann Ausdrücke, wie z.B:

x
0
1 + x
(0 + 1)+x
x + x + (2 + (1 + x))

usw.

Danke, Stefan

PS: Am liebsten wären mir kleine schlanke (Linux-) Kommandozeilenprogrämmchen.

hustbaer

Nö, kenne ich nicht, aber sowas ist schnell selbst geschrieben.
In Python/PHP/Perl etc. ganz ganz einfach, aber sogar in C++ kein wirkliches Ding.
Mach mal

Apollon

Aehm... Dir ist klar, dass die generierte Menge unendlich ist?

hustbaer

Ups, das "alle" hab ich übersehen, das macht die Aufgabe etwas weniger trivial *pfeiff*

Die Menge ist trotzdem nicht unendlich, da er "Ausdrücke einer bestimmten Länge" geschrieben hat.

CStoll

Selber schreiben lautet die Devise:

typedef pair<string,string> rule;

string use_rule(rule r,string orig)
{
  size_t p=orig.find(r.first);
  if(p!=string::npos) orig.replace(p,rule.first.length(),rule.second);
  return orig;
}

void construct(string start)
{
  if(start.length()>max_length) return;

  int possible_rules=0;
  for(int i=0;i<rule_count;++i)
  {
    string next=use_rule(rule[i],start);
    if(next!=start)
    {
      ++possible_rules;
      construct(next);
    }
  }
  if(possible_rules==0)
    fout<<start<<endl;
}

Real_PsychoDAD

Danke für die vielen Antworten!

@CStoll

Ich hab deinen C++-Code mal in ein folgendes Programm eingebunden:

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

using namespace std;

const int max_length = 10;

typedef pair<string,string> rule;

vector<rule> rules;

string use_rule(rule r,string orig)
{
  size_t p=orig.find(r.first);
  if(p!=string::npos)
     orig.replace(p,r.first.length(),r.second);
  return orig;
}

void construct(string start)
{
  if(start.length()>max_length) return;

  int rule_count = rules.size();
  int possible_rules=0;
  for(int i=0;i<rule_count;++i)
  {
    string next=use_rule(rules[i],start);
    if(next!=start)
    {
      ++possible_rules;
      construct(next);
    }
  }
  if(possible_rules==0)
    cout<<start<<endl;
}

int main(void) {
   rules.push_back(rule("Expr", "(Expr)"));
   rules.push_back(rule("Expr", "Expr + Expr"));
   rules.push_back(rule("Expr", "C"));
   rules.push_back(rule("Expr", "x"));
   rules.push_back(rule("Expr", "0"));
   rules.push_back(rule("Expr", "1"));
   rules.push_back(rule("Expr", "2"));
   construct("Expr");
   return 0;
}

Und als Ausgabe kommt:

(((C)))
(((x)))
(((0)))
(((1)))
(((2)))
((C))
((x))
((0))
((1))
((2))
(C)
(x)
(0)
(1)
(2)
C
x
0
1
2

Scheint also irgendwie nicht ganz zu funktionieren, und hab jetzt auch keine Idee wo der Fehler liegt.

@hustbaer
Mit Perl/Python kenn ich mich nicht so aus, komme bisher mit AWK & Bash
super zurecht. Aber falls Du ein entsprechendes Skript dafür hast/kennst kannst es ja mal posten.

hustbaer

Nö, ich kenne kein fertiges Script was etwas ähnliches macht. Ich meinte bloss irgendeine der mächtigeren Scriptsprachen weil man solche und ähnliche Dinge in denen meist recht einfach implementieren kann, alleine die ganzen Textverarbeitungsfunktionen die die mitbringen.

Ich denke es fehlt noch die Unterscheidung zwischen Grammatikelementen und "Strings" (for lack of a better word).

Die Grammatik müsste also wohl schonmal eher so aussehen:

Expr: "(" Expr ")"
Expr: Expr " + " Expr
Expr: C
C: "x"
C: "0"
C: "1"
C: "2"

Expr und C sind dabei die "Elemente", alles in "" sind dann eben "Strings", also Dinge auf die keine weiteren Regeln angewendet werden können. Und das Programm müsste wohl alle "Elemente" ersetzen, solange bis im Output nurmehr "Strings" übrig sind, denn etwas wie "Expr + 0" wird wohl als mögliche Kombination nicht erwünscht sein. Dabei müsste dann für jedes "Element" welches noch übrig ist auch jede passende Rule angewendet werden. Was man als "Länge" definiert ist dabei dann wohl etwas schwierig, aber vielleicht einfach die Anzahl der "Strings" im Output. Wenn man dann "leere" Rules verbietet lässt sich das Abbruchkriterium recht einfach festlegen, nämlich "(#Elemente + #Strings) > N".

Wenn man die Länge des fertigen Strings als Limit verwenden möchte kann man einfach jedes "Element" als 1 Zeichen zählen, da ja "leere" Rules verboten sind. Wenn keine "Elemente" mehr übrig sind prüft man die Länge des fertigen Strings nochmal und verwirft ihn ggf.

Real_PsychoDAD

Das Programm CStoll ist doch korrekt, mein Fehler war nur die Abbruchbedingung

if(start.length()>max_length) return;

weswegen die Regel Expr -> Expr + Expr nie angewendet wurde, da max_length zu gering gesetzt war, wenn man max_length entsprechend erhöht erzeugt er auch alle Ausdrücke bzw. eine bessere Unterscheidung wäre halt nur die Wörter zu zählen
(was ich ja eigentlich irgendwie im Hinterkopf hatte und trotzdem den "Fehler" nicht sah), man muss nicht extra zwischen Grammatikelementen und "Strings" unterscheiden.

Danke nochmal allen Beteiligten!

hustbaer

Ups, sorry, ja. Das Programm dürfte wirklich korrekt sein, ich habs nur zuerst nicht ganz verstanden, der Name "possible_rules" hat mich verwirrt...

Und die Unterscheidung zwischen Text und Grammatikelementen ist nicht notwändig, könnte aber das Programm deutlich schneller machen -- was aber natürlich nur wichtig bzw. sinnvoll ist wenn es nicht sowieso schon schnell genug läuft. Und natürlich dürfen dann im "Text" keine Namen von Grammatikelementen auftauchen, ist aber logisch.

finix

hustbaer schrieb:

Ich denke es fehlt noch die Unterscheidung zwischen Grammatikelementen und "Strings" (for lack of a better word).

Du meinst die Unterscheidung zwischen den beiden Grammatikelementen Nichtterminalsymbol und Terminalsymbol?

Ich frage mich nur wie du das Programm dadurch schneller machen willst... korrekt, ja, aber schneller durch mehr Komplexität?