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
