X-Git-Url: http://nitlanguage.org diff --git a/contrib/nitcc/src/grammar.nit b/contrib/nitcc/src/grammar.nit index 3a5d97e..fc10a98 100644 --- a/contrib/nitcc/src/grammar.nit +++ b/contrib/nitcc/src/grammar.nit @@ -12,12 +12,12 @@ # 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] @@ -34,7 +34,8 @@ class Gram 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 @@ -54,12 +55,13 @@ class Gram 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 @@ -87,6 +89,7 @@ class Gram 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 @@ -206,6 +209,7 @@ class Gram 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 @@ -232,6 +236,7 @@ class Gram 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 @@ -258,6 +263,7 @@ class Gram 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 @@ -316,19 +322,19 @@ class Production # 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 @@ -339,8 +345,10 @@ class Production # 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] @@ -374,6 +382,7 @@ class Production do var res = new Array[Item] for a in alts do + if a.phony then continue res.add a.first_item end return res @@ -389,7 +398,7 @@ class Alternative 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] @@ -417,12 +426,15 @@ class Alternative 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 @@ -435,20 +447,27 @@ class Alternative 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 @@ -467,7 +486,7 @@ abstract class Element # 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 @@ -476,15 +495,17 @@ abstract class Element 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 @@ -554,7 +575,7 @@ class LRAutomaton # 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") @@ -601,7 +622,7 @@ class LRAutomaton 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") @@ -610,14 +631,6 @@ class LRAutomaton 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) @@ -627,6 +640,7 @@ private class Generator 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}" @@ -634,14 +648,12 @@ private class Generator 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 @@ -870,13 +882,13 @@ 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 + # Mangled name fun cname: String do return name.to_cmangle - # number + # Number var number: Int = -1 # Set of all items @@ -891,7 +903,7 @@ class LRState # 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 @@ -913,7 +925,7 @@ class LRState return true end - # Recusively extends item outside the core + # Recursively extends item outside the core fun extends(i: Item) do var e = i.next @@ -938,7 +950,7 @@ class LRState 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? @@ -947,7 +959,7 @@ class LRState # 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 @@ -983,6 +995,8 @@ class LRState 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}:" @@ -1019,7 +1033,7 @@ class LRState 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}" @@ -1027,9 +1041,12 @@ class LRState 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] @@ -1054,7 +1071,7 @@ end 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 @@ -1083,14 +1100,14 @@ class Item 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]