Name: Anonymous 2013-07-18 16:31
Parsing an expression:
Definitions:
A code struct consists of a token list. A token can be a keyword, an identifier, a constant,
or a symbol (which can be an operator or a punctuator).
An expression code struct consists of a list of expression code elements.
An expression code element is an element which is found in an expression, and can be one of the following.
* An operator with operator type and description.
* A constant value.
* A named object.
* A member identifier (must only follow a member selection operator).
* A sub-expression (i.e. a parenthesis).
An expression struct consists of either an expression code element that is not an operator, or an operation struct.
An operation struct consists of an operator with type and description, and one or two operands which are either
expression code elements that are not operators, or operation structs.
Procedure:
Phase one:
Accept a code struct and a range within which the expression resides.
Create an expression code struct which will contain each element of the expression.
Parse the token list in the code struct from left to right within the range, while error-checking the syntax.
Create an expression code element from each code token and insert it into the expression code struct.
Create an expression struct.
Invoke phase two with the newly-created expression code struct, and the entire range of said struct, as arguments.
Assign the result of phase two to the expression struct.
Return the expression struct as the result of phase one.
Phase two:
Accept an expression code struct, and a range within which the concerned elements reside.
* If the range is only one element wide, that element must be a constant value, a named object, a member identifier,
or a sub-expression (which, if so, is now parsed by invoking phase one). This element is then returned as the
result of phase two.
* If the range covers more than one element, do an operator search with reverse precedence and associativity. (i.e.
find the operator whose operation will be performed last).
Create an operation struct, and assign to it the operator type and description of the operator found in the search.
Invoke phase two on the elements within the range, if any, preceding the operator, and assign the result as an
operand of the operation struct. Type-check the result such that it is compatible with the operator.
Repeat this for the elements within range, if any, succeeding the operator.
Return the operation struct as the result of phase two.
Result:
This procedure will create an expression tree which will represent the operations performed.
The branches on the bottom of the tree are those operations that shall be performed first. Thus, this structure
is well suited for a recursive code generator.
The result of performing this procedure on the following example expression can be presented as so:
foobar[i + 2] = foo + bar * x[j - 1]
(((foobar)[((i) + (2))]) = ((foo) + ((bar) * ((x)[((j) - (1))]))))
( )
( ) = ( )
(foobar)[( )] (foo) + ( )
(i) + (2) (bar) * ( )
(x)[( )]
(j) - (1)
=
|
[ ]________|________+
| |
foobar__|__+ foo_____|_____*
| |
i_|_2 bar__|__[ ]
|
x__|__-
|
j_|_1
Definitions:
A code struct consists of a token list. A token can be a keyword, an identifier, a constant,
or a symbol (which can be an operator or a punctuator).
An expression code struct consists of a list of expression code elements.
An expression code element is an element which is found in an expression, and can be one of the following.
* An operator with operator type and description.
* A constant value.
* A named object.
* A member identifier (must only follow a member selection operator).
* A sub-expression (i.e. a parenthesis).
An expression struct consists of either an expression code element that is not an operator, or an operation struct.
An operation struct consists of an operator with type and description, and one or two operands which are either
expression code elements that are not operators, or operation structs.
Procedure:
Phase one:
Accept a code struct and a range within which the expression resides.
Create an expression code struct which will contain each element of the expression.
Parse the token list in the code struct from left to right within the range, while error-checking the syntax.
Create an expression code element from each code token and insert it into the expression code struct.
Create an expression struct.
Invoke phase two with the newly-created expression code struct, and the entire range of said struct, as arguments.
Assign the result of phase two to the expression struct.
Return the expression struct as the result of phase one.
Phase two:
Accept an expression code struct, and a range within which the concerned elements reside.
* If the range is only one element wide, that element must be a constant value, a named object, a member identifier,
or a sub-expression (which, if so, is now parsed by invoking phase one). This element is then returned as the
result of phase two.
* If the range covers more than one element, do an operator search with reverse precedence and associativity. (i.e.
find the operator whose operation will be performed last).
Create an operation struct, and assign to it the operator type and description of the operator found in the search.
Invoke phase two on the elements within the range, if any, preceding the operator, and assign the result as an
operand of the operation struct. Type-check the result such that it is compatible with the operator.
Repeat this for the elements within range, if any, succeeding the operator.
Return the operation struct as the result of phase two.
Result:
This procedure will create an expression tree which will represent the operations performed.
The branches on the bottom of the tree are those operations that shall be performed first. Thus, this structure
is well suited for a recursive code generator.
The result of performing this procedure on the following example expression can be presented as so:
foobar[i + 2] = foo + bar * x[j - 1]
(((foobar)[((i) + (2))]) = ((foo) + ((bar) * ((x)[((j) - (1))]))))
( )
( ) = ( )
(foobar)[( )] (foo) + ( )
(i) + (2) (bar) * ( )
(x)[( )]
(j) - (1)
=
|
[ ]________|________+
| |
foobar__|__+ foo_____|_____*
| |
i_|_2 bar__|__[ ]
|
x__|__-
|
j_|_1