Strict Programming Language

Strict Programming Language

  • Docs
  • API
  • Blog

›All Blog Posts

All Blog Posts

  • March 2023 Mutable
  • January 2023 Multi Line Text Expressions and Introducing New Lines in Strict
  • January 2023 Namings in Strict
  • December 2022 Traits and Components
  • November 2022 Multi Line List Expressions
  • November 2022 Strict Base and Example folders moved to separate repository
  • October 2022 Shunting Yard
  • September 2022 For loops
  • September 2022 Details about Mutability in Strict
  • July 2022 Introduction To Generics In Strict
  • May 2021 Strict Newbie Experiences
  • June 2021 Slow Progress
  • May 2021 BNF Grammar
  • May 2021 Next Steps
  • Jul 2020 Getting Back Into It
  • Jul 2020 Optimizing FindType
  • Jul 2020 Package Loading
  • Jun 2020 Parsing Methods
  • Jun 2020 As Simple As Possible
  • Jun 2020 Back to blogging
  • May 2020 Slow and not steady
  • Apr 2020 Sdk going open source
  • Feb 2020 Still work in progress
  • Jan 2020 website is up

October 2022 Shunting Yard

October 15, 2022

Murali Tandabany

When I was struggling with parsing the nested group expressions, Benjamin Nitschke introduced an algorithm to me called Shuting Yard which solves group expression parsing in a much simpler way. In this blog, we are going to discuss the details about this Shunting Yard algorithm and learn it's usages in Strict.

What is Shunting Yard?

It is a stack-based algorithm which takes arithmetic or logical expressions as input and convert them into postfix notation. The output postfix notation gives us the order of execution of the arithmetic or logical expression operations in order to arrive at the correct result.

More details about the algorithm can be found in this wikipedia page link

https://en.wikipedia.org/wiki/Shunting_yard_algorithm

How Shunting Yard is used in Strict?

We took the complete advantage of Shunting Yard algorithm in the Parser section where each line of code needs to be parsed and spit out into correct expressions. Here, the strict program lines can contain any type of expression such as Number, Text or complex nested group Binary expression with member calls and method calls. In order to parse all theses types of expressions, mainly nested group expressions in the parser without having many performance intensive checks and conditions, we need a simple and clever algorithm like Shunting Yard.

The method expression parser itself takes care of all of the easy kind expressions in the front level which helps to improve the performance of parsing phase. When it comes to complex type expressions, we need to give it as input to the Shunting yard where the complex expression is first tokenized using Phrase Tokenizer class and then each token is ordered based on the operator precendence which then finally gives us back the postfix tokens.

These postfix tokens are stored in the Stack and the method expression parser will pop out each token and construct the result expression with few checks. Specifically, constructing binary expressions out of postfix tokens makes the job very much easier with the use of recursion.

For example:

(2 + (3 + 5) * 5) * 2  converted to -> 2, 3, 5, +, 5, *, +, 2, *

What is Phrase Tokenizer?

Phrase Tokenizer is a class inside Shunting Yard and it is used to tokenize the complex expressions into separate tokens based on certains conditions.

For example:

1 + 2 -> tokenized into "1" , "+", "2"
"Hello + World" + 5 -> tokenized into ""Hello + World"", "+", "5"

For certains types of expression where tokenizing is not helpful, Phrase Tokenizer will spit out the whole expression as single token and then the method expression parser will handle it by splitting the expression into much simpler form and uses Shunting yard again if needed. Mostly, if the expression is nested with arithmetic or logical operators, then tokenizing them will make more sense than for method call or member call expressions.

For example:

Add(4 * 5 + 3 - 1)

This whole expression will be treated as single token in the Phrase Tokenizer and then the method expression parser will split this into separate expressions as shown below

Add as Method call 
4 * 5 + 3 - 1 to Shunting Yard and get output as 4, 5, *, 3, +, 1, -

For more details about Shunting yard and phrase tokenizer, refer to the Strict code base in github.

Recent Posts
  • What is Shunting Yard?
  • How Shunting Yard is used in Strict?
  • What is Phrase Tokenizer?
Strict Programming Language
Docs
Getting StartedCoding StyleAPI Reference
Community
Stack OverflowProject ChatTwitter
More
HelpGitHubStar
Copyright © 2023 strict-lang