# 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]
# Dump of the concrete grammar and the transformations
fun pretty: String
do
- var res = new Buffer
+ 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 = 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
+
+ # Is the alternative unparsable? (ie not in the automaton)
+ var phony = false is writable
- # Imitialize codes with the elements
+ # 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
# 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 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}"
end
- add "end"
add "redef class NToken"
for s in states do
# 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
+ # Mangled name
fun cname: String do return name.to_cmangle
- # number
+ # Number
var number: Int = -1
# Set of all items
# 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
- for ri in a.to_a do for si in guarded_shift[t] do
- if lookahead(ri).has(si) then
- 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 continue
- print "Automatic Dangling on state {self.number} {self.name} for token {t}:"
- print "\treduce: {ri}"
- print "\tshift: {si}"
- if si != csi then
- print "\tcore shift: {csi}"
+ end
+ 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
- a.remove(ri)
+ 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 a.is_empty then
- guarded_reduce.keys.remove(t)
+ 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
+ removed_reduces.add t
else
print "SHIFT/REDUCE Conflict on state {self.number} {self.name} for token {t}:"
- for i in a do print "\treduce: {i}"
+ print "\treduce: {ri}"
for i in guarded_shift[t] do print "\tshift: {i}"
+ removed_reduces.add 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`
+ # 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
redef fun to_s
do
- var b = new Buffer
+ var b = new FlatBuffer
b.append("{alt.prod.name}::{alt.name}=")
for i in [0..alt.elems.length[
do
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