Logo

Syntax-Directed Translation

Syntax-Directed Translation

A context-free-grammar with some additional rules is known as a syntax-directed definition. In SDT, attributes are associated with grammar symbols and rules are associated with productions. The attributes can be any kind of number, type, table, string, etc.

In other words, we can say that; CFG + Semantic rules = SDT.

Inherited and Synthesized Attributes

  • SDT supports only these two attributes.
  • A synthesized attribute is a nonterminal attribute on the left-side or head of the production. This attribute depicts the information that is being passed to the parse tree. The synthesized attribute can take values only from its children.

Example: Consider a production X => YZ. If attributes of X depend on attributes of Y or Z, then it is known as synthesized attributes.

  • An inherited attribute is a nonterminal attribute on the right side of the production. This attribute can take values from their parents or siblings.

           Example: Consider a production X => YZ. If an attribute of Y depends on the                attribute of X or Z, then it is known as inherited attributes.

It is to note that terminals can have synthesized attributes but not inherited attributes.

Example:

Below is an example of a Syntax-directed definition of a simple desk calculator.

PRODUCTION                                    SEMANTIC RULES

L => E n                                                     L.val = E.val

E => E1 + T                                                E.val = E1.val + T.val

E => T                                                         E: val = T: val

T => T1 * F                                                 T: val = T 1 : val # F: val

T => F                                                         T: val = F: val

F => (E)                                                    F.val = E.val

F => digit                                                   F.val = digit.lexval

Related Topics

Optimization of Basic Blocks in Compiler Design

Optimization of Basic Blocks We can apply the optimization process on a basic block. While optimization, there is no need to change the set of expressions computed by the block. The basic...

3 minutes read.

Syntax Analysis Compiler Design

Syntax Analysis This article will describe the parsing method used in the compiler. The grammatical rule of programming language can be constructed with the help of context-free grammars or BNF (Backus–Naur...

3 minutes read.

LR Parser in Compiler Design

LR Parser The most popular type of bottom-up parsing is LR(K) parsing. The LR() parser scans the input from left – to – right, which is the actual abbreviation of L...

2 minutes read.

CLR Parsing Compiler Design

CLR Parsing CLR parsing refers to the canonical lookahead. We will use the canonical collection of LR(1) items for the construction of the CLR(1) parsing table. Generally, CLR(1) parsing has more...

6 minutes read.

Basic Blocks and Flow Graphs in Compiler Design

Basic Blocks and Flow Graphs In this section, we are going to learn how to work with basic block and flow graphs in compiler design. Basic Block The basic block is a set...

3 minutes read.

Machine-Independent Optimizations in Compiler Design

Machine-Independent Optimizations The main aim of machine-independent optimization is to improve the generated intermediate code so that compiler can get better target code. Eliminating unwanted code from the object code or replacing...

8 minutes read.

LR Parser Compiler Design

LR Parser LR parsing is a type of bottom-up parsing that is used to parse the large class of grammars. Here "L" stands for left-to-right scanning of the input "R" stands...

6 minutes read.

Run-Time Environments

Run-Time Environments Storage Organization Every target program has its own logical address, and an executable program runs in it. The logical address space has the location for each program value. The...

2 minutes read.

S-attributed and L-attributed SDTs

S-attributed and L-attributed SDTs STD stands for Syntax Directed Translation. When we associate some informal notations called semantic rules and the grammar, they are known as STD. So we can say...

2 minutes read.

Three-Address Code

Three-Address Code If there is at most one operator on the right side of the instruction, then the instruction will be the three-address code so that no arithmetic expressions are permitted....

2 minutes read.

Compiler Design Tutorial

Our compiler design tutorial will provide all the information about compiler from basic to advanced level. This compiler tutorial will help the student for their semester as well as for...

3 minutes read.

LALR 1 Parsing | Compiler Design

LALR (1) Parsing The LALR parsing refers to the "lookahead LR" that has many lesser steps than typical parsers based on LR(1) items. For constructing the LALR(1) parsing table, the canonical...

6 minutes read.

SLR 1 Parsing Compiler Design

SLR(1) Parsing It is a simple LR parsing. Most of the function of this parsing is the same as LR(0) parsing. The parsing table for both the parser vary. The SLR(1)...

5 minutes read.

Run-Time Storage Management

Run-Time Storage Management Every executing program has its own logical address space. Logical address space is partitioned into: Code: It is responsible for storing the executable target code. Static: It is used to...

3 minutes read.

Bottom-Up Parsing in Compiler Design

Bottom-Up Parsing A bottom-up parsing constructs the parse tree for an input string beginning from the bottom (the leaves) and moves to work towards the top (the root). Bottom-up parsing is...

6 minutes read.

Switch Case Statement Compiler Design

Case Statement The “case” or “switch” statement is available in various languages. The following is the syntax for the case statement: switch (E)  {             case V1: S1             case V2: S2 ...

1 minute read.

Derivation and Parse Tree in Compiler Design

Derivation and Parse Tree In this article, we will learn Derivation and Parse Tree. Derivations The parse tree can be constructed by taking a derivational view in which production is treated as rewriting...

4 minutes read.

Stack Allocation of Space

Stack Allocation of Space Almost all compilers for languages that use procedure, functions, or methods manage their run-time memory as a stack. Whenever a procedure is called, the local variable's space...

2 minutes read.

Phases of Compiler

Phases of Compiler The compilation process of a compiler goes through various phases. Each phase of the compiler takes the output from the previous as an input. Here we will see all...

2 minutes read.

Symbol Table Compiler Design

Symbol Table It is an important data structure used by the compiler. It stores information about various entities such as object, class, variable names, functions name, interfaces, procedure, literals, string etc.  The...

3 minutes read.