1# Rules providing basic arithmetic operations 2 3HAIKU_ZERO = + 0 ; 4HAIKU_ONE = + 1 ; 5 6HAIKU_PAD_9 = 0 1 2 3 4 5 6 7 8 ; 7 8# a > b <==> $(HAIKU_DIGIT_GREATER_$(a)[1$(b)]) 9HAIKU_DIGIT_GREATER_0 = $(HAIKU_PAD_9) ; 10HAIKU_DIGIT_GREATER_1 = $(HAIKU_PAD_9) 1 ; 11HAIKU_DIGIT_GREATER_2 = $(HAIKU_PAD_9) 1 1 ; 12HAIKU_DIGIT_GREATER_3 = $(HAIKU_PAD_9) 1 1 1 ; 13HAIKU_DIGIT_GREATER_4 = $(HAIKU_PAD_9) 1 1 1 1 ; 14HAIKU_DIGIT_GREATER_5 = $(HAIKU_PAD_9) 1 1 1 1 1 ; 15HAIKU_DIGIT_GREATER_6 = $(HAIKU_PAD_9) 1 1 1 1 1 1 ; 16HAIKU_DIGIT_GREATER_7 = $(HAIKU_PAD_9) 1 1 1 1 1 1 1 ; 17HAIKU_DIGIT_GREATER_8 = $(HAIKU_PAD_9) 1 1 1 1 1 1 1 1 ; 18HAIKU_DIGIT_GREATER_9 = $(HAIKU_PAD_9) 1 1 1 1 1 1 1 1 1 ; 19 20# a + b == $(HAIKU_DIGIT_ADD_$(a)[1$(b)]) (carry ignored) 21HAIKU_DIGIT_ADD_0 = $(HAIKU_PAD_9) 0 1 2 3 4 5 6 7 8 9 ; 22HAIKU_DIGIT_ADD_1 = $(HAIKU_PAD_9) 1 2 3 4 5 6 7 8 9 0 ; 23HAIKU_DIGIT_ADD_2 = $(HAIKU_PAD_9) 2 3 4 5 6 7 8 9 0 1 ; 24HAIKU_DIGIT_ADD_3 = $(HAIKU_PAD_9) 3 4 5 6 7 8 9 0 1 2 ; 25HAIKU_DIGIT_ADD_4 = $(HAIKU_PAD_9) 4 5 6 7 8 9 0 1 2 3 ; 26HAIKU_DIGIT_ADD_5 = $(HAIKU_PAD_9) 5 6 7 8 9 0 1 2 3 4 ; 27HAIKU_DIGIT_ADD_6 = $(HAIKU_PAD_9) 6 7 8 9 0 1 2 3 4 5 ; 28HAIKU_DIGIT_ADD_7 = $(HAIKU_PAD_9) 7 8 9 0 1 2 3 4 5 6 ; 29HAIKU_DIGIT_ADD_8 = $(HAIKU_PAD_9) 8 9 0 1 2 3 4 5 6 7 ; 30HAIKU_DIGIT_ADD_9 = $(HAIKU_PAD_9) 9 0 1 2 3 4 5 6 7 8 ; 31 32# a - b == $(HAIKU_DIGIT_SUB_$(a)[1$(b)]) (carry ignored) 33HAIKU_DIGIT_SUB_0 = $(HAIKU_PAD_9) 0 9 8 7 6 5 4 3 2 1 ; 34HAIKU_DIGIT_SUB_1 = $(HAIKU_PAD_9) 1 0 9 8 7 6 5 4 3 2 ; 35HAIKU_DIGIT_SUB_2 = $(HAIKU_PAD_9) 2 1 0 9 8 7 6 5 4 3 ; 36HAIKU_DIGIT_SUB_3 = $(HAIKU_PAD_9) 3 2 1 0 9 8 7 6 5 4 ; 37HAIKU_DIGIT_SUB_4 = $(HAIKU_PAD_9) 4 3 2 1 0 9 8 7 6 5 ; 38HAIKU_DIGIT_SUB_5 = $(HAIKU_PAD_9) 5 4 3 2 1 0 9 8 7 6 ; 39HAIKU_DIGIT_SUB_6 = $(HAIKU_PAD_9) 6 5 4 3 2 1 0 9 8 7 ; 40HAIKU_DIGIT_SUB_7 = $(HAIKU_PAD_9) 7 6 5 4 3 2 1 0 9 8 ; 41HAIKU_DIGIT_SUB_8 = $(HAIKU_PAD_9) 8 7 6 5 4 3 2 1 0 9 ; 42HAIKU_DIGIT_SUB_9 = $(HAIKU_PAD_9) 9 8 7 6 5 4 3 2 1 0 ; 43 44# a * b == $(HAIKU_DIGIT_MULT_CARRY_$(a)[1$(b)]) $(HAIKU_DIGIT_MULT_$(a)[1$(b)]) 45HAIKU_DIGIT_MULT_0 = $(HAIKU_PAD_9) 0 0 0 0 0 0 0 0 0 0 ; 46HAIKU_DIGIT_MULT_1 = $(HAIKU_PAD_9) 0 1 2 3 4 5 6 7 8 9 ; 47HAIKU_DIGIT_MULT_2 = $(HAIKU_PAD_9) 0 2 4 6 8 0 2 4 6 8 ; 48HAIKU_DIGIT_MULT_3 = $(HAIKU_PAD_9) 0 3 6 9 2 5 8 1 4 7 ; 49HAIKU_DIGIT_MULT_4 = $(HAIKU_PAD_9) 0 4 8 2 6 0 4 8 2 6 ; 50HAIKU_DIGIT_MULT_5 = $(HAIKU_PAD_9) 0 5 0 5 0 5 0 5 0 5 ; 51HAIKU_DIGIT_MULT_6 = $(HAIKU_PAD_9) 0 6 2 8 4 0 6 2 8 4 ; 52HAIKU_DIGIT_MULT_7 = $(HAIKU_PAD_9) 0 7 4 1 8 5 2 9 6 3 ; 53HAIKU_DIGIT_MULT_8 = $(HAIKU_PAD_9) 0 8 6 4 2 0 8 6 4 2 ; 54HAIKU_DIGIT_MULT_9 = $(HAIKU_PAD_9) 0 9 8 7 6 5 4 3 2 1 ; 55 56HAIKU_DIGIT_MULT_CARRY_0 = $(HAIKU_PAD_9) 0 0 0 0 0 0 0 0 0 0 ; 57HAIKU_DIGIT_MULT_CARRY_1 = $(HAIKU_PAD_9) 0 0 0 0 0 0 0 0 0 0 ; 58HAIKU_DIGIT_MULT_CARRY_2 = $(HAIKU_PAD_9) 0 0 0 0 0 1 1 1 1 1 ; 59HAIKU_DIGIT_MULT_CARRY_3 = $(HAIKU_PAD_9) 0 0 0 0 1 1 1 2 2 2 ; 60HAIKU_DIGIT_MULT_CARRY_4 = $(HAIKU_PAD_9) 0 0 0 1 1 2 2 2 3 3 ; 61HAIKU_DIGIT_MULT_CARRY_5 = $(HAIKU_PAD_9) 0 0 1 1 2 2 3 3 4 4 ; 62HAIKU_DIGIT_MULT_CARRY_6 = $(HAIKU_PAD_9) 0 0 1 1 2 3 3 4 4 5 ; 63HAIKU_DIGIT_MULT_CARRY_7 = $(HAIKU_PAD_9) 0 0 1 2 2 3 4 4 5 6 ; 64HAIKU_DIGIT_MULT_CARRY_8 = $(HAIKU_PAD_9) 0 0 1 2 3 4 4 5 6 7 ; 65HAIKU_DIGIT_MULT_CARRY_9 = $(HAIKU_PAD_9) 0 0 1 2 3 4 5 6 7 8 ; 66 67 68# pragma mark - Number Operations 69 70 71rule NormalizeNum number 72{ 73 # NormalizeNum <number> ; 74 75 local sign ; 76 if $(number[1]) = "-" || $(number[1] = "+" { 77 sign = $(number[1]) ; 78 number = $(number[2-]) ; 79 } else { 80 sign = "+" ; 81 } 82 83 # cut off leading zeros 84 local number = [ FReverse $(number) ] ; 85 while $(number[1]) = 0 { 86 number = $(number[2-]) ; 87 } 88 number = [ FReverse $(number) ] ; 89 90 # zero is respresented as + 0 91 if ! $(number) { 92 number = 0 ; 93 sign = "+" ; 94 } 95 96 return $(sign) $(number) ; 97} 98 99rule Num string : dontExit 100{ 101 # Num <number string> [ : <dontExit> ] ; 102 103 # split the string into three parts: sign, digits, and remainder 104 local temp = [ Match ([^0-9]*)([0-9]+)(.*) : $(string) ] ; 105 106 # there must be digits, but there must not be a remainder 107 if ! $(temp[2]) || $(temp[3]) { 108 if $(dontExit) { 109 return ; 110 } 111 Exit "Not a number" ; 112 } 113 114 # get the sign 115 local number ; 116 if ! $(temp[1]) { 117 number = "+" ; 118 } else if $(temp[1]) = "+" || $(temp[1]) = "-" { 119 number = $(temp[1]) ; 120 } else { 121 if $(dontExit) { 122 return ; 123 } 124 Exit "Not a number (sign)" ; 125 } 126 127 # split the digits 128 temp = $(temp[2]) ; 129 while $(temp[1]) { 130 # split off the last digit 131 temp = [ Match (.*)([0-9]) : $(temp[1]) ] ; 132 number += $(temp[2]) ; 133 } 134 135 # normalize 136 return [ NormalizeNum $(number) ] ; 137} 138 139rule Num2String number 140{ 141 # Num2String <number> ; 142 143 local sign = $(number[1]) ; 144 if $(sign) = "+" { 145 sign = "" ; 146 } 147 148 number = [ FReverse $(number[2-]) ] ; 149 150 return $(sign)$(number:J=) ; 151} 152 153rule NumGreaterAbs a : b 154{ 155 # NumGreaterAbs <a> : <b> ; 156 157 # we compare from least to most significant digit 158 local cmp = 0 ; 159 while $(a) && $(b) { 160 # chop off the first digit 161 local da = $(a[1]:E=0) ; 162 local db = $(b[1]:E=0) ; 163 a = $(a[2-]) ; 164 b = $(b[2-]) ; 165 166 if $(da) != $(db) { 167 if $(HAIKU_DIGIT_GREATER_$(da)[1$(db)]) { 168 cmp = 1 ; 169 } else { 170 cmp = -1 ; 171 } 172 } 173 } 174 175 # a is greater, if b is not longer and a is either longer or equally long 176 # and greater according to the digits comparison 177 if ! $(b) && ( $(a) || $(cmp) = 1 ) { 178 return 1 ; 179 } 180 return ; 181} 182 183rule AddNumAbs a : b 184{ 185 # AddNum <a> : <b> ; 186 187 local result ; 188 local carry ; 189 while $(a) || $(b) || $(carry) { 190 # chop off the first digit 191 local da = $(a[1]:E=0) ; 192 local db = $(b[1]:E=0) ; 193 a = $(a[2-]) ; 194 b = $(b[2-]) ; 195 196 # add carry to the first digit 197 if $(carry) { 198 local daa = $(HAIKU_DIGIT_ADD_1[1$(da)]) ; 199 carry = $(HAIKU_DIGIT_GREATER_$(da)[1$(daa)]) ; 200 da = $(daa) ; 201 } 202 203 # add digits 204 local dr = $(HAIKU_DIGIT_ADD_$(da)[1$(db)]) ; 205 if $(HAIKU_DIGIT_GREATER_$(da)[1$(dr)]) { 206 carry = 1 ; 207 } 208 209 result += $(dr) ; 210 } 211 212 return $(result) ; 213} 214 215rule SubNumAbs a : b 216{ 217 # SubNum <a> : <b> ; 218 219 local result ; 220 local carry ; 221 while $(a) && ( $(b) || $(carry) ) { 222 # chop off the first digit 223 local da = $(a[1]:E=0) ; 224 local db = $(b[1]:E=0) ; 225 a = $(a[2-]) ; 226 b = $(b[2-]) ; 227 228 # sub carry from the first digit 229 if $(carry) { 230 local daa = $(HAIKU_DIGIT_SUB_$(da)[11]) ; 231 carry = $(HAIKU_DIGIT_GREATER_$(daa)[1$(da)]) ; 232 da = $(daa) ; 233 } 234 235 # sub digits 236 local dr = $(HAIKU_DIGIT_SUB_$(da)[1$(db)]) ; 237 if $(HAIKU_DIGIT_GREATER_$(dr)[1$(da)]) { 238 carry = 1 ; 239 } 240 241 result += $(dr) ; 242 } 243 244 if $(b) || $(carry) { 245 Exit "Error: SubNumAbs: Can't subtract greater from smaller number." ; 246 } 247 248 return $(result) ; 249} 250 251rule NegNum a 252{ 253 # NegNum <a> ; 254 255 if $(a[1]) = "+" { 256 if $(a) = $(HAIKU_ZERO) { 257 return $(a) ; 258 } 259 return "-" $(a[2-]) ; 260 } else { 261 return "+" $(a[2-]) ; 262 } 263} 264 265rule AddNum a : b 266{ 267 # AddNum <a> : <b> ; 268 269 local signa = $(a[1]) ; 270 local signb = $(b[1]) ; 271 a = $(a[2-]) ; 272 b = $(b[2-]) ; 273 274 if $(signa) = $(signb) { 275 return $(signa) [ AddNumAbs $(a) : $(b) ] ; 276 } else { 277 local result ; 278 if [ NumGreaterAbs $(a) : $(b) ] { 279 result = $(signa) [ SubNumAbs $(a) : $(b) ] ; 280 } else { 281 result = $(signb) [ SubNumAbs $(b) : $(a) ] ; 282 } 283 return [ NormalizeNum $(result) ] ; 284 } 285} 286 287rule SubNum a : b 288{ 289 # SubNum <a> : <b> ; 290 return [ AddNum $(a) : [ NegNum $(b) ] ] ; 291} 292 293rule MultNumAbsDigit a : digit 294{ 295 # MultNumAbsDigit <a> : <digit> ; 296 297 local digitMultiples = $(HAIKU_DIGIT_MULT_$(digit)) ; 298 local digitCarries = $(HAIKU_DIGIT_MULT_CARRY_$(digit)) ; 299 300 local result ; 301 local carry = 0 ; 302 while $(a) || $(carry) != 0 { 303 # chop off the first digit 304 local da = $(a[1]:E=0) ; 305 a = $(a[2-]) ; 306 307 local dr = $(digitMultiples[1$(da)]) ; 308 309 # add carry to the resulting digit 310 if $(carry) { 311 local dra = $(HAIKU_DIGIT_ADD_$(dr)[1$(carry)]) ; 312 carry = $(HAIKU_DIGIT_GREATER_$(dr)[1$(dra)]:E=0) ; 313 dr = $(dra) ; 314 } 315 316 # new carry 317 carry = $(HAIKU_DIGIT_ADD_$(carry:E=0)[1$(digitCarries[1$(da)])]) ; 318 319 result += $(dr) ; 320 } 321 322 return $(result) ; 323} 324 325rule MultNum a : b 326{ 327 # MultNum <a> : <b> ; 328 329 # If one of the factors is 0, we save us computation and normalization. 330 if $(a) = $(HAIKU_ZERO) || $(b) = $(HAIKU_ZERO) { 331 return $(HAIKU_ZERO) ; 332 } 333 334 # get the sign for the result 335 local sign = "+" ; 336 if $(a[1]) != $(b[1]) { 337 sign = "-" ; 338 } 339 340 a = $(a[2-]) ; 341 b = $(b[2-]) ; 342 343 # multiply the individual digits of b with a and add up the result 344 local result = 0 ; 345 local prefix ; 346 while $(b) { 347 local db = $(b[1]) ; 348 b = $(b[2-]) ; 349 350 local adb = $(prefix) [ MultNumAbsDigit $(a) : $(db) ] ; 351 result = [ AddNumAbs $(result) : $(adb) ] ; 352 353 prefix += 0 ; 354 } 355 356 return $(sign) $(result) ; 357} 358 359rule NumGreater a : b 360{ 361 local signa = $(a[1]) ; 362 local signb = $(b[1]) ; 363 a = $(a[2-]) ; 364 b = $(b[2-]) ; 365 366 if $(signa) = $(signb) { 367 if $(signa) = "+" { 368 return [ NumGreaterAbs $(a) : $(b) ] ; 369 } else { 370 return [ NumGreaterAbs $(b) : $(a) ] ; 371 } 372 } else { 373 if $(signa) = "+" { 374 return 1 ; 375 } else { 376 return ; 377 } 378 } 379} 380 381 382# pragma mark - Number String Operations 383 384 385rule Inc a 386{ 387 # Inc <number string a> ; 388 return [ Num2String [ AddNum [ Num $(a) ] : + 1 ] ] ; 389} 390 391rule Dec a 392{ 393 # Dec <number string a> ; 394 return [ Num2String [ AddNum [ Num $(a) ] : - 1 ] ] ; 395} 396 397rule Neg a 398{ 399 # Neg <number string a> ; 400 return [ Num2String [ NegNum [ Num $(a) ] ] ] ; 401} 402 403rule Add a : b 404{ 405 # Add <number string a> : <number string b> ; 406 return [ Num2String [ AddNum [ Num $(a) ] : [ Num $(b) ] ] ] ; 407} 408 409rule Sub a : b 410{ 411 # Sub <number string a> : <number string b> ; 412 return [ Num2String [ SubNum [ Num $(a) ] : [ Num $(b) ] ] ] ; 413} 414 415rule Mult a : b 416{ 417 # Mult <number string a> : <number string b> ; 418 return [ Num2String [ MultNum [ Num $(a) ] : [ Num $(b) ] ] ] ; 419} 420 421rule Equal a : b 422{ 423 # Equal <number string a> : <number string b> ; 424 if [ Num $(a) ] = [ Num $(b) ] { 425 return 1 ; 426 } 427 428 return ; 429} 430 431rule Less a : b 432{ 433 # Less <number string a> : <number string b> ; 434 return [ NumGreater [ Num $(b) ] : [ Num $(a) ] ] ; 435} 436 437rule Greater a : b 438{ 439 # Greater <number string a> : <number string b> ; 440 return [ NumGreater [ Num $(a) ] : [ Num $(b) ] ] ; 441} 442 443rule LessOrEqual a : b 444{ 445 # LessOrEqual <number string a> : <number string b> ; 446 if [ NumGreater [ Num $(a) ] : [ Num $(b) ] ] { 447 return ; 448 } 449 return 1 ; 450} 451 452rule GreaterOrEqual a : b 453{ 454 # GreaterOrEqual <number string a> : <number string b> ; 455 if [ NumGreater [ Num $(b) ] : [ Num $(a) ] ] { 456 return ; 457 } 458 return 1 ; 459} 460 461 462# pragma mark - Expression Parser 463 464 465rule ParseAtom expression 466{ 467 # ParseAtom <expression> ; 468 469 # expression: '(' expression ')' | number 470 471 if $(expression[1]) = "(" { 472 local result = [ ParseExpression $(expression[2-]) ] ; 473 if $(result[2]) != ")" { 474 Exit "ParseAtom: Parse error: Expected \")\"." ; 475 } 476 return $(result[1]) $(result[3-]) ; 477 } else { 478 if ! $(expression) { 479 Exit "ParseAtom: Parse error: Unexpected end of expression." ; 480 } 481 482 local num = [ Num $(expression[1]) : 1 ] ; 483 if ! $(num) { 484 Exit "ParseAtom: Parse error: Expected number instead of:" 485 $(expression[1]) ; 486 } 487 488 return [ Num2String $(num) ] $(expression[2-]) ; 489 } 490} 491 492rule ParseUnary expression 493{ 494 # ParseUnary <expression> ; 495 496 # expression: ('+'/'-')* atom 497 498 if ! $(expression) { 499 Exit "ParseUnary: Parse error: Unexpected end of expression." ; 500 } 501 502 # eat all unary "+" and "-" operations 503 local neg ; 504 while $(expression[1]) = "+" || $(expression[1]) = "-" { 505 if $(expression[1]) = "-" { 506 if $(neg) { 507 neg = ; 508 } else { 509 neg = 1 ; 510 } 511 } 512 513 expression = $(expression[2-]) ; 514 } 515 516 local result = [ ParseAtom $(expression) ] ; 517 518 if $(neg) { 519 return [ Neg $(result[1]) ] $(result[2-]) ; 520 } 521 return $(result) ; 522} 523 524rule ParseTerm expression 525{ 526 # ParseTerm <expression> ; 527 528 # expression: unary ('*' unary)* 529 530 local result = [ ParseUnary $(expression) ] ; 531 local product = $(result[1]) ; 532 expression = $(result[2-]) ; 533 534 while $(expression[1]) = "*" { 535 # get the operation 536 local operation ; 537 operation = Mult ; 538 539 # parse the next operand 540 result = [ ParseUnary $(expression[2-]) ] ; 541 expression = $(result[2-]) ; 542 543 # compute the product 544 product = [ $(operation) $(product) : $(result[1]) ] ; 545 } 546 547 return $(product) $(expression) ; 548} 549 550rule ParseExpression expression 551{ 552 # ParseExpression <expression> ; 553 554 # expression: term ('+'/'-' term)* 555 556 local result = [ ParseTerm $(expression) ] ; 557 local sum = $(result[1]) ; 558 expression = $(result[2-]) ; 559 560 while $(expression[1]) = "+" || $(expression[1]) = "-" { 561 # get the operation 562 local operation ; 563 if $(expression[1]) = "+" { 564 operation = Add ; 565 } else { 566 operation = Sub ; 567 } 568 569 # parse the next operand 570 result = [ ParseTerm $(expression[2-]) ] ; 571 expression = $(result[2-]) ; 572 573 # compute the sum 574 sum = [ $(operation) $(sum) : $(result[1]) ] ; 575 } 576 577 return $(sum) $(expression) ; 578} 579 580 581rule Expr expression 582{ 583 # Expr <expression> ; 584 585 # tokenize the expression 586 local tokens ; 587 local string ; 588 for string in $(expression) { 589 while $(string) { 590 local split = [ Match "[ \t]*(-|[()+*]|[0-9]*)(.*)" : $(string) ] ; 591 if ! $(split[1]) { 592 Exit "Expr: Syntax error: Invalid token: \"$(string)\"." ; 593 } 594 595 tokens += $(split[1]) ; 596 string = $(split[2]) ; 597 } 598 } 599 600 local result = [ ParseExpression $(tokens) ] ; 601 if $(result[2-]) { 602 Exit "Expr: Garbage at end of expression:" $(result[2-]) ; 603 } 604 605 return $(result[1]) ; 606} 607