Table of contents
1.
Introduction
2.
Structure of Parse Trees
3.
Parse Tree in ATL
4.
Frequently Asked Questions
4.1.
What is the other name of the parse tree?
4.2.
A parse tree follows which Grammar?
4.3.
What does ATL stand for?
4.4.
Why do we need ATL?
5.
Conclusion
Last Updated: Mar 27, 2024
Hard

Parse trees

Author dhananjay
0 upvote
Career growth poll
Do you think IIT Guwahati certified course can help you in your career?

Introduction

ATL stands for Active Template Library, developed by Microsoft. The purpose of ATL is to simplify the program based on the Component Object Model (COM ). An ATL contains a set of C++ template classes to develop efficient COM objects.

Parse trees

In this blog, we will discuss the Parse trees in ATL and why we need Parse trees in ATL.

But before this, let's talk about the structure of parse trees.

Structure of Parse Trees

A parser tree represents the symbols that are terminal or non-terminal. A parse tree displays the syntactic structure of a string concerning context-free Grammar.
 

Non-terminal symbols are those symbols responsible for the creation of the sentence but are not present in the sentence. The terminal symbols are those characters or alphabets in a string generated with the grammar.
 

A parse tree shows an in-memory representation of the data with a structure that has proper grammar meaning. The tree data structure indicates the hierarchical relation between the nodes or data.

The parse tree is based on the precedence of operators.  First, we will traverse the deepest sub-tree. As a result, the parent node operator has lower priority than the sub-tree operator.
 

A parse tree follows some rules.

  • All nodes in a parse tree must be terminal symbols.
  • The intermediate nodes have to be nonterminal.
  • To get the original input string, use in-order traversal.
     

Example

a+x*y is the expression we will use to represent the pare tree.

parse tree

Parse Tree in ATL

We use Parse Tree in ATL to create a register script. The registry script in ATL is responsible for providing data-driven access to the system's registry.  The data-driven access is more efficient than API driven because it takes only one or two lines of code to enter a key in the script.

The ATL Control Wizard automatically generates a registry script in the COM environment. You can check out the script in the .rgs file.

With the help of parser trees, we can add multiple keys and subkeys in the script.
 

A parser tree has the following form:

<root-key>{<registry expression>}+

Where

<root-key> ::=
 HKEY_CLASSES_ROOT | HKEY_CURRENT_USER |
 HKEY_LOCAL_MACHINE | HKEY_USERS 

All these names mentioned in the root key expressions are names of the key of the user with their subkeys.
 

<registry-expression> ::=
  <Add-Key> | <Delete-Key>

<Add-Key> ::=
  [ForceRemove | NoRemove | val] <Key-Name> [<Key-Value>] [ { <Add-Key> } ]

<Delete-Key> ::=
  Delete <Key-Name>

<Key-Name> ::=
  '<AlphaNumeric>+'

<AlphaNumeric> ::=
  any non-null character.

<Key-Value> ::=
  <Key-Type> <Key-Name>

<Key-Type> ::=
  s | d

 

You can add multiple keys in the parse tree, and the important thing is registrar will opens the handle of a subkey until the parser is completed, which is more efficient than parsing one key at a time.

Example

HKEY_CLASSES_ROOT
{
    'MyKey'
    {
        'SubKey'
        {
            'newkey'
        }
    }
}

 

The registrar will first open the HKEY_CLASSES_ROOT/Mykey. It observes there is a subkey in MyKey, and then the registrar will not close the MyKey instead, it will keep the handle open and creates SubKey with Parent Handle.

Check out this problem - Duplicate Subtree In Binary Tree

Frequently Asked Questions

What is the other name of the parse tree?

A parse tree is also known as a derivate tree.

A parse tree follows which Grammar?

A parse tree follows context-free grammar.

What does ATL stand for?

ATL stands for the active template library.

Why do we need ATL?

We need ATL to provide efficient and easy-to-implement COM objects.

Conclusion

In this blog, we learned about the parse tree and how to use the parse tree in ATL to create a registrar script in ATL.

To learn more about ATL, check out the following articles.

 

To learn more about DSA, competitive coding, and many more knowledgeable topics, please look into the guided paths on Coding Ninjas Studio. Also, you can enroll in our courses and check out the mock test and problems available to you. Please check out our interview experiences and interview bundle for placement preparations.

Happy Coding!

Live masterclass