# See the License for the specific language governing permissions and
# limitations under the License.
-# A gramar describing a language
+# A grammar describing a language
class Gram
- # The productions (non-terminal) of the conctete grammar
+ # The productions (non-terminal) of the concrete grammar
var prods = new Array[Production]
- # The additionnal abstract productions of the grammar
+ # The additional abstract productions of the grammar
# TODO clean AST
var ast_prods = new Array[Production]
else
res.append("{p.name} =\n")
end
- var last = p.alts.last
+ var last = null
+ if not p.alts.is_empty then 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
return res.to_s
end
- # Inline (ie. remove from the conctete grammar) some production
+ # Inline (ie. remove from the concrete 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
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
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
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
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
# The alternative of the production
var alts = new Array[Alternative]
- # Additionnal alternatives in the AST
+ # Additional 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
+ # FIXME: cleanup AST
+ var spe: nullable Production = null is writable
# 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
+ var altone = false is writable
# The cname of the class in the AST
# FIXME: cleanup AST
# 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]
do
var res = new Array[Item]
for a in alts do
+ if a.phony then continue
res.add a.first_item
end
return res
var prod: Production
# The name of the alternative
- var name: String writable
+ var name: String is writable
# The elements of the alternative
var elems: Array[Element]
end
# The code for the reduction
- var codes: nullable Array[Code] writable = null
+ var codes: nullable Array[Code] = null is writable
# Is the alternative transformed (ie not in the AST)
- var trans writable = false
+ var trans = false is writable
- # Imitialize codes with the elements
+ # Is the alternative unparsable? (ie not in the automaton)
+ var phony = false is writable
+
+ # Initialize codes with the elements
fun make_codes
do
if codes != null then return
end
end
-# A step in the construction of the AST. used to modelize transformations
+# A step in the construction of the AST.
+# Used to model 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
+
+# Allocate a new AST node for an alternative using the correct number of popped elements
class CodeNew
super Code
+
+ # The associated alternative
var alt: Alternative
+
redef fun to_s do return "New {alt.name}/{alt.elems.length}"
end
+
# Get null
class CodeNull
super Code
# The mangled name of the element
fun cname: String do return "N{name.to_cmangle}"
- # the name of the class in the AST
+ # The name of the class in the AST
fun acname: String do
var res = acname_cache
if res == null then
end
return res
end
+
+ # The name of the class in the AST
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
+ # States of the LR automaton that shift on self
var shifts = new ArraySet[LRState]
- # States of the LR automatio that reduce on self in the lookahead(1)
+ # States of the LR automaton that reduce on self in the lookahead(1)
var reduces = new ArraySet[LRState]
end
res.add "\t\tREDUCE {r}\n"
end
end
- return res.to_s
+ return res.join
end
# Generate a graphviz file of the automaton
fun to_dot(path: String)
do
- var f = new OFStream.open(path)
+ var f = new FileWriter.open(path)
f.write("digraph g \{\n")
f.write("rankdir=LR;\n")
f.write("node[shape=Mrecord,height=0];\n")
do
var gen = new Generator
gen.gen_to_nit(self, name)
- var f = new OFStream.open(filepath)
+ var f = new FileWriter.open(filepath)
for s in gen.out do
f.write(s)
f.write("\n")
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)
var gram = autom.grammar
add "# Parser generated by nitcc for the grammar {name}"
+ add "module {name}_parser is generated, no_warning(\"missing-doc\",\"old-init\")"
add "import nitcc_runtime"
add "class Parser_{name}"
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}"
+ add "private 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}"
+ add "private fun goto_{p.cname}: Goto_{p.cname} do return once new Goto_{p.cname}"
+ for a in p.alts do
+ add "private fun reduce_{a.cname}(parser: Parser) do"
+ gen_reduce_to_nit(a)
+ add "end"
+ end
end
- add "end"
add "redef class NToken"
for s in states do
if s.reduces.length != 1 then
add "\t\tparser.parse_error"
else
- gen_reduce_to_nit(s.reduces.first)
+ add "\t\treduce_{s.reduces.first.cname}(parser)"
+ #gen_reduce_to_nit(s.reduces.first)
end
add "\tend"
end
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 "\t\treduce_{s.guarded_reduce[t].first.alt.cname}(parser)"
+ #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}\""
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)
+ add "\t\treduce_{s.reduces.first.cname}(parser)"
+ #gen_reduce_to_nit(s.reduces.first)
else
abort
end
# A state in a LR automaton
class LRState
- # name of the automaton (short part from the start)
+ # Name of the automaton (short part from the start)
var name: String
- # malglen name
- fun cname: String do return name.to_cmangle
+ # Mangled name
+ var cname: String is lazy do return name.to_cmangle
- # number
- var number: Int = -1
+ # Number
+ var number = -1
# Set of all items
var items = new HashSet[Item]
# Ingoing transitions
var outs = new Array[LRTransition]
- # trans function
+ # Trans function
fun trans(e: Element): nullable LRState
do
for t in outs do if t.elem == e then return t.to
return true
end
- # Recusively extends item outside the core
+ # Recursively extends item outside the core
fun extends(i: Item)
do
var e = i.next
var gotos = new ArraySet[Production]
# Reduction guarded by tokens
var guarded_reduce = new HashMap[Token, Set[Item]]
- # Shitfs guarded by tokens
+ # Shifts guarded by tokens
var guarded_shift = new HashMap[Token, Set[Item]]
# Does the state need a guard to perform an action?
# 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
+ # Compute guards and conflicts
fun analysis
do
# Extends the core
abort
end
end
+ # Token to remove as reduction guard to solve S/R conflicts
+ var removed_reduces = new Array[Token]
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
+ conflicting_items.add_all a
+ end
+ if guarded_shift.has_key(t) then
var ri = a.first
var confs = new Array[Item]
var ress = new Array[String]
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)
+ removed_reduces.add 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}"
+ removed_reduces.add t
+ conflicting_items.add_all a
+ conflicting_items.add_all guarded_shift[t]
end
end
end
+ for t in removed_reduces do
+ guarded_reduce.keys.remove(t)
+ t.reduces.remove(self)
+ end
end
- # Return `i` and all other items of the state that expands, directly or undirectly, to `i`
+ # Items within a reduce/reduce or a shift/reduce conflict.
+ #
+ # Is computed by `analysis`
+ var conflicting_items = new ArraySet[Item]
+
+ # Return `i` and all other items of the state that expands, directly or indirectly, to `i`
fun back_expand(i: Item): Set[Item]
do
var res = new ArraySet[Item]
class LRTransition
# The origin state
var from: LRState
- # The testination state
+ # The destination state
var to: LRState
# The element labeling the transition
var elem: Element
return b.to_s
end
- # The element thatr follow the dot, null if the fdot is at the end
+ # The element that follows the dot, null if the dot is at the end
fun next: nullable Element
do
if pos >= alt.elems.length then return null
return alt.elems[pos]
end
- # SLR loohahead
+ # SLR lookahead
fun lookahead: Set[Token]
do
var res = new HashSet[Token]
nitlanguage / nit.git / blobdiff