1# frozen_string_literal: false 2#-- 3# $originalId: parser.rb,v 1.8 2006/07/06 11:42:07 aamine Exp $ 4# 5# Copyright (c) 1999-2006 Minero Aoki 6# 7# This program is free software. 8# You can distribute/modify this program under the same terms of ruby. 9# 10# As a special exception, when this code is copied by Racc 11# into a Racc output file, you may use that output file 12# without restriction. 13#++ 14 15module Racc 16 class ParseError < StandardError; end 17end 18unless defined?(::ParseError) 19 ParseError = Racc::ParseError 20end 21 22# Racc is a LALR(1) parser generator. 23# It is written in Ruby itself, and generates Ruby programs. 24# 25# == Command-line Reference 26# 27# racc [-o<var>filename</var>] [--output-file=<var>filename</var>] 28# [-e<var>rubypath</var>] [--embedded=<var>rubypath</var>] 29# [-v] [--verbose] 30# [-O<var>filename</var>] [--log-file=<var>filename</var>] 31# [-g] [--debug] 32# [-E] [--embedded] 33# [-l] [--no-line-convert] 34# [-c] [--line-convert-all] 35# [-a] [--no-omit-actions] 36# [-C] [--check-only] 37# [-S] [--output-status] 38# [--version] [--copyright] [--help] <var>grammarfile</var> 39# 40# [+filename+] 41# Racc grammar file. Any extension is permitted. 42# [-o+outfile+, --output-file=+outfile+] 43# A filename for output. default is <+filename+>.tab.rb 44# [-O+filename+, --log-file=+filename+] 45# Place logging output in file +filename+. 46# Default log file name is <+filename+>.output. 47# [-e+rubypath+, --executable=+rubypath+] 48# output executable file(mode 755). where +path+ is the Ruby interpreter. 49# [-v, --verbose] 50# verbose mode. create +filename+.output file, like yacc's y.output file. 51# [-g, --debug] 52# add debug code to parser class. To display debugging information, 53# use this '-g' option and set @yydebug true in parser class. 54# [-E, --embedded] 55# Output parser which doesn't need runtime files (racc/parser.rb). 56# [-C, --check-only] 57# Check syntax of racc grammar file and quit. 58# [-S, --output-status] 59# Print messages time to time while compiling. 60# [-l, --no-line-convert] 61# turns off line number converting. 62# [-c, --line-convert-all] 63# Convert line number of actions, inner, header and footer. 64# [-a, --no-omit-actions] 65# Call all actions, even if an action is empty. 66# [--version] 67# print Racc version and quit. 68# [--copyright] 69# Print copyright and quit. 70# [--help] 71# Print usage and quit. 72# 73# == Generating Parser Using Racc 74# 75# To compile Racc grammar file, simply type: 76# 77# $ racc parse.y 78# 79# This creates Ruby script file "parse.tab.y". The -o option can change the output filename. 80# 81# == Writing A Racc Grammar File 82# 83# If you want your own parser, you have to write a grammar file. 84# A grammar file contains the name of your parser class, grammar for the parser, 85# user code, and anything else. 86# When writing a grammar file, yacc's knowledge is helpful. 87# If you have not used yacc before, Racc is not too difficult. 88# 89# Here's an example Racc grammar file. 90# 91# class Calcparser 92# rule 93# target: exp { print val[0] } 94# 95# exp: exp '+' exp 96# | exp '*' exp 97# | '(' exp ')' 98# | NUMBER 99# end 100# 101# Racc grammar files resemble yacc files. 102# But (of course), this is Ruby code. 103# yacc's $$ is the 'result', $0, $1... is 104# an array called 'val', and $-1, $-2... is an array called '_values'. 105# 106# See the {Grammar File Reference}[rdoc-ref:lib/racc/rdoc/grammar.en.rdoc] for 107# more information on grammar files. 108# 109# == Parser 110# 111# Then you must prepare the parse entry method. There are two types of 112# parse methods in Racc, Racc::Parser#do_parse and Racc::Parser#yyparse 113# 114# Racc::Parser#do_parse is simple. 115# 116# It's yyparse() of yacc, and Racc::Parser#next_token is yylex(). 117# This method must returns an array like [TOKENSYMBOL, ITS_VALUE]. 118# EOF is [false, false]. 119# (TOKENSYMBOL is a Ruby symbol (taken from String#intern) by default. 120# If you want to change this, see the grammar reference. 121# 122# Racc::Parser#yyparse is little complicated, but useful. 123# It does not use Racc::Parser#next_token, instead it gets tokens from any iterator. 124# 125# For example, <code>yyparse(obj, :scan)</code> causes 126# calling +obj#scan+, and you can return tokens by yielding them from +obj#scan+. 127# 128# == Debugging 129# 130# When debugging, "-v" or/and the "-g" option is helpful. 131# 132# "-v" creates verbose log file (.output). 133# "-g" creates a "Verbose Parser". 134# Verbose Parser prints the internal status when parsing. 135# But it's _not_ automatic. 136# You must use -g option and set +@yydebug+ to +true+ in order to get output. 137# -g option only creates the verbose parser. 138# 139# === Racc reported syntax error. 140# 141# Isn't there too many "end"? 142# grammar of racc file is changed in v0.10. 143# 144# Racc does not use '%' mark, while yacc uses huge number of '%' marks.. 145# 146# === Racc reported "XXXX conflicts". 147# 148# Try "racc -v xxxx.y". 149# It causes producing racc's internal log file, xxxx.output. 150# 151# === Generated parsers does not work correctly 152# 153# Try "racc -g xxxx.y". 154# This command let racc generate "debugging parser". 155# Then set @yydebug=true in your parser. 156# It produces a working log of your parser. 157# 158# == Re-distributing Racc runtime 159# 160# A parser, which is created by Racc, requires the Racc runtime module; 161# racc/parser.rb. 162# 163# Ruby 1.8.x comes with Racc runtime module, 164# you need NOT distribute Racc runtime files. 165# 166# If you want to include the Racc runtime module with your parser. 167# This can be done by using '-E' option: 168# 169# $ racc -E -omyparser.rb myparser.y 170# 171# This command creates myparser.rb which `includes' Racc runtime. 172# Only you must do is to distribute your parser file (myparser.rb). 173# 174# Note: parser.rb is LGPL, but your parser is not. 175# Your own parser is completely yours. 176module Racc 177 178 unless defined?(Racc_No_Extensions) 179 Racc_No_Extensions = false # :nodoc: 180 end 181 182 class Parser 183 184 Racc_Runtime_Version = '1.4.6' 185 Racc_Runtime_Revision = %w$originalRevision: 1.8 $[1] 186 187 Racc_Runtime_Core_Version_R = '1.4.6' 188 Racc_Runtime_Core_Revision_R = %w$originalRevision: 1.8 $[1] 189 begin 190 require 'racc/cparse' 191 # Racc_Runtime_Core_Version_C = (defined in extension) 192 Racc_Runtime_Core_Revision_C = Racc_Runtime_Core_Id_C.split[2] 193 unless new.respond_to?(:_racc_do_parse_c, true) 194 raise LoadError, 'old cparse.so' 195 end 196 if Racc_No_Extensions 197 raise LoadError, 'selecting ruby version of racc runtime core' 198 end 199 200 Racc_Main_Parsing_Routine = :_racc_do_parse_c # :nodoc: 201 Racc_YY_Parse_Method = :_racc_yyparse_c # :nodoc: 202 Racc_Runtime_Core_Version = Racc_Runtime_Core_Version_C # :nodoc: 203 Racc_Runtime_Core_Revision = Racc_Runtime_Core_Revision_C # :nodoc: 204 Racc_Runtime_Type = 'c' # :nodoc: 205 rescue LoadError 206 Racc_Main_Parsing_Routine = :_racc_do_parse_rb 207 Racc_YY_Parse_Method = :_racc_yyparse_rb 208 Racc_Runtime_Core_Version = Racc_Runtime_Core_Version_R 209 Racc_Runtime_Core_Revision = Racc_Runtime_Core_Revision_R 210 Racc_Runtime_Type = 'ruby' 211 end 212 213 def Parser.racc_runtime_type # :nodoc: 214 Racc_Runtime_Type 215 end 216 217 def _racc_setup 218 @yydebug = false unless self.class::Racc_debug_parser 219 @yydebug = false unless defined?(@yydebug) 220 if @yydebug 221 @racc_debug_out = $stderr unless defined?(@racc_debug_out) 222 @racc_debug_out ||= $stderr 223 end 224 arg = self.class::Racc_arg 225 arg[13] = true if arg.size < 14 226 arg 227 end 228 229 def _racc_init_sysvars 230 @racc_state = [0] 231 @racc_tstack = [] 232 @racc_vstack = [] 233 234 @racc_t = nil 235 @racc_val = nil 236 237 @racc_read_next = true 238 239 @racc_user_yyerror = false 240 @racc_error_status = 0 241 end 242 243 # The entry point of the parser. This method is used with #next_token. 244 # If Racc wants to get token (and its value), calls next_token. 245 # 246 # Example: 247 # def parse 248 # @q = [[1,1], 249 # [2,2], 250 # [3,3], 251 # [false, '$']] 252 # do_parse 253 # end 254 # 255 # def next_token 256 # @q.shift 257 # end 258 def do_parse 259 __send__(Racc_Main_Parsing_Routine, _racc_setup(), false) 260 end 261 262 # The method to fetch next token. 263 # If you use #do_parse method, you must implement #next_token. 264 # 265 # The format of return value is [TOKEN_SYMBOL, VALUE]. 266 # +token-symbol+ is represented by Ruby's symbol by default, e.g. :IDENT 267 # for 'IDENT'. ";" (String) for ';'. 268 # 269 # The final symbol (End of file) must be false. 270 def next_token 271 raise NotImplementedError, "#{self.class}\#next_token is not defined" 272 end 273 274 def _racc_do_parse_rb(arg, in_debug) 275 action_table, action_check, action_default, action_pointer, 276 _, _, _, _, 277 _, _, token_table, _, 278 _, _, * = arg 279 280 _racc_init_sysvars 281 tok = act = i = nil 282 283 catch(:racc_end_parse) { 284 while true 285 if i = action_pointer[@racc_state[-1]] 286 if @racc_read_next 287 if @racc_t != 0 # not EOF 288 tok, @racc_val = next_token() 289 unless tok # EOF 290 @racc_t = 0 291 else 292 @racc_t = (token_table[tok] or 1) # error token 293 end 294 racc_read_token(@racc_t, tok, @racc_val) if @yydebug 295 @racc_read_next = false 296 end 297 end 298 i += @racc_t 299 unless i >= 0 and 300 act = action_table[i] and 301 action_check[i] == @racc_state[-1] 302 act = action_default[@racc_state[-1]] 303 end 304 else 305 act = action_default[@racc_state[-1]] 306 end 307 while act = _racc_evalact(act, arg) 308 ; 309 end 310 end 311 } 312 end 313 314 # Another entry point for the parser. 315 # If you use this method, you must implement RECEIVER#METHOD_ID method. 316 # 317 # RECEIVER#METHOD_ID is a method to get next token. 318 # It must 'yield' the token, which format is [TOKEN-SYMBOL, VALUE]. 319 def yyparse(recv, mid) 320 __send__(Racc_YY_Parse_Method, recv, mid, _racc_setup(), true) 321 end 322 323 def _racc_yyparse_rb(recv, mid, arg, c_debug) 324 action_table, action_check, action_default, action_pointer, 325 _, _, _, _, 326 _, _, token_table, _, 327 _, _, * = arg 328 329 _racc_init_sysvars 330 act = nil 331 i = nil 332 333 catch(:racc_end_parse) { 334 until i = action_pointer[@racc_state[-1]] 335 while act = _racc_evalact(action_default[@racc_state[-1]], arg) 336 ; 337 end 338 end 339 recv.__send__(mid) do |tok, val| 340 unless tok 341 @racc_t = 0 342 else 343 @racc_t = (token_table[tok] or 1) # error token 344 end 345 @racc_val = val 346 @racc_read_next = false 347 348 i += @racc_t 349 unless i >= 0 and 350 act = action_table[i] and 351 action_check[i] == @racc_state[-1] 352 act = action_default[@racc_state[-1]] 353 end 354 while act = _racc_evalact(act, arg) 355 ; 356 end 357 358 while not(i = action_pointer[@racc_state[-1]]) or 359 not @racc_read_next or 360 @racc_t == 0 # $ 361 unless i and i += @racc_t and 362 i >= 0 and 363 act = action_table[i] and 364 action_check[i] == @racc_state[-1] 365 act = action_default[@racc_state[-1]] 366 end 367 while act = _racc_evalact(act, arg) 368 ; 369 end 370 end 371 end 372 } 373 end 374 375 ### 376 ### common 377 ### 378 379 def _racc_evalact(act, arg) 380 action_table, action_check, _, action_pointer, 381 _, _, _, _, 382 _, _, _, shift_n, reduce_n, 383 _, _, * = arg 384 385 if act > 0 and act < shift_n 386 # 387 # shift 388 # 389 if @racc_error_status > 0 390 @racc_error_status -= 1 unless @racc_t == 1 # error token 391 end 392 @racc_vstack.push @racc_val 393 @racc_state.push act 394 @racc_read_next = true 395 if @yydebug 396 @racc_tstack.push @racc_t 397 racc_shift @racc_t, @racc_tstack, @racc_vstack 398 end 399 400 elsif act < 0 and act > -reduce_n 401 # 402 # reduce 403 # 404 code = catch(:racc_jump) { 405 @racc_state.push _racc_do_reduce(arg, act) 406 false 407 } 408 if code 409 case code 410 when 1 # yyerror 411 @racc_user_yyerror = true # user_yyerror 412 return -reduce_n 413 when 2 # yyaccept 414 return shift_n 415 else 416 raise '[Racc Bug] unknown jump code' 417 end 418 end 419 420 elsif act == shift_n 421 # 422 # accept 423 # 424 racc_accept if @yydebug 425 throw :racc_end_parse, @racc_vstack[0] 426 427 elsif act == -reduce_n 428 # 429 # error 430 # 431 case @racc_error_status 432 when 0 433 unless arg[21] # user_yyerror 434 on_error @racc_t, @racc_val, @racc_vstack 435 end 436 when 3 437 if @racc_t == 0 # is $ 438 throw :racc_end_parse, nil 439 end 440 @racc_read_next = true 441 end 442 @racc_user_yyerror = false 443 @racc_error_status = 3 444 while true 445 if i = action_pointer[@racc_state[-1]] 446 i += 1 # error token 447 if i >= 0 and 448 (act = action_table[i]) and 449 action_check[i] == @racc_state[-1] 450 break 451 end 452 end 453 throw :racc_end_parse, nil if @racc_state.size <= 1 454 @racc_state.pop 455 @racc_vstack.pop 456 if @yydebug 457 @racc_tstack.pop 458 racc_e_pop @racc_state, @racc_tstack, @racc_vstack 459 end 460 end 461 return act 462 463 else 464 raise "[Racc Bug] unknown action #{act.inspect}" 465 end 466 467 racc_next_state(@racc_state[-1], @racc_state) if @yydebug 468 469 nil 470 end 471 472 def _racc_do_reduce(arg, act) 473 _, _, _, _, 474 goto_table, goto_check, goto_default, goto_pointer, 475 nt_base, reduce_table, _, _, 476 _, use_result, * = arg 477 state = @racc_state 478 vstack = @racc_vstack 479 tstack = @racc_tstack 480 481 i = act * -3 482 len = reduce_table[i] 483 reduce_to = reduce_table[i+1] 484 method_id = reduce_table[i+2] 485 void_array = [] 486 487 tmp_t = tstack[-len, len] if @yydebug 488 tmp_v = vstack[-len, len] 489 tstack[-len, len] = void_array if @yydebug 490 vstack[-len, len] = void_array 491 state[-len, len] = void_array 492 493 # tstack must be updated AFTER method call 494 if use_result 495 vstack.push __send__(method_id, tmp_v, vstack, tmp_v[0]) 496 else 497 vstack.push __send__(method_id, tmp_v, vstack) 498 end 499 tstack.push reduce_to 500 501 racc_reduce(tmp_t, reduce_to, tstack, vstack) if @yydebug 502 503 k1 = reduce_to - nt_base 504 if i = goto_pointer[k1] 505 i += state[-1] 506 if i >= 0 and (curstate = goto_table[i]) and goto_check[i] == k1 507 return curstate 508 end 509 end 510 goto_default[k1] 511 end 512 513 # This method is called when a parse error is found. 514 # 515 # ERROR_TOKEN_ID is an internal ID of token which caused error. 516 # You can get string representation of this ID by calling 517 # #token_to_str. 518 # 519 # ERROR_VALUE is a value of error token. 520 # 521 # value_stack is a stack of symbol values. 522 # DO NOT MODIFY this object. 523 # 524 # This method raises ParseError by default. 525 # 526 # If this method returns, parsers enter "error recovering mode". 527 def on_error(t, val, vstack) 528 raise ParseError, sprintf("\nparse error on value %s (%s)", 529 val.inspect, token_to_str(t) || '?') 530 end 531 532 # Enter error recovering mode. 533 # This method does not call #on_error. 534 def yyerror 535 throw :racc_jump, 1 536 end 537 538 # Exit parser. 539 # Return value is Symbol_Value_Stack[0]. 540 def yyaccept 541 throw :racc_jump, 2 542 end 543 544 # Leave error recovering mode. 545 def yyerrok 546 @racc_error_status = 0 547 end 548 549 # For debugging output 550 def racc_read_token(t, tok, val) 551 @racc_debug_out.print 'read ' 552 @racc_debug_out.print tok.inspect, '(', racc_token2str(t), ') ' 553 @racc_debug_out.puts val.inspect 554 @racc_debug_out.puts 555 end 556 557 def racc_shift(tok, tstack, vstack) 558 @racc_debug_out.puts "shift #{racc_token2str tok}" 559 racc_print_stacks tstack, vstack 560 @racc_debug_out.puts 561 end 562 563 def racc_reduce(toks, sim, tstack, vstack) 564 out = @racc_debug_out 565 out.print 'reduce ' 566 if toks.empty? 567 out.print ' <none>' 568 else 569 toks.each {|t| out.print ' ', racc_token2str(t) } 570 end 571 out.puts " --> #{racc_token2str(sim)}" 572 573 racc_print_stacks tstack, vstack 574 @racc_debug_out.puts 575 end 576 577 def racc_accept 578 @racc_debug_out.puts 'accept' 579 @racc_debug_out.puts 580 end 581 582 def racc_e_pop(state, tstack, vstack) 583 @racc_debug_out.puts 'error recovering mode: pop token' 584 racc_print_states state 585 racc_print_stacks tstack, vstack 586 @racc_debug_out.puts 587 end 588 589 def racc_next_state(curstate, state) 590 @racc_debug_out.puts "goto #{curstate}" 591 racc_print_states state 592 @racc_debug_out.puts 593 end 594 595 def racc_print_stacks(t, v) 596 out = @racc_debug_out 597 out.print ' [' 598 t.each_index do |i| 599 out.print ' (', racc_token2str(t[i]), ' ', v[i].inspect, ')' 600 end 601 out.puts ' ]' 602 end 603 604 def racc_print_states(s) 605 out = @racc_debug_out 606 out.print ' [' 607 s.each {|st| out.print ' ', st } 608 out.puts ' ]' 609 end 610 611 def racc_token2str(tok) 612 self.class::Racc_token_to_s_table[tok] or 613 raise "[Racc Bug] can't convert token #{tok} to string" 614 end 615 616 # Convert internal ID of token symbol to the string. 617 def token_to_str(t) 618 self.class::Racc_token_to_s_table[t] 619 end 620 621 end 622 623end 624