8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
* Copyright (c) 1997 Sun Microsystems, Inc.
* Copyright (c) 1998-2000 by Scriptics Corporation.
* Contributions from Don Porter, NIST, 2006. (not subject to US copyright)
*
* See the file "license.terms" for information on usage and redistribution of
* this file, and for a DISCLAIMER OF ALL WARRANTIES.
*
* RCS: @(#) $Id: tclCompExpr.c,v 1.75 2007/08/10 16:00:13 dgp Exp $
*/
#include "tclInt.h"
#include "tclCompile.h" /* CompileEnv */
/*
* Expression parsing takes place in the routine ParseExpr(). It takes a
|
|
|
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
* Copyright (c) 1997 Sun Microsystems, Inc.
* Copyright (c) 1998-2000 by Scriptics Corporation.
* Contributions from Don Porter, NIST, 2006. (not subject to US copyright)
*
* See the file "license.terms" for information on usage and redistribution of
* this file, and for a DISCLAIMER OF ALL WARRANTIES.
*
* RCS: @(#) $Id: tclCompExpr.c,v 1.76 2007/08/14 17:18:34 dgp Exp $
*/
#include "tclInt.h"
#include "tclCompile.h" /* CompileEnv */
/*
* Expression parsing takes place in the routine ParseExpr(). It takes a
|
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
|
int right; /* "Pointer" to the right operand. */
union {
int parent; /* "Pointer" to the parent operand. */
int prev; /* "Pointer" joining incomplete tree stack */
} p;
unsigned char lexeme; /* Code that identifies the operator. */
unsigned char precedence; /* Precedence of the operator */
unsigned char mark; /* Mark used to control inorder traversal. */
} OpNode;
/*
* The storage for the tree is dynamically allocated array of OpNodes. The
* array is grown as parsing needs dictate according to a scheme similar to
* Tcl's string growth algorithm, so that the resizing costs are O(N) and so
* that we use at least half the memory allocated as expressions get large.
|
|
|
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
|
int right; /* "Pointer" to the right operand. */
union {
int parent; /* "Pointer" to the parent operand. */
int prev; /* "Pointer" joining incomplete tree stack */
} p;
unsigned char lexeme; /* Code that identifies the operator. */
unsigned char precedence; /* Precedence of the operator */
unsigned char mark; /* Mark used to control traversal. */
} OpNode;
/*
* The storage for the tree is dynamically allocated array of OpNodes. The
* array is grown as parsing needs dictate according to a scheme similar to
* Tcl's string growth algorithm, so that the resizing costs are O(N) and so
* that we use at least half the memory allocated as expressions get large.
|
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
|
#define IsOperator(l) ((l) >= 0)
#define NotOperator(l) ((l) < 0)
/*
* Note that it is sufficient to store in the tree just the type of leaf
* operand, without any explicit pointer to which leaf. This is true because
* the inorder traversals of the completed tree we perform are known to visit
* the leaves in the same order as the original parse.
*
* In a completed parse tree, those OpNodes that are themselves (roots of
* subexpression trees that are) operands of some operator store in their
* p.parent field a "pointer" to the OpNode of that operator. The p.parent
* field permits a destructive inorder traversal of the tree within a
* non-recursive routine (ConvertTreeToTokens() and CompileExprTree()). This
* means that even expression trees of great depth pose no risk of blowing
* the C stack.
*
* While the parse tree is being constructed, the same memory space is used
* to hold the p.prev field which chains together a stack of incomplete
* trees awaiting their right operands.
*
* The lexeme field is filled in with the lexeme of the operator that is
* returned by the ParseLexeme() routine. Only lexemes for unary and
* binary operators get stored in an OpNode. Other lexmes get different
* treatement.
*
* The precedence field provides a place to store the precedence of the
* operator, so it need not be looked up again and again.
*
* The mark field is use to control the inorder traversal of the tree, so
* that it can be done non-recursively. The mark values are:
*/
enum Marks {
MARK_LEFT, /* Next step of traversal is to visit left subtree */
MARK_RIGHT, /* Next step of traversal is to visit right subtree */
MARK_PARENT, /* Next step of traversal is to return to parent */
|
|
|
|
|
<
|
|
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
|
#define IsOperator(l) ((l) >= 0)
#define NotOperator(l) ((l) < 0)
/*
* Note that it is sufficient to store in the tree just the type of leaf
* operand, without any explicit pointer to which leaf. This is true because
* the traversals of the completed tree we perform are known to visit
* the leaves in the same order as the original parse.
*
* In a completed parse tree, those OpNodes that are themselves (roots of
* subexpression trees that are) operands of some operator store in their
* p.parent field a "pointer" to the OpNode of that operator. The p.parent
* field permits a traversal of the tree within a * non-recursive routine
* (ConvertTreeToTokens() and CompileExprTree()). This means that even
* expression trees of great depth pose no risk of blowing the C stack.
*
* While the parse tree is being constructed, the same memory space is used
* to hold the p.prev field which chains together a stack of incomplete
* trees awaiting their right operands.
*
* The lexeme field is filled in with the lexeme of the operator that is
* returned by the ParseLexeme() routine. Only lexemes for unary and
* binary operators get stored in an OpNode. Other lexmes get different
* treatement.
*
* The precedence field provides a place to store the precedence of the
* operator, so it need not be looked up again and again.
*
* The mark field is use to control the traversal of the tree, so
* that it can be done non-recursively. The mark values are:
*/
enum Marks {
MARK_LEFT, /* Next step of traversal is to visit left subtree */
MARK_RIGHT, /* Next step of traversal is to visit right subtree */
MARK_PARENT, /* Next step of traversal is to return to parent */
|