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 20: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
);