Home » Compiler Design

Operator Precedence Parser

In this article, we are going to learn about Operator precedence parser in Compiler Design, and other related terminologies.
Submitted by Anusha Sharma, on March 28, 2018

What is Operator Precedence Parser?

1. It is constructed for both ambiguous and unambiguous grammar.
2. It is constructed only for operator grammar.
3. It takes the grammar with less complexity.
4. It cannot be constructed for every grammar.
5. It is generally used for the languages which are mostly useful in scientific notations.

Syntax Directed Translation

Symantec analyzer verify the each and every sentence of the source code .Syntax analyzer takes care of the operator and working on required number of operands or not. Symantec analysis can be implemented by parsing along with the semantic rules by attaching the semantic rules for each and every grammar rule.

Other Applications of SDT

1. To store the type information into symbol table.
2. To build the syntax tree.
3. To generate intermediate code.
4. To generate target code.
5. To evaluate the algebraic expression.

Annotated Parse Tree

The parser tree shows the attribute value at each and every node is known as annotated parse tree.

Types of Attributes

Based on the process of evaluation attribute can be classified into 2 types:

1. Synthesis Attribute: The attribute whose value is evaluated in terms of attributes value of its children is called synthesized attribute.
2. Inherited Attribute: The attribute whose value is calculated in terms of attribute value of its parent or siblings is called inherited attribute.

Types OF SDT

SDT can be defined into two ways,

1. S-attribute: It uses only synthesized attributes. Symantec rules can be placed at the right end. Attributes are evaluated during bottom up parsing.
2. L-attribute: It uses synthesized and inherited attributes. Inherited attributes values are inherited from the parent or left sibling. Symantec rule can be placed on the RHS. Attributes are evaluated using depth first right to left process.

Optimization

The process of reducing the number of instructions to improve the performance of the compiler without affecting the outcome of source program is known as optimization.

Optimization is of two types:

1. Machine independent optimization or language dependent optimization.
2. Machine dependent optimization or language independent optimization.

Machine independent optimization

The optimization of three address code is called machine dependent optimization.

Types of machine independent optimization

1. Local: The optimization which is performed within a block is called local optimization, where block is collection of three address statements.
2. Global: The optimization which is performed at program level is known as global optimization. The complete source program is divided into blocks with the help of leaders.
3. Loop: The process of optimization within the loop is called loop optimization.

Characteristics of Local And Global Optimization

1. Constant propagation: Replacing the value of constant before compile time is known as constant propagation.
2. Strength reduction: Replacing the costly operator at cheapest operator is known as strength reduction.
3. Constant folding: Replacing the value of expression before compile time is known as constant folding.
4. Redundant: Avoiding the evaluation of any expression more than once.