3 * $OpenBSD: bc.y,v 1.32 2006/05/18 05:49:53 otto Exp $
4 * $DragonFly: src/usr.bin/bc/bc.y,v 1.3 2007/09/01 18:42:08 pavalos 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.
36 #include <sys/types.h>
51 #include "pathnames.h"
53 #define END_NODE ((ssize_t) -1)
54 #define CONST_STRING ((ssize_t) -2)
55 #define ALLOC_STRING ((ssize_t) -3)
74 static void grow(void);
75 static ssize_t cs(const char *);
76 static ssize_t as(const char *);
77 static ssize_t node(ssize_t, ...);
78 static void emit(ssize_t);
79 static void emit_macro(int, ssize_t);
80 static void free_tree(void);
81 static ssize_t numnode(int);
82 static ssize_t lookup(char *, size_t, char);
83 static ssize_t letter_node(char *);
84 static ssize_t array_node(char *);
85 static ssize_t function_node(char *);
87 static void add_par(ssize_t);
88 static void add_local(ssize_t);
89 static void warning(const char *);
90 static void init(void);
91 static __dead2 void usage(void);
92 static char *escape(const char *);
94 static ssize_t instr_sz = 0;
95 static struct tree *instructions = NULL;
96 static ssize_t current = 0;
97 static int macro_char = '0';
98 static int reset_macro_char = '0';
99 static int nesting = 0;
100 static int breakstack[16];
101 static int breaksp = 0;
102 static ssize_t prologue;
103 static ssize_t epilogue;
104 static bool st_has_continue;
105 static char str_table[UCHAR_MAX][2];
106 static bool do_fork = true;
107 static u_short var_count;
110 extern char *__progname;
112 #define BREAKSTACK_SZ (sizeof(breakstack)/sizeof(breakstack[0]))
114 /* These values are 4.4BSD bc compatible */
115 #define FUNC_CHAR 0x01
116 #define ARRAY_CHAR 0xa1
118 /* Skip '\0', [, \ and ] */
119 #define ENCODE(c) ((c) < '[' ? (c) : (c) + 3);
120 #define VAR_BASE (256-4)
121 #define MAX_VARIABLES (VAR_BASE * VAR_BASE)
129 struct lvalue lvalue;
134 %token COMMA SEMICOLON LPAR RPAR LBRACE RBRACE LBRACKET RBRACKET DOT
137 %token <str> NUMBER STRING
138 %token DEFINE BREAK QUIT LENGTH
139 %token RETURN FOR IF WHILE SQRT
140 %token SCALE IBASE OBASE AUTO
141 %token CONTINUE ELSE PRINT
146 %nonassoc EQUALS LESS_EQ GREATER_EQ UNEQUALS LESS GREATER
147 %right <str> ASSIGN_OP
149 %left MULTIPLY DIVIDE REMAINDER
154 %type <lvalue> named_expression
155 %type <node> argument_list
156 %type <node> alloc_macro
157 %type <node> expression
158 %type <node> function
159 %type <node> function_header
160 %type <node> input_item
161 %type <node> opt_argument_list
162 %type <node> opt_expression
163 %type <node> opt_relational_expression
164 %type <node> opt_statement
165 %type <node> print_expression
166 %type <node> print_expression_list
167 %type <node> relational_expression
168 %type <node> return_expression
169 %type <node> semicolon_list
170 %type <node> statement
171 %type <node> statement_list
175 program : /* empty */
179 input_item : semicolon_list NEWLINE
182 macro_char = reset_macro_char;
185 st_has_continue = false;
191 st_has_continue = false;
203 semicolon_list : /* empty */
208 | semicolon_list SEMICOLON statement
210 $$ = node($1, $3, END_NODE);
212 | semicolon_list SEMICOLON
215 statement_list : /* empty */
220 | statement_list NEWLINE
221 | statement_list NEWLINE statement
223 $$ = node($1, $3, END_NODE);
225 | statement_list SEMICOLON
226 | statement_list SEMICOLON statement
228 $$ = node($1, $3, END_NODE);
233 opt_statement : /* empty */
240 statement : expression
242 $$ = node($1, cs("ps."), END_NODE);
244 | named_expression ASSIGN_OP expression
247 $$ = node($3, cs($2), $1.store,
250 $$ = node($1.load, $3, cs($2), $1.store,
255 $$ = node(cs("["), as($1),
261 warning("break not in for or while");
266 breakstack[breaksp-1]),
273 warning("continue not in for or while");
276 st_has_continue = true;
277 $$ = node(numnode(nesting -
278 breakstack[breaksp-1] - 1),
289 sigprocmask(SIG_BLOCK, NULL, &mask);
294 | RETURN return_expression
297 warning("return must be in a function");
302 | FOR LPAR alloc_macro opt_expression SEMICOLON
303 opt_relational_expression SEMICOLON
304 opt_expression RPAR opt_statement pop_nesting
309 n = node($10, cs("M"), $8, cs("s."),
312 n = node($10, $8, cs("s."), $6, $3,
316 $$ = node($4, cs("s."), $6, $3, cs(" "),
319 | IF LPAR alloc_macro pop_nesting relational_expression RPAR
323 $$ = node($5, $3, cs(" "), END_NODE);
325 | IF LPAR alloc_macro pop_nesting relational_expression RPAR
326 opt_statement ELSE alloc_macro pop_nesting opt_statement
330 $$ = node($5, $3, cs("e"), $9, cs(" "),
333 | WHILE LPAR alloc_macro relational_expression RPAR
334 opt_statement pop_nesting
339 n = node($6, cs("M"), $4, $3, END_NODE);
341 n = node($6, $4, $3, END_NODE);
343 $$ = node($4, $3, cs(" "), END_NODE);
345 | LBRACE statement_list RBRACE
349 | PRINT print_expression_list
355 alloc_macro : /* empty */
357 $$ = cs(str_table[macro_char]);
359 /* Do not use [, \ and ] */
360 if (macro_char == '[')
363 else if (macro_char == 'a')
365 else if (macro_char == ARRAY_CHAR)
367 else if (macro_char == 255)
368 fatal("program too big");
369 if (breaksp == BREAKSTACK_SZ)
370 fatal("nesting too deep");
371 breakstack[breaksp++] = nesting++;
375 pop_nesting : /* empty */
381 function : function_header opt_parameter_list RPAR opt_newline
382 LBRACE NEWLINE opt_auto_define_list
383 statement_list RBRACE
385 int n = node(prologue, $8, epilogue,
386 cs("0"), numnode(nesting),
389 reset_macro_char = macro_char;
395 function_header : DEFINE LETTER LPAR
397 $$ = function_node($2);
403 breakstack[breaksp] = 0;
407 opt_newline : /* empty */
417 parameter_list : LETTER
419 add_par(letter_node($1));
422 | LETTER LBRACKET RBRACKET
424 add_par(array_node($1));
427 | parameter_list COMMA LETTER
429 add_par(letter_node($3));
432 | parameter_list COMMA LETTER LBRACKET RBRACKET
434 add_par(array_node($3));
443 | AUTO define_list NEWLINE
444 | AUTO define_list SEMICOLON
450 add_local(letter_node($1));
453 | LETTER LBRACKET RBRACKET
455 add_local(array_node($1));
458 | define_list COMMA LETTER
460 add_local(letter_node($3));
463 | define_list COMMA LETTER LBRACKET RBRACKET
465 add_local(array_node($3));
480 argument_list : expression
481 | argument_list COMMA expression
483 $$ = node($1, $3, END_NODE);
485 | argument_list COMMA LETTER LBRACKET RBRACKET
487 $$ = node($1, cs("l"), array_node($3),
493 opt_relational_expression
498 | relational_expression
501 relational_expression
502 : expression EQUALS expression
504 $$ = node($1, $3, cs("="), END_NODE);
506 | expression UNEQUALS expression
508 $$ = node($1, $3, cs("!="), END_NODE);
510 | expression LESS expression
512 $$ = node($1, $3, cs(">"), END_NODE);
514 | expression LESS_EQ expression
516 $$ = node($1, $3, cs("!<"), END_NODE);
518 | expression GREATER expression
520 $$ = node($1, $3, cs("<"), END_NODE);
522 | expression GREATER_EQ expression
524 $$ = node($1, $3, cs("!>"), END_NODE);
528 $$ = node($1, cs(" 0!="), END_NODE);
536 $$ = node(cs("0"), epilogue,
537 numnode(nesting), cs("Q"), END_NODE);
541 $$ = node($1, epilogue,
542 numnode(nesting), cs("Q"), END_NODE);
546 $$ = node(cs("0"), epilogue,
547 numnode(nesting), cs("Q"), END_NODE);
552 opt_expression : /* empty */
559 expression : named_expression
561 $$ = node($1.load, END_NODE);
564 $$ = node(cs("l."), END_NODE);
568 $$ = node(cs(" "), as($1), END_NODE);
570 | LPAR expression RPAR
574 | LETTER LPAR opt_argument_list RPAR
576 $$ = node($3, cs("l"),
577 function_node($1), cs("x"),
581 | MINUS expression %prec UMINUS
583 $$ = node(cs(" 0"), $2, cs("-"),
586 | expression PLUS expression
588 $$ = node($1, $3, cs("+"), END_NODE);
590 | expression MINUS expression
592 $$ = node($1, $3, cs("-"), END_NODE);
594 | expression MULTIPLY expression
596 $$ = node($1, $3, cs("*"), END_NODE);
598 | expression DIVIDE expression
600 $$ = node($1, $3, cs("/"), END_NODE);
602 | expression REMAINDER expression
604 $$ = node($1, $3, cs("%"), END_NODE);
606 | expression EXPONENT expression
608 $$ = node($1, $3, cs("^"), END_NODE);
610 | INCR named_expression
612 $$ = node($2.load, cs("1+d"), $2.store,
615 | DECR named_expression
617 $$ = node($2.load, cs("1-d"),
620 | named_expression INCR
622 $$ = node($1.load, cs("d1+"),
625 | named_expression DECR
627 $$ = node($1.load, cs("d1-"),
630 | named_expression ASSIGN_OP expression
633 $$ = node($3, cs($2), cs("d"), $1.store,
636 $$ = node($1.load, $3, cs($2), cs("d"),
639 | LENGTH LPAR expression RPAR
641 $$ = node($3, cs("Z"), END_NODE);
643 | SQRT LPAR expression RPAR
645 $$ = node($3, cs("v"), END_NODE);
647 | SCALE LPAR expression RPAR
649 $$ = node($3, cs("X"), END_NODE);
651 | BOOL_NOT expression
653 $$ = node($2, cs("N"), END_NODE);
655 | expression BOOL_AND alloc_macro pop_nesting expression
657 ssize_t n = node(cs("R"), $5, END_NODE);
659 $$ = node($1, cs("d0!="), $3, END_NODE);
661 | expression BOOL_OR alloc_macro pop_nesting expression
663 ssize_t n = node(cs("R"), $5, END_NODE);
665 $$ = node($1, cs("d0="), $3, END_NODE);
667 | expression EQUALS expression
669 $$ = node($1, $3, cs("G"), END_NODE);
671 | expression UNEQUALS expression
673 $$ = node($1, $3, cs("GN"), END_NODE);
675 | expression LESS expression
677 $$ = node($3, $1, cs("("), END_NODE);
679 | expression LESS_EQ expression
681 $$ = node($3, $1, cs("{"), END_NODE);
683 | expression GREATER expression
685 $$ = node($1, $3, cs("("), END_NODE);
687 | expression GREATER_EQ expression
689 $$ = node($1, $3, cs("{"), END_NODE);
696 $$.load = node(cs("l"), letter_node($1),
698 $$.store = node(cs("s"), letter_node($1),
702 | LETTER LBRACKET expression RBRACKET
704 $$.load = node($3, cs(";"),
705 array_node($1), END_NODE);
706 $$.store = node($3, cs(":"),
707 array_node($1), END_NODE);
727 print_expression_list
729 | print_expression_list COMMA print_expression
731 $$ = node($1, $3, END_NODE);
737 $$ = node($1, cs("ds.n"), END_NODE);
741 char *p = escape($1);
742 $$ = node(cs("["), as(p), cs("]n"), END_NODE);
754 if (current == instr_sz) {
755 newsize = instr_sz * 2 + 1;
756 p = realloc(instructions, newsize * sizeof(*p));
770 instructions[current].index = CONST_STRING;
771 instructions[current].u.cstr = str;
779 instructions[current].index = ALLOC_STRING;
780 instructions[current].u.astr = strdup(str);
781 if (instructions[current].u.astr == NULL)
787 node(ssize_t arg, ...)
796 instructions[current++].index = arg;
799 arg = va_arg(ap, ssize_t);
801 instructions[current++].index = arg;
802 } while (arg != END_NODE);
811 if (instructions[i].index >= 0)
812 while (instructions[i].index != END_NODE)
813 emit(instructions[i++].index);
815 fputs(instructions[i].u.cstr, stdout);
819 emit_macro(int node, ssize_t code)
823 printf("]s%s\n", instructions[node].u.cstr);
832 for (i = 0; i < current; i++)
833 if (instructions[i].index == ALLOC_STRING)
834 free(instructions[i].u.astr);
844 p = str_table['0' + num];
846 p = str_table['A' - 10 + num];
848 errx(1, "internal error: break num > 15");
849 return node(cs(" "), cs(p), END_NODE);
854 lookup(char * str, size_t len, char type)
860 /* The scanner allocated an extra byte already */
861 if (str[len-1] != type) {
866 found = hsearch(entry, FIND);
868 if (var_count == MAX_VARIABLES)
869 errx(1, "too many variables");
875 p[1] = ENCODE(num / VAR_BASE + 1);
876 p[2] = ENCODE(num % VAR_BASE + 1);
879 entry.data = (char *)p;
880 entry.key = strdup(str);
881 if (entry.key == NULL)
883 found = hsearch(entry, ENTER);
887 return cs(found->data);
891 letter_node(char *str)
896 if (len == 1 && str[0] != '_')
897 return cs(str_table[(int)str[0]]);
899 return lookup(str, len, 'L');
903 array_node(char *str)
908 if (len == 1 && str[0] != '_')
909 return cs(str_table[(int)str[0] - 'a' + ARRAY_CHAR]);
911 return lookup(str, len, 'A');
915 function_node(char *str)
920 if (len == 1 && str[0] != '_')
921 return cs(str_table[(int)str[0] - 'a' + FUNC_CHAR]);
923 return lookup(str, len, 'F');
929 prologue = node(cs("S"), n, prologue, END_NODE);
930 epilogue = node(epilogue, cs("L"), n, cs("s."), END_NODE);
936 prologue = node(cs("0S"), n, prologue, END_NODE);
937 epilogue = node(epilogue, cs("L"), n, cs("s."), END_NODE);
946 if (yyin != NULL && feof(yyin))
947 n = asprintf(&str, "%s: %s:%d: %s: unexpected EOF",
948 __progname, filename, lineno, s);
949 else if (isspace(yytext[0]) || !isprint(yytext[0]))
951 "%s: %s:%d: %s: ascii char 0x%02x unexpected",
952 __progname, filename, lineno, s, yytext[0]);
954 n = asprintf(&str, "%s: %s:%d: %s: %s unexpected",
955 __progname, filename, lineno, s, yytext);
960 for (p = str; *p != '\0'; p++) {
961 if (*p == '[' || *p == ']' || *p =='\\')
965 fputs("]pc\n", stdout);
972 errx(1, "%s:%d: %s", filename, lineno, s);
976 warning(const char *s)
978 warnx("%s:%d: %s", filename, lineno, s);
986 for (i = 0; i < UCHAR_MAX; i++) {
988 str_table[i][1] = '\0';
990 if (hcreate(1 << 16) == 0)
998 fprintf(stderr, "usage: %s [-cl] [-e expression] [file ...]\n",
1004 escape(const char *str)
1008 ret = malloc(strlen(str) + 1);
1013 while (*str != '\0') {
1015 * We get _escaped_ strings here. Single backslashes are
1016 * already converted to double backslashes
1019 if (*++str == '\\') {
1066 pid = waitpid(dc, &status, WCONTINUED);
1072 if (WIFEXITED(status) || WIFSIGNALED(status))
1080 main(int argc, char *argv[])
1089 sargv = malloc(argc * sizeof(char *));
1093 if ((cmdexpr = strdup("")) == NULL)
1095 /* The d debug option is 4.4 BSD bc(1) compatible */
1096 while ((ch = getopt(argc, argv, "cde:l")) != -1) {
1104 if (asprintf(&cmdexpr, "%s%s\n", cmdexpr, optarg) == -1)
1109 sargv[sargc++] = _PATH_LIBB;
1119 interactive = isatty(STDIN_FILENO);
1120 for (i = 0; i < argc; i++)
1121 sargv[sargc++] = argv[i];
1125 err(1, "cannot create pipe");
1128 err(1, "cannot fork");
1130 signal(SIGCHLD, sigchld);
1131 close(STDOUT_FILENO);
1136 close(STDIN_FILENO);
1140 execl(_PATH_DC, "dc", "-x", (char *)NULL);
1141 err(1, "cannot find dc");