2 /* $OpenBSD: bc.y,v 1.33 2009/10/27 23:59:36 deraadt Exp $ */
5 * Copyright (c) 2003, Otto Moerbeek <otto@drijf.net>
7 * Permission to use, copy, modify, and distribute this software for any
8 * purpose with or without fee is hereby granted, provided that the above
9 * copyright notice and this permission notice appear in all copies.
11 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
12 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
13 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
14 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
15 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
16 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
17 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
21 * This implementation of bc(1) uses concepts from the original 4.4
22 * BSD bc(1). The code itself is a complete rewrite, based on the
23 * Posix defined bc(1) grammar. Other differences include type safe
24 * usage of pointers to build the tree of emitted code, typed yacc
25 * rule values, dynamic allocation of all data structures and a
26 * completely rewritten lexical analyzer using lex(1).
28 * Some effort has been made to make sure that the generated code is
29 * the same as the code generated by the older version, to provide
30 * easy regression testing.
33 #include <sys/cdefs.h>
34 __FBSDID("$FreeBSD$");
36 #include <sys/types.h>
54 #include "pathnames.h"
56 #define BC_VER "1.0-FreeBSD"
57 #define END_NODE ((ssize_t) -1)
58 #define CONST_STRING ((ssize_t) -2)
59 #define ALLOC_STRING ((ssize_t) -3)
81 static void grow(void);
82 static ssize_t cs(const char *);
83 static ssize_t as(const char *);
84 static ssize_t node(ssize_t, ...);
85 static void emit(ssize_t);
86 static void emit_macro(int, ssize_t);
87 static void free_tree(void);
88 static ssize_t numnode(int);
89 static ssize_t lookup(char *, size_t, char);
90 static ssize_t letter_node(char *);
91 static ssize_t array_node(char *);
92 static ssize_t function_node(char *);
94 static void add_par(ssize_t);
95 static void add_local(ssize_t);
96 static void warning(const char *);
97 static void init(void);
98 static void usage(void);
99 static char *escape(const char *);
101 static ssize_t instr_sz = 0;
102 static struct tree *instructions = NULL;
103 static ssize_t current = 0;
104 static int macro_char = '0';
105 static int reset_macro_char = '0';
106 static int nesting = 0;
107 static int breakstack[16];
108 static int breaksp = 0;
109 static ssize_t prologue;
110 static ssize_t epilogue;
111 static bool st_has_continue;
112 static char str_table[UCHAR_MAX][2];
113 static bool do_fork = true;
114 static u_short var_count;
117 static void sigchld(int);
119 extern char *__progname;
121 #define BREAKSTACK_SZ (sizeof(breakstack)/sizeof(breakstack[0]))
123 /* These values are 4.4BSD bc compatible */
124 #define FUNC_CHAR 0x01
125 #define ARRAY_CHAR 0xa1
127 /* Skip '\0', [, \ and ] */
128 #define ENCODE(c) ((c) < '[' ? (c) : (c) + 3);
129 #define VAR_BASE (256-4)
130 #define MAX_VARIABLES (VAR_BASE * VAR_BASE)
132 const struct option long_options[] =
134 {"expression", required_argument, NULL, 'e'},
135 {"help", no_argument, NULL, 'h'},
136 {"mathlib", no_argument, NULL, 'l'},
137 /* compatibility option */
138 {"quiet", no_argument, NULL, 'q'},
139 {"version", no_argument, NULL, 'v'},
140 {NULL, no_argument, NULL, 0}
148 struct lvalue lvalue;
154 %token COMMA SEMICOLON LPAR RPAR LBRACE RBRACE LBRACKET RBRACKET DOT
157 %token <str> NUMBER STRING
158 %token DEFINE BREAK QUIT LENGTH
159 %token RETURN FOR IF WHILE SQRT
160 %token SCALE IBASE OBASE AUTO
161 %token CONTINUE ELSE PRINT
166 %nonassoc EQUALS LESS_EQ GREATER_EQ UNEQUALS LESS GREATER
167 %right <str> ASSIGN_OP
169 %left MULTIPLY DIVIDE REMAINDER
174 %type <lvalue> named_expression
175 %type <node> argument_list
176 %type <node> alloc_macro
177 %type <node> expression
178 %type <node> function
179 %type <node> function_header
180 %type <node> input_item
181 %type <node> opt_argument_list
182 %type <node> opt_expression
183 %type <node> opt_relational_expression
184 %type <node> opt_statement
185 %type <node> print_expression
186 %type <node> print_expression_list
187 %type <node> relational_expression
188 %type <node> return_expression
189 %type <node> semicolon_list
190 %type <node> statement
191 %type <node> statement_list
195 program : /* empty */
199 input_item : semicolon_list NEWLINE
202 macro_char = reset_macro_char;
205 st_has_continue = false;
211 st_has_continue = false;
223 semicolon_list : /* empty */
228 | semicolon_list SEMICOLON statement
230 $$ = node($1, $3, END_NODE);
232 | semicolon_list SEMICOLON
235 statement_list : /* empty */
240 | statement_list NEWLINE
241 | statement_list NEWLINE statement
243 $$ = node($1, $3, END_NODE);
245 | statement_list SEMICOLON
246 | statement_list SEMICOLON statement
248 $$ = node($1, $3, END_NODE);
253 opt_statement : /* empty */
260 statement : expression
262 $$ = node($1, cs("ps."), END_NODE);
264 | named_expression ASSIGN_OP expression
267 $$ = node($3, cs($2), $1.store,
270 $$ = node($1.load, $3, cs($2), $1.store,
275 $$ = node(cs("["), as($1),
281 warning("break not in for or while");
286 breakstack[breaksp-1]),
293 warning("continue not in for or while");
296 st_has_continue = true;
297 $$ = node(numnode(nesting -
298 breakstack[breaksp-1] - 1),
309 sigprocmask(SIG_BLOCK, NULL, &mask);
314 | RETURN return_expression
317 warning("return must be in a function");
322 | FOR LPAR alloc_macro opt_expression SEMICOLON
323 opt_relational_expression SEMICOLON
324 opt_expression RPAR opt_statement pop_nesting
329 n = node($10, cs("M"), $8, cs("s."),
332 n = node($10, $8, cs("s."), $6, $3,
336 $$ = node($4, cs("s."), $6, $3, cs(" "),
339 | IF LPAR alloc_macro pop_nesting relational_expression RPAR
343 $$ = node($5, $3, cs(" "), END_NODE);
345 | IF LPAR alloc_macro pop_nesting relational_expression RPAR
346 opt_statement ELSE alloc_macro pop_nesting opt_statement
350 $$ = node($5, $3, cs("e"), $9, cs(" "),
353 | WHILE LPAR alloc_macro relational_expression RPAR
354 opt_statement pop_nesting
359 n = node($6, cs("M"), $4, $3, END_NODE);
361 n = node($6, $4, $3, END_NODE);
363 $$ = node($4, $3, cs(" "), END_NODE);
365 | LBRACE statement_list RBRACE
369 | PRINT print_expression_list
375 alloc_macro : /* empty */
377 $$ = cs(str_table[macro_char]);
379 /* Do not use [, \ and ] */
380 if (macro_char == '[')
383 else if (macro_char == 'a')
385 else if (macro_char == ARRAY_CHAR)
387 else if (macro_char == 255)
388 fatal("program too big");
389 if (breaksp == BREAKSTACK_SZ)
390 fatal("nesting too deep");
391 breakstack[breaksp++] = nesting++;
395 pop_nesting : /* empty */
401 function : function_header opt_parameter_list RPAR opt_newline
402 LBRACE NEWLINE opt_auto_define_list
403 statement_list RBRACE
405 int n = node(prologue, $8, epilogue,
406 cs("0"), numnode(nesting),
409 reset_macro_char = macro_char;
415 function_header : DEFINE LETTER LPAR
417 $$ = function_node($2);
423 breakstack[breaksp] = 0;
427 opt_newline : /* empty */
437 parameter_list : LETTER
439 add_par(letter_node($1));
442 | LETTER LBRACKET RBRACKET
444 add_par(array_node($1));
447 | parameter_list COMMA LETTER
449 add_par(letter_node($3));
452 | parameter_list COMMA LETTER LBRACKET RBRACKET
454 add_par(array_node($3));
463 | AUTO define_list NEWLINE
464 | AUTO define_list SEMICOLON
470 add_local(letter_node($1));
473 | LETTER LBRACKET RBRACKET
475 add_local(array_node($1));
478 | define_list COMMA LETTER
480 add_local(letter_node($3));
483 | define_list COMMA LETTER LBRACKET RBRACKET
485 add_local(array_node($3));
500 argument_list : expression
501 | argument_list COMMA expression
503 $$ = node($1, $3, END_NODE);
505 | argument_list COMMA LETTER LBRACKET RBRACKET
507 $$ = node($1, cs("l"), array_node($3),
513 opt_relational_expression
518 | relational_expression
521 relational_expression
522 : expression EQUALS expression
524 $$ = node($1, $3, cs("="), END_NODE);
526 | expression UNEQUALS expression
528 $$ = node($1, $3, cs("!="), END_NODE);
530 | expression LESS expression
532 $$ = node($1, $3, cs(">"), END_NODE);
534 | expression LESS_EQ expression
536 $$ = node($1, $3, cs("!<"), END_NODE);
538 | expression GREATER expression
540 $$ = node($1, $3, cs("<"), END_NODE);
542 | expression GREATER_EQ expression
544 $$ = node($1, $3, cs("!>"), END_NODE);
548 $$ = node($1, cs(" 0!="), END_NODE);
556 $$ = node(cs("0"), epilogue,
557 numnode(nesting), cs("Q"), END_NODE);
561 $$ = node($1, epilogue,
562 numnode(nesting), cs("Q"), END_NODE);
566 $$ = node(cs("0"), epilogue,
567 numnode(nesting), cs("Q"), END_NODE);
572 opt_expression : /* empty */
579 expression : named_expression
581 $$ = node($1.load, END_NODE);
584 $$ = node(cs("l."), END_NODE);
588 $$ = node(cs(" "), as($1), END_NODE);
590 | LPAR expression RPAR
594 | LETTER LPAR opt_argument_list RPAR
596 $$ = node($3, cs("l"),
597 function_node($1), cs("x"),
601 | MINUS expression %prec UMINUS
603 $$ = node(cs(" 0"), $2, cs("-"),
606 | expression PLUS expression
608 $$ = node($1, $3, cs("+"), END_NODE);
610 | expression MINUS expression
612 $$ = node($1, $3, cs("-"), END_NODE);
614 | expression MULTIPLY expression
616 $$ = node($1, $3, cs("*"), END_NODE);
618 | expression DIVIDE expression
620 $$ = node($1, $3, cs("/"), END_NODE);
622 | expression REMAINDER expression
624 $$ = node($1, $3, cs("%"), END_NODE);
626 | expression EXPONENT expression
628 $$ = node($1, $3, cs("^"), END_NODE);
630 | INCR named_expression
632 $$ = node($2.load, cs("1+d"), $2.store,
635 | DECR named_expression
637 $$ = node($2.load, cs("1-d"),
640 | named_expression INCR
642 $$ = node($1.load, cs("d1+"),
645 | named_expression DECR
647 $$ = node($1.load, cs("d1-"),
650 | named_expression ASSIGN_OP expression
653 $$ = node($3, cs($2), cs("d"), $1.store,
656 $$ = node($1.load, $3, cs($2), cs("d"),
659 | LENGTH LPAR expression RPAR
661 $$ = node($3, cs("Z"), END_NODE);
663 | SQRT LPAR expression RPAR
665 $$ = node($3, cs("v"), END_NODE);
667 | SCALE LPAR expression RPAR
669 $$ = node($3, cs("X"), END_NODE);
671 | BOOL_NOT expression
673 $$ = node($2, cs("N"), END_NODE);
675 | expression BOOL_AND alloc_macro pop_nesting expression
677 ssize_t n = node(cs("R"), $5, END_NODE);
679 $$ = node($1, cs("d0!="), $3, END_NODE);
681 | expression BOOL_OR alloc_macro pop_nesting expression
683 ssize_t n = node(cs("R"), $5, END_NODE);
685 $$ = node($1, cs("d0="), $3, END_NODE);
687 | expression EQUALS expression
689 $$ = node($1, $3, cs("G"), END_NODE);
691 | expression UNEQUALS expression
693 $$ = node($1, $3, cs("GN"), END_NODE);
695 | expression LESS expression
697 $$ = node($3, $1, cs("("), END_NODE);
699 | expression LESS_EQ expression
701 $$ = node($3, $1, cs("{"), END_NODE);
703 | expression GREATER expression
705 $$ = node($1, $3, cs("("), END_NODE);
707 | expression GREATER_EQ expression
709 $$ = node($1, $3, cs("{"), END_NODE);
716 $$.load = node(cs("l"), letter_node($1),
718 $$.store = node(cs("s"), letter_node($1),
722 | LETTER LBRACKET expression RBRACKET
724 $$.load = node($3, cs(";"),
725 array_node($1), END_NODE);
726 $$.store = node($3, cs(":"),
727 array_node($1), END_NODE);
747 print_expression_list
749 | print_expression_list COMMA print_expression
751 $$ = node($1, $3, END_NODE);
757 $$ = node($1, cs("ds.n"), END_NODE);
761 char *p = escape($1);
762 $$ = node(cs("["), as(p), cs("]n"), END_NODE);
774 if (current == instr_sz) {
775 newsize = instr_sz * 2 + 1;
776 p = realloc(instructions, newsize * sizeof(*p));
791 instructions[current].index = CONST_STRING;
792 instructions[current].u.cstr = str;
801 instructions[current].index = ALLOC_STRING;
802 instructions[current].u.astr = strdup(str);
803 if (instructions[current].u.astr == NULL)
809 node(ssize_t arg, ...)
818 instructions[current++].index = arg;
821 arg = va_arg(ap, ssize_t);
823 instructions[current++].index = arg;
824 } while (arg != END_NODE);
834 if (instructions[i].index >= 0)
835 while (instructions[i].index != END_NODE)
836 emit(instructions[i++].index);
838 fputs(instructions[i].u.cstr, stdout);
842 emit_macro(int nodeidx, ssize_t code)
847 printf("]s%s\n", instructions[nodeidx].u.cstr);
856 for (i = 0; i < current; i++)
857 if (instructions[i].index == ALLOC_STRING)
858 free(instructions[i].u.astr);
868 p = str_table['0' + num];
870 p = str_table['A' - 10 + num];
872 errx(1, "internal error: break num > 15");
873 return (node(cs(" "), cs(p), END_NODE));
878 lookup(char * str, size_t len, char type)
884 /* The scanner allocated an extra byte already */
885 if (str[len-1] != type) {
890 found = hsearch(entry, FIND);
892 if (var_count == MAX_VARIABLES)
893 errx(1, "too many variables");
899 p[1] = ENCODE(num / VAR_BASE + 1);
900 p[2] = ENCODE(num % VAR_BASE + 1);
903 entry.data = (char *)p;
904 entry.key = strdup(str);
905 if (entry.key == NULL)
907 found = hsearch(entry, ENTER);
911 return (cs(found->data));
915 letter_node(char *str)
920 if (len == 1 && str[0] != '_')
921 return (cs(str_table[(int)str[0]]));
923 return (lookup(str, len, 'L'));
927 array_node(char *str)
932 if (len == 1 && str[0] != '_')
933 return (cs(str_table[(int)str[0] - 'a' + ARRAY_CHAR]));
935 return (lookup(str, len, 'A'));
939 function_node(char *str)
944 if (len == 1 && str[0] != '_')
945 return (cs(str_table[(int)str[0] - 'a' + FUNC_CHAR]));
947 return (lookup(str, len, 'F'));
954 prologue = node(cs("S"), n, prologue, END_NODE);
955 epilogue = node(epilogue, cs("L"), n, cs("s."), END_NODE);
962 prologue = node(cs("0S"), n, prologue, END_NODE);
963 epilogue = node(epilogue, cs("L"), n, cs("s."), END_NODE);
967 yyerror(const char *s)
972 if (yyin != NULL && feof(yyin))
973 n = asprintf(&str, "%s: %s:%d: %s: unexpected EOF",
974 __progname, filename, lineno, s);
975 else if (isspace(yytext[0]) || !isprint(yytext[0]))
977 "%s: %s:%d: %s: ascii char 0x%02x unexpected",
978 __progname, filename, lineno, s, yytext[0]);
980 n = asprintf(&str, "%s: %s:%d: %s: %s unexpected",
981 __progname, filename, lineno, s, yytext);
986 for (p = str; *p != '\0'; p++) {
987 if (*p == '[' || *p == ']' || *p =='\\')
991 fputs("]pc\n", stdout);
999 errx(1, "%s:%d: %s", filename, lineno, s);
1003 warning(const char *s)
1006 warnx("%s:%d: %s", filename, lineno, s);
1014 for (i = 0; i < UCHAR_MAX; i++) {
1015 str_table[i][0] = i;
1016 str_table[i][1] = '\0';
1018 if (hcreate(1 << 16) == 0)
1027 fprintf(stderr, "usage: %s [-chlqv] [-e expression] [file ...]\n",
1033 escape(const char *str)
1037 ret = malloc(strlen(str) + 1);
1042 while (*str != '\0') {
1044 * We get _escaped_ strings here. Single backslashes are
1045 * already converted to double backslashes
1048 if (*++str == '\\') {
1097 pid = waitpid(dc, &status, WUNTRACED);
1103 if (WIFEXITED(status) || WIFSIGNALED(status))
1119 main(int argc, char *argv[])
1128 sargv = malloc(argc * sizeof(char *));
1132 if ((cmdexpr = strdup("")) == NULL)
1134 /* The d debug option is 4.4 BSD bc(1) compatible */
1135 while ((ch = getopt_long(argc, argv, "cde:hlqv",
1136 long_options, NULL)) != -1) {
1144 if (asprintf(&cmdexpr, "%s%s\n", cmdexpr, optarg) == -1)
1152 sargv[sargc++] = _PATH_LIBB;
1155 /* compatibility option */
1158 fprintf(stderr, "%s (BSD bc) %s\n", __progname, BC_VER);
1169 interactive = isatty(STDIN_FILENO);
1170 for (i = 0; i < argc; i++)
1171 sargv[sargc++] = argv[i];
1175 err(1, "cannot create pipe");
1178 err(1, "cannot fork");
1180 signal(SIGCHLD, sigchld);
1181 close(STDOUT_FILENO);
1186 close(STDIN_FILENO);
1190 execl(_PATH_DC, "dc", "-x", (char *)NULL);
1191 err(1, "cannot find dc");
1195 el = el_init("bc", stdin, stderr, stderr);
1196 hist = history_init();
1197 history(hist, &he, H_SETSIZE, 100);
1198 el_set(el, EL_HIST, history, hist);
1199 el_set(el, EL_EDITOR, "emacs");
1200 el_set(el, EL_SIGNAL, 1);
1201 el_set(el, EL_PROMPT, dummy_prompt);
1202 el_source(el, NULL);