3 * $OpenBSD: bc.y,v 1.25 2005/03/17 16:59:31 otto Exp $
4 * $DragonFly: src/usr.bin/bc/bc.y,v 1.2 2005/04/21 18:50:22 swildner 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)
70 static void grow(void);
71 static ssize_t cs(const char *);
72 static ssize_t as(const char *);
73 static ssize_t node(ssize_t, ...);
74 static void emit(ssize_t);
75 static void emit_macro(int, ssize_t);
76 static void free_tree(void);
77 static ssize_t numnode(int);
78 static ssize_t lookup(char *, size_t, char);
79 static ssize_t letter_node(char *);
80 static ssize_t array_node(char *);
81 static ssize_t function_node(char *);
83 static void add_par(ssize_t);
84 static void add_local(ssize_t);
85 static void warning(const char *);
86 static void init(void);
87 static __dead2 void usage(void);
88 static char *escape(const char *);
90 static size_t instr_sz = 0;
91 static struct tree *instructions = NULL;
92 static ssize_t current = 0;
93 static int macro_char = '0';
94 static int reset_macro_char = '0';
95 static int nesting = 0;
96 static int breakstack[16];
97 static int breaksp = 0;
98 static ssize_t prologue;
99 static ssize_t epilogue;
100 static bool st_has_continue;
101 static char str_table[UCHAR_MAX][2];
102 static bool do_fork = true;
103 static u_short var_count;
105 extern char *__progname;
107 #define BREAKSTACK_SZ (sizeof(breakstack)/sizeof(breakstack[0]))
109 /* These values are 4.4BSD bc compatible */
110 #define FUNC_CHAR 0x01
111 #define ARRAY_CHAR 0xa1
113 /* Skip '\0', [, \ and ] */
114 #define ENCODE(c) ((c) < '[' ? (c) : (c) + 3);
115 #define VAR_BASE (256-4)
116 #define MAX_VARIABLES (VAR_BASE * VAR_BASE)
124 struct lvalue lvalue;
129 %token COMMA SEMICOLON LPAR RPAR LBRACE RBRACE LBRACKET RBRACKET DOT
132 %token <str> NUMBER STRING
133 %token DEFINE BREAK QUIT LENGTH
134 %token RETURN FOR IF WHILE SQRT
135 %token SCALE IBASE OBASE AUTO
136 %token CONTINUE ELSE PRINT
141 %nonassoc EQUALS LESS_EQ GREATER_EQ UNEQUALS LESS GREATER
142 %right <str> ASSIGN_OP
144 %left MULTIPLY DIVIDE REMAINDER
149 %type <lvalue> named_expression
150 %type <node> argument_list
151 %type <node> alloc_macro
152 %type <node> expression
153 %type <node> function
154 %type <node> function_header
155 %type <node> input_item
156 %type <node> opt_argument_list
157 %type <node> opt_expression
158 %type <node> opt_relational_expression
159 %type <node> opt_statement
160 %type <node> print_expression
161 %type <node> print_expression_list
162 %type <node> relational_expression
163 %type <node> return_expression
164 %type <node> semicolon_list
165 %type <node> statement
166 %type <node> statement_list
170 program : /* empty */
174 input_item : semicolon_list NEWLINE
177 macro_char = reset_macro_char;
180 st_has_continue = false;
186 st_has_continue = false;
198 semicolon_list : /* empty */
203 | semicolon_list SEMICOLON statement
205 $$ = node($1, $3, END_NODE);
207 | semicolon_list SEMICOLON
210 statement_list : /* empty */
215 | statement_list NEWLINE
216 | statement_list NEWLINE statement
218 $$ = node($1, $3, END_NODE);
220 | statement_list SEMICOLON
221 | statement_list SEMICOLON statement
223 $$ = node($1, $3, END_NODE);
228 opt_statement : /* empty */
235 statement : expression
237 $$ = node($1, cs("ps."), END_NODE);
239 | named_expression ASSIGN_OP expression
242 $$ = node($3, cs($2), $1.store,
245 $$ = node($1.load, $3, cs($2), $1.store,
250 $$ = node(cs("["), as($1),
256 warning("break not in for or while");
261 breakstack[breaksp-1]),
268 warning("continue not in for or while");
271 st_has_continue = true;
272 $$ = node(numnode(nesting -
273 breakstack[breaksp-1] - 1),
283 | RETURN return_expression
286 warning("return must be in a function");
291 | FOR LPAR alloc_macro opt_expression SEMICOLON
292 opt_relational_expression SEMICOLON
293 opt_expression RPAR opt_statement pop_nesting
298 n = node($10, cs("M"), $8, cs("s."),
301 n = node($10, $8, cs("s."), $6, $3,
305 $$ = node($4, cs("s."), $6, $3, cs(" "),
308 | IF LPAR alloc_macro pop_nesting relational_expression RPAR
312 $$ = node($5, $3, cs(" "), END_NODE);
314 | IF LPAR alloc_macro pop_nesting relational_expression RPAR
315 opt_statement ELSE alloc_macro pop_nesting opt_statement
319 $$ = node($5, $3, cs("e"), $9, cs(" "),
322 | WHILE LPAR alloc_macro relational_expression RPAR
323 opt_statement pop_nesting
328 n = node($6, cs("M"), $4, $3, END_NODE);
330 n = node($6, $4, $3, END_NODE);
332 $$ = node($4, $3, cs(" "), END_NODE);
334 | LBRACE statement_list RBRACE
338 | PRINT print_expression_list
344 alloc_macro : /* empty */
346 $$ = cs(str_table[macro_char]);
348 /* Do not use [, \ and ] */
349 if (macro_char == '[')
352 else if (macro_char == 'a')
354 else if (macro_char == ARRAY_CHAR)
356 else if (macro_char == 255)
357 fatal("program too big");
358 if (breaksp == BREAKSTACK_SZ)
359 fatal("nesting too deep");
360 breakstack[breaksp++] = nesting++;
364 pop_nesting : /* empty */
370 function : function_header opt_parameter_list RPAR opt_newline
371 LBRACE NEWLINE opt_auto_define_list
372 statement_list RBRACE
374 int n = node(prologue, $8, epilogue,
375 cs("0"), numnode(nesting),
378 reset_macro_char = macro_char;
384 function_header : DEFINE LETTER LPAR
386 $$ = function_node($2);
392 breakstack[breaksp] = 0;
396 opt_newline : /* empty */
406 parameter_list : LETTER
408 add_par(letter_node($1));
411 | LETTER LBRACKET RBRACKET
413 add_par(array_node($1));
416 | parameter_list COMMA LETTER
418 add_par(letter_node($3));
421 | parameter_list COMMA LETTER LBRACKET RBRACKET
423 add_par(array_node($3));
432 | AUTO define_list NEWLINE
433 | AUTO define_list SEMICOLON
439 add_local(letter_node($1));
442 | LETTER LBRACKET RBRACKET
444 add_local(array_node($1));
447 | define_list COMMA LETTER
449 add_local(letter_node($3));
452 | define_list COMMA LETTER LBRACKET RBRACKET
454 add_local(array_node($3));
469 argument_list : expression
470 | argument_list COMMA expression
472 $$ = node($1, $3, END_NODE);
474 | argument_list COMMA LETTER LBRACKET RBRACKET
476 $$ = node($1, cs("l"), array_node($3),
482 opt_relational_expression
487 | relational_expression
490 relational_expression
491 : expression EQUALS expression
493 $$ = node($1, $3, cs("="), END_NODE);
495 | expression UNEQUALS expression
497 $$ = node($1, $3, cs("!="), END_NODE);
499 | expression LESS expression
501 $$ = node($1, $3, cs(">"), END_NODE);
503 | expression LESS_EQ expression
505 $$ = node($1, $3, cs("!<"), END_NODE);
507 | expression GREATER expression
509 $$ = node($1, $3, cs("<"), END_NODE);
511 | expression GREATER_EQ expression
513 $$ = node($1, $3, cs("!>"), END_NODE);
517 $$ = node($1, cs(" 0!="), END_NODE);
525 $$ = node(cs("0"), epilogue,
526 numnode(nesting), cs("Q"), END_NODE);
530 $$ = node($1, epilogue,
531 numnode(nesting), cs("Q"), END_NODE);
535 $$ = node(cs("0"), epilogue,
536 numnode(nesting), cs("Q"), END_NODE);
541 opt_expression : /* empty */
548 expression : named_expression
550 $$ = node($1.load, END_NODE);
553 $$ = node(cs("l."), END_NODE);
557 $$ = node(cs(" "), as($1), END_NODE);
559 | LPAR expression RPAR
563 | LETTER LPAR opt_argument_list RPAR
565 $$ = node($3, cs("l"),
566 function_node($1), cs("x"),
570 | MINUS expression %prec UMINUS
572 $$ = node(cs(" 0"), $2, cs("-"),
575 | expression PLUS expression
577 $$ = node($1, $3, cs("+"), END_NODE);
579 | expression MINUS expression
581 $$ = node($1, $3, cs("-"), END_NODE);
583 | expression MULTIPLY expression
585 $$ = node($1, $3, cs("*"), END_NODE);
587 | expression DIVIDE expression
589 $$ = node($1, $3, cs("/"), END_NODE);
591 | expression REMAINDER expression
593 $$ = node($1, $3, cs("%"), END_NODE);
595 | expression EXPONENT expression
597 $$ = node($1, $3, cs("^"), END_NODE);
599 | INCR named_expression
601 $$ = node($2.load, cs("1+d"), $2.store,
604 | DECR named_expression
606 $$ = node($2.load, cs("1-d"),
609 | named_expression INCR
611 $$ = node($1.load, cs("d1+"),
614 | named_expression DECR
616 $$ = node($1.load, cs("d1-"),
619 | named_expression ASSIGN_OP expression
622 $$ = node($3, cs($2), cs("d"), $1.store,
625 $$ = node($1.load, $3, cs($2), cs("d"),
628 | LENGTH LPAR expression RPAR
630 $$ = node($3, cs("Z"), END_NODE);
632 | SQRT LPAR expression RPAR
634 $$ = node($3, cs("v"), END_NODE);
636 | SCALE LPAR expression RPAR
638 $$ = node($3, cs("X"), END_NODE);
640 | BOOL_NOT expression
642 $$ = node($2, cs("N"), END_NODE);
644 | expression BOOL_AND 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 BOOL_OR alloc_macro pop_nesting expression
652 ssize_t n = node(cs("R"), $5, END_NODE);
654 $$ = node($1, cs("d0="), $3, END_NODE);
656 | expression EQUALS expression
658 $$ = node($1, $3, cs("G"), END_NODE);
660 | expression UNEQUALS expression
662 $$ = node($1, $3, cs("GN"), END_NODE);
664 | expression LESS expression
666 $$ = node($3, $1, cs("("), END_NODE);
668 | expression LESS_EQ expression
670 $$ = node($3, $1, cs("{"), END_NODE);
672 | expression GREATER expression
674 $$ = node($1, $3, cs("("), END_NODE);
676 | expression GREATER_EQ expression
678 $$ = node($1, $3, cs("{"), END_NODE);
685 $$.load = node(cs("l"), letter_node($1),
687 $$.store = node(cs("s"), letter_node($1),
691 | LETTER LBRACKET expression RBRACKET
693 $$.load = node($3, cs(";"),
694 array_node($1), END_NODE);
695 $$.store = node($3, cs(":"),
696 array_node($1), END_NODE);
716 print_expression_list
718 | print_expression_list COMMA print_expression
720 $$ = node($1, $3, END_NODE);
726 $$ = node($1, cs("ds.n"), END_NODE);
730 char *p = escape($1);
731 $$ = node(cs("["), as(p), cs("]n"), END_NODE);
743 if (current == instr_sz) {
744 newsize = instr_sz * 2 + 1;
745 p = realloc(instructions, newsize * sizeof(*p));
759 instructions[current].index = CONST_STRING;
760 instructions[current].u.cstr = str;
768 instructions[current].index = ALLOC_STRING;
769 instructions[current].u.astr = strdup(str);
770 if (instructions[current].u.astr == NULL)
776 node(ssize_t arg, ...)
785 instructions[current++].index = arg;
788 arg = va_arg(ap, ssize_t);
790 instructions[current++].index = arg;
791 } while (arg != END_NODE);
800 if (instructions[i].index >= 0)
801 while (instructions[i].index != END_NODE)
802 emit(instructions[i++].index);
804 fputs(instructions[i].u.cstr, stdout);
808 emit_macro(int node, ssize_t code)
812 printf("]s%s\n", instructions[node].u.cstr);
821 for (i = 0; i < current; i++)
822 if (instructions[i].index == ALLOC_STRING)
823 free(instructions[i].u.astr);
833 p = str_table['0' + num];
835 p = str_table['A' - 10 + num];
837 errx(1, "internal error: break num > 15");
838 return node(cs(" "), cs(p), END_NODE);
843 lookup(char * str, size_t len, char type)
849 /* The scanner allocated an extra byte already */
850 if (str[len-1] != type) {
855 found = hsearch(entry, FIND);
857 if (var_count == MAX_VARIABLES)
858 errx(1, "too many variables");
864 p[1] = ENCODE(num / VAR_BASE + 1);
865 p[2] = ENCODE(num % VAR_BASE + 1);
868 entry.data = (char *)p;
869 entry.key = strdup(str);
870 if (entry.key == NULL)
872 found = hsearch(entry, ENTER);
876 return cs(found->data);
880 letter_node(char *str)
885 if (len == 1 && str[0] != '_')
886 return cs(str_table[(int)str[0]]);
888 return lookup(str, len, 'L');
892 array_node(char *str)
897 if (len == 1 && str[0] != '_')
898 return cs(str_table[(int)str[0] - 'a' + ARRAY_CHAR]);
900 return lookup(str, len, 'A');
904 function_node(char *str)
909 if (len == 1 && str[0] != '_')
910 return cs(str_table[(int)str[0] - 'a' + FUNC_CHAR]);
912 return lookup(str, len, 'F');
918 prologue = node(cs("S"), n, prologue, END_NODE);
919 epilogue = node(epilogue, cs("L"), n, cs("s."), END_NODE);
925 prologue = node(cs("0S"), n, prologue, END_NODE);
926 epilogue = node(epilogue, cs("L"), n, cs("s."), END_NODE);
935 asprintf(&str, "%s: %s:%d: %s: unexpected EOF",
936 __progname, filename, lineno, s);
937 else if (isspace(yytext[0]) || !isprint(yytext[0]))
938 asprintf(&str, "%s: %s:%d: %s: ascii char 0x%02x unexpected",
939 __progname, filename, lineno, s, yytext[0]);
941 asprintf(&str, "%s: %s:%d: %s: %s unexpected",
942 __progname, filename, lineno, s, yytext);
947 for (p = str; *p != '\0'; p++) {
948 if (*p == '[' || *p == ']' || *p =='\\')
952 fputs("]pc\n", stdout);
959 errx(1, "%s:%d: %s", filename, lineno, s);
963 warning(const char *s)
965 warnx("%s:%d: %s", filename, lineno, s);
973 for (i = 0; i < UCHAR_MAX; i++) {
975 str_table[i][1] = '\0';
977 if (hcreate(1 << 16) == 0)
985 fprintf(stderr, "%s: usage: [-cl] [-e expression] [file ...]\n",
991 escape(const char *str)
995 ret = malloc(strlen(str) + 1);
1000 while (*str != '\0') {
1002 * We get _escaped_ strings here. Single backslashes are
1003 * already converted to double backslashes
1006 if (*++str == '\\') {
1046 main(int argc, char *argv[])
1055 sargv = malloc(argc * sizeof(char *));
1059 if ((cmdexpr = strdup("")) == NULL)
1061 /* The d debug option is 4.4 BSD bc(1) compatible */
1062 while ((ch = getopt(argc, argv, "cde:l")) != -1) {
1070 if (asprintf(&cmdexpr, "%s%s\n", cmdexpr, optarg) == -1)
1075 sargv[sargc++] = _PATH_LIBB;
1085 for (i = 0; i < argc; i++)
1086 sargv[sargc++] = argv[i];
1090 err(1, "cannot create pipe");
1093 err(1, "cannot fork");
1094 else if (ret == 0) {
1095 close(STDOUT_FILENO);
1100 close(STDIN_FILENO);
1104 execl(_PATH_DC, "dc", "-x", (char *)NULL);
1105 err(1, "cannot find dc");
1108 signal(SIGINT, abort_line);