README: document nit_env.sh
[nit.git] / lib / nitcc_runtime.nit
1 # This file is part of NIT ( http://www.nitlanguage.org ).
2 #
3 # Licensed under the Apache License, Version 2.0 (the "License");
4 # you may not use this file except in compliance with the License.
5 # You may obtain a copy of the License at
6 #
7 # http://www.apache.org/licenses/LICENSE-2.0
8 #
9 # Unless required by applicable law or agreed to in writing, software
10 # distributed under the License is distributed on an "AS IS" BASIS,
11 # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 # See the License for the specific language governing permissions and
13 # limitations under the License.
14
15 # Runtime library required by parsers and lexers generated by nitcc
16 module nitcc_runtime
17
18 # A abstract parser engine generated by nitcc
19 abstract class Parser
20 # The list of tokens
21 # FIXME: provide something better, like a lexer?
22 var tokens = new List[NToken]
23
24 # Look at the next token
25 # Used by generated parsers
26 fun peek_token: NToken do return tokens.first
27
28 # Consume the next token
29 # Used by generated parsers
30 fun get_token: NToken do return tokens.shift
31
32 # Consume the next token and shift to the state `dest`.
33 # Used by generated parsers
34 fun shift(dest: LRState)
35 do
36 var t = get_token
37 #print "shift {t} -> {dest}"
38 node_stack.push t
39 state_stack.push state
40 state = dest
41 end
42
43 # After a reduction on `goto` go to the next state
44 # Used by generated parsers
45 fun goto(goto: LRGoto)
46 do
47 #print "reduce from {state} -> {prod}"
48 state.goto(self, goto)
49 end
50
51 # push a new state on the stack of states (
52 # Used by generated parsers
53 fun push(dest: LRState)
54 do
55 #print "push prod {prod} -> {dest}"
56 state_stack.push state
57 state = dest
58 end
59
60 # Pop and return the last node
61 # Also pop (and discard) the associated state
62 # Used by generated parsers
63 fun pop: Node
64 do
65 var res = node_stack.pop
66 state = state_stack.pop
67 return res
68 end
69
70 # Produce a parse error and stop the parsing
71 # Used by generated parsers
72 fun parse_error
73 do
74 var token = peek_token
75 #print "* parse error in state {state} on token {token}"
76 #print " expected: {state.error_msg}"
77 #print " node_stack={node_stack.join(", ")}"
78 #print " state_stack={state_stack.join(", ")}"
79 node_stack.add(token)
80 var error: NError
81 if token isa NLexerError then
82 error = token
83 else
84 error = new NParserError
85 error.position = token.position
86 error.text = token.text
87 error.token = token
88 end
89 error.error_tree.children.add_all(node_stack)
90 error.expected = state.error_msg
91 node_stack.clear
92 node_stack.add error
93 stop = true
94 end
95
96 # The stating state for parsing
97 # Used by generated parsers
98 protected fun start_state: LRState is abstract
99
100 # The current state
101 # Used by generated parsers
102 var state: LRState is noinit
103
104 init
105 do
106 state = start_state
107 end
108
109 # The stack of nodes
110 # Used by generated parsers
111 var node_stack = new Array[Node]
112
113 # The stack of states
114 # Used by generated parsers
115 var state_stack = new Array[LRState]
116
117 # Should the parser stop
118 # Used by generated parsers
119 var stop = true is writable
120
121 # Parse a full sequence of tokens and return a complete syntactic tree
122 fun parse: Node
123 do
124 state = start_state
125 state_stack.clear
126 node_stack.clear
127 stop = false
128 while not stop do
129 #print "* current state {state}"
130 #print " tokens={tokens.join(" ")}"
131 #print " node_stack={node_stack.join(" ")}"
132 #print " state_stack={state_stack.join(" ")}"
133 state.action(self)
134 end
135 #print "* over"
136 return node_stack.first
137 end
138 end
139
140 # A state in a parser LR automaton generated by nitcc
141 # Used by generated parsers
142 abstract class LRState
143 fun action(parser: Parser) is abstract
144 fun goto(parser: Parser, goto: LRGoto) is abstract
145 fun error_msg: String do return "FIXME"
146 end
147
148 # A concrete production in a parser LR automation generated by nitcc
149 # Used by generated parsers
150 abstract class LRGoto
151 end
152
153 ###
154
155 # A abstract lexer engine generated by nitcc
156 abstract class Lexer
157 # The input stream of characters
158 var stream: String
159
160 # The stating state for lexing
161 # Used by generated parsers
162 protected fun start_state: DFAState is abstract
163
164 # Lexize a stream of characters and return a sequence of tokens
165 fun lex: List[NToken]
166 do
167 var res = new List[NToken]
168 var state = start_state
169 var pos = 0
170 var pos_start = 0
171 var pos_end = 0
172 var line = 1
173 var line_start = 1
174 var line_end = 0
175 var col = 1
176 var col_start = 1
177 var col_end = 0
178 var last_state: nullable DFAState = null
179 var text = stream
180 var length = text.length
181 loop
182 if state.is_accept then
183 pos_end = pos - 1
184 line_end = line
185 col_end = col
186 last_state = state
187 end
188 var c
189 var next
190 if pos >= length then
191 c = '\0'
192 next = null
193 else
194 c = text.chars[pos]
195 next = state.trans(c)
196 end
197 if next == null then
198 if pos_start < length then
199 if last_state == null then
200 var token = new NLexerError
201 var position = new Position(pos_start, pos, line_start, line, col_start, col)
202 token.position = position
203 token.text = text.substring(pos_start, pos-pos_start+1)
204 res.add token
205 break
206 end
207 var position = new Position(pos_start, pos_end, line_start, line_end, col_start, col_end)
208 var token = last_state.make_token(position, text.substring(pos_start, pos_end-pos_start+1))
209 if token != null then res.add(token)
210 end
211 if pos >= length then
212 var token = new NEof
213 var position = new Position(pos, pos, line, line, col, col)
214 token.position = position
215 token.text = ""
216 res.add token
217 break
218 end
219 state = start_state
220 pos_start = pos_end + 1
221 pos = pos_start
222 line_start = line_end
223 line = line_start
224 col_start = col_end
225 col = col_start
226
227 last_state = null
228 continue
229 end
230 state = next
231 pos += 1
232 col += 1
233 if c == '\n' then
234 line += 1
235 col = 1
236 end
237 end
238 return res
239 end
240 end
241
242 # A state in a lexer automaton generated by nitcc
243 # Used by generated lexers
244 interface DFAState
245 fun is_accept: Bool do return false
246 fun trans(c: Char): nullable DFAState do return null
247 fun make_token(position: Position, text: String): nullable NToken is abstract
248 end
249
250 ###
251
252 # A abstract visitor on syntactic trees generated by nitcc
253 abstract class Visitor
254 # The main entry point to visit a node `n`
255 # Should not be redefined
256 fun enter_visit(n: Node)
257 do
258 visit(n)
259 end
260
261 # The specific implementation of a visit
262 #
263 # Should be redefined by concrete visitors
264 #
265 # Should not be called directly (use `enter_visit` instead)
266 #
267 # By default, the visitor just rescursively visit the children of `n`
268 protected fun visit(n: Node)
269 do
270 n.visit_children(self)
271 end
272 end
273
274 # Print a node (using to_s) on a line and recustively each children indented (with two spaces)
275 class TreePrinterVisitor
276 super Visitor
277 var writer: Writer
278 private var indent = 0
279 redef fun visit(n)
280 do
281 for i in [0..indent[ do writer.write(" ")
282 writer.write(n.to_s)
283 writer.write("\n")
284 indent += 1
285 super
286 indent -= 1
287 end
288 end
289
290 # A position into a input stream
291 # Used to give position to tokens
292 class Position
293 var pos_start: Int
294 var pos_end: Int
295 var line_start: Int
296 var line_end: Int
297 var col_start: Int
298 var col_end: Int
299
300 redef fun to_s do return "{line_start}:{col_start}-{line_end}:{col_end}"
301
302 # Get the lines covered by `self` and underline the target columns.
303 #
304 # This is useful for pretty printing errors or debug the output
305 #
306 # ~~~
307 # var src = "var Foo = new Array[Int]"
308 # var pos = new Position(0,0, 1, 1, 5, 8)
309 #
310 # assert pos.underline(src) == """
311 # var Foo = new Array[Int]
312 # ^^^"""
313 # ~~~
314 fun underline(source: Text): String
315 do
316 var res = new FlatBuffer
317
318 # All the concerned lines
319 var lines = source.split("\n")
320 for line in [line_start..line_end] do
321 res.append lines[line-1]
322 res.append "\n"
323 end
324
325 # Cover all columns, no matter their lines
326 var col_start = col_start.min(col_end)
327 var col_end = self.col_start.max(col_end)
328
329 # " ^^^^"
330 var ptr = " "*(col_start-1).max(0) + "^"*(col_end-col_start)
331 res.append ptr
332
333 return res.to_s
334 end
335 end
336
337 # A node of a syntactic tree
338 abstract class Node
339 # The name of the node (as used in the grammar file)
340 fun node_name: String do return class_name
341
342 # A point of view on the direct children of the node
343 fun children: SequenceRead[nullable Node] is abstract
344
345 # A point of view of a depth-first visit of all non-null children
346 var depth: Collection[Node] = new DephCollection(self)
347
348 # Visit all the children of the node with the visitor `v`
349 protected fun visit_children(v: Visitor)
350 do
351 for c in children do if c != null then v.enter_visit(c)
352 end
353
354 # The position of the node in the input stream
355 var position: nullable Position = null is writable
356
357 # Produce a graphiz file for the syntaxtic tree rooted at `self`.
358 fun to_dot(filepath: String)
359 do
360 var f = new FileWriter.open(filepath)
361 f.write("digraph g \{\n")
362 f.write("rankdir=BT;\n")
363
364 var a = new Array[NToken]
365 to_dot_visitor(f, a)
366
367 f.write("\{ rank=same\n")
368 var first = true
369 for n in a do
370 if first then
371 first = false
372 else
373 f.write("->")
374 end
375 f.write("n{n.object_id}")
376 end
377 f.write("[style=invis];\n")
378 f.write("\}\n")
379
380 f.write("\}\n")
381 f.close
382 end
383
384 private fun to_dot_visitor(f: Writer, a: Array[NToken])
385 do
386 f.write("n{object_id} [label=\"{node_name}\"];\n")
387 for x in children do
388 if x == null then continue
389 f.write("n{x.object_id} -> n{object_id};\n")
390 x.to_dot_visitor(f,a )
391 end
392 end
393
394 redef fun to_s do
395 var pos = position
396 if pos == null then
397 return "{node_name}"
398 else
399 return "{node_name}@({pos})"
400 end
401 end
402 end
403
404 private class DephCollection
405 super Collection[Node]
406 var node: Node
407 redef fun iterator do return new DephIterator([node].iterator)
408 end
409
410 private class DephIterator
411 super Iterator[Node]
412
413 var stack = new List[Iterator[nullable Node]]
414
415 init(i: Iterator[nullable Node]) is old_style_init do
416 stack.add i
417 end
418
419 redef fun is_ok do return not stack.is_empty
420 redef fun item do return stack.last.item.as(not null)
421 redef fun next
422 do
423 var i = stack.last
424 stack.push i.item.children.iterator
425 i.next
426 while is_ok do
427 if not stack.last.is_ok then
428 stack.pop
429 continue
430 end
431 if stack.last.item == null then
432 stack.last.next
433 continue
434 end
435 return
436 end
437 end
438 end
439
440 # A token produced by the lexer and used in a syntactic tree
441 abstract class NToken
442 super Node
443
444 redef fun children do return once new Array[Node]
445
446 redef fun to_dot_visitor(f, a)
447 do
448 var labe = "{node_name}"
449 var pos = position
450 if pos != null then labe += "\\n{pos}"
451 var text = self.text
452 if node_name != "'{text}'" then
453 labe += "\\n'{text.escape_to_c}'"
454 end
455 f.write("n{object_id} [label=\"{labe}\",shape=box];\n")
456 a.add(self)
457 end
458
459 # The text associated with the token
460 var text: String = "" is writable
461
462 redef fun to_s do
463 var res = super
464 var text = self.text
465 if node_name != "'{text}'" then
466 res += "='{text.escape_to_c}'"
467 end
468 return res
469 end
470 end
471
472 # The special token for the end of stream
473 class NEof
474 super NToken
475 end
476
477 # A special token used to represent a parser or lexer error
478 abstract class NError
479 super NToken
480
481 # All the partially built tree during parsing (aka the node_stack)
482 var error_tree = new Nodes[Node]
483
484 # The things unexpected
485 fun unexpected: String is abstract
486
487 # The things expected (if any)
488 var expected: nullable String = null
489
490 # The error message,using `expected` and `unexpected`
491 fun message: String
492 do
493 var exp = expected
494 var res = "Unexpected {unexpected}"
495 if exp != null then res += "; is acceptable instead: {exp}"
496 return res
497 end
498 end
499
500 # A lexer error as a token for the unexpected characted
501 class NLexerError
502 super NError
503
504 redef fun unexpected do return "character '{text.chars.first}'"
505 end
506
507 # A parser error linked to a unexpected token
508 class NParserError
509 super NError
510
511 # The unexpected token
512 var token: nullable NToken = null
513
514 redef fun unexpected
515 do
516 var res = token.node_name
517 var text = token.text
518 if not text.is_empty and res != "'{text}'" then
519 res += " '{text.escape_to_c}'"
520 end
521 return res
522 end
523 end
524
525 # A hogeneous sequence of node, used to represent unbounded lists (and + modifier)
526 class Nodes[T: Node]
527 super Node
528 redef var children: Array[T] = new Array[T]
529 end
530
531 # A production with a specific, named and statically typed children
532 abstract class NProd
533 super Node
534 redef var children: SequenceRead[nullable Node] = new NProdChildren(self)
535
536 # The exact number of direct children
537 # Used to implement `children` by generated parsers
538 fun number_of_children: Int is abstract
539
540 # The specific children got by its index
541 # Used to implement `children` by generated parsers
542 fun child(x: Int): nullable Node is abstract
543 end
544
545
546 private class NProdChildren
547 super SequenceRead[nullable Node]
548 var prod: NProd
549 redef fun iterator do return new NProdIterator(prod)
550 redef fun length do return prod.number_of_children
551 redef fun is_empty do return prod.number_of_children == 0
552 redef fun [](i) do return prod.child(i)
553 end
554
555 private class NProdIterator
556 super IndexedIterator[nullable Node]
557 var prod: NProd
558 redef var index = 0
559 redef fun is_ok do return index < prod.number_of_children
560 redef fun next do index += 1
561 redef fun item do return prod.child(index)
562 end
563
564 # All-in-one abstract class to test generated parsers on a given
565 abstract class TestParser
566 # How to get a new lexer on a given stream of character
567 fun new_lexer(text: String): Lexer is abstract
568
569 # How to get a new parser
570 fun new_parser: Parser is abstract
571
572 # The name of the language (used for generated files)
573 fun name: String is abstract
574
575 # Use the class as the main enrty point of the program
576 # - parse arguments and options of the command
577 # - test the parser (see `work`)
578 fun main: Node
579 do
580 if args.is_empty then
581 print "usage {name}_test <filepath> | - | -e <text>"
582 exit 0
583 end
584
585 var filepath = args.shift
586 var text
587 if filepath == "-" then
588 text = sys.stdin.read_all
589 else if filepath == "-e" then
590 if args.is_empty then
591 print "Error: -e need a text"
592 exit 1
593 end
594 text = args.shift
595 else
596 var f = new FileReader.open(filepath)
597 text = f.read_all
598 f.close
599 end
600
601 if not args.is_empty then
602 print "Error: superfluous arguments."
603 exit 1
604 end
605
606 return work(text)
607 end
608
609 # Produce a full syntactic tree for a given stream of character
610 # Produce also statistics and output files
611 fun work(text: String): Node
612 do
613 print "INPUT: {text.length} chars"
614 var l = new_lexer(text)
615 var tokens = l.lex
616
617 var tokout = "{name}.tokens.out"
618 print "TOKEN: {tokens.length} tokens (see {tokout})"
619
620 var f = new FileWriter.open(tokout)
621 for t in tokens do
622 f.write "{t.to_s}\n"
623 end
624 f.close
625
626 var p = new_parser
627 p.tokens.add_all(tokens)
628
629 var n = p.parse
630
631 var astout = "{name}.ast.out"
632 f = new FileWriter.open(astout)
633 var tpv = new TreePrinterVisitor(f)
634 var astdotout = "{name}.ast.dot"
635 if n isa NError then
636 print "Syntax error: {n.message}"
637 print "ERROR: {n} (see {astout} and {astdotout})"
638 tpv.enter_visit(n)
639 n = n.error_tree
640 else
641 print "ROOT: {n}; {n.depth.length} nodes (see {astout} and {astdotout})"
642 end
643 tpv.enter_visit(n)
644 n.to_dot(astdotout)
645 f.close
646
647 return n
648 end
649 end