require 'set'
class Grammardef
def initialize
@rules = Hash.new()
end
def setexiom(axiom)
@axiom = axiom
print "axiom:\n", @axiom, "\n", "setted\n"
end
def setnterm(nterms)
@nterms = nterms.split(/ +/).delete_if { |x| x == "" }
@nterms << @axiom
#@nterms = @nterms.sort { |x,y| y <=> x }
print "nterms:\n", @nterms, "\n", "setted\n"
end
def setterm(terms)
@terms = terms.split(/ +|\"/).delete_if { |x| x == "" }
print "terms:\n", @terms, "\n", "setted\n"
end
def setrules(rules)
#print "rules:\n", rules.split(/( *|\\n)\$RULE /).delete_if {|x| (x == "") || (x == "\\n")}, "\n", "setted\n"
rulesregexp = Regexp.new(/\$RULE (([A-Z]\'{0,1}) =(([( [A-Z]\'{0,1})( \"[a-z]\"| \"\*\"| \"\+\"| \"\(\"| \"\)\")]+\\n| \$EPS\\n)+))/)
a = rulesregexp.match(rules)[0]
#print "rules:\n", a, "\n"
self.setrule(a)
while rulesregexp.match(rules) != nil
rules = rules[rulesregexp.match(rules)[0].length, rules.length]
if (rulesregexp.match(rules) != nil)
a = rulesregexp.match(rules)[0]
#print a, "\n"
self.setrule(a)
end
end
print "rules hash:\n", @rules, "\n"
end
def setrule(rule)
ruleregexp = Regexp.new(/\$RULE (([A-Z]\'{0,1}) =(([( [A-Z]\'{0,1})( \"[a-z]\"| \"\*\"| \"\+\"| \"\(\"| \"\)\")]+\\n| \$EPS\\n)+))/)
leftpart = ruleregexp.match(rule)[2]
rightparts = ruleregexp.match(rule)[3]
#print "rule left:\n", leftpart, "\nrule rights:\n", rightparts, "\n"
rightpartsarr = rightparts.split(/\\n/).delete_if { |x| x == "" }
#print "right parts array\n", rightpartsarr, "\n******************************************************\n"
rightpartsset = Set.new()
(rightpartsarr).each do |x|
onealt = x.split(/ +|\"/).delete_if { |x| x == "" }
rightpartsset.add(onealt)
#print onealt, "\n******************************************************\n"
@rules[leftpart] = rightpartsset
end
end
def axiom
@axiom
end
def nterms
@nterms
end
def terms
@terms
end
def rules
@rules
end
def rulebynterm(nterm)
@rules[nterm]
end
def arrtostr(x)
#print x, " in arrtostr\n"
str = ""
x.each { |x| str += x }
str
end
def phi(seq)
#print "in phi", seq, "\n"
if @nterms.include?(seq[0]) && seq.length == 1
return @FIRST[seq[0]]
end
if seq[0] == "$EPS"
retset = (Set.new() << "$EPS")
return retset
end
if @terms.include?(seq[0])
retset = (Set.new() << seq[0])
return retset
end
if @nterms.include?(seq[0])
if !@FIRST[seq[0]].include?("$EPS")
return @FIRST[seq[0]]
else
epsset = (Set.new() << "$EPS")
subarr = seq[1 .. seq.length - 1]
#print "subarr in phi: ", subarr, "\n"
if subarr.length == 0
retset = @FIRST[seq[0]] - epsset
else
retset = (@FIRST[seq[0]] - epsset) + phi(subarr)
end
return retset
end
end
print "no arr in phi"
end
def FIRSTF()
@FIRST = Hash.new
(@nterms).each do |x|
@FIRST[x] = Set.new
end
begin
@FIRSTold = @FIRST.clone
(@nterms).each do |x|
(@rules[x]).each do |y|
@FIRST[x] += self.phi(y)
end
end
end while @FIRSTold != @FIRST
#print "FIRST\n"
#@FIRST.each {|key, value| @FIRST[key] ; print "#{key} is ", value.inspect, "\n" }
(@nterms).each do |x|
test1 = @FIRST[x]
x1 = [x]
test2 = phi(x1)
#print test1.inspect, " ", test2.inspect, "\n"
end
print "first hash:\n", @FIRST, "\n"
end
def FOLLOWF()
@FOLLOW = Hash.new
(@nterms).each do |x|
@FOLLOW[x] = Set.new
end
@FOLLOW[@axiom] << "$"
(@nterms).each do |x|
(@rules[x]).each do |y|
#print x, ":", y, "\n"
(y).each_index do |z|
#print z, "\n"
if @nterms.include?(y[z])
if z != y.length - 1
#print "Y: ", y[z], " v: ", y[z+1 .. y.length - z], "\n"
@FOLLOW[y[z]] += (phi(y[z+1 .. y.length - z]) - ["$EPS"])
else
#print "Y: ", y[z], " v: ", [], "\n"
end
end
end
end
end
begin
@FOLLOWold = @FOLLOW.clone
#print "iter\n"
(@nterms).each do |x|
(@rules[x]).each do |y|
(y).each_index do |z|
if @nterms.include?(y[z])
if z != y.length - 1
#print "Y: ", y[z], " v: ", y[z+1 .. y.length - z], "\n"
#@FOLLOW[y[z]] += (phi(y[z+1 .. y.length - z]) - ["$EPS"])
#print phi(y[z+1 .. y.length - z]).inspect, "beforeepsif\n"
if phi(y[z+1 .. y.length - z]).include?("$EPS")
#print phi(y[z+1 .. y.length - z]).inspect, "\n"
#print "INCLUDE EPS follow y: ", @FOLLOW[y[z]].inspect, "follow x: ", @FOLLOW[x].inspect, "\n"
@FOLLOW[y[z]] += @FOLLOW[x]
end
else
#print "Y: ", y[z], " v: ", [], "\n"
#print"y: ",y[z], "follow y: ", @FOLLOW[y[z]].inspect, "follow x: ", @FOLLOW[x].inspect, "\n"
@FOLLOW[y[z]] += @FOLLOW[x]
end
end
end
end
end
end while @FOLLOWold != @FOLLOW
print "follow hash:\n", @FOLLOW, "\n"
end
def settable
#print "starting settable\n"
@table = Hash.new()
(@nterms).each do |x|
(@terms).each do |y|
#print "nterm: ", x, " term: ", y, "\n"
@table[[x, y]] = ["ERROR"]
end
@table[[x, "$"]] = ["ERROR"]
end
(@nterms).each do |x|
(@rules[x]).each do |y|
#print y, "--FIRST--", self.phi(y).inspect, "\n"
(self.phi(y)).each do |z|
#print @table[[x, z]], "\n"
#@table[[x, z]] = y
if self.phi(y).include?("$EPS")
#print "include", self.phi(y).inspect, "\n"
(@FOLLOW[x]).each do |b|
#print b, "\n"
if @table[[x, b]] == ["ERROR"]
@table[[x, b]] = y
else
@table[[x, b]] += y
end
end
else
#print "not include", self.phi(y).inspect, "\n"
if @table[[x, z]] == ["ERROR"]
@table[[x, z]] = y
else
@table[[x, z]] += y
end
end
end
end
end
#print "table:\n", @table, "\n"
mas2 = ["+", "*", "n", "(", ")", "$"]
mas1 = ["E", "E'", "T", "T'", "F"]
(mas1).each do |x|
(mas2).each do |y|
#print x, " ", y, " ", @table[[x, y]], "\n"
end
end
end
def topdownparse(x)
print "\n\n\nstarting topdown\n\n\n"
@terms << "$EPS"
mag = []
mag.push("$")
mag.push(@axiom)
a = x.shift
x1 = "random"
while x1 != "$" do
x1 = mag.pop
if x1 == "$"
if x == []
break
else
print "error0\n"
break
end
end
if (@terms).include?(x1)
if x1 == a
a = x.shift
else
if x1 != "$EPS"
print "error1\n"
break
else
next
end
end
else
if a == nil
a = "$"
end
if @table[[x1, a]] != ["ERROR"]
mas = @table[[x1, a]]
mas.reverse!
mag += mas
print "rule: ", x1, " -> ", mas.reverse!, "\n"
else
print "error2\n"
break
end
end
end
end
end
class Progreader
def initialize(exampleprog)
#exampleprog = "$AXIOM E\\n$NTERM E' T T' F\\n$TERM \"+\" \"*\" \"(\" \")\" \"n\"\\n$RULE E = T\\n$RULE E' = \"+\" T E'\\n $EPS\\n"
progregexp = Regexp.new(/\$AXIOM ([A-Z0-9']+)\\n\$NTERM(( [A-Z0-9']+)+)\\n\$TERM( ".+")+\\n((\$RULE [A-Z0-9']+ =(( ([A-Z0-9'\$]|(".+"))+)+\\n)+)+)/)
prog = progregexp.match(exampleprog)
@arifmGrammar = Grammardef.new
#print "\n$$$allprogram:\n", prog, "\n"
#print "axiom:\n", prog[1], "\n"
@arifmGrammar.setexiom(prog[1])
#print "nterm:\n", prog[2], "\n"
@arifmGrammar.setnterm(prog[2])
#print "term:\n", prog[4], "\n"
@arifmGrammar.setterm(prog[4])
#print "rules:\n", prog[6], "\n"
@arifmGrammar.setrules(prog[5])
@arifmGrammar.FIRSTF
@arifmGrammar.FOLLOWF
@arifmGrammar.settable
#@arifmGrammar.topdownparse(["(" ,"n", "+", "n", ")"])
end
def arifmGrammar
@arifmGrammar
end
end
class Filecustomreader
def initialize(filename)
#read from file
file = File.new(filename, "r")
@mygram = "";
while line = file.gets
@mygram += line.chomp + "\\n"
end
@mygram = @mygram[0, @mygram.length - 0]
#print @mygram
#print "\nqqqqq\n"
end
def mygram
@mygram
end
end
#exampleprog = "$AXIOM E\\n$NTERM E' T T' F\\n$TERM \"+\" \"*\" \"(\" \")\" \"n\"\\n$RULE E = T E'\\n$RULE E' = \"+\" T E'\\n $EPS\\n$RULE T = F T'\\n$RULE T' = \"*\" F T'\\n $EPS\\n$RULE F = \"n\"\\n \"(\" E \")\"\\n"
#progreader = Progreader.new(exampleprog)
reader = Filecustomreader.new("/Users/vladimir/Desktop/tablelab7/gramgram.txt")
progreader = Progreader.new(reader.mygram)
arifmGrammar = progreader.arifmGrammar
#print arifmGrammar, "\n"