import minilang_test_parser
+# An naive recursive stack-based interpreter of the minilang language.
class Interpretor
super Visitor
+
+ # A stack of numeric values
var stack = new Array[Int]
+
+ # A stack of boolean values
var bstack = new Array[Bool]
+
+ # The current values assigned to each variable
var vars = new HashMap[String, Int]
redef fun visit(n) do n.accept_calculator(self)
end
redef class Node
+ # Execution of the node by the interpreter `v`
fun accept_calculator(v: Interpretor) do visit_children(v)
end
# The start state
var start: State
- # State that are accect states
+ # State that are accept states
var accept = new Array[State]
# All states
var states = new Array[State]
- # Tokens associated on accept states
- # use `add_tag` to update
+ # Tokens associated on accept states.
+ # Use `add_tag` to update
var tags = new HashMap[State, Set[Token]]
- # Accept states associated on tokens
- # use `add_tag` to update
+ # Accept states associated on tokens.
+ # Use `add_tag` to update
var retrotags = new HashMap[Token, Set[State]]
# Tag all accept states
assert retrotags[t].has(s)
end
- # Remove all occurences of a tag in an automaton
+ # Remove all occurrences of a tag in an automaton
fun clear_tag(t: Token)
do
if not retrotags.has_key(t) then return
retrotags.keys.remove(t)
end
- # Remove tokens from conflicting state according the the inclusion of language
+ # Remove tokens from conflicting state according the inclusion of language.
# REQUIRE: self isa DFA automaton
fun solve_token_inclusion
do
end
end
- # Initialize a new automaton for the empty language
- # one state, no accept, no transition
+ # Initialize a new automaton for the empty language.
+ # One state, no accept, no transition.
init empty
do
var state = new State
states.add state
end
- # Initialize a new automaton for the empty-string language
- # one state, is accept, no transition
+ # Initialize a new automaton for the empty-string language.
+ # One state, is accept, no transition.
init epsilon
do
var state = new State
states.add state
end
- # Initialize a new automation for the language that accepts only a single symbol
- # Two state, the second is accept, one transition on `symbol`
+ # Initialize a new automation for the language that accepts only a single symbol.
+ # Two state, the second is accept, one transition on `symbol`.
init atom(symbol: Int)
do
var s = new State
states.add a
end
- # Contatenate `other` to `self`
- # other is modified and invalidated.
+ # Concatenate `other` to `self`.
+ # Other is modified and invalidated.
fun concat(other: Automaton)
do
var s2 = other.start
states.add_all other.states
end
- # `self` become the alternation of `self` and `other`
+ # `self` become the alternation of `self` and `other`.
# `other` is modified and invalidated.
fun alternate(other: Automaton)
do
states.add_all other.states
end
- # Return a new automaton that recognize `self` but not `other`
- # For a theorical POV, this is the substraction of languages.
- # Note: the implementation use `to_dfa` internally, so the theorical complexity is not cheap.
+ # Return a new automaton that recognize `self` but not `other`.
+ # For a theoretical POV, this is the subtraction of languages.
+ # Note: the implementation use `to_dfa` internally, so the theoretical complexity is not cheap.
fun except(other: Automaton): Automaton
do
var ta = new Token("1")
return c
end
- # `self` absorbs all states, transisions, tags, and acceptations of `other`
- # An epsilon transition is added between `self.start` and `other.start`
+ # `self` absorbs all states, transitions, tags, and acceptations of `other`.
+ # An epsilon transition is added between `self.start` and `other.start`.
fun absorb(other: Automaton)
do
states.add_all other.states
f.close
end
- # Transform a NFA to a DFA
- # note: the DFA is not miminized
+ # Transform a NFA to a DFA.
+ # note: the DFA is not minimized.
fun to_dfa: Automaton
do
trim
return dfa
end
- # epsilon-closure on a state of states
- # used by `to_dfa`
+ # Epsilon-closure on a state of states.
+ # Used by `to_dfa`.
private fun eclosure(states: Collection[State]): Set[State]
do
var res = new ArraySet[State]
return res
end
- # trans on a set of states
- # Used by `to_dfa`
+ # Trans on a set of states.
+ # Used by `to_dfa`.
fun trans(states: Collection[State], symbol: Int): Set[State]
do
var res = new ArraySet[State]
return res
end
- # Generate the Nit source code of the lexer
- # `filepath` is the name of the ouptit file
- # `parser` is the name of the parser module (used to import the token classes)
+ # Generate the Nit source code of the lexer.
+ # `filepath` is the name of the output file.
+ # `parser` is the name of the parser module (used to import the token classes).
fun gen_to_nit(filepath: String, name: String, parser: nullable String)
do
var gen = new DFAGenerator(filepath, name, self, parser)
var automaton: Automaton
var parser: nullable String
- var out: OStream
- init(filepath: String, name: String, automaton: Automaton, parser: nullable String) do
- self.filepath = filepath
- self.name = name
- self.automaton = automaton
- self.parser = parser
+ var out: OStream is noinit
+
+ init do
self.out = new OFStream.open(filepath)
end
# A state in a finite automaton
class State
# Outgoing transitions
-
var outs = new Array[Transition]
- # Ingoing tyransitions
+
+ # Ingoing transitions
var ins = new Array[Transition]
# Add a transitions to `to` on `symbol` (null means epsilon)
return t
end
+ # Get the first state following the transition `i`.
+ # Null if no transition for `i`.
fun trans(i: Int): nullable State
do
for t in outs do
# A range of symbols on a transition
class TSymbol
+ # The first symbol in the range
var first: Int
+
+ # The last symbol if any.
+ #
+ # `null` means infinity.
var last: nullable Int
redef fun to_s
# The symbol on the transition (null means epsilon)
var symbol: nullable TSymbol
- # Remove the transition from the automaton
- # Detash from `from` and `to`
+ # Remove the transition from the automaton.
+ # Detach from `from` and `to`.
fun delete
do
from.outs.remove(self)
# 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
# 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
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]
# See the License for the specific language governing permissions and
# limitations under the License.
-# Ad-hoc hand-writen lexer for nitcc
-# This avoid to commit (and relyon ) a generated lexer
-#
+# Ad-hoc hand-written lexer for nitcc
+# This avoid to commit (and rely on) a generated lexer
module nitcc_lexer0
# Required for the tokens definitions
import nitcc_parser
-# Hand-writen lexer of nitcc
-# Used only for the boostrap of the tool.
+# Hand-written lexer of nitcc.
+# Used only for the bootstrap of the tool.
class Lexer_nitcc
+ # The text to tokenize
var text: String
- var iter: Iterator[Char] = "".chars.iterator
+ # The iterator on text
+ private var iter: Iterator[Char] is noinit
+
+ # The current position
var pos = 0
- var tokens = new Array[NToken]
+ # The tokens currently produced
+ private var tokens = new Array[NToken]
+ # Tokenize and returns the tokens
fun lex: Array[NToken]
do
iter = text.chars.iterator
return tokens
end
- fun error(c: Char)
+ private fun error(c: Char)
do
print "pos {pos}: Lexer error on '{c}'."
abort
end
- fun str
+ private fun str
do
var b = new FlatBuffer
b.add('\'')
abort
end
- fun id(c: Char)
+ private fun id(c: Char)
do
var b = new FlatBuffer
b.add c
tokens.add token
end
- fun kw(c: Char)
+ private fun kw(c: Char)
do
var b = new FlatBuffer
b.add c
tokens.add token
end
- fun trim
+ private fun trim
do
while iter.is_ok and iter.item <= ' ' do
iter.next
class CollectNameVisitor
super Visitor
+ # All the productions
var nprods = new Array[Nprod]
# Symbol table to associate things (prods and exprs) with their name
# The current production, used to initialize priorities
var prod: nullable Production = null
- # The current priority counter to name tranformed productions
+ # The current priority counter to name transformed productions
var pricpt: Int = 0
# Run the semantic analysis of the grammar
# First visit to collect names
enter_visit(n)
- # Second visit to use collectec names and build rhings
+ # Second visit to use collected names and build things
var v2 = new CheckNameVisitor(self)
v2.enter_visit(n)
- # Inline all the ?
+ # Inline all the `?`
gram.inline(v2.quesizes.values)
- # Inlile all the prods sufixed by '_imline' #TODO use a real keyword
+ # Inline all the prods suffixed by '_inline' #TODO use a real keyword
for p in gram.prods do
if not p.name.has_suffix("_inline") then continue
print "inline {p}"
# The collected element names, for the alternative
var elems_names = new Array[nullable String]
- # The collected elementname, for the nelem
+ # The collected element names, for the nelem
var elemname: nullable String = null
# Is the alternative transformed, for the alternative
var trans = false
# The current priority class
- # Used the check, and tranform the grammar
+ # Used the check, and transform the grammar
var pri: nullable Npriority = null
# Known ignored tokens
var rejecteds = new Array[Element]
# Pool of elements that are modified with + (reuse them!)
- private var plusizes = new HashMap[Element, Production]
+ var plusizes = new HashMap[Element, Production]
# Create a + version of an element
fun plusize(e: Element): Production
end
# Pool of elements that are modified with ? (reuse them!)
- private var quesizes = new HashMap[Element, Production]
+ var quesizes = new HashMap[Element, Production]
# Create a ? version of an element
fun quesize(e: Element): Production
end
# The current nexpr, used to track dependency on named expressions (see `Nexpr::precs`)
- var nexpr: nullable Nexpr
+ var nexpr: nullable Nexpr = null
# The current production, used to initialize alternatives
- var prod: nullable Production
+ var prod: nullable Production = null
# The main visitor, used to access the grammar of the symbol table
var v1: CollectNameVisitor
- init(v1: CollectNameVisitor) do self.v1 = v1
redef fun visit(n) do n.accept_check_name_visitor(self)
end
# The associated NFA (cached, see `build_nfa`)
private var nfa: nullable Automaton
- # Build the NFA, possibily building the NFA of required expressions
+ # Build the NFA, possibly building the NFA of required expressions
# Print an error if there is a circular dependency
# The result is cached
fun build_nfa: Automaton do
abort
else if e isa Token then
# The token was build and registered during the visit
- # So, unregister then, the bit Ignred token will be build later
+ # So, unregister them, the big Ignored token will be build later
v.v1.gram.tokens.remove(e)
else
abort
end
redef class Nprod
- # The associated main production
- # ie the last priority class
+ # The associated main production.
+ # i.e. the last priority class.
var prod: nullable Production
- # The associated most-priority production
- # ie the first priority class
- # If there is no priority then `sub_prod == prod`
+ # The associated most-priority production.
+ # i.e. the first priority class.
+ # If there is no priority then `sub_prod == prod`.
var sub_prod: nullable Production
redef fun accept_collect_prod(v) do
end
redef class Npriority
+ # It is the last priority group?
var is_last = false
# The associated production
var prod: nullable Production
- # The production in the with the next less priority class
- # null is there is no priority or if the first priority class
+ # The production in the with the next less priority class.
+ # `null` if there is no priority or if the first priority class.
var next: nullable Production
redef fun accept_collect_prod(v) do
v.pri = self
super
- # Inject a new alternative that goes to the next less prioty class
+ # Inject a new alternative that goes to the next less priority class
var alt = prod.new_alt2(prod.name + "_" + prod.alts.length.to_s, [next.as(not null)])
alt.trans = true
alt.codes = [new CodePop]
end
redef class Alternative
+ # The short name of the alternative.
+ # Used for errors
var short_name: nullable String
end
redef fun make_rfa: Automaton
do
var a = new Automaton.epsilon
- var val
for c in self.value.chars do
var b = new Automaton.atom(c.ascii)
a.concat(b)
nitlanguage / nit.git / commitdiff