# 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]
res.append("{p.name} =\n")
end
var last = null
- if not p.alts.is_empty then p.alts.last
+ 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
# 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
+ # 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)
# 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]
# 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
+ 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
end
end
end
+ for t in removed_reduces do
+ guarded_reduce.keys.remove(t)
+ 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
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