Name
Tree::Term - Create a parse tree from an array of terms representing an expression.
Synopsis
The expression to parse is presented as an array of words, the first letter of each word indicates its lexical role as in:
my @e = qw(
v_sub a_is v_array as
v1 d_== v2 a_then v3 d_plus v4 a_else
v5 d_== v6 a_then v7 d_minus v8 a_else v9 d_times b v10 a_+ v11 B);
Where:
a assign - infix operator with priority 2 binding right to left
b open - open parenthesis
B close - close parenthesis
d dyad - infix operator with priority 3 binding left to right
p prefix - monadic prefix operator
q suffix - monadic suffix operator
s semi-colon - infix operator with priority 1 binding left to right
v variable - a variable in the expression
The results of parsing the expression can be printed with flat which provides a left to right representation of the parse tree.
is_deeply parse(@e)->flat, <<END;
is
sub as
array then
== else
v1 v2 plus then
v3 v4 == else
v5 v6 minus times
v7 v8 v9 +
v10 v11
END
Description
Create a parse tree from an array of terms representing an expression.
Version 20210724.
The following sections describe the methods in each functional area of this module. For an alphabetic listing of all methods by name see Index.
Parse
Create a parse tree from an array of terms representing an expression.
LexicalStructure()
Return the lexical codes and their relationships in a data structure so this information can be used in other contexts.
Example:
is_deeply LexicalStructure, # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲
syntaxError(@expression)
Check the syntax of an expression without parsing it. Die with a helpful message if an error occurs. The helpful message will be slightly different from that produced by parse as it cannot contain information from the non existent parse tree.
Parameter Description
1 @expression Expression to parse
Example:
if (1)
{eval {syntaxError(qw(v1 p1))}; # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲
ok -1 < index $@, <<END =~ s({a}) ( )gsr;
Unexpected 'prefix operator': p1 following 'variable': v1 at position 2.
Expected: 'assignment operator', 'closing parenthesis',
'dyadic operator', 'semi-colon' or 'suffix operator'.
END
}
parse(@expression)
Parse an expression.
Parameter Description
1 @expression Expression to parse
Example:
ok T [qw(v_sub a_is v_array as v1 d_== v2 a_then v3 d_plus v4 a_else v5 d_== v6 a_then v7 d_minus v8 a_else v9 d_times b v10 a_+ v11 B)], <<END;
is
sub as
array then
== else
v1 v2 plus then
v3 v4 == else
v5 v6 minus times
v7 v8 v9 +
v10 v11
END
}
if (1) {
ok validPair('B', 'd');
ok validPair('b', 'B');
ok validPair('v', 'a');
ok !validPair('v', 'v');
Validate
Validating is the same as parsing except we do not start at the beginning, instead we start at any lexical element and proceed a few steps from there.
validPair($A, $B)
Confirm that the specified pair of lexical elements can occur as a sequence.
Parameter Description
1 $A First element
2 $B Second element
Example:
ok validPair('B', 'd'); # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲
ok validPair('b', 'B'); # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲
ok validPair('v', 'a'); # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲
ok !validPair('v', 'v'); # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲
Print a parse tree to make it easy to visualize its structure.
flat($expression, @title)
Print the terms in the expression as a tree from left right to make it easier to visualize the structure of the tree.
Parameter Description
1 $expression Root term
2 @title Optional title
Example:
my @e = qw(v1 a2 v3 d4 v5 s6 v8 a9 v10);
is_deeply parse(@e)->flat, <<END; # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲
s6
a2 a9
v1 d4 v8 v10
v3 v5
END
}
ok T [qw(v1 a2 v3 s s s v4 a5 v6 s s)], <<END;
s
s empty1
s a5
s empty1 v4 v6
a2 empty1
v1 v3
END
ok T [qw(b B)], <<END;
empty1
END
ok T [qw(b b B B)], <<END;
empty1
END
ok T [qw(b b v1 B B)], <<END;
v1
END
ok T [qw(b b v1 a2 v3 B B)], <<END;
a2
v1 v3
END
ok T [qw(b b v1 a2 v3 d4 v5 B B)], <<END;
a2
v1 d4
v3 v5
END
ok T [qw(p1 v1)], <<END;
p1
v1
END
ok T [qw(p2 p1 v1)], <<END;
p2
p1
v1
END
ok T [qw(v1 q1)], <<END;
q1
v1
END
ok T [qw(v1 q1 q2)], <<END;
q2
q1
v1
END
ok T [qw(p2 p1 v1 q1 q2)], <<END;
q2
q1
p2
p1
v1
END
ok T [qw(p2 p1 v1 q1 q2 d3 p4 p3 v2 q3 q4)], <<END;
d3
q2 q4
q1 q3
p2 p4
p1 p3
v1 v2
END
ok T [qw(p2 p1 v1 q1 q2 d3 p4 p3 v2 q3 q4 d4 p6 p5 v3 q5 q6 s)], <<END;
d3
q2 d4
q1 q4 q6
p2 q3 q5
p1 p4 p6
v1 p3 p5
v2 v3
END
ok T [qw(b s B)], <<END;
empty1
END
ok T [qw(b s s B)], <<END;
s
empty1 empty1
END
if (1) {
my @e = qw(b b p2 p1 v1 q1 q2 B d3 b p4 p3 v2 q3 q4 d4 p6 p5 v3 q5 q6 B s B s);
is_deeply parse(@e)->flat, <<END; # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲
d3
q2 d4
q1 q4 q6
p2 q3 q5
p1 p4 p6
v1 p3 p5
v2 v3
END
}
ok T [qw(b b v1 B s B s)], <<END;
v1
END
ok T [qw(v1 q1 s)], <<END;
q1
v1
END
ok T [qw(b b v1 q1 q2 B q3 q4 s B q5 q6 s)], <<END;
q6
q5
q4
q3
q2
q1
v1
END
ok T [qw(p1 p2 b v1 B)], <<END;
p1
p2
v1
END
ok T [qw(v1 d1 p1 p2 v2)], <<END;
d1
v1 p1
p2
v2
END
ok T [qw(p1 p2 b p3 p4 b p5 p6 v1 d1 v2 q1 q2 B q3 q4 s B q5 q6 s)], <<END;
q6
q5
p1
p2
q4
q3
p3
p4
d1
p5 q2
p6 q1
v1 v2
END
ok T [qw(p1 p2 b p3 p4 b p5 p6 v1 a1 v2 q1 q2 B q3 q4 s B q5 q6 s)], <<END;
q6
q5
p1
p2
q4
q3
p3
p4
a1
p5 q2
p6 q1
v1 v2
END
ok T [qw(b v1 B d1 b v2 B)], <<END;
d1
v1 v2
END
ok T [qw(b v1 B q1 q2 d1 b v2 B)], <<END;
d1
q2 v2
q1
v1
END
ok T [qw(v1 s)], <<END;
v1
END
ok T [qw(v1 s s)], <<END;
s
v1 empty1
END
ok T [qw(v1 s b s B)], <<END;
s
v1 empty1
END
ok T [qw(v1 s b b s s B B)], <<END;
s
v1 s
empty1 empty1
END
ok T [qw(b v1 s B s s)], <<END;
s
v1 empty1
END
ok T [qw(v1 a b1 b2 v2 B2 B1 s)], <<END;
a
v1 v2
END
ok T [qw(v1 a1 b1 v2 a2 b2 v3 B2 B1 s)], <<END;
a1
v1 a2
v2 v3
END
ok T [qw(v1 a1 p1 v2)], <<END;
a1
v1 p1
v2
END
ok T [qw(b1 v1 q1 q2 B1)], <<END;
q2
q1
v1
END
ok T [qw(b1 v1 q1 q2 s B1)], <<END;
q2
q1
v1
END
ok T [qw(p1 b1 v1 B1 q1)], <<END;
q1
p1
v1
END
ok T [qw(b1 v1 B1 a1 v2)], <<END;
a1
v1 v2
END
ok T [qw(v1 q1 a1 v2)], <<END;
a1
q1 v2
v1
END
ok T [qw(s1 p1 v1)], <<END;
s1
empty2 p1
v1
END
ok E <<END;
a
Expression must start with 'opening parenthesis', 'prefix operator', 'semi-colon' or 'variable', not 'assignment operator': a.
Expression must start with 'opening parenthesis', 'prefix operator', 'semi-colon' or 'variable', not 'assignment operator': a.
END
ok E <<END;
B
Expression must start with 'opening parenthesis', 'prefix operator', 'semi-colon' or 'variable', not 'closing parenthesis': B.
Expression must start with 'opening parenthesis', 'prefix operator', 'semi-colon' or 'variable', not 'closing parenthesis': B.
END
ok E <<END;
d1
Expression must start with 'opening parenthesis', 'prefix operator', 'semi-colon' or 'variable', not 'dyadic operator': d1.
Expression must start with 'opening parenthesis', 'prefix operator', 'semi-colon' or 'variable', not 'dyadic operator': d1.
END
ok E <<END;
p1
Expected: 'opening parenthesis', 'prefix operator' or 'variable' after final 'prefix operator': p1.
Expected: 'opening parenthesis', 'prefix operator' or 'variable' after final 'prefix operator': p1.
END
ok E <<END;
q1
Expression must start with 'opening parenthesis', 'prefix operator', 'semi-colon' or 'variable', not 'suffix operator': q1.
Expression must start with 'opening parenthesis', 'prefix operator', 'semi-colon' or 'variable', not 'suffix operator': q1.
END
ok E <<END;
s
END
ok E <<END;
v1
END
ok E <<END;
b v1
Incomplete expression. Expected: 'assignment operator', 'closing parenthesis', 'dyadic operator', 'semi-colon' or 'suffix operator'.
No closing parenthesis matching b at position 1.
END
ok E <<END;
b v1 B B
Unexpected 'closing parenthesis': B following 'closing parenthesis': B at position 4. Expected: 'assignment operator', 'closing parenthesis', 'dyadic operator', 'semi-colon' or 'suffix operator'.
Unexpected closing parenthesis B at position 4. Expected: 'assignment operator', 'closing parenthesis', 'dyadic operator', 'semi-colon' or 'suffix operator'.
END
ok E <<END;
v1 d1 d2 v2
Unexpected 'dyadic operator': d2 following 'dyadic operator': d1 at position 3. Expected: 'opening parenthesis', 'prefix operator' or 'variable'.
Unexpected 'dyadic operator': d2 following 'dyadic operator': d1 at position 3. Expected: 'opening parenthesis', 'prefix operator' or 'variable'.
END
ok E <<END;
v1 p1
Unexpected 'prefix operator': p1 following term ending at position 2. Expected: 'assignment operator', 'closing parenthesis', 'dyadic operator', 'semi-colon' or 'suffix operator'.
Unexpected 'prefix operator': p1 following 'variable': v1 at position 2. Expected: 'assignment operator', 'closing parenthesis', 'dyadic operator', 'semi-colon' or 'suffix operator'.
END
ok E <<END;
b1 B1 v1
Unexpected 'variable': v1 following term ending at position 3. Expected: 'assignment operator', 'closing parenthesis', 'dyadic operator', 'semi-colon' or 'suffix operator'.
Unexpected 'variable': v1 following 'closing parenthesis': B1 at position 3. Expected: 'assignment operator', 'closing parenthesis', 'dyadic operator', 'semi-colon' or 'suffix operator'.
END
ok E <<END;
b1 B1 p1 v1
Unexpected 'prefix operator': p1 following term ending at position 3. Expected: 'assignment operator', 'closing parenthesis', 'dyadic operator', 'semi-colon' or 'suffix operator'.
Unexpected 'prefix operator': p1 following 'closing parenthesis': B1 at position 3. Expected: 'assignment operator', 'closing parenthesis', 'dyadic operator', 'semi-colon' or 'suffix operator'.
END
if (1)
{eval {syntaxError(qw(v1 p1))};
ok -1 < index $@, <<END =~ s({a}) ( )gsr;
Unexpected 'prefix operator': p1 following 'variable': v1 at position 2.
Expected: 'assignment operator', 'closing parenthesis',
'dyadic operator', 'semi-colon' or 'suffix operator'.
END
Hash Definitions
Tree::Term Definition
Description of a term in the expression.
Output fields
operands
Operands to which the operator will be applied.
operator
Operator to be applied to one or more operands.
up
Parent term if this is a sub term.
Tree::Term::Codes Definition
Lexical item codes.
Output fields
B
Closing parenthesis.
a
Infix operator with priority 2 binding right to left typically used in an assignment.
b
Opening parenthesis.
d
Infix operator with priority 3 binding left to right typically used in arithmetic.
p
Monadic prefix operator.
q
Monadic suffix operator.
s
Infix operator with priority 1 binding left to right typically used to separate statements.
t
A term in the expression.
v
A variable in the expression.
Tree::Term::LexicalCode Definition
Lexical item codes.
Output fields
letter
Letter code used to refer to the lexical item.
name
Descriptive name of lexical item.
next
Letters codes of items that can follow this lexical item.
Tree::Term::LexicalStructure Definition
Lexical item codes.
Output fields
codes
Code describing each lexical item
first
Lexical items we can start with
last
Lexical items we can end with
Private Methods
new($count)
Create a new term from the indicated number of items on top of the stack
Parameter Description
1 $count Number of terms
LexicalCode($letter, $next, $name)
Lexical code definition
Parameter Description
1 $letter Letter used to refer to the lexical item
2 $next Letters of items that can follow this lexical item
3 $name Descriptive name of lexical item
type($s)
Type of term
Parameter Description
1 $s Term to test
expandElement($e)
Describe a lexical element
Parameter Description
1 $e Element to expand
expandCodes($e)
Expand a string of codes
Parameter Description
1 $e Codes to expand
expected($s)
String of next possible lexical items
Parameter Description
1 $s Lexical item
unexpected($element, $unexpected, $position)
Complain about an unexpected element
Parameter Description
1 $element Last good element
2 $unexpected Unexpected element
3 $position Position
check_XXXX()
Check that the top of the stack has one of XXXX
test_XXXX($item)
Check that we have XXXX
Parameter Description
1 $item Item to test
test_t($item)
Check that we have a term
Parameter Description
1 $item Item to test
reduce($priority)
Reduce the stack at the specified priority
Parameter Description
1 $priority Priority
reduce1()
Reduce the stack at priority 1
reduce2()
Reduce the stack at priority 2
pushElement()
Push an element
accept_a()
Assign
accept_b()
Open
accept_B()
Closing parenthesis
accept_d()
Infix but not assign or semi-colon
accept_p()
Prefix
accept_q()
Post fix
accept_s()
Semi colon
accept_v()
Variable
parseExpression()
Parse an expression.
depth($term)
Depth of a term in an expression.
Parameter Description
1 $term Term
listTerms($expression)
List the terms in an expression in post order
Parameter Description
1 $expression Root term
Index
1 accept_a - Assign
2 accept_B - Closing parenthesis
3 accept_b - Open
4 accept_d - Infix but not assign or semi-colon
5 accept_p - Prefix
6 accept_q - Post fix
7 accept_s - Semi colon
8 accept_v - Variable
9 check_XXXX - Check that the top of the stack has one of XXXX
10 depth - Depth of a term in an expression.
11 expandCodes - Expand a string of codes
12 expandElement - Describe a lexical element
13 expected - String of next possible lexical items
14 flat - Print the terms in the expression as a tree from left right to make it easier to visualize the structure of the tree.
15 LexicalCode - Lexical code definition
16 LexicalStructure - Return the lexical codes and their relationships in a data structure so this information can be used in other contexts.
17 listTerms - List the terms in an expression in post order
18 new - Create a new term from the indicated number of items on top of the stack
19 parse - Parse an expression.
20 parseExpression - Parse an expression.
21 pushElement - Push an element
22 reduce - Reduce the stack at the specified priority
23 reduce1 - Reduce the stack at priority 1
24 reduce2 - Reduce the stack at priority 2
25 syntaxError - Check the syntax of an expression without parsing it.
26 test_t - Check that we have a term
27 test_XXXX - Check that we have XXXX
28 type - Type of term
29 unexpected - Complain about an unexpected element
30 validPair - Confirm that the specified pair of lexical elements can occur as a sequence.
Installation
This module is written in 100% Pure Perl and, thus, it is easy to read, comprehend, use, modify and install via cpan:
sudo cpan install Tree::Term
Author
Copyright
Copyright (c) 2016-2021 Philip R Brenan.
This module is free software. It may be used, redistributed and/or modified under the same terms as Perl itself.