require "Warshall" ## # Author:: Sebastian Bauer # Author:: Alexander Jede # Author:: Sergej Krun # Author:: René Wickmann # # Grammatiken # =========== # # Dieses Programm liest einen Regelteil einer SIC-Grammatik ein, # zerlegt ihn in seine Bestandteile und stellt einige Methoden # zur Verfügung um mit den so entstandenen Teilen zu arbeiten. ## # Die Klasse Symb repräsentiert die Symbole einer Grammatik. # # Ihre Attribute sind: # - @name -> die Bezeichnung des Symbols in der Grammatik als String # - @terminal -> Boolean der angibt ob das Symbol ein Terminal ist class Symb attr_accessor :terminal ## # Konstruktor von Symb: # Setzt @name gleich dem übergebenen String und setzt @terminal standardmäßig auf True. # # Parameter: # - name -> Ein String, welcher das Symbol geschrieben darstellt. def initialize(name) @name = name @terminal = true end ## # Getter für @name: def getName @name end ## # to_s von Symb: # # Return: # -> @name def to_s @name end ## # == Operator von Symb # # Return: # -> True, wenn die @name-Attribute der Symbole = sind # -> False, wenn zweites Symbol nil ist, oder @name-Attribut nicht überinstimmt. def ==(anOther) if (anOther!=nil) then return (@name == anOther.getName) else return false end end ## # Operator von Symb # # Return: # -> 1 wenn das erste @name Attribut länger ist # -> 0 wenn beide gleichlang sind # -> -1 wenn das erste @name Attribut kleiner ist # -> false, wenn das zweite Symbol nil ist def (anOther) if (anOther!=nil) then return (@name anOther.getName) else return false end end end ## # Diese Klasse repräsentiert die einzelne Alternative auf der # rechten Seite einer Regel. Sie besteht aus einem Array von # Symbolen. # # Ihre Attribute sind: # - @symbs -> Das Array der Symbole (Positon nach ihrem Auftreten) class Alternative ## # Konstruktor von Alternative: # # Der Konstruktor zerlegt einen übergebenen String einer rechten # Seite einer Regel an den Leerstellen in Teilstrings. Diese # werden dem Konstruktor der Klasse Symb übergeben und die neuen # Symbole in das Array @symbs gesteckt. # # Parameter: # - alt -> Ein String einer Regelalternative (Standardwert = nil) def initialize(alt = nil) @symbs = Array.new # Nur wenn alt nicht nil ist müssen die Symbole abgelegt werden if alt != nil # Trennt den String an jeder Leerstelle alt.split(/\s+/).each { |symb| symb = symb.delete " " # Nur wenn der nun erkannte Teilstring nicht nur aus Leerzeichen bestanden hat wird ein # neues Symbol mit dem Teilstring erstelt und im @symbs-Array abgelegt. if symb != "" @symbs.push(Symb.new(symb)) end } end end ## # Getter für @symbs def getSymbols return @symbs end ## # Gibt die Anzahl der Symbole im @symbs-Array zurück # # Return: Anzahl der Symbole in der Alternative def countSymbols return @symbs.size end ## # [i] Operator von Alternative # # Return: (i-1)tes Symbol der Alternative def [] (ind) return @symbs[ind] end ## # Oerator von Alternative # # Return: # -> 1 wenn die erste Alternative.to_s länger ist # -> 0 wenn beide gleichlang sind # -> -1 wenn die erste Alternative.to_s kleiner ist. # -> false, wenn die zweite Alternative nil ist def (anOther) return (@symbs.to_s anOther.getSymbols.to_s) end ## # to_s von Alternative # # Return: Alle Symbole des @symb-Arrays mit to_s geschrieben und mit je einem Leerzeichen getrennt. def to_s res = String.new # Jedes Symbol aus @symbs an den String anfügen @symbs.each{ |symb| res = res+" "+symb.to_s } res end ## # Prüft ob diese Alternative eine Epsilon-Alternative ist. Dies ist der Fall, wenn sie keine # Symbole enthält also @symbs leer ist. # # Return: # -> Boolean der Angibt ob es eine Epsilon-Alternative ist def isEpsilon @symbs.empty? end end ## # Diese Klasse repräsentiert die einzelnen Regeln. Jede Regel besteht aus # einem Symbol als linker Regelseite und einem Array mit Alternativen als # rechter Seite der Regel. # # Ihre Attribute sind: # - @symbol -> Das Symbol der linken Regelseite # - @alts -> Array aller Alternativen class Rule ## # Konstruktor von Rule: # Zerlegt eine als String in SIC-Format gegebene Regel in ihre Bestandteile und legt sie in den # Attributen @symbol und @alts entsprechend ab. def initialize(rule) leftside, rightside = rule.split(/\s*->/) @symbol = Symb.new(leftside.strip) @symbol.terminal = false @alts = Array.new # Wenn auf der rechten Regelseite nichts steht wird eine Epsilon-Alternative angelegt. if rightside == nil @alts.push Alternative.new() # Ansonsten wird die rechte Seite an einem Zeilenumbruch, belibig vielen Blanks und "|" # in die einzelnen Alternativen zerlegt und weiterbearbeitet else # Für jede der so gefundenen Alternativen wird geprüft ob sie Epsilon-Alternativen sind. rightside.split(/\n\s*\|/).each { |a| # Wenn es keine Epsilon-Alternative ist wird eine neue Alternative erzeugt und in # @alts abgelegt. if (a.delete " ") != "" @alts.push Alternative.new(a) # Andernfals wird eine neue Epsilon-Alternative erzeugt und abgelegt. else @alts.push Alternative.new(nil) end } end end ## # Getter für @symbol def getSymbol return @symbol end ## # Getter für @alts def getAlts return @alts end ## # Gibt die Anzahl der Alternativen im @alts-Array zurück # # Return: Anzahl der Alternativen einer Regel def countAlts return @alts.size end ## # [i] Operator von Rule # # Return: (i-1)te Alternative der Regel def [] (ind) return @alts[ind] end ## # to_s von Rule # # Return: # -> Die Regel im SIC-Format def to_s res = @symbol.to_s+" ->" # Jede Alternative an den String anfügen @alts.each_index{|i| # Wenn noch Alternativen folgen anfügen mit Zeilenumbruch und "|" if i != @alts.length-1 res = res + " " + @alts[i].to_s + "\n |" # sonst nur anfügen der Alternative.to_s else res = res + " " + @alts[i].to_s end } res end ## # Prüft ob aus einer Regel direkt(!) Epsilon abgeleitet werden kann (wenn entweder keine Alternativen # vorhanden sind oder eine dieser Alternativen eine Epsilon-Alternative ist). # # Return: # -> Boolean der angibt, ob eine direkte Epsilon-Ableitung möglich ist oder nicht. def isEpsilon # Wenn keine Alternativen vorhanden sind wird true zurückgegeben, if @alts.empty? return true # ansonsten muss jede Alternative einzeln geprüft werden. else @alts.each{ |alt| # Wenn die Alternative Epsilon-Alternative ist wird true zurückgegeben. if alt.isEpsilon return true end } end return false end ## # Die Methode erzeugt Ausdrucksgrammatiken aus Kurzangaben. # * Die Kurzangaben sind eine Folge von Zeilen, die jeweils ein Operatortoken (z.B. addOp) in seinen Eigenschaften beschreiben. # * Bei binären Operatortoken hat die Zeile den Aufbau: ; # steht für left, right oder none und legt die Assoziativität des # Operators fest; none besagt, daß keine Assoziativität vorliegt und daher # bei mehr als einem Operator voll geklammert werden muß. # * Bei unären Operatortoken hat die Zeile den Aufbau: ; # steht für pre oder post und legt fest, ob der Operator vor oder nach dem Operanden steht. # * Die Operatorzeilen sind nach wachsender Präzedenz angeordnet, d.h. # die erste Zeile gehört zu dem Operatortoken, das am schwächsten bindet. # * Die letzte Zeile hat die Form: atom , ..., # und führt die atomaren Bestandteile des Ausdrucks ein. # * Die erste Zeile hat die Form: name # und führt den Namen der Ausdrucksgrammatik ein, mit dem alle erzeugten Nonterminals beginnen. def Rule.from_Yacc(input) i = 1 output = "" puts input + "\n" zeilen = input.split("\n") name = zeilen[0].split[1] # Erste Zeile output += name + " -> " + name + i.to_s + "\n" # Mittlere Zeilen zeilen.delete_at(0) zeilen.each do |zeile| optoken = zeile.split[0] operator = zeile.split[1] if optoken == "left" output += name + i.to_s + " -> " + name + i.to_s + " " + operator + " " + name + (i+1).to_s + "\n" output += " " * (name + i.to_s).length + " | " + name + (i+1).to_s + "\n" i += 1 elsif optoken == "right" output += name + i.to_s + " -> " + name + (i+1).to_s + " " + operator + " " + name + i.to_s + "\n" output += " " * (name + i.to_s).length + " | " + name + (i+1).to_s + "\n" i += 1 elsif optoken == "none" output += name + i.to_s + " -> " + name + (i+1).to_s + " " + operator + " " + name + (i+1).to_s + "\n" output += " " * (name + i.to_s).length + " | " + name + (i+1).to_s + "\n" i += 1 elsif optoken == "pre" output += name + i.to_s + " -> " + operator + " " + name + i.to_s + " " + "\n" output += " " * (name + i.to_s).length + " | " + name + (i+1).to_s + "\n" i += 1 elsif optoken == "post" output += name + i.to_s + " -> " + name + i.to_s + " " + operator + " " + name + (i+1).to_s + "\n" output += " " * (name + i.to_s).length + " | " + name + (i+1).to_s + "\n" i += 1 end end # Letzte Zeile output += name + i.to_s + " -> " + "(" + name + 1.to_s + ")" +"\n" atome = zeilen[zeilen.size-1].split(/,\s|\s/) atome.delete_at(0) atome.each do |atom| output += " " * (name + i.to_s).length + " | " + atom + "\n" end puts output end ## # liefert die Relation zu einer Regel def toRel links = @symbol tmpMenge = Menge.new(getAlts) tmpRel = Relation.new([[]]) tmpMenge.each{|i| i.getSymbols.each{|j| tmpRel.addPaar!(links.to_s, j.to_s )}} return tmpRel end end ## # Diese Klasse repräsentiert eine komplette Grammatik, mit Regeln, (Non-)Terminalsymbolen # und einem Startsymbol. # # Ihre Attribute sind: # - @rules -> Alle Regeln in einem Hash (Schlüßel ist das Symbol auf der Linken Seite) # - @terminals -> Array aller terminalen Symbole # - @nonterminals -> Array aller non-terminale Symbole # - @startsymbol -> Das Startsymbol der Grammatik # - @epsilonSymbole -> Menge aller Non-Terminal aus denen Epsilon abgeleitet werden kann class Grammar # Der Konstruktor der Grammatik bekommt den Regelteil einer SIC-Grammatik # als String übergeb und spaltet ihn an einer Leerzeile in die einzelne # Regel, welche wiederum an den Konstruktor von Rule übergeben wird. Die # so entstehenden Regeln kommen in den @rules-Hash. Das Symbol der ersten # Regel wird das Startsymbol der Grammatik, alle anderen linksseitigen # Symbole sind die Non-Terminale. Die Terminale ergeben sich aus allen Symbolen # der zu allen Regeln gehörigen Alternativen die nicht vom Namen her mit # einem Non-Terminal übereinstimmen. def initialize(gram) @rules = Hash.new @terminals = Array.new @nonterminals = Array.new gram.split(/\n\s*\n\s*/).each do |rule| newrule = Rule.new(rule) if @rules.size == 0 @startsymbol = newrule.getSymbol end @rules[newrule.getSymbol] = newrule @nonterminals.push(newrule.getSymbol) end @rules.each_value {|rule| rule.getAlts.each do |alt| alt.getSymbols.each do |symb| if @nonterminals.include?(symb) == false @terminals.push symb else symb.terminal = false end end end } @epsilonSymbole = epsilon_Symbole; end ## # Getter für @startsymbol def getStartsymbol return @startsymbol end ## # Getter für @terminals def getTerminals return @terminals end ## # Getter für @nonterminals def getNonterminals return @nonterminals end ## #Getter für @rules def getRules return @rules end ## # Getter für @epsilonSymbole def getEpsilonSymb return @epsilonSymbole end ## # Die to_s Methode liefert die Grammatik in einem String zurück. # Dabei steht jede Regel in einer Zeile und zwischen den Regeln ist eine Leerzeile. # Für das Format der Regeln, siehe Rule#to_s def to_s res = @rules[@startsymbol].to_s @rules.each_pair{|key,r| if key != @startsymbol res = res + "\n\n" +r.to_s end } res end ## # Liefert einen Array mit den Symbolen (Nonterminale), die Epsilon produzieren können. # def epsilon_Symbole res = Menge.new([]) # 1.Runde direkte Epsilon ableitungen finden @rules.each_pair {|name,rule| if rule.isEpsilon res.enthaelt?(name) ? () : (res.add(name)) end } # 2. - x. Runde Suche nach indirekten Ableitungen neues = true while neues neues = false @rules.each_pair {|name,rule| rule.getAlts.each {|alt| nureps = true alt.getSymbols.each {|symb| res.enthaelt?(symb) ? () : (nureps = false) } nureps and !(res.enthaelt?(name)) ? (res.add(name);neues=true) : () } } end return res end ## # Diese Methode ermöglicht das Speichern der Grammatik in eine Datei. # Als Format wird YAML ( http://www.yaml.org/ ) benutzt, somit ist die Datei im Plaintext und kann auch mit einem # einfachem Editor bearbeitet werden. *Vorsicht*: Dabei kann man die Formatierung beschädigen, so dass # die gespeicherte Grammatik nicht mehr geladen werden kann. # file - Der Pfad zu der Datei in Form eines Strings, in der die Grammatik gespeichert werden soll. # Sollte die Datei nicht vorhanden sein, wird sie erstellt. Ansonsten wird die Datei überschrieben! def save(file) require 'yaml' gramma = Grammar.new(to_s) File.open(file,"w"){|data| YAML.dump(gramma,data) } end ## # Diese Methode ermöglicht es eine in einer Datei abgespeicherte Grammatik wieder zu laden. # Ein mögliches vorgehen wäre, in dem man eine leere Grammar erstellt und davon die Methode Grammar#load_grammar # aufruft. Zum Beispiel:: # g = Grammar.new("") # g.load("/home/alex/SavedGrammar.yaml") # Grammar#load(file) - Der Pfad zu der Datei in Form eines String, in der die Grammatik gespeichert ist. # def load(file) require 'yaml' gramma = YAML::load(File.open(file)) if gramma.class == Grammar @rules = gramma.getRules @terminals = gramma.getTerminals @nonterminals = gramma.getNonterminals @startsymbol = gramma.getStartsymbol @epsilonSymbole = gramma.getEpsilonSymb else #raise "Wrong File.\n It was not a Grammar" end end ## # Diese Methode stellt eine SIC-compatible Grammatik in Form eines Strings her. # Zu Beginn werden die terminalen Zeichen aufgelistet, gefolgt von den nichtterminalen Zeichen, # dem Startsymbol und zum Schluss den Ableitregeln. # Vor jedem Abschnitt leitet eine Überschrift die jeweiligen Zeichen ein, der noch eine zusätzliche # Leerzeile folgt. def to_SIC res = "Terminals:\n\n" getTerminals.each{ |termsym| res += termsym.to_s + " " } res += "\n\nNonterminals:\n\n" getNonterminals.each{ |nonterm| res += nonterm.to_s + " " } res += "\n\nStartingsymbol:\n\n" + getStartsymbol.to_s res += "\n\nRules:\n\n" + to_s return res end # liefert die Relation zu einer Grammatik def toRel erg = Relation.new([[]]) getRules.each_key{|i| erg = erg.vereinigt(getRules[i].toRel)} return erg end # fügt eine Regel zur Grammatik hinzu def addRule(str) tempregel = str + self.to_s temp = Grammar.new(tempregel) return temp end end #Testfälle der Klasse Symb require "test/unit" class SymbToTest g \n |h") @regel2 = Rule.new("D -> p p") @regel3 = Rule.new("B -> ") end # Die Methode prüft, ob das Non-Terminal auf der linken Seite zurückgegeben wird und ob es auch ein Non-Terminal ist. def test_getSymbol assert_equal("P", @regel1.getSymbol.to_s) assert(!(@regel1.getSymbol.terminal)) # mit "!", da die linke Regelseite ein Non-Terminal ist end # Die Methode testet, ob die richtigen Alternativen zurückgegeben werden, ob die Alternative bei @regel2 auch nur als eine Alternative erkannt wird # und ob es nach der einen erkannten Alternative auch keine weiteren mehr gibt. def test_getAlts assert_equal(" g h", @regel1.getAlts.to_s) assert_equal(" p p", @regel2.getAlts.to_s) assert_equal(" p p", @regel2.getAlts[0].to_s) assert_equal(nil, @regel2.getAlts[1]) end # Die Methode testet, ob die richtige Anzahl an Alternativen zurückgegeben wird. # Bei @regel1 sind es zwei, bei @regel2 ist es eine und bei @regel3 ist es auch eine, nämlich das Epsilon. def test_countAlts assert(2 == @regel1.countAlts) assert(1 == @regel2.countAlts) assert(1 == @regel3.countAlts) end # Die Methode prüft, ob man durch Angabe eines Index auf eine beliebige Alternative zugreifen kann. def test_ind assert_equal(" h", @regel1.[](1).to_s) assert_equal(" p p", @regel2.[](0).to_s) assert_equal("", @regel3.[](0).to_s) end # Die Methode testet die gewünschte Ausgabe. def test_to_s assert_equal("P -> g\n | h", @regel1.to_s) assert_equal("D -> p p", @regel2.to_s) end # Die Methode prüft, ob die @regel1 und @regel2 kein Epsilon ist aber die @regel3 schon. def test_isEpsilon assert(!(@regel1.isEpsilon)) assert(!(@regel2.isEpsilon)) assert(@regel3.isEpsilon) end end #Testfälle der Klasse Grammar class GrammarToTest g \n |h \n\nD -> p p") @grammatik2 = Grammar.new("S -> H \n |h \n\nH -> A \n |B \n |c \n\nA -> a \n |b \n\nB -> ") end # Die Methode testet, ob das richtige Startsymbol zurückgegeben wird und ob es sich dabei um ein Non-Terminal handelt. def test_getStartsymbol assert_equal("P",@grammatik1.getStartsymbol.to_s) assert(!(@grammatik1.getStartsymbol.terminal)) assert_equal("S",@grammatik2.getStartsymbol.to_s) assert(!(@grammatik2.getStartsymbol.terminal)) end # Die Methode testet, ob alle Terminale aus der gegebenen Grammatik auch als Terminale erkannt wurden. def test_getTerminals ablage1 = ablage2 = Array.new @grammatik1.getTerminals.each_key do |schluessel| ablage1 +=[schluessel] end assert_equal("pgh", ablage1.to_s) @grammatik2.getTerminals.each_key do |schluessel| ablage2 +=[schluessel] end assert_equal("abch", ablage2.to_s) end # Die Methode testet, ob alle Non-Terminale aus der gegebenen Grammatik auch als Non-Terminale erkannt wurden. def test_getNonterminals ablage1 = ablage2 = Array.new @grammatik1.getNonterminals.each_key do |schluessel| ablage1 +=[schluessel] end assert_equal("DP", ablage1.to_s) @grammatik2.getNonterminals.each_key do |schluessel| ablage2 +=[schluessel] end assert_equal("ABHS", ablage2.to_s) end # Die Methode prüft, ob auch alle einzelnen Regeln erkannt wurden. def test_getRules assert_equal("P -> g\n | h", @grammatik1.getRules[@grammatik1.getStartsymbol].to_s) assert_equal("D -> p p", @grammatik1.getRules[@grammatik1.getNonterminals["D"]].to_s) assert_equal("S -> H\n | h", @grammatik2.getRules[@grammatik2.getStartsymbol].to_s) assert_equal("H -> A\n | B\n | c", @grammatik2.getRules[@grammatik2.getNonterminals["H"]].to_s) assert_equal("A -> a\n | b", @grammatik2.getRules[@grammatik2.getNonterminals["A"]].to_s) assert_equal("B -> ", @grammatik2.getRules[@grammatik2.getNonterminals["B"]].to_s) end # Die Methode prüft, ob alle Symbole erkannt wurden, die Epsilon produzieren können. def test_epsilon_Symbole assert_equal("",@grammatik1.epsilon_Symbole.to_s) assert_equal(@grammatik2.getNonterminals["B"],@grammatik2.epsilon_Symbole[0]) assert_equal(@grammatik2.getNonterminals["H"],@grammatik2.epsilon_Symbole[1]) assert_equal(@grammatik2.getStartsymbol,@grammatik2.epsilon_Symbole[2]) end # Die Methode prüft, ob die Grammatik im gewünschten Format ausgegeben wird. def test_to_s assert_equal("P -> g\n | h\n\nD -> p p", @grammatik1.to_s) end # Die Methode prüft, ob die Grammatik im gewünschten SIC-Format ausgegeben wird. def test_to_SIC assert_equal("Terminals:\n\np g h \n\nNonterminals:\n\nD P \n\nStartingsymbol:\n\nP\n\nRules:\n\nP -> g\n | h\n\nD -> p p", @grammatik1.to_SIC) end end =begin # Ausgabetest für die Klassenmethode Rule.from_Yacc Rule.from_Yacc("name Arith\nleft addOp\nleft multOp\nright expOp\npre addOp\natom zahl, name\n") Rule.from_Yacc("name L\nnone logBinOp\npre negOp\natom true, false, name\n") gets =end @grammatik1 = Grammar.new("P -> g \n |h \n\nD -> p p") @grammatik2 = Grammar.new("S -> H \n |h \n\nH -> A \n |B \n |c \n\nA -> a \n |b \n\nB -> ") puts @grammatik2.to_SIC gets