Do you think IIT Guwahati certified course can help you in your career?
Introduction
People often don't know how to make Syntax-Directed Translation Schemes and get confused. Are you also the one? You are in the right place.
We will first learn about Syntax-Directed Translation Schemes and then their example for better understanding. Furthermore, we will discuss usage of Syntax-Directed Translation Schemes for given data.
Let's dive into the topic now to know more in detail.
Syntax-Directed Translation Schemes
It is context-free grammar, and we use it to evaluate the order of semantic rules. The semantic rules are contained on the right side of the productions in the translation scheme. Braces are used to enclose the position where action has to be taken, which is also written on the right side of the production.
It's a notation in which each context-free Grammar production is linked to a collection of semantic rules or actions. Each grammar symbol is connected to a set of attributes. Syntax-directed definitions are thus formed by combining the language and the collection of semantic actions.
The generation of intermediate code, adding the information in the symbol table about constructs type, or generation of object code can be the translation. Modern compilers hide extra implementation details to simplify the user's life by using syntax-directed translation and removing the user's need to indicate the order in which semantic rules should be evaluated.
Semantic Actions
Whenever the parser recognizes the input string generated by a context-free grammar, this action gets executed.
For Example, A → BC {Semantic Action}
Curly braces are used to write semantic action. There's a production attached to it.
Note-
When A is expanded to derive BC, which derives string ‘w’ in the Top-Down Parser, semantic action is taken.
When BC is reduced to A in a Bottom-Up Parser, semantic action is generated.
Syntax Directed Translation Scheme for Postfix Code
The operators appear after operands in postfix notation. That means we take out operators between operands and put them after operands.
For example,
Consider the grammar
A → A(1) + A(2)
A → A(1) ∗ A(2)
A → ( A(1))
A → id
The Postfix Translation for the grammar is shown in the table below.
Production
Semantic Action
A → A(1) + A(2)
A. CODE = A(1). CODE| |A(2). CODE | |'+'
A → A(1) ∗ A(2)
A. CODE = A(1). CODE| |A(2). CODE | |'∗'
A → (A(1))
A. CODE = A(1). CODE
A → id
A. CODE = id
Translation for Postfix Notation
‘A.CODE’ denotes property or translation of the grammatical symbol A. It refers to a series of three-address statements that evaluates A. The concatenation (| |) of the translation of the nonterminals on the right followed by the operator is the translation of the nonterminal on the left of each production.
The translation value ‘A.CODE’ is the concatenation of two translations ‘A(1). CODE’ & ‘A(2). CODE’ and symbol '+' in the first production, which is A → A(1) + A(2)
The translation value ‘A.CODE’ is the concatenation of two translations ‘A(1). CODE’ & ‘A(2). CODE’ and symbol '*' in the first production, which is A → A(1) ∗ A(2)
The symbol | | represents the concatenation.
The translation of parenthesized expression is the same as that of unparenthesized expression in the third production, A→ (A(1)).
The translation of any identifier in the fourth production E → id is the identifier itself.
The attributes and translations for the grammatical sign A are listed below.
A. VAL → It tells the value of E.
A. PLACE → It describes the name that will hold the value of the expression.
A. CODE → The sequence of three address statements computing the expression.
What are the three different types of address codes?
Three-address code is a short, intermediate code to create and convert to machine code. It only uses three locations and one operator to describe an expression, and the value computed at each instruction is saved in a compiler-generated temporary variable.
What is context-free grammar?
A context-free grammar is a type of formal grammar that generates all available strings in a formal language.
G is a context-free grammar defined by four tuples:
G = (V, T, P, S) where G is grammar.
What is top-down parsing?
The top-down parsing technique parses the input and begins building a parse tree from the root node to the leaf nodes.
What is bottom-up parsing?
Bottom-up parsing begins from a tree's leaf nodes and progresses upward until it reaches the root node. We start with a sentence and work backward through the production rules to arrive at the start symbol.
What is prefix notation?
The operators appear before operands in prefix notation. That means we take out operators between operands and put them before operands.
Conclusion
In this article, we have extensively discussed the topic of Syntax-Directed Translation Schemes.
We hope that this blog has helped you enhance your knowledge regarding encryption
85+ registered