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                 var error: NError
  80                 if token isa NLexerError then
  81                         error = token
  82                 else
  83                         error = new NParserError
  84                         error.position = token.position
  85                         error.text = token.text
  86                         error.token = token
  87                 end
  88                 error.error_tree.items.add_all(node_stack)
  89                 error.expected = state.error_msg
  90                 node_stack.clear
  91                 node_stack.add error
  92                 stop = true
  93         end
  94
  95         # The stating state for parsing
  96         # Used by generated parsers
  97         protected fun start_state: LRState is abstract
  98
  99         # The current state
 100         # Used by generated parsers
 101         var state: LRState
 102
 103         init
 104         do
 105                 state = start_state
 106         end
 107
 108         # The stack of nodes
 109         # Used by generated parsers
 110         var node_stack = new Array[Node]
 111
 112         # The stack of states
 113         # Used by generated parsers
 114         var state_stack = new Array[LRState]
 115
 116         # Should the parser stop
 117         # Used by generated parsers
 118         var stop writable = true
 119
 120         # Parse a full sequence of tokens and return a complete syntactic tree
 121         fun parse: Node
 122         do
 123                 state = start_state
 124                 state_stack.clear
 125                 node_stack.clear
 126                 stop = false
 127                 while not stop do
 128                         #print "* current state {state}"
 129                         #print "  tokens={tokens.join(" ")}"
 130                         #print "  node_stack={node_stack.join(" ")}"
 131                         #print "  state_stack={state_stack.join(" ")}"
 132                         state.action(self)
 133                 end
 134                 #print "* over"
 135                 return node_stack.first
 136         end
 137 end
 138
 139 # A state in a parser LR automaton generated by nitcc
 140 # Used by generated parsers
 141 abstract class LRState
 142         fun action(parser: Parser) is abstract
 143         fun goto(parser: Parser, goto: LRGoto) is abstract
 144         fun error_msg: String do return "FIXME"
 145 end
 146
 147 # A concrete production in a parser LR automation generated by nitcc
 148 # Used by generated parsers
 149 abstract class LRGoto
 150 end
 151
 152 ###
 153
 154 # A abstract lexer engine generated by nitcc
 155 abstract class Lexer
 156         # The input stream of characters
 157         var stream: String
 158
 159         # The stating state for lexing
 160         # Used by generated parsers
 161         protected fun start_state: DFAState is abstract
 162
 163         # Lexize a stream of characters and return a sequence of tokens
 164         fun lex: List[NToken]
 165         do
 166                 var res = new List[NToken]
 167                 var state = start_state
 168                 var pos = 0
 169                 var pos_start = 0
 170                 var pos_end = 0
 171                 var line = 1
 172                 var line_start = 1
 173                 var line_end = 0
 174                 var col = 1
 175                 var col_start = 1
 176                 var col_end = 0
 177                 var last_state: nullable DFAState = null
 178                 var text = stream
 179                 var length = text.length
 180                 loop
 181                         if state.is_accept then
 182                                 pos_end = pos - 1
 183                                 line_end = line
 184                                 col_end = col
 185                                 last_state = state
 186                         end
 187                         var c
 188                         if pos >= length then
 189                                 c = '\0'
 190                         else
 191                                 c = text[pos]
 192                         end
 193                         var next = state.trans(c)
 194                         if next == null then
 195                                 if last_state == null then
 196                                         var token = new NLexerError
 197                                         var position = new Position(pos_start, pos, line_start, line, col_start, col)
 198                                         token.position = position
 199                                         token.text = text.substring(pos_start, pos-pos_start+1)
 200                                         res.add token
 201                                         break
 202                                 end
 203                                 var position = new Position(pos_start, pos_end, line_start, line_end, col_start, col_end)
 204                                 var token = last_state.make_token(position, text.substring(pos_start, pos_end-pos_start+1))
 205                                 if token != null then res.add(token)
 206                                 if pos >= length then
 207                                         token = new NEof
 208                                         position = new Position(pos, pos, line, line, col, col)
 209                                         token.position = position
 210                                         token.text = ""
 211                                         res.add token
 212                                         break
 213                                 end
 214                                 state = start_state
 215                                 pos_start = pos_end + 1
 216                                 pos = pos_start
 217                                 line_start = line_end
 218                                 line = line_start
 219                                 col_start = col_end
 220                                 col = col_start
 221
 222                                 last_state = null
 223                                 continue
 224                         end
 225                         state = next
 226                         pos += 1
 227                         col += 1
 228                         if c == '\n' then
 229                                 line += 1
 230                                 col = 1
 231                         end
 232                 end
 233                 return res
 234         end
 235 end
 236
 237 # A state in a lexer automaton generated by nitcc
 238 # Used by generated lexers
 239 interface DFAState
 240         fun is_accept: Bool do return false
 241         fun trans(c: Char): nullable DFAState do return null
 242         fun make_token(position: Position, text: String): nullable NToken is abstract
 243 end
 244
 245 ###
 246
 247 # A abstract visitor on syntactic trees generated by nitcc
 248 abstract class Visitor
 249         # The main entry point to visit a node `n`
 250         # Should not be redefined
 251         fun enter_visit(n: Node)
 252         do
 253                 visit(n)
 254         end
 255
 256         # The specific implementation of a visit
 257         #
 258         # Should be redefined by concrete visitors
 259         #
 260         # Should not be called directly (use `enter_visit` instead)
 261         #
 262         # By default, the visitor just rescursively visit the children of `n`
 263         protected fun visit(n: Node)
 264         do
 265                 n.visit_children(self)
 266         end
 267 end
 268
 269 # Print a node (using to_s) on a line and recustively each children indented (with two spaces)
 270 class TreePrinterVisitor
 271         super Visitor
 272         var writer: OStream
 273         private var indent = 0
 274         init(writer: OStream) do self.writer = writer
 275         redef fun visit(n)
 276         do
 277                 for i in [0..indent[ do writer.write("  ")
 278                 writer.write(n.to_s)
 279                 writer.write("\n")
 280                 indent += 1
 281                 super
 282                 indent -= 1
 283         end
 284 end
 285
 286 # A position into a input stream
 287 # Used to give position to tokens
 288 class Position
 289         var pos_start: Int
 290         var pos_end: Int
 291         var line_start: Int
 292         var line_end: Int
 293         var col_start: Int
 294         var col_end: Int
 295         redef fun to_s do return "{line_start}:{col_start}-{line_end}:{col_end}"
 296 end
 297
 298 # A node of a syntactic tree
 299 abstract class Node
 300         # The name of the node (as used in the grammar file)
 301         fun node_name: String do return class_name
 302
 303         # A point of view on the direct childrens of the node
 304         fun children: SequenceRead[nullable Node] is abstract
 305
 306         # Visit all the children of the node with the visitor `v`
 307         protected fun visit_children(v: Visitor)
 308         do
 309                 for c in children do if c != null then v.enter_visit(c)
 310         end
 311
 312         # The position of the node in the input stream
 313         var position: nullable Position writable = null
 314
 315         # Produce a graphiz file for the syntaxtic tree rooted at `self`.
 316         fun to_dot(filepath: String)
 317         do
 318                 var f = new OFStream.open(filepath)
 319                 f.write("digraph g \{\n")
 320                 f.write("rankdir=BT;\n")
 321
 322                 var a = new Array[NToken]
 323                 to_dot_visitor(f, a)
 324
 325                 f.write("\{ rank=same\n")
 326                 var first = true
 327                 for n in a do
 328                         if first then
 329                                 first = false
 330                         else
 331                                 f.write("->")
 332                         end
 333                         f.write("n{n.object_id}")
 334                 end
 335                 f.write("[style=invis];\n")
 336                 f.write("\}\n")
 337
 338                 f.write("\}\n")
 339                 f.close
 340         end
 341
 342         private fun to_dot_visitor(f: OStream, a: Array[NToken])
 343         do
 344                 f.write("n{object_id} [label=\"{node_name}\"];\n")
 345                 for x in children do
 346                         if x == null then continue
 347                         f.write("n{x.object_id} -> n{object_id};\n")
 348                         x.to_dot_visitor(f,a )
 349                 end
 350         end
 351
 352         redef fun to_s do
 353                 var pos = position
 354                 if pos == null then
 355                         return "{node_name}"
 356                 else
 357                         return "{node_name}@({pos})"
 358                 end
 359         end
 360 end
 361
 362 # A token produced by the lexer and used in a syntactic tree
 363 abstract class NToken
 364         super Node
 365
 366         redef fun children do return once new Array[Node]
 367
 368         redef fun to_dot_visitor(f, a)
 369         do
 370                 var labe = "{node_name}"
 371                 var pos = position
 372                 if pos != null then labe += "\\n{pos}"
 373                 var text = self.text
 374                 if node_name != "'{text}'" then
 375                         labe += "\\n'{text.escape_to_c}'"
 376                 end
 377                 f.write("n{object_id} [label=\"{labe}\",shape=box];\n")
 378                 a.add(self)
 379         end
 380
 381         # The text associated with the token
 382         var text: String writable = ""
 383
 384         redef fun to_s do
 385                 var res = super
 386                 var text = self.text
 387                 if node_name != "'{text}'" then
 388                         res += "='{text.escape_to_c}'"
 389                 end
 390                 return res
 391         end
 392 end
 393
 394 # The special token for the end of stream
 395 class NEof
 396         super NToken
 397 end
 398
 399 # A special token used to represent a parser or lexer error
 400 abstract class NError
 401         super NToken
 402
 403         # All the partially built tree during parsing (aka the node_stack)
 404         var error_tree = new Nodes[Node]
 405
 406         # The things unexpected
 407         fun unexpected: String is abstract
 408
 409         # The things expected (if any)
 410         var expected: nullable String = null
 411
 412         # The error message,using `expected` and `unexpected`
 413         fun message: String
 414         do
 415                 var exp = expected
 416                 var res = "Unexpected {unexpected}"
 417                 if exp != null then res += "; is acceptable instead: {exp}"
 418                 return res
 419         end
 420 end
 421
 422 # A lexer error as a token for the unexpected characted
 423 class NLexerError
 424         super NError
 425
 426         redef fun unexpected do return "character '{text.first}'"
 427 end
 428
 429 # A parser error linked to a unexpected token
 430 class NParserError
 431         super NError
 432         # The unexpected token
 433         var token: nullable NToken
 434
 435         redef fun unexpected do return token.node_name
 436 end
 437
 438 # A hogeneous sequence of node, used to represent unbounded lists (and + modifier)
 439 class Nodes[T: Node]
 440         super Node
 441         redef fun children do return items
 442         var items = new Array[T]
 443 end
 444
 445 # A production with a specific, named and statically typed childrens
 446 class NProd
 447         super Node
 448         redef var children: SequenceRead[nullable Node] = new NProdChildren(self)
 449
 450         # The exact number of direct children
 451         # Used to implement `children` by generated parsers
 452         fun number_of_children: Int is abstract
 453
 454         # The specific children got by its index
 455         # Used to implement `children` by generated parsers
 456         fun child(x: Int): nullable Node is abstract
 457 end
 458
 459
 460 private class NProdChildren
 461         super SequenceRead[nullable Node]
 462         var prod: NProd
 463         redef fun iterator do return new NProdIterator(prod)
 464         redef fun length do return prod.number_of_children
 465         redef fun is_empty do return prod.number_of_children == 0
 466         redef fun [](i) do return prod.child(i)
 467 end
 468
 469 private class NProdIterator
 470         super IndexedIterator[nullable Node]
 471         var prod: NProd
 472         redef var index = 0
 473         redef fun is_ok do return index < prod.number_of_children
 474         redef fun next do index += 1
 475         redef fun item do return prod.child(index)
 476 end
 477
 478 # All-in-one abstract class to test generated parsers on a given
 479 abstract class TestParser
 480         # How to get a new lexer on a given stream of character
 481         fun new_lexer(text: String): Lexer is abstract
 482
 483         # How to get a new parser
 484         fun new_parser: Parser is abstract
 485
 486         # The name of the language (used for generated files)
 487         fun name: String is abstract
 488
 489         # Use the class as the main enrty point of the program
 490         # - parse arguments and options of the command
 491         # - test the parser (see `work`)
 492         fun main: Node
 493         do
 494                 if args.is_empty then
 495                         print "usage {name}_test <filepath> | - | -e <text>"
 496                         exit 0
 497                 end
 498
 499                 var filepath = args.shift
 500                 var text
 501                 if filepath == "-" then
 502                         text = stdin.read_all
 503                 else if filepath == "-e" then
 504                         if args.is_empty then
 505                                 print "Error: -e need a text"
 506                                 exit 1
 507                         end
 508                         text = args.shift
 509                 else
 510                         var f = new IFStream.open(filepath)
 511                         text = f.read_all
 512                         f.close
 513                 end
 514
 515                 if not args.is_empty then
 516                         print "Error: superfluous arguments."
 517                         exit 1
 518                 end
 519
 520                 return work(text)
 521         end
 522
 523         # Produce a full syntactic tree for a given stream of character
 524         # Produce also statistics and output files
 525         fun work(text: String): Node
 526         do
 527                 print "INPUT: {text.length} chars"
 528                 var l = new_lexer(text)
 529                 var tokens = l.lex
 530
 531                 var tokout = "{name}.tokens.out"
 532                 print "TOKEN: {tokens.length} tokens (see {tokout})"
 533
 534                 var f = new OFStream.open(tokout)
 535                 for t in tokens do
 536                         f.write "{t.to_s}\n"
 537                 end
 538                 f.close
 539
 540                 var p = new_parser
 541                 p.tokens.add_all(tokens)
 542
 543                 var n = p.parse
 544
 545                 var astout = "{name}.ast.out"
 546                 f = new OFStream.open(astout)
 547                 var tpv = new TreePrinterVisitor(f)
 548                 var astdotout = "{name}.ast.dot"
 549                 if n isa NError then
 550                         print "Syntax error: {n.message}"
 551                         print "ERROR: {n} (see {astout} and {astdotout})"
 552                         tpv.enter_visit(n)
 553                         n = n.error_tree
 554                 else
 555                         print "ROOT: {n} (see {astout} and {astdotout})"
 556                 end
 557                 tpv.enter_visit(n)
 558                 n.to_dot(astdotout)
 559                 f.close
 560
 561                 return n
 562         end
 563 end