src/parser/xss/lexer.xss

   1 /* This file is part of NIT ( http://www.nitlanguage.org ).
   2  *
   3  * Copyright 2008 Jean Privat <jean@pryen.org>
   4  * Based on algorithms developped for ( http://www.sablecc.org/ ).
   5  *
   6  * Licensed under the Apache License, Version 2.0 (the "License");
   7  * you may not use this file except in compliance with the License.
   8  * You may obtain a copy of the License at
   9  *
  10  *     http://www.apache.org/licenses/LICENSE-2.0
  11  *
  12  * Unless required by applicable law or agreed to in writing, software
  13  * distributed under the License is distributed on an "AS IS" BASIS,
  14  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  15  * See the License for the specific language governing permissions and
  16  * limitations under the License.
  17  */
  18
  19 $ template make_lexer()
  20
  21 # The lexer extract NIT tokens from an input stream.
  22 # It is better user with the Parser
  23 class Lexer
  24         # Last peeked token
  25         var _token: nullable Token
  26
  27         # Lexer current state
  28         var _state: Int = 0
  29
  30         # Name of the stream (as given to tokens)
  31         readable var _filename: String
  32
  33         # Input stream where character are read
  34         var _stream: IStream
  35
  36         # Pushback buffer to store unread character
  37         var _stream_buf: Buffer
  38
  39         # Number of character stored in the pushback buffer
  40         var _stream_pos: Int
  41
  42         # Current line number in the input stream
  43         var _line: Int = 0
  44
  45         # Current column in the input stream
  46         var _pos: Int = 0
  47
  48         # Was the last character a cariage-return?
  49         var _cr: Bool = false
  50
  51         # If the end of stream?
  52         var _eof: Bool = false
  53
  54         # Current working text read from the input stream
  55         var _text: Buffer
  56
  57 $ foreach {lexer_data/state}
  58         # Constante state values
  59         private fun state_${translate(@name,"ABCDEFGHIJKLMNOPQRSTUVWXYZ","abcdefghijklmnopqrstuvwxyz")}: Int do return @id end
  60 $ end foreach
  61
  62         # Create a new lexer for a stream (and a name)
  63         init(stream: IStream, fname: String)
  64         do
  65                 _filename = fname
  66                 _text = new Buffer
  67                 _stream = stream
  68                 _stream_pos = -1
  69                 _stream_buf = new Buffer
  70                 build_goto_table
  71                 build_accept_table
  72         end
  73
  74         # Give the next token (but do not consume it)
  75         fun peek: Token
  76         do
  77                 while _token == null do
  78                         _token = get_token
  79                 end
  80                 return _token.as(not null)
  81         end
  82
  83         # Give and consume the next token
  84         fun next: Token
  85         do
  86                 var result = _token
  87                 while result == null do
  88                         result = get_token
  89                 end
  90                 _token = null
  91                 return result.as(not null)
  92         end
  93
  94         # Get a token, or null if it is discarded
  95         private fun get_token: nullable Token
  96         do
  97                 var dfa_state = 0
  98
  99                 var start_pos = _pos
 100                 var start_line = _line
 101
 102                 var accept_state = -1
 103                 var accept_token = -1
 104                 var accept_length = -1
 105                 var accept_pos = -1
 106                 var accept_line = -1
 107
 108                 var goto_table = _goto_table[_state]
 109                 var accept = _accept_table[_state]
 110                 var text = _text
 111                 text.clear
 112
 113                 while true do
 114                         var c = get_char
 115
 116                         if c != -1 then
 117                                 var cr = _cr
 118                                 var line = _line
 119                                 var pos = _pos
 120                                 if c == 10 then
 121                                         if cr then
 122                                                 cr = false
 123                                         else
 124                                                 line = line + 1
 125                                                 pos = 0
 126                                         end
 127                                 else if c == 13 then
 128                                         line = line + 1
 129                                         pos = 0
 130                                         cr = true
 131                                 else
 132                                         pos = pos + 1
 133                                         cr = false
 134                                 end
 135
 136                                 text.add(c.ascii)
 137
 138                                 var first_loop = true # aka until
 139                                 while dfa_state < -1 or first_loop do
 140                                         var old_state = dfa_state
 141                                         if dfa_state < -1 then
 142                                                 old_state = -2 - dfa_state
 143                                         end
 144
 145                                         dfa_state = -1
 146
 147                                         var tmp0 = goto_table[old_state]
 148                                         var low = 0
 149                                         var high = tmp0.length - 1
 150
 151                                         if high >= 0 then
 152                                                 var tmp1 = tmp0.intern_items
 153                                                 while low <= high do
 154                                                         var middle = (low + high) / 2
 155                                                         var tmp2 = tmp1[middle].intern_items
 156
 157                                                         if c < tmp2[0] then
 158                                                                 high = middle - 1
 159                                                         else if c > tmp2[1] then
 160                                                                 low = middle + 1
 161                                                         else
 162                                                                 dfa_state = tmp2[2]
 163                                                                 low = high + 1 # aka break
 164                                                         end
 165                                                 end
 166                                         end
 167                                         first_loop = false # aka until
 168                                 end
 169
 170                                 _cr = cr
 171                                 _line = line
 172                                 _pos = pos
 173                         else
 174                                 dfa_state = -1
 175                         end
 176
 177                         if dfa_state >= 0 then
 178                                 if accept[dfa_state] != -1 then
 179                                         accept_state = dfa_state
 180                                         accept_token = accept[dfa_state]
 181                                         accept_length = text.length
 182                                         accept_pos = _pos
 183                                         accept_line = _line
 184                                 end
 185                         else
 186                                 if accept_state != -1 then
 187 $ foreach {//token}
 188                                         if accept_token == ${position()-1} then
 189                                                 var location = new Location(_filename, start_line + 1, accept_line + 1, start_pos + 1, accept_pos)
 190 $    if {not(@text)}
 191 $        if {@parser_index}
 192                                                 var token_text = text.substring(0, accept_length)
 193                                                 var token = new @ename.init_tk(token_text, location)
 194 $        end
 195 $    else
 196                                                 var token = new @ename.init_tk(location)
 197 $    end
 198                                                 push_back(accept_length)
 199                                                 _pos = accept_pos
 200                                                 _line = accept_line
 201 $    if {count(transition[@from!=@to])!=0}
 202                                                 var state_id = _state
 203 $        foreach transition in {transition[@from!=@to]}
 204                                                 if state_id == ${/parser/lexer_data/state[@name=$transition/@from]/@id} then
 205                                                         _state = state_${translate(@to,"ABCDEFGHIJKLMNOPQRSTUVWXYZ","abcdefghijklmnopqrstuvwxyz")}
 206                                                 end
 207 $        end
 208 $    end if
 209 $    if {@parser_index}
 210                                                 return token
 211 $    else
 212                                                 return null
 213 $    end
 214                                         end
 215 $ end foreach
 216                                 else
 217                                         var location = new Location(_filename, start_line + 1, accept_line + 1, start_pos + 1, accept_pos)
 218                                         if text.length > 0 then
 219                                                 var token = new PError.init_error("Unknown token: {text}", location)
 220                                                 return token
 221                                         else
 222                                                 var token = new EOF(location)
 223                                                 return token
 224                                         end
 225                                 end
 226                         end
 227                 end
 228                 return null
 229         end
 230
 231         # Read the next character.
 232         # The character is read from the stream of from the pushback buffer.
 233         private fun get_char: Int
 234         do
 235                 if _eof then
 236                         return -1
 237                 end
 238
 239                 var result: Int
 240
 241                 var sp = _stream_pos
 242                 if sp >= 0 then
 243                         var res = _stream_buf[_stream_pos]
 244                         _stream_pos = sp - 1
 245                         result = res.ascii
 246                 else
 247                         result = _stream.read_char
 248                 end
 249
 250                 if result == -1 then
 251                         _eof = true
 252                 end
 253
 254                 return result
 255         end
 256
 257         # Unread some characters.
 258         # Unread characters are stored in the pushback buffer.
 259         private fun push_back(accept_length: Int)
 260         do
 261                 var length = _text.length
 262                 var i = length - 1
 263                 while i >= accept_length do
 264                         _eof = false
 265                         _stream_pos = _stream_pos + 1
 266                         _stream_buf[_stream_pos] = _text[i]
 267                         i = i - 1
 268                 end
 269         end
 270
 271         var _goto_table: Array[Array[Array[Array[Int]]]]
 272         private fun build_goto_table
 273         do
 274                 _goto_table = once [
 275 $ foreach {lexer_data/goto_table/state}
 276                         [
 277 $     foreach {row}
 278 $         if {count(goto)!=0}
 279                                 [
 280 $             foreach {goto}
 281                                         [@low, @high, @state] [-sep ','-]
 282 $             end foreach
 283                                 ] [-sep ','-]
 284 $         else
 285                                 nil_array [-sep ','-]
 286 $         end
 287 $     end foreach
 288                         ] [-sep ','-]
 289 $ end foreach
 290                 ]
 291         end
 292
 293         private fun nil_array: Array[Array[Int]]
 294         do
 295                 return once new Array[Array[Int]]
 296         end
 297
 298         var _accept_table: Array[Array[Int]]
 299         private fun build_accept_table do
 300                 _accept_table = once [
 301 $ foreach {lexer_data/accept_table/state}
 302                         [
 303                                 [-foreach {i}-]${.} [-sep ','-] [-end foreach-]
 304
 305                         ] [-sep ','-]
 306 $ end foreach
 307                 ]
 308         end
 309 end
 310
 311 $ end template