ExpressionTree

A simple arithmetic expression parser written in C. Organizes arithmetic expression (user input string) into an Abstract Syntax Tree (AST) which reflects operator precedence and associativity.

Lexical Symbols

The tokenizer classifies the input string into 3 classes:

• variables (regex ^[A-Za-z_]+[A-Za-z0-9_]$)
• integral numeric literals (regex ^[0-9]+$)
• operators (one of {'+', '-', '*', '/', '%', '++', '--'})

Grammar:

• Grammar is defined to formalize the rules of arithmetic (operator precedence, associativity) and outline the output tree structure.
• Non-terminals are lower-cased words like expr, mult, unary: they could be thought of as recursive "functions" that could be further expanded using the rules defined to the right of :=.
• Terminals are TOK_LIT and TOK_VAR, they cannot be further expanded and are defined using regex.
• The precedence of each rule will determine how "tall" they are in the resulting AST, in the following grammar, the rules/non-terminals that are closer to the bottom have higher precedence.

		expr	:=  expr '+' mult
                |   expr '-' mult
                |   mult

		mult	:= mult '*' unary
                |  mult '/' unary
                |  mult '%' unary
                |  mult atom		// implicit multiplication
                |  unary

		unary	:= '+' unary
                |  '-' unary
                |  incdec

		incdec  := '++' incdec
                |  '--' incdec
                |  incdec '++'
                |  incdec '--'
                |  atom

		atom	:= TOK_LIT | TOK_VAR | '(' expr ')'

		TOK_VAR	:= ^[A-Za-z_]+[_A-Za-z0-9]*$
		TOK_LIT	:= ^[0-9]+$

• Note: implicit multiplication is supported via the syntax

	(TOK_LIT|TOK_VAR) <space> (TOK_LIT|TOK_VAR) 

This differs from regular programming language grammar for which above syntax could mean (TOK_LIT|TOK_VAR) initialization.

Operator Precedence in Above Grammar

	("+"|"-") < ("*"|"/"|"%") < ("++"|"--")

Caveats

Notes on IncDec (++ or --)

• They are right associative and have the highest precedence, meaning that expression a b ++ ⇔ a * (b++) and ++ a b ⇔ (++a) * b.
• Their respective parse trees are:

    	"*"
    	 |__"a"
    	 |__"++"
    	  |__"b"
  

  and

    	"*"
    	 |__"++"
    	  |__"a"
    	 |__"b"
  

Warning on Mixing IncDec and Implicit Multiplication

• Mixing prefix IncDec, postfix IncDec, and implicit multiplication together is strongly discouraged.
• Please refer to following examples for how this project handles such cases.

Example 1

The expression a ++ b obeys the grammar rules defined above, and there are 2 ways the ++ operator could be associated with variables a and b.

1. a * (++b)
2. (a++) * b

This project chooses the second way: "any ++ or -- that is preceeded by either a variable or literal is going to be treated as a unary postfix increment/decrement expression".

Example 2

Consider the expression a++ --b, there are 2 possible groupings:

1. a++ --b ⇔ (a++) * (--b)
2. a++ --b ⇔ ((a++)--) * b

• This project goes with the second grouping when generating ASTs.

• To reiterate, it is strongly discouraged to write expressions similar to above example, the correct way to do so is either using the conventional * operator or parentheses to specify associativity.

Output (parseTree.txt)

• The output is a simple visual display of the AST. Specifically, a pre-order tree-walk of the AST.

• An ASTNode is either a TOK_LIT, a TOK_VAR, or an operator surrounded by "".

• A node's child is placed below itself, preceed with a space and the symbol |__.

  • notice that 2 children are siblings (on the same level of the entire AST) if their |__ symbols line up with each other.
  • As an example, the AST for expression (a + b) / 2 will look like

    "/"
     |__"+"
      |__"a"
      |__"b"
     |__"2"
  

• Implicit mulitiplication will be handled by manually making an extra * node between the two operands.

  • Expressions2 a and a 2 will thus become

   	"*"                "*"
   	 |__"2"             |_"a"
   	 |__"a"             |_"2"
  

• If an ExpressionTree is built successfully, it will be printed onto a file named parseTree.txt in this directory.

Compile/Build Instructions

Assume gcc and Make are available on the machine.

• refer to Makefile for build, test, and clean instructions.
• On successful builds, an executable named expressionTree will be present in the working directory.
• if valgrind is installed on the machine, make valgrind will run the executable with valgrind to check for memory errors.

Rules Summary

Simple Build

	make

Build Then Execute

	make test

Build, Test, Execute, then Check Memory Fault

• assume valgrind is installed on machine

	make valgrind

Remove Executable

	make clean

Design Goals/Direction

• see design.md

Inspirations and References

1. https://github.com/PixelRifts/math-expr-evaluator/tree/master
2. https://craftinginterpreters.com
3. https://matklad.github.io/2020/04/13/simple-but-powerful-pratt-parsing.html