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

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.

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

philiprbrenan@gmail.com

http://www.appaapps.com

Copyright

This module is free software. It may be used, redistributed and/or modified under the same terms as Perl itself.

To install Tree::Term, copy and paste the appropriate command in to your terminal.

cpanm

cpanm Tree::Term

CPAN shell

perl -MCPAN -e shell
install Tree::Term

For more information on module installation, please visit the detailed CPAN module installation guide.

	Global
`s`	Focus search bar
`?`	Bring up this help dialog

	GitHub
`g` `p`	Go to pull requests
`g` `i`	go to github issues (only if github is preferred repository)

	POD
`g` `a`	Go to author
`g` `c`	Go to changes
`g` `i`	Go to issues
`g` `d`	Go to dist
`g` `r`	Go to repository/SCM
`g` `s`	Go to source
`g` `b`	Go to file browse

	Search terms
module: (e.g. module:Plugin)
distribution: (e.g. distribution:Dancer auth)
author: (e.g. author:SONGMU Redis)
version: (e.g. version:1.00)

Name

Synopsis

Description

Parse

LexicalStructure()

syntaxError(@expression)

parse(@expression)

Validate

validPair($A, $B)

Print

flat($expression, @title)

Hash Definitions

Tree::Term Definition

Output fields

operands

operator

up

Tree::Term::Codes Definition

Output fields

B

a

b

d

p

q

s

t

v

Tree::Term::LexicalCode Definition

Output fields

letter

name

next

Tree::Term::LexicalStructure Definition

Output fields

codes

first

last

Private Methods

new($count)

LexicalCode($letter, $next, $name)

type($s)

expandElement($e)

expandCodes($e)

expected($s)

unexpected($element, $unexpected, $position)

check_XXXX()

test_XXXX($item)

test_t($item)

reduce($priority)

reduce1()

reduce2()

pushElement()

accept_a()

accept_b()

accept_B()

accept_d()

accept_p()

accept_q()

accept_s()

accept_v()

parseExpression()

depth($term)

listTerms($expression)

Index

Installation

Author

Copyright

Module Install Instructions