[nit.git] / contrib / nitcc / src / grammar.nit

# 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 FlatBuffer
                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 = null
                        if not p.alts.is_empty then 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:\n"
                                for x in p.firsts do res.append "\t//   {x}\n"
                        end
                        if not p.afters.is_empty then
                                res.append "\t// afters:\n"
                                for x in p.afters do res.append "\t//   {x}\n"
                        end
                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
                                if a.phony then continue
                                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 a.phony then continue
                                                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
                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)

                analyse

                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}"

                                # Look for an existing LR0 state in the automaton
                                var new_state = true
                                for n in seen do
                                        if n == next then
                                                next = n
                                                new_state = false
                                                break
                                        end
                                end

                                # If not, add it to the pool and the todo-list
                                if new_state then
                                        next.number = seen.length
                                        assert not seen.has(next)
                                        seen.add(next)
                                        todo.add(next)
                                end

                                # Add the transition
                                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
                                        if a.phony then continue
                                        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
                                        if a.phony then continue
                                        var i = a.first_item
                                        loop
                                                var e = i.next
                                                if e == null then break
                                                if e isa Token then
                                                        if try_add(fs, i) 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
                                                i = i.avance
                                        end
                                end
                        end
                        if not changed then break
                end

                loop
                        var changed = false
                        for p1 in prods do
                                for a in p1.alts do
                                        if a.phony then continue
                                        var p0: nullable Production = null
                                        var i = a.first_item
                                        loop
                                                var e = i.next
                                                if e == null then break
                                                var p = p0
                                                if e isa Production then p0 = e else p0 = null
                                                if p == null then
                                                        i = i.avance
                                                        continue
                                                end

                                                var afs = p.afters

                                                if e isa Token then
                                                        if try_add(afs, i) 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
                                                i = i.avance
                                        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[Item], t: Item): 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[Item]
        # The tokens that may follows the production (as in SLR)
        var afters = new HashSet[Item]


        # 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
                        if a.phony then continue
                        res.add a.first_item
                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 first item of the alternative
        var first_item = new Item(self, 0)

        # 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

        # Is the alternative unparsable? (ie not in the automaton)
        var phony 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"
                                if i.next != null then continue
                                for i2 in s.lookahead(i) do
                                        res.add "\t\t\t{i2}\n"
                                end
                        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"
                                if i.next != null then continue
                                for i2 in s.lookahead(i) do
                                        res.add "\t\t\t{i2}\n"
                                end
                        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 SLR\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, name: String)
        do
                var gen = new Generator
                gen.gen_to_nit(self, name)
                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, name: String)
        do
                var states = autom.states
                var gram = autom.grammar

                add "# Parser generated by nitcc for the grammar {name}"
                add "import nitcc_runtime"

                add "class Parser_{name}"
                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.children.add(n1)"
                else if alt.name.has_suffix("+_one") then
                        add "\t\tvar prod = new {alt.prod.acname}"
                        add "\t\tprod.children.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 false

                items.add(i)
                if i.pos > 0 or i.alt.prod.accept then core.add(i)
                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
                for i2 in e.start_state do
                        if add(i2) then extends(i2)
                end
        end

        # SLR lookahead
        fun lookahead(i: Item): Set[Item]
        do
                return i.alt.prod.afters
        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, Set[Item]]
        # Shitfs guarded by tokens
        var guarded_shift = new HashMap[Token, Set[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
                # Extends the core
                for i in items.to_a do
                        extends(i)
                end

                # Collect action and conflicts
                for i in items do
                        var n = i.next
                        if n == null then
                                reduces.add(i.alt)
                                for i2 in lookahead(i) do
                                        var t = i2.next
                                        assert t isa Token
                                        t.reduces.add(self)
                                        if not guarded_reduce.has_key(t) then
                                                guarded_reduce[t] = new ArraySet[Item]
                                        end
                                        guarded_reduce[t].add(i)
                                end
                        else if n isa Token then
                                shifts.add(n)
                                n.shifts.add(self)
                                if not guarded_shift.has_key(n) then
                                        guarded_shift[n] = new ArraySet[Item]
                                end
                                guarded_shift[n].add(i)
                        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 "\treduce: {i}"
                        else if guarded_shift.has_key(t) then
                                var ri = a.first
                                var confs = new Array[Item]
                                var ress = new Array[String]
                                var g = guarded_shift[t]
                                for si in lookahead(ri) do
                                        if si.next != t then continue
                                        if not g.has(si) then
                                                confs.add(si)
                                                continue
                                        end
                                        var p = ri.alt.prod
                                        var csi: nullable Item = null
                                        for bsi in back_expand(si) do
                                                if bsi.alt.prod == p then
                                                        csi = bsi
                                                        break
                                                end
                                        end
                                        if csi == null then
                                                confs.add(si)
                                                continue
                                        end
                                        ress.add "\tshift:  {si}"
                                        if si != csi then
                                                ress.add "\tcore shift: {csi}"
                                        end
                                end
                                if confs.is_empty then
                                        print "Automatic Dangling on state {self.number} {self.name} for token {t}:"
                                        print "\treduce: {ri}"
                                        for r in ress do print r
                                        guarded_reduce.keys.remove(t)
                                else
                                        print "SHIFT/REDUCE Conflict on state {self.number} {self.name} for token {t}:"
                                        print "\treduce: {ri}"
                                        for i in guarded_shift[t] do print "\tshift:  {i}"
                                end
                        end
                end
        end

        # Return `i` and all other items of the state that expands, directly or undirectly, to `i`
        fun back_expand(i: Item): Set[Item]
        do
                var res = new ArraySet[Item]
                var todo = [i]
                res.add(i)
                while not todo.is_empty do
                        var x = todo.pop
                        if x.pos > 0 then continue
                        var p = x.alt.prod
                        for y in items do
                                if y.next != p then continue
                                if res.has(y) then continue
                                res.add(y)
                                todo.add(y)
                        end
                end
                return res
        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) before an element
class Item
        # The alternative
        var alt: Alternative
        # The dot index (0 means before the first element)
        var pos: Int

        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 FlatBuffer
                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(".")
                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
                return res
        end

        # The item that advanced once
        fun avance: Item
        do
                var res = new Item(alt, pos+1)
                return res
        end
end