+# This file is part of NIT ( http://www.nitlanguage.org ).
+#
+# Licensed under the Apache License, Version 2.0 (the "License");
+# you may not use this file except in compliance with the License.
+# You may obtain a copy of the License at
+#
+# http://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing, software
+# distributed under the License is distributed on an "AS IS" BASIS,
+# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+# See the License for the specific language governing permissions and
+# limitations under the License.
+
+# A gramar describing a language
+class Gram
+ # The productions (non-terminal) of the conctete grammar
+ var prods = new Array[Production]
+
+ # The additionnal abstract productions of the grammar
+ # TODO clean AST
+ var ast_prods = new Array[Production]
+
+ # The tokens (terminals) of the grammar
+ var tokens = new Array[Token]
+
+ # Dump of the concrete grammar and the transformations
+ fun pretty: String
+ do
+ var res = new Buffer
+ for p in prods do
+ if p.spe != null then
+ res.append("{p.name} \{-> {p.spe.name}\}=\n")
+ else
+ res.append("{p.name} =\n")
+ end
+ var last = p.alts.last
+ for a in p.alts do
+ res.append("\t\{{a.name}:\} {a.elems.join(" ")}")
+ if a.codes == null then a.make_codes
+ res.append("\n\t\t\{-> {a.codes.join(", ")}\}")
+ if a == last then res.append(" ;\n") else res.append(" |\n")
+ end
+ if p.is_nullable then res.append "\t// is nullable\n"
+ if not p.firsts.is_empty then res.append "\t// firsts: {p.firsts.join(" ")}\n"
+ if not p.afters.is_empty then res.append "\t// afters: {p.afters.join(" ")}\n"
+ end
+ return res.to_s
+ end
+
+ # Inline (ie. remove from the conctete grammar) some production
+ # REQUIRE: no circular production in `prods`
+ fun inline(prods: Collection[Production])
+ do
+ for p in self.prods do
+ for a in p.alts.to_a do
+ var to_inline = false
+ for e in a.elems do
+ if e isa Production and prods.has(e) then to_inline = true
+ end
+ if not to_inline then continue
+
+ if a.codes == null then a.make_codes
+
+ var a0 = new Alternative(p, a.name, new Array[Element])
+ a0.trans = true
+ a0.codes = new Array[Code]
+ var pool = [a0]
+ var pool2 = new Array[Alternative]
+ for e in a.elems do
+ if not e isa Production or not prods.has(e) then
+ for x in pool do
+ x.elems.add(e)
+ x.codes.add(new CodePop)
+ end
+ continue
+ end
+ if p == e then
+ print "Circular inlining on {p} :: {a}"
+ abort
+ end
+ pool2.clear
+ for a2 in e.alts do
+ if a2.codes == null then a2.make_codes
+ for x in pool do
+ var name = a.name + "_" + pool2.length.to_s
+ var na = new Alternative(p, name, new Array[Element])
+ na.trans = true
+ pool2.add(na)
+ na.elems.add_all(x.elems)
+ na.elems.add_all(a2.elems)
+ na.codes = new Array[Code]
+ na.codes.add_all(x.codes.as(not null))
+ na.codes.add_all(a2.codes.as(not null))
+ end
+ end
+ var tmp = pool
+ pool = pool2
+ pool2 = tmp
+ end
+ for x in pool do
+ x.codes.add(a.codes.last)
+ end
+ p.ast_alts.add(a)
+ p.alts.remove(a)
+ p.alts.add_all(pool)
+ end
+ end
+ for p in prods do
+ self.prods.remove(p)
+ self.ast_prods.add(p)
+ end
+ end
+
+ # Compute a LR automaton
+ fun lr0: LRAutomaton
+ do
+ analyse
+
+ var start = new Production("_start")
+ start.accept = true
+ var eof = new Token("Eof")
+ tokens.add(eof)
+ start.new_alt("Start", self.prods.first, eof)
+ prods.add(start)
+ var first = new LRState("Start")
+ first.number = 0
+ for i in start.start_state do first.add(i)
+
+ var automaton = new LRAutomaton(self)
+
+ var todo = new List[LRState]
+ todo.add first
+ var seen = new HashSet[LRState]
+ seen.add first
+
+ while not todo.is_empty do
+ var state = todo.shift
+
+ #print state
+ automaton.states.add(state)
+ state.analysis
+
+ var nexts = new HashMap[Element, LRState]
+ for i in state.items do
+ var e = i.next
+ if e == null then continue
+ if nexts.has_key(e) then
+ nexts[e].add(i.avance)
+ else
+ var name
+ if state == automaton.states.first then
+ name = e.to_s
+ else
+ name = "{state.name} {e}"
+ end
+ var next = new LRState(name)
+ nexts[e] = next
+ next.add(i.avance)
+ end
+ end
+
+ for e, next in nexts do
+
+ #print "#states: {seen.length}"
+
+ var new_state = true
+ for n in seen do
+ if n == next then
+ for i in next.items do
+ if n.add(i) then n.extends(i)
+ end
+ next = n
+ new_state = false
+ break
+ end
+ end
+
+ if new_state then
+ next.number = seen.length
+ assert not seen.has(next)
+ seen.add(next)
+ todo.add(next)
+ end
+
+ var t = new LRTransition(state, next, e)
+ state.outs.add t
+ next.ins.add t
+ end
+ end
+ return automaton
+ end
+
+ # Compute `nullables`, `firsts` and `afters` of productions
+ fun analyse
+ do
+ loop
+ var changed = false
+ for p in prods do
+ if p.is_nullable then continue
+ for a in p.alts do
+ var nullabl = true
+ for e in a.elems do
+ if e isa Token then
+ nullabl = false
+ break
+ else if e isa Production then
+ if not e.is_nullable then nullabl = false
+ break
+ else
+ abort
+ end
+ end
+ if nullabl then
+ p.is_nullable = true
+ changed = true
+ end
+ end
+ end
+ if not changed then break
+ end
+
+ loop
+ var changed = false
+ for p in prods do
+ var fs = p.firsts
+ for a in p.alts do
+ for e in a.elems do
+ if e isa Token then
+ if try_add(fs, e) then changed = true
+ break
+ else if e isa Production then
+ for t in e.firsts do
+ if try_add(fs, t) then changed = true
+ end
+ if not e.is_nullable then break
+ else
+ abort
+ end
+ end
+ end
+ end
+ if not changed then break
+ end
+
+ loop
+ var changed = false
+ for p1 in prods do
+ for a in p1.alts do
+ var p0: nullable Production = null
+ for e in a.elems do
+ var p = p0
+ if e isa Production then p0 = e else p0 = null
+ if p == null then continue
+
+ var afs = p.afters
+
+ if e isa Token then
+ if try_add(afs, e) then changed = true
+ else if e isa Production then
+ for t in e.firsts do
+ if try_add(afs, t) then changed = true
+ end
+ if e.is_nullable then
+ for t in e.afters do
+ if try_add(afs, t) then changed = true
+ end
+ end
+ else
+ abort
+ end
+ end
+ if p0 != null then
+ var afs = p0.afters
+ for t in p1.afters do
+ if try_add(afs, t) then changed = true
+ end
+ end
+ end
+ end
+ if not changed then break
+ end
+ end
+
+ # used by `analyse`
+ private fun try_add(set: Set[Token], t: Token): Bool
+ do
+ var res = not set.has(t)
+ if res then set.add(t)
+ return res
+ end
+
+end
+
+# A production of a grammar
+class Production
+ super Element
+ # The alternative of the production
+ var alts = new Array[Alternative]
+
+ # Additionnal alternatives in the AST
+ var ast_alts = new Array[Alternative]
+
+ # Is self the accept production
+ var accept = false
+
+ # Is self transformed to a other production for the AST
+ # FIXME: cleaup AST
+ var spe: nullable Production writable = null
+
+ # Is self contains only a single alternative (then no need for a abstract production class in the AST)
+ # FIXME cleanup AST
+ var altone writable = false
+
+ # The cname of the class in the AST
+ # FIXME: cleanup AST
+ redef fun acname do
+ if spe != null then return spe.acname
+ return super
+ end
+
+ # Is the production nullable
+ var is_nullable = false
+ # The first tokens of the production
+ var firsts = new HashSet[Token]
+ # The tokens that may follows the production (as in SLR)
+ var afters = new HashSet[Token]
+
+
+ # Crate a new empty alternative
+ fun new_alt0(name: String): Alternative
+ do
+ var a = new Alternative(self, name, new Array[Element])
+ alts.add a
+ return a
+ end
+
+ # Crate a new alternative with some elements
+ fun new_alt(name: String, elems: Element...): Alternative
+ do
+ var a = new Alternative(self, name, elems)
+ alts.add a
+ return a
+ end
+
+ # Crate a new alternative with some elements
+ fun new_alt2(name: String, elems: Array[Element]): Alternative
+ do
+ var a = new Alternative(self, name, elems)
+ alts.add a
+ return a
+ end
+
+ # Return a set of items for the production
+ fun start_state: Array[Item]
+ do
+ var res = new Array[Item]
+ for a in alts do
+ res.add new Item(a, 0)
+ end
+ return res
+ end
+
+ # States in the LR automaton that has a outgoing transition on self
+ var gotos = new ArraySet[LRState]
+end
+
+# An alternative of a production
+class Alternative
+ # The production
+ var prod: Production
+
+ # The name of the alternative
+ var name: String writable
+
+ # The elements of the alternative
+ var elems: Array[Element]
+
+ # The name of the elements
+ var elems_names = new Array[nullable String]
+
+ # Return a name for a given element (or a number if unamed)
+ fun elemname(i: Int): String
+ do
+ if i >= elems_names.length then return "{i}"
+ var n = elems_names[i]
+ if n == null then return "{i}"
+ return n
+ end
+
+ redef fun to_s do return "{prod.name}::{name}={elems.join(" ")}"
+
+ # A mangled name
+ fun cname: String do
+ return "N{name.to_cmangle}"
+ end
+
+ # The code for the reduction
+ var codes: nullable Array[Code] writable = null
+
+ # Is the alternative transformed (ie not in the AST)
+ var trans writable = false
+
+ # Imitialize codes with the elements
+ fun make_codes
+ do
+ if codes != null then return
+ var codes = new Array[Code]
+ self.codes = codes
+ for e in elems do
+ codes.add(new CodePop)
+ end
+ codes.add(new CodeNew(self))
+ end
+end
+
+# A step in the construction of the AST. used to modelize transformations
+interface Code
+end
+# Get a element from the stack
+class CodePop
+ super Code
+ redef fun to_s do return "pop"
+end
+# Allocate a new AST node for an alternative using the correct number of poped elements
+class CodeNew
+ super Code
+ var alt: Alternative
+ redef fun to_s do return "New {alt.name}/{alt.elems.length}"
+end
+# Get null
+class CodeNull
+ super Code
+ redef fun to_s do return "null"
+end
+
+# Elements of an alternative.
+# Either a `Production` or a `Token`
+abstract class Element
+ # The name of the element
+ var name: String
+ redef fun to_s do return name
+
+ private var acname_cache: nullable String = null
+
+ # The mangled name of the element
+ fun cname: String do return "N{name.to_cmangle}"
+
+ # the name of the class in the AST
+ fun acname: String do
+ var res = acname_cache
+ if res == null then
+ res = "N{to_s.to_cmangle}"
+ acname_cache = res
+ end
+ return res
+ end
+ fun acname=(s: String) do acname_cache = s
+end
+
+# A terminal element
+class Token
+ super Element
+ # States of the LR automatio that shift on self
+ var shifts = new ArraySet[LRState]
+ # States of the LR automatio that reduce on self in the lookahead(1)
+ var reduces = new ArraySet[LRState]
+end
+
+#
+
+# A LR automaton
+class LRAutomaton
+ # The grammar of the automaton
+ var grammar: Gram
+
+ # The set of states
+ var states = new Array[LRState]
+
+ # Dump of the automaton
+ fun pretty: String
+ do
+ var res = new Array[String]
+ res.add "* LRAutomaton: {states.length} states\n"
+ for s in states do
+ res.add "s{s.number} {s.name}\n"
+ res.add "\tCORE\n"
+ for i in s.core do
+ res.add "\t\t{i}\n"
+ end
+ res.add "\tOTHER ITEMS\n"
+ for i in s.items do
+ if s.core.has(i) then continue
+ res.add "\t\t{i}\n"
+ end
+ res.add "\tTRANSITIONS {s.outs.length}\n"
+ for t in s.outs do
+ res.add "\t\t{t.elem} |-> s{t.to.number}\n"
+ end
+ res.add "\tACTIONS\n"
+ if s.is_lr0 then
+ res.add "\t\tSTATE LR0\n"
+ else
+ res.add "\t\tSTATE LALR\n"
+ for t, a in s.guarded_reduce do
+ if a.length > 1 then
+ res.add "\t\t/!\\ REDUCE/REDUCE CONFLICT\n"
+ break
+ else if s.shifts.has(t) then
+ res.add "\t\t/!\\ SHIFT/REDUCE CONFLICT\n"
+ break
+ end
+ end
+ end
+ if not s.shifts.is_empty then
+ res.add "\t\tSHIFT {s.shifts.join(" ")}\n"
+ end
+ for r in s.reduces do
+ res.add "\t\tREDUCE {r}\n"
+ end
+ end
+ return res.to_s
+ end
+
+ # Generate a graphviz file of the automaton
+ fun to_dot(path: String)
+ do
+ var f = new OFStream.open(path)
+ f.write("digraph g \{\n")
+ f.write("rankdir=LR;\n")
+ f.write("node[shape=Mrecord,height=0];\n")
+
+ for s in states do
+ f.write "s{s.number} [label=\"{s.number} {s.name.escape_to_dot}|"
+ for i in s.core do
+ f.write "{i.to_s.escape_to_dot}\\l"
+ end
+ f.write("|")
+ for i in s.items do
+ if s.core.has(i) then continue
+ f.write "{i.to_s.escape_to_dot}\\l"
+ end
+ f.write "\""
+ if not s.is_lr0 then
+ var conflict = false
+ for t, a in s.guarded_reduce do
+ if a.length > 1 then
+ f.write ",color=red"
+ conflict = true
+ break
+ else if s.shifts.has(t) then
+ f.write ",color=orange"
+ conflict = true
+ break
+ end
+ end
+ if not conflict then
+ f.write ",color=blue"
+ end
+ end
+ f.write "];\n"
+ for t in s.outs do
+ f.write "s{s.number} -> s{t.to.number} [label=\"{t.elem.to_s.escape_to_dot}\"];\n"
+ end
+ end
+ f.write("\}\n")
+ f.close
+ end
+
+ # Generate the parser of the automaton
+ fun gen_to_nit(filepath: String)
+ do
+ var gen = new Generator
+ gen.gen_to_nit(self)
+ var f = new OFStream.open(filepath)
+ for s in gen.out do
+ f.write(s)
+ f.write("\n")
+ end
+ f.close
+ end
+end
+
+redef class String
+ # escape string used in labels for graphviz
+ fun escape_to_dot: String
+ do
+ return escape_more_to_c("|\{\}")
+ end
+end
+
+private class Generator
+ var out = new Array[String]
+ fun add(s: String) do out.add(s)
+ fun gen_to_nit(autom: LRAutomaton)
+ do
+ var states = autom.states
+ var gram = autom.grammar
+
+ add "# Parser generated by nitcc"
+ add "import nitcc_runtime"
+
+ add "class MyParser"
+ add "\tsuper Parser"
+ add "\tredef fun start_state do return state_{states.first.cname}"
+ add "end"
+
+ add "redef class Object"
+ for s in states do
+ add "\tprivate fun state_{s.cname}: LRState{s.cname} do return once new LRState{s.cname}"
+ end
+ for p in gram.prods do
+ add "\tprivate fun goto_{p.cname}: Goto_{p.cname} do return once new Goto_{p.cname}"
+ end
+ add "end"
+
+ add "redef class NToken"
+ for s in states do
+ if not s.need_guard then continue
+ add "\t# guarded action for state {s.name}"
+ add "\t# {s.shifts.length} shift(s) and {s.reduces.length} reduce(s)"
+ add "\tprivate fun action_s{s.cname}(parser: Parser) do"
+ if s.reduces.length != 1 then
+ add "\t\tparser.parse_error"
+ else
+ gen_reduce_to_nit(s.reduces.first)
+ end
+ add "\tend"
+ end
+ add "end"
+
+ for t in gram.tokens do
+ if t.name == "Eof" then
+ add "redef class {t.cname}"
+ else
+ add "class {t.cname}"
+ end
+ add "\tsuper NToken"
+ for s in t.shifts do
+ if not s.need_guard then continue
+ add "\tredef fun action_s{s.cname}(parser) do"
+ gen_shift_to_nit(s, t)
+ add "\tend"
+ end
+ for s in t.reduces do
+ if not s.need_guard then continue
+ if s.reduces.length <= 1 then continue
+ add "\tredef fun action_s{s.cname}(parser) do"
+ gen_reduce_to_nit(s.guarded_reduce[t].first.alt)
+ add "\tend"
+ end
+ add "\tredef fun node_name do return \"{t.name.escape_to_nit}\""
+ add "end"
+ end
+
+ add "redef class LRGoto"
+ for s in states do
+ if s.gotos.length <= 1 then continue
+ add "\tprivate fun goto_s{s.cname}(parser: Parser) do abort"
+ end
+ add "end"
+
+ for p in gram.prods do
+ add "class Goto_{p.cname}"
+ add "\tsuper LRGoto"
+ for s in p.gotos do
+ if s.gotos.length <= 1 then continue
+ add "\tredef fun goto_s{s.cname}(parser) do"
+ gen_goto_to_nit(s, p)
+ add "\tend"
+ end
+ add "end"
+ end
+
+ var ps = gram.prods.to_a
+ ps.add_all(gram.ast_prods)
+ for p in ps do
+ if p.spe == null and not p.altone then
+ if p.name.has_suffix("?") or p.name.has_suffix("+") then continue
+ add "class {p.acname}"
+ add "\tsuper NProd"
+ add "\tredef fun node_name do return \"{p.name.escape_to_nit}\""
+ add "end"
+ end
+
+ var als = p.alts.to_a
+ als.add_all(p.ast_alts)
+ for a in als do
+ if a.trans then continue
+ add "class {a.cname}"
+ if p.altone then
+ add "\tsuper NProd"
+ else
+ add "\tsuper {p.acname}"
+ end
+ add "\tredef fun node_name do return \"{a.name.escape_to_nit}\""
+ var initarg = new Array[String]
+ for i in [0..a.elems.length[ do
+ add "\tvar n_{a.elemname(i)}: {a.elems[i].acname}"
+ initarg.add("n_{a.elemname(i)}: {a.elems[i].acname}")
+ end
+ if initarg.is_empty then
+ add "\tinit do end"
+ else
+ add "\tinit({initarg.join(", ")}) do"
+ for i in [0..a.elems.length[ do
+ add "\t\tself.n_{a.elemname(i)} = n_{a.elemname(i)}"
+ end
+ add "\tend"
+ end
+ add "\tredef fun number_of_children do return {a.elems.length}"
+ add "\tredef fun child(i) do"
+ for i in [0..a.elems.length[ do
+ add "\t\tif i == {i} then return n_{a.elemname(i)}"
+ end
+ add "\t\tabort"
+ add "\tend"
+ add "end"
+ end
+ end
+
+ for s in states do
+ add "# State {s.name}"
+ add "private class LRState{s.cname}"
+ add "\tsuper LRState"
+
+ add "\tredef fun to_s do return \"{s.name.escape_to_nit}\""
+
+ var err = new Array[String]
+ for t in s.outs do
+ var e = t.elem
+ if e isa Production then err.add e.name
+ end
+ if err.is_empty then for t in s.outs do
+ var e = t.elem
+ if e isa Token then err.add e.name
+ end
+
+ add "\tredef fun error_msg do return \"{err.join(", ").escape_to_nit}\""
+
+ add "\tredef fun action(parser) do"
+ if s.need_guard then
+ add "\t\tparser.peek_token.action_s{s.cname}(parser)"
+ else if s.reduces.length == 1 then
+ gen_reduce_to_nit(s.reduces.first)
+ else
+ abort
+ end
+ add "\tend"
+
+ if not s.gotos.is_empty then
+ add "\tredef fun goto(parser, goto) do"
+ if s.gotos.length > 1 then
+ add "\t\tgoto.goto_s{s.cname}(parser)"
+ else
+ gen_goto_to_nit(s, s.gotos.first)
+ end
+ add "\tend"
+ end
+
+ add "end"
+ end
+
+
+ end
+
+ fun gen_shift_to_nit(s: LRState, t: Token)
+ do
+ var dest = s.trans(t)
+ add "\t\tparser.shift(state_{dest.cname})"
+
+ end
+
+ fun gen_goto_to_nit(s: LRState, p: Production)
+ do
+ var dest = s.trans(p)
+ add "\t\tparser.push(state_{dest.cname})"
+ end
+
+ fun gen_reduce_to_nit(alt: Alternative)
+ do
+ add "\t\t# REDUCE {alt}"
+ var i = alt.elems.length - 1
+ for e in alt.elems.to_a.reversed do
+ add "\t\tvar n{i} = parser.pop.as({e.acname})"
+ i -= 1
+ end
+
+ if alt.name.has_suffix("+_more") then
+ add "\t\tvar prod = n0"
+ add "\t\tn0.items.add(n1)"
+ else if alt.name.has_suffix("+_one") then
+ add "\t\tvar prod = new {alt.prod.acname}"
+ add "\t\tprod.items.add(n0)"
+ else
+ alt.make_codes
+ var cpt = 0
+ i = 0
+ var st = new Array[String]
+ for c in alt.codes.as(not null) do
+ if c isa CodePop then
+ st.add "n{i}"
+ i += 1
+ else if c isa CodeNull then
+ st.add "null"
+ else if c isa CodeNew then
+ var calt = c.alt
+ cpt += 1
+ var from = st.length - calt.elems.length
+ var args = new List[String]
+ for j in [from..st.length[ do
+ args.unshift(st.pop)
+ end
+
+ if args.is_empty then
+ add "\t\tvar p{cpt} = new {calt.cname}"
+ else
+ add "\t\tvar p{cpt} = new {calt.cname}({args.join(", ")})"
+ end
+ #var x = 0
+ #for j in [from..st.length[ do
+ #if st[j] == "null" then continue
+ #add "\t\tp{cpt}.n_{calt.elemname(x)} = {st[j]}"
+ #x += 1
+ #end
+ st.add("p{cpt}")
+ end
+ end
+ assert st.length == 1
+ add "\t\tvar prod = {st.first}"
+ end
+
+ add "\t\tparser.node_stack.push prod"
+ if alt.prod.accept then
+ add "\t\tparser.stop = true"
+ else
+ add "\t\tparser.goto(goto_{alt.prod.cname})"
+ end
+ end
+end
+
+# A state in a LR automaton
+class LRState
+ # name of the automaton (short part from the start)
+ var name: String
+
+ # malglen name
+ fun cname: String do return name.to_cmangle
+
+ # number
+ var number: Int = -1
+
+ # Set of all items
+ var items = new HashSet[Item]
+
+ # Set of items only in the core
+ var core = new HashSet[Item]
+
+ # Outgoing transitions
+ var ins = new Array[LRTransition]
+
+ # Ingoing transitions
+ var outs = new Array[LRTransition]
+
+ # trans function
+ fun trans(e: Element): nullable LRState
+ do
+ for t in outs do if t.elem == e then return t.to
+ return null
+ end
+
+ redef fun ==(o) do return o isa LRState and core == o.core
+ redef fun hash do return items.length
+
+ redef fun to_s do return items.join(" ; ")
+
+ # Add and item in the core
+ fun add(i: Item): Bool
+ do
+ #if items.has(i) then return
+
+ #print "add {i} in {inspect}={self}"
+ var found = false
+ for i2 in items do
+ if i.alt == i2.alt and i.pos == i2.pos then
+ if i2.future.has_all(i.future) then return false
+ i2.future.add_all(i.future)
+ found = true
+
+ break
+ end
+ end
+ if not found then
+ items.add(i)
+ if i.pos > 0 or i.alt.prod.accept then core.add(i)
+ end
+ return true
+ end
+
+ # Recusively extends item outside the core
+ fun extends(i: Item)
+ do
+ var e = i.next
+ if e == null then return
+ if not e isa Production then return
+ var la = i.lookahead
+ for i2 in e.start_state do
+ i2.future.add_all(la)
+ if add(i2) then extends(i2)
+ end
+ end
+
+ # Set of all reductions
+ var reduces = new ArraySet[Alternative]
+ # Set of all shifts
+ var shifts = new ArraySet[Token]
+ # Set of all goto
+ var gotos = new ArraySet[Production]
+ # Reduction guarded by tokens
+ var guarded_reduce = new HashMap[Token, Array[Item]]
+ # Shitfs guarded by tokens
+ var guarded_shift = new HashMap[Token, Array[Item]]
+
+ # Does the state need a guard to perform an action?
+ fun need_guard: Bool do return not shifts.is_empty or reduces.length > 1
+
+ # Is the state LR0
+ fun is_lr0: Bool do return reduces.length <= 1 and shifts.is_empty or reduces.is_empty
+
+ # compute guards and conflicts
+ fun analysis
+ do
+ for i in items.to_a do
+ extends(i)
+ end
+
+ for i in items do
+ var n = i.next
+ if n == null then
+ reduces.add(i.alt)
+ #for t in i.alt.prod.afters do
+ for t in i.future do
+ t.reduces.add(self)
+ if guarded_reduce.has_key(t) then
+ guarded_reduce[t].add(i)
+ else
+ guarded_reduce[t] = [i]
+ end
+ end
+ else if n isa Token then
+ shifts.add(n)
+ n.shifts.add(self)
+ if guarded_shift.has_key(n) then
+ guarded_shift[n].add(i)
+ else
+ guarded_shift[n] = [i]
+ end
+ else if n isa Production then
+ gotos.add(n)
+ n.gotos.add(self)
+ else
+ abort
+ end
+ end
+ for t, a in guarded_reduce do
+ if a.length > 1 then
+ print "REDUCE/REDUCE Conflict on state {self.number} {self.name} for token {t}:"
+ for i in a do print "\t{i}"
+ else if guarded_shift.has_key(t) then
+ print "SHIFT/REDUCE Conflict on state {self.number} {self.name} for token {t}:"
+ for i in a do print "\t{i}"
+ for i in guarded_shift[t] do print "\t{i}"
+ end
+ end
+ end
+end
+
+# A transition in a LR automaton
+class LRTransition
+ # The origin state
+ var from: LRState
+ # The testination state
+ var to: LRState
+ # The element labeling the transition
+ var elem: Element
+end
+
+# A alternative with a cursor (dot) and possibly a future
+class Item
+ # The alternative
+ var alt: Alternative
+ # The dot index (0 means before the first element)
+ var pos: Int
+ # The possible future
+ var future = new ArraySet[Token]
+
+ redef fun ==(o) do return o isa Item and alt == o.alt and pos == o.pos
+ redef fun hash do return alt.hash + pos
+
+ redef fun to_s
+ do
+ var b = new Buffer
+ b.append("{alt.prod.name}::{alt.name}=")
+ for i in [0..alt.elems.length[
+ do
+ if pos == i then b.append(".") else b.append(" ")
+ b.append(alt.elems[i].to_s)
+ end
+ if pos == alt.elems.length then b.append(".")
+ if not future.is_empty then
+ b.append("/\{")
+ b.append(future.join(" "))
+ b.append("\}")
+ end
+ return b.to_s
+ end
+
+ # The element thatr follow the dot, null if the fdot is at the end
+ fun next: nullable Element
+ do
+ if pos >= alt.elems.length then return null
+ return alt.elems[pos]
+ end
+
+ # SLR loohahead
+ fun lookahead: Set[Token]
+ do
+ var res = new HashSet[Token]
+ var p = pos + 1
+ while p < alt.elems.length do
+ var e = alt.elems[p]
+ if e isa Token then
+ res.add(e)
+ break
+ else if e isa Production then
+ res.add_all(e.firsts)
+ if not e.is_nullable then break
+ end
+ p += 1
+ end
+ if p >= alt.elems.length then
+ res.add_all(future)
+ end
+ return res
+ end
+
+ # The item that advanced once
+ fun avance: Item
+ do
+ var res = new Item(alt, pos+1)
+ res.future.add_all(future)
+ return res
+ end
+end