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                 _text.clear
 111
 112                 while true do
 113                         var c = get_char
 114
 115                         if c != -1 then
 116                                 if c == 10 then
 117                                         if _cr then
 118                                                 _cr = false
 119                                         else
 120                                                 _line = _line + 1
 121                                                 _pos = 0
 122                                         end
 123                                 else if c == 13 then
 124                                         _line = _line + 1
 125                                         _pos = 0
 126                                         _cr = true
 127                                 else
 128                                         _pos = _pos + 1
 129                                         _cr = false
 130                                 end
 131
 132                                 _text.add(c.ascii)
 133
 134                                 var first_loop = true # aka until
 135                                 while dfa_state < -1 or first_loop do
 136                                         var old_state = dfa_state
 137                                         if dfa_state < -1 then
 138                                                 old_state = -2 - dfa_state
 139                                         end
 140
 141                                         dfa_state = -1
 142
 143                                         var tmp1 = goto_table[old_state]
 144                                         var low = 0
 145                                         var high = tmp1.length - 1
 146
 147                                         while low <= high do
 148                                                 var middle = (low + high) / 2
 149                                                 var tmp2 = tmp1[middle]
 150
 151                                                 if c < tmp2[0] then
 152                                                         high = middle - 1
 153                                                 else if c > tmp2[1] then
 154                                                         low = middle + 1
 155                                                 else
 156                                                         dfa_state = tmp2[2]
 157                                                         low = high + 1 # aka break
 158                                                 end
 159                                         end
 160                                         first_loop = false # aka until
 161                                 end
 162                         else
 163                                 dfa_state = -1
 164                         end
 165
 166                         if dfa_state >= 0 then
 167                                 if accept[dfa_state] != -1 then
 168                                         accept_state = dfa_state
 169                                         accept_token = accept[dfa_state]
 170                                         accept_length = _text.length
 171                                         accept_pos = _pos
 172                                         accept_line = _line
 173                                 end
 174                         else
 175                                 if accept_state != -1 then
 176 $ foreach {//token}
 177                                         if accept_token == ${position()-1} then
 178 $    if {not(@text)}
 179 $        if {@parser_index}
 180                                                 var token_text = _text.substring(0, accept_length)
 181                                                 var token = new @ename.init_tk(token_text, _filename, start_line + 1, start_pos + 1)
 182 $        end
 183 $    else
 184                                                 var token = new @ename.init_tk(_filename, start_line + 1, start_pos + 1)
 185 $    end
 186                                                 push_back(accept_length)
 187                                                 _pos = accept_pos
 188                                                 _line = accept_line
 189 $    if {count(transition[@from!=@to])!=0}
 190                                                 var state_id = _state
 191 $        foreach transition in {transition[@from!=@to]}
 192                                                 if state_id == ${/parser/lexer_data/state[@name=$transition/@from]/@id} then
 193                                                         _state = state_${translate(@to,"ABCDEFGHIJKLMNOPQRSTUVWXYZ","abcdefghijklmnopqrstuvwxyz")}
 194                                                 end
 195 $        end
 196 $    end if
 197 $    if {@parser_index}
 198                                                 return token
 199 $    else
 200                                                 return null
 201 $    end
 202                                         end
 203 $ end foreach
 204                                 else
 205                                         if _text.length > 0 then
 206                                                 var token = new PError.init_error(_filename, start_line + 1, start_pos + 1, "Unknown token: {_text}")
 207                                                 return token
 208                                         else
 209                                                 var token = new EOF(_filename, start_line + 1, start_pos + 1)
 210                                                 return token
 211                                         end
 212                                 end
 213                         end
 214                 end
 215                 return null
 216         end
 217
 218         # Read the next character.
 219         # The character is read from the stream of from the pushback buffer.
 220         private fun get_char: Int
 221         do
 222                 if _eof then
 223                         return -1
 224                 end
 225
 226                 var result: Int
 227
 228                 var sp = _stream_pos
 229                 if sp >= 0 then
 230                         var res = _stream_buf[_stream_pos]
 231                         _stream_pos = sp - 1
 232                         result = res.ascii
 233                 else
 234                         result = _stream.read_char
 235                 end
 236
 237                 if result == -1 then
 238                         _eof = true
 239                 end
 240
 241                 return result
 242         end
 243
 244         # Unread some characters.
 245         # Unread characters are stored in the pushback buffer.
 246         private fun push_back(accept_length: Int)
 247         do
 248                 var length = _text.length
 249                 var i = length - 1
 250                 while i >= accept_length do
 251                         _eof = false
 252                         _stream_pos = _stream_pos + 1
 253                         _stream_buf[_stream_pos] = _text[i]
 254                         i = i - 1
 255                 end
 256         end
 257
 258         var _goto_table: Array[Array[Array[Array[Int]]]]
 259         private fun build_goto_table
 260         do
 261                 _goto_table = once [
 262 $ foreach {lexer_data/goto_table/state}
 263                         [
 264 $     foreach {row}
 265 $         if {count(goto)!=0}
 266                                 [
 267 $             foreach {goto}
 268                                         [@low, @high, @state] [-sep ','-]
 269 $             end foreach
 270                                 ] [-sep ','-]
 271 $         else
 272                                 nil_array [-sep ','-]
 273 $         end
 274 $     end foreach
 275                         ] [-sep ','-]
 276 $ end foreach
 277                 ]
 278         end
 279
 280         private fun nil_array: Array[Array[Int]]
 281         do
 282                 return once new Array[Array[Int]]
 283         end
 284
 285         var _accept_table: Array[Array[Int]]
 286         private fun build_accept_table do
 287                 _accept_table = once [
 288 $ foreach {lexer_data/accept_table/state}
 289                         [
 290                                 [-foreach {i}-]${.} [-sep ','-] [-end foreach-]
 291
 292                         ] [-sep ','-]
 293 $ end foreach
 294                 ]
 295         end
 296 end
 297
 298 $ end template