3 * $OpenBSD: bc.y,v 1.23 2004/02/18 07:43:58 otto Exp $
4 * $DragonFly: src/usr.bin/bc/bc.y,v 1.1 2004/09/20 04:20:34 dillon Exp $
8 * Copyright (c) 2003, Otto Moerbeek <otto@drijf.net>
10 * Permission to use, copy, modify, and distribute this software for any
11 * purpose with or without fee is hereby granted, provided that the above
12 * copyright notice and this permission notice appear in all copies.
14 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
15 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
16 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
17 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
18 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
19 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
20 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
24 * This implementation of bc(1) uses concepts from the original 4.4
25 * BSD bc(1). The code itself is a complete rewrite, based on the
26 * Posix defined bc(1) grammar. Other differences include type safe
27 * usage of pointers to build the tree of emitted code, typed yacc
28 * rule values, dynamic allocation of all data structures and a
29 * completely rewritten lexical analyzer using lex(1).
31 * Some effort has been made to make sure that the generated code is
32 * the same as the code generated by the older version, to provide
33 * easy regression testing.
47 #include "pathnames.h"
49 #define END_NODE ((ssize_t) -1)
50 #define CONST_STRING ((ssize_t) -2)
51 #define ALLOC_STRING ((ssize_t) -3)
64 static void grow(void);
65 static ssize_t cs(const char *);
66 static ssize_t as(const char *);
67 static ssize_t node(ssize_t, ...);
68 static void emit(ssize_t);
69 static void emit_macro(int, ssize_t);
70 static void free_tree(void);
71 static ssize_t numnode(int);
72 static ssize_t lookup(char *, size_t, char);
73 static ssize_t letter_node(char *);
74 static ssize_t array_node(char *);
75 static ssize_t function_node(char *);
77 static void add_par(ssize_t);
78 static void add_local(ssize_t);
79 static void warning(const char *);
80 static void init(void);
81 static void usage(void);
82 static char *escape(const char *);
84 static size_t instr_sz = 0;
85 static struct tree *instructions = NULL;
86 static ssize_t current = 0;
87 static int macro_char = '0';
88 static int reset_macro_char = '0';
89 static int nesting = 0;
90 static int breakstack[16];
91 static int breaksp = 0;
92 static ssize_t prologue;
93 static ssize_t epilogue;
94 static bool st_has_continue;
95 static char str_table[UCHAR_MAX][2];
99 static char *filename;
100 static bool do_fork = true;
101 static u_short var_count;
103 extern char *__progname;
105 #define BREAKSTACK_SZ (sizeof(breakstack)/sizeof(breakstack[0]))
107 /* These values are 4.4BSD bc compatible */
108 #define FUNC_CHAR 0x01
109 #define ARRAY_CHAR 0xa1
111 /* Skip '\0', [, \ and ] */
112 #define ENCODE(c) ((c) < '[' ? (c) : (c) + 3);
113 #define VAR_BASE (256-4)
114 #define MAX_VARIABLES (VAR_BASE * VAR_BASE)
122 struct lvalue lvalue;
127 %token COMMA SEMICOLON LPAR RPAR LBRACE RBRACE LBRACKET RBRACKET DOT
130 %token <str> NUMBER STRING
131 %token DEFINE BREAK QUIT LENGTH
132 %token RETURN FOR IF WHILE SQRT
133 %token SCALE IBASE OBASE AUTO
134 %token CONTINUE ELSE PRINT
139 %nonassoc EQUALS LESS_EQ GREATER_EQ UNEQUALS LESS GREATER
140 %right <str> ASSIGN_OP
142 %left MULTIPLY DIVIDE REMAINDER
147 %type <lvalue> named_expression
148 %type <node> argument_list
149 %type <node> alloc_macro
150 %type <node> expression
151 %type <node> function
152 %type <node> function_header
153 %type <node> input_item
154 %type <node> opt_argument_list
155 %type <node> opt_expression
156 %type <node> opt_relational_expression
157 %type <node> opt_statement
158 %type <node> print_expression
159 %type <node> print_expression_list
160 %type <node> relational_expression
161 %type <node> return_expression
162 %type <node> semicolon_list
163 %type <node> statement
164 %type <node> statement_list
168 program : /* empty */
172 input_item : semicolon_list NEWLINE
175 macro_char = reset_macro_char;
178 st_has_continue = false;
184 st_has_continue = false;
192 semicolon_list : /* empty */
197 | semicolon_list SEMICOLON statement
199 $$ = node($1, $3, END_NODE);
201 | semicolon_list SEMICOLON
204 statement_list : /* empty */
209 | statement_list NEWLINE
210 | statement_list NEWLINE statement
212 $$ = node($1, $3, END_NODE);
214 | statement_list SEMICOLON
215 | statement_list SEMICOLON statement
217 $$ = node($1, $3, END_NODE);
222 opt_statement : /* empty */
229 statement : expression
231 $$ = node($1, cs("ps."), END_NODE);
233 | named_expression ASSIGN_OP expression
236 $$ = node($3, cs($2), $1.store,
239 $$ = node($1.load, $3, cs($2), $1.store,
244 $$ = node(cs("["), as($1),
250 warning("break not in for or while");
255 breakstack[breaksp-1]),
262 warning("continue not in for or while");
265 st_has_continue = true;
266 $$ = node(numnode(nesting -
267 breakstack[breaksp-1] - 1),
277 | RETURN return_expression
280 warning("return must be in a function");
285 | FOR LPAR alloc_macro opt_expression SEMICOLON
286 opt_relational_expression SEMICOLON
287 opt_expression RPAR opt_statement pop_nesting
292 n = node($10, cs("M"), $8, cs("s."),
295 n = node($10, $8, cs("s."), $6, $3,
299 $$ = node($4, cs("s."), $6, $3, cs(" "),
302 | IF LPAR alloc_macro pop_nesting relational_expression RPAR
306 $$ = node($5, $3, cs(" "), END_NODE);
308 | IF LPAR alloc_macro pop_nesting relational_expression RPAR
309 opt_statement ELSE alloc_macro pop_nesting opt_statement
313 $$ = node($5, $3, cs("e"), $9, cs(" "),
316 | WHILE LPAR alloc_macro relational_expression RPAR
317 opt_statement pop_nesting
322 n = node($6, cs("M"), $4, $3, END_NODE);
324 n = node($6, $4, $3, END_NODE);
326 $$ = node($4, $3, cs(" "), END_NODE);
328 | LBRACE statement_list RBRACE
332 | PRINT print_expression_list
338 alloc_macro : /* empty */
340 $$ = cs(str_table[macro_char]);
342 /* Do not use [, \ and ] */
343 if (macro_char == '[')
346 else if (macro_char == 'a')
348 else if (macro_char == ARRAY_CHAR)
350 else if (macro_char == 255)
351 fatal("program too big");
352 if (breaksp == BREAKSTACK_SZ)
353 fatal("nesting too deep");
354 breakstack[breaksp++] = nesting++;
358 pop_nesting : /* empty */
364 function : function_header opt_parameter_list RPAR opt_newline
365 LBRACE NEWLINE opt_auto_define_list
366 statement_list RBRACE
368 int n = node(prologue, $8, epilogue,
369 cs("0"), numnode(nesting),
372 reset_macro_char = macro_char;
378 function_header : DEFINE LETTER LPAR
380 $$ = function_node($2);
386 breakstack[breaksp] = 0;
390 opt_newline : /* empty */
400 parameter_list : LETTER
402 add_par(letter_node($1));
405 | LETTER LBRACKET RBRACKET
407 add_par(array_node($1));
410 | parameter_list COMMA LETTER
412 add_par(letter_node($3));
415 | parameter_list COMMA LETTER LBRACKET RBRACKET
417 add_par(array_node($3));
426 | AUTO define_list NEWLINE
427 | AUTO define_list SEMICOLON
433 add_local(letter_node($1));
436 | LETTER LBRACKET RBRACKET
438 add_local(array_node($1));
441 | define_list COMMA LETTER
443 add_local(letter_node($3));
446 | define_list COMMA LETTER LBRACKET RBRACKET
448 add_local(array_node($3));
463 argument_list : expression
464 | argument_list COMMA expression
466 $$ = node($1, $3, END_NODE);
468 | argument_list COMMA LETTER LBRACKET RBRACKET
470 $$ = node($1, cs("l"), array_node($3),
476 opt_relational_expression
481 | relational_expression
484 relational_expression
485 : expression EQUALS expression
487 $$ = node($1, $3, cs("="), END_NODE);
489 | expression UNEQUALS expression
491 $$ = node($1, $3, cs("!="), END_NODE);
493 | expression LESS expression
495 $$ = node($1, $3, cs(">"), END_NODE);
497 | expression LESS_EQ expression
499 $$ = node($1, $3, cs("!<"), END_NODE);
501 | expression GREATER expression
503 $$ = node($1, $3, cs("<"), END_NODE);
505 | expression GREATER_EQ expression
507 $$ = node($1, $3, cs("!>"), END_NODE);
511 $$ = node($1, cs(" 0!="), END_NODE);
519 $$ = node(cs("0"), epilogue,
520 numnode(nesting), cs("Q"), END_NODE);
524 $$ = node($1, epilogue,
525 numnode(nesting), cs("Q"), END_NODE);
529 $$ = node(cs("0"), epilogue,
530 numnode(nesting), cs("Q"), END_NODE);
535 opt_expression : /* empty */
542 expression : named_expression
544 $$ = node($1.load, END_NODE);
547 $$ = node(cs("l."), END_NODE);
551 $$ = node(cs(" "), as($1), END_NODE);
553 | LPAR expression RPAR
557 | LETTER LPAR opt_argument_list RPAR
559 $$ = node($3, cs("l"),
560 function_node($1), cs("x"),
564 | MINUS expression %prec UMINUS
566 $$ = node(cs(" 0"), $2, cs("-"),
569 | expression PLUS expression
571 $$ = node($1, $3, cs("+"), END_NODE);
573 | expression MINUS expression
575 $$ = node($1, $3, cs("-"), END_NODE);
577 | expression MULTIPLY expression
579 $$ = node($1, $3, cs("*"), END_NODE);
581 | expression DIVIDE expression
583 $$ = node($1, $3, cs("/"), END_NODE);
585 | expression REMAINDER expression
587 $$ = node($1, $3, cs("%"), END_NODE);
589 | expression EXPONENT expression
591 $$ = node($1, $3, cs("^"), END_NODE);
593 | INCR named_expression
595 $$ = node($2.load, cs("1+d"), $2.store,
598 | DECR named_expression
600 $$ = node($2.load, cs("1-d"),
603 | named_expression INCR
605 $$ = node($1.load, cs("d1+"),
608 | named_expression DECR
610 $$ = node($1.load, cs("d1-"),
613 | named_expression ASSIGN_OP expression
616 $$ = node($3, cs($2), cs("d"), $1.store,
619 $$ = node($1.load, $3, cs($2), cs("d"),
622 | LENGTH LPAR expression RPAR
624 $$ = node($3, cs("Z"), END_NODE);
626 | SQRT LPAR expression RPAR
628 $$ = node($3, cs("v"), END_NODE);
630 | SCALE LPAR expression RPAR
632 $$ = node($3, cs("X"), END_NODE);
634 | BOOL_NOT expression
636 $$ = node($2, cs("N"), END_NODE);
638 | expression BOOL_AND alloc_macro pop_nesting expression
640 ssize_t n = node(cs("R"), $5, END_NODE);
642 $$ = node($1, cs("d0!="), $3, END_NODE);
644 | expression BOOL_OR alloc_macro pop_nesting expression
646 ssize_t n = node(cs("R"), $5, END_NODE);
648 $$ = node($1, cs("d0="), $3, END_NODE);
650 | expression EQUALS expression
652 $$ = node($1, $3, cs("G"), END_NODE);
654 | expression UNEQUALS expression
656 $$ = node($1, $3, cs("GN"), END_NODE);
658 | expression LESS expression
660 $$ = node($3, $1, cs("("), END_NODE);
662 | expression LESS_EQ expression
664 $$ = node($3, $1, cs("{"), END_NODE);
666 | expression GREATER expression
668 $$ = node($1, $3, cs("("), END_NODE);
670 | expression GREATER_EQ expression
672 $$ = node($1, $3, cs("{"), END_NODE);
679 $$.load = node(cs("l"), letter_node($1),
681 $$.store = node(cs("s"), letter_node($1),
685 | LETTER LBRACKET expression RBRACKET
687 $$.load = node($3, cs(";"),
688 array_node($1), END_NODE);
689 $$.store = node($3, cs(":"),
690 array_node($1), END_NODE);
710 print_expression_list
712 | print_expression_list COMMA print_expression
714 $$ = node($1, $3, END_NODE);
720 $$ = node($1, cs("ds.n"), END_NODE);
724 char *p = escape($1);
725 $$ = node(cs("["), as(p), cs("]n"), END_NODE);
737 if (current == instr_sz) {
738 newsize = instr_sz * 2 + 1;
739 p = realloc(instructions, newsize * sizeof(*p));
753 instructions[current].index = CONST_STRING;
754 instructions[current].u.cstr = str;
762 instructions[current].index = ALLOC_STRING;
763 instructions[current].u.astr = strdup(str);
764 if (instructions[current].u.astr == NULL)
770 node(ssize_t arg, ...)
779 instructions[current++].index = arg;
782 arg = va_arg(ap, ssize_t);
784 instructions[current++].index = arg;
785 } while (arg != END_NODE);
794 if (instructions[i].index >= 0)
795 while (instructions[i].index != END_NODE)
796 emit(instructions[i++].index);
798 fputs(instructions[i].u.cstr, stdout);
802 emit_macro(int node, ssize_t code)
806 printf("]s%s\n", instructions[node].u.cstr);
815 for (i = 0; i < current; i++)
816 if (instructions[i].index == ALLOC_STRING)
817 free(instructions[i].u.astr);
827 p = str_table['0' + num];
829 p = str_table['A' - 10 + num];
831 errx(1, "internal error: break num > 15");
832 return node(cs(" "), cs(p), END_NODE);
837 lookup(char * str, size_t len, char type)
843 /* The scanner allocated an extra byte already */
844 if (str[len-1] != type) {
849 found = hsearch(entry, FIND);
851 if (var_count == MAX_VARIABLES)
852 errx(1, "too many variables");
858 p[1] = ENCODE(num / VAR_BASE + 1);
859 p[2] = ENCODE(num % VAR_BASE + 1);
862 entry.data = (char *)p;
863 entry.key = strdup(str);
864 if (entry.key == NULL)
866 found = hsearch(entry, ENTER);
870 return cs(found->data);
874 letter_node(char *str)
879 if (len == 1 && str[0] != '_')
880 return cs(str_table[(int)str[0]]);
882 return lookup(str, len, 'L');
886 array_node(char *str)
891 if (len == 1 && str[0] != '_')
892 return cs(str_table[(int)str[0] - 'a' + ARRAY_CHAR]);
894 return lookup(str, len, 'A');
898 function_node(char *str)
903 if (len == 1 && str[0] != '_')
904 return cs(str_table[(int)str[0] - 'a' + FUNC_CHAR]);
906 return lookup(str, len, 'F');
912 prologue = node(cs("S"), n, prologue, END_NODE);
913 epilogue = node(epilogue, cs("L"), n, cs("s."), END_NODE);
919 prologue = node(cs("0S"), n, prologue, END_NODE);
920 epilogue = node(epilogue, cs("L"), n, cs("s."), END_NODE);
926 if (fileindex < sargc) {
927 filename = sargv[fileindex++];
928 yyin = fopen(filename, "r");
931 err(1, "cannot open %s", filename);
933 } else if (fileindex == sargc) {
948 if (isspace(yytext[0]) || !isprint(yytext[0]))
949 asprintf(&str, "%s: %s:%d: %s: ascii char 0x%x unexpected",
950 __progname, filename, lineno, s, yytext[0]);
952 asprintf(&str, "%s: %s:%d: %s: %s unexpected",
953 __progname, filename, lineno, s, yytext);
958 for (p = str; *p != '\0'; p++) {
959 if (*p == '[' || *p == ']' || *p =='\\')
963 fputs("]pc\n", stdout);
970 errx(1, "%s:%d: %s", filename, lineno, s);
974 warning(const char *s)
976 warnx("%s:%d: %s", filename, lineno, s);
984 for (i = 0; i < UCHAR_MAX; i++) {
986 str_table[i][1] = '\0';
988 if (hcreate(1 << 16) == 0)
996 fprintf(stderr, "%s: usage: [-cl] [file ...]\n", __progname);
1001 escape(const char *str)
1005 ret = malloc(strlen(str) + 1);
1010 while (*str != '\0') {
1012 * We get _escaped_ strings here. Single backslashes are
1013 * already converted to double backslashes
1016 if (*++str == '\\') {
1056 main(int argc, char *argv[])
1064 sargv = malloc(argc * sizeof(char *));
1068 /* The d debug option is 4.4 BSD dc(1) compatible */
1069 while ((ch = getopt(argc, argv, "cdl")) != -1) {
1076 sargv[sargc++] = _PATH_LIBB;
1086 for (i = 0; i < argc; i++)
1087 sargv[sargc++] = argv[i];
1091 err(1, "cannot create pipe");
1094 err(1, "cannot fork");
1095 else if (ret == 0) {
1096 close(STDOUT_FILENO);
1101 close(STDIN_FILENO);
1105 execl(_PATH_DC, "dc", "-x", (char *)NULL);
1106 err(1, "cannot find dc");
1109 signal(SIGINT, abort_line);