t-h2o/parsmath

Parsing math expression

Table of Contents

• 1. Examples input
• 2. Grammar for expressions
  • 2.1. Variations
  • 2.2. Tokens
  • 2.3. Lexical analysis
  • 2.4. Tree
• 3. Program
  • 3.1. Classes
  • 3.2. Parsing
• 4. Output
• 5. Resources

1. Examples input

• Precedence

  Input	Correct	Error
  \$x + 5 * y\$	\$x + (5 * y)\$	\$(x + 5) * y\$

• Associativity

  Input	Correct	Error
  \$7 - 3 + 2\$	\$(7 - 3) + 2\$	\$7 - (3 + 2)\$

2. Grammar for expressions

E

Expression

T

Term

F

Factor

2.1. Variations

• \$E -> T + E | T - E | T\$

• \$T -> F * T | F / T | F\$

• \$F -> ID | "Integers" | (E) - F\$

2.2. Tokens

• ID

  

• integer

  

2.3. Lexical analysis

code

function scanToken()

Scans the input and sets nextToken to point to the newly scanned token.

variable

nextToken

OOP

Object-Oriented Programming

2.4. Tree

Tree example with: \$-(x + 5) * 2\$

The superclass tree node:

Infix operators:

Prefix unary operators:

others:

3. Program

3.1. Classes

3.2. Parsing

4. Output

$ ./parsmath 20 x 5 + 3

((20 x 5) + 3) = 103
+ ─┬─ x ─┬─ 5
   │     └─ 20
   └─ 3

$ ./parsmath 2 + 5 x 3

(2 + (5 x 3)) = 17
+ ─┬─ x ─┬─ 3
   │     └─ 5
   └─ 2

$ ./parsmath 2 + 5 x 3 - 7

((2 + (5 x 3)) - 7) = 10
- ─┬─ + ─┬─ x ─┬─ 3
   │     │     └─ 5
   │     └─ 2
   └─ 7

$ ./parsmath 2 + 5 - 3 x 7

((2 + 5) - (3 x 7)) = -14
- ─┬─ + ─┬─ 5
   │     └─ 2
   └─ x ─┬─ 7
         └─ 3

$ ./parsmath 2 + 5 - 15 / 7

((2 + 5) - (15 / 7)) = 5
- ─┬─ + ─┬─ 5
   │     └─ 2
   └─ / ─┬─ 7
         └─ 15

$ ./parsmath 1 + 2 + 3 + 4 + 5 - 6 - 7 + 9

(((((((1 + 2) + 3) + 4) + 5) - 6) - 7) + 9) = 11
+ ─┬─ - ─┬─ - ─┬─ + ─┬─ + ─┬─ + ─┬─ + ─┬─ 2
   │     │     │     │     │     │     └─ 1
   │     │     │     │     │     └─ 3
   │     │     │     │     └─ 4
   │     │     │     └─ 5
   │     │     └─ 6
   │     └─ 7
   └─ 9

5. Resources

source code

• GitHub: t-h2o/parsmath

wikipedia

• LR parser

  LR parser

  Left-to-right, Rightmost derivation in reverse