3. Syntax directed translations

Question 1

Syntax directed translation(SDT)

Answer 1

1. Syntax director translation has augmented(add extra) rules to grammar that facilitates semantic analysis
2. SDT involves passing information bottom - up or top down to parse tree in the form of attributes attached to notes
3. SDT rules use
   a. Lexical values of nodes
   b. Constants
   C. Attributes associated with the non terminals in their definition
4. The general approach to SDT is to construct a parse tree or a syntax tree and compute the values of attributes at the nodes of tree by visiting them in some order
5. ** This also helps in finding the errors**
6. To evaluate translation rules we can employee one depthfirst search travels on parse tree
7. Write about synthetic and inherited attributes
   eg: https://www.geeksforgeeks.org/syntax-directed-translation-in-compiler-design/
   - In Example, We should write Symantec rules for the given production rules
   - Then draw a parse tree
   - Now substitute the values and calculate the values
   adv:
8. Ease of implementation(Very easy to implement
9. SDT separates translation process from parsing process allowing it easier to modify and maintain the compiler and Separates translation concerns from parsing concerns makes it more modular and extensible compiler designs
10. Efficient code generation
    disadv:
11. Ltd expensiveness
12. Inflexibility
13. Ltd error recovery

Question 2

Syntax directed translation scheme

Answer 2

1. Postfix SDT
2. post fix translation scheme with parser stack implementation of it
3. SD T with actions inside the production
4. Eliminating left recursion from S D T
5. SDT’s for L attributed definitions

Question 3

Syntax directed definition

Answer 3

1. In SDD(Syntax directed definition) Along with the grammar we associate some informal notations and these notations are called as Symantic rules
   Grammar + Symantec rule = SDD
2. Here every nonterminal can get one Or more attributes or sometimes zero attributes depending on the type of attribute
3. The value of these attributes is evaluated by Symantec Rules Associated with the production rule
4. In semantic role attribute is value and it may hold anything like string number a memory location or a complex record
5. Here wherever a construct encounters in the programming language that it is translated according to the semantic rules define in the particular programming language
   Example
   Production Semantic Rules
   E → E + T E.val := E.val + T.val
   E → T E.val := T.val
   T → T * F T.val := T.val + F.val
   T → F T.val := F.val
   F → num F.val := num.lexval

–E.val is one of the attributes of E.
-num.lexval is the attribute returned by the lexical analyzer.

After the definition of SDD Write about annotated parse tree, types of attributes

Question 4

Annotated parse tree

Answer 4

The parse tree containing the values of attributes at each node for given input string is called annotated or decorated parse tree.
Features –
High level specification
Hides implementation details
Explicit order of evaluation is not specified

Question 5

Types of attributes

Answer 5

1. Synthesized attributes
2. Inherited attributes

Question 6

1. synthesized attributes:

Answer 6

The attributes whose values are computed from the values of attributes at children notes in parse tree
eg:
**E –> E1 + T { E.val = E1.val + T.val} **
E.val will be derived by adding the values E1.val and T.val (children nodes)
Procedure:
1. Write SDD using app. Symantec rules for each production in grammar given
2. Annotated parse trees Generated
3. attribute values are computed in bottom up manner
4. Value obtained at root node is the final o/p
According to the input strings the values are first declared to the child values and are denoted to upper notes or parent notes
eg:
https://www.geeksforgeeks.org/compiler-design-syntax-directed-definition/

Question 7

2. Inherited attributes

Answer 7

1. These attributes which derive their values from their parent or sibling notes
   eg:
   A –> BCD { C.in = A.in, C.type = B.type }
   Procedure of computation:
2. Construct S D D using Symantec actions or rules
3. Annotated parse trees generated
4. attribute values are computed top down manner
   eg: Example is little tough
   https://www.geeksforgeeks.org/compiler-design-syntax-directed-definition/

Question 8

Evaluation orders for SDD

Answer 8

1. Evaluation order for SBD includes how SDD is evaluated with the help of attributes, dependency graphs, semantic rules, and S & L attribute definitions
2. Sdd helps in semantic analysis in compiler so it is important to know how sdds are evaluated and their evaluation order
3. To calculate the evaluation we need to know dependency graph
   Dependency graph:
4. provides information about order of evaluation of attributes with the help of edges or semantic rules
5. If we need to evaluate the second node attribute, We should already been evaluated first node attribute
6. Edges represent the Symantec rules of the corresponding production
   Dependency graph rules
7. A Node independency graph corresponds to the node of the parse tree for each attribute
8. If we need to evaluate the second node attribute, We should already been evaluated first node attribute
   ** Ordering the evaluation of attributes**
9. An edge in the dependency graph represents that the attribute of the second node is dependent on the attribute of the 1st node for the further evaluation this order of evaluation gives a linear order called as topological order
10. There is no way to evaluate sdd on parse tree when there is cycle present in the graph, As no topological order exists in cycles
    eg:
    https://www.geeksforgeeks.org/evaluation-order-for-sdd/
    Production Table
    S.No. Productions Semantic Rules
11. S ⇢ A & B S.val = A.syn + B.syn
12. A ⇢ A1 # B A.syn = A1.syn * B.syn
    A1.inh = A.syn
13. A1 ⇢ B A1.syn = B.syn
14. B ⇢ digit B.syn = digit.lexval
    steps:
    **1. write semantic rules for given production(like above)
15. Draw annotated parse tree and calculate the values
16. Now draw dependency graph from annotated parse tree
17. Now we need to draw two tables
    Table1– contains two columns– Nodes And its attributes
    Table 2 - - contains add two columns- edges(from& to) And corresponding Symantec rules**

S - attributed definitions
Can have only synthesised attributes
- in this type of definitions semantic roles are placed at end of the production rule only
- Evaluation is based on bottom up parsing
eg:
S ⇢ AB { S.x = f(A.x | B.x) }
L - attributed definitions
Can have both synthesised and inherited( Restricted inherited as attributes can only have be taken from left sibling or parent)
- In this type of definition semantic rules can be placed anywhere in RHS of the production
- It’s evaluation is based on in order topological sorting
eg:
S ⇢ AB {A.x = S.x + 2} or S ⇢ AB { B.x = f(A.x | B.x) } or S ⇢ AB { S.x = f(A.x | B.x) }
** Semantic Rules with controlled side-effects:**
Side effects are the program fragment contained within semantic rules. These side effects in SDD can be controlled in two ways: Permit incidental side effects and constraint admissible evaluation orders to have the same translation as any admissible order.

Question 9

Postfix translation schemes

Answer 9

1. Sdt’s which has its semantic actions at the right end of the production are called as post fix translation schemes
2. This type of translation of SDT has its corresponding semantics at the last in the rhs of the production
   Example:
   S ⇢ A#B{S.val = A.val * B.val}
   A ⇢B@1{A.val = B.val + 1}
   B ⇢num{B.val = num.lexval}

Question 10

parser-Stack implementation of postfix SDTs

Answer 10

Postfix is STDS are implemented when the
1. Symantec actions are at the right end of the production
2. with bottom up parser(like LR Parser or shift-reduce parser)
3. with the** non terminals having synthesised attributes**
4. Arsenal contains record for nonterminals in the grammar and their corresponding attri
5. nonterminal symbols of the production are pushed into a parser stack
6. The attributes are synthesised and semantic actions are at the right ends the attributes of the nonterminals are evaluated for the symbol in the top of the stack
production:
A ⇢ BC{A.str = B.str . C.str}
B ⇢a {B.str = a}
C ⇢b{C.str = b}

Initially, the parser stack:
B C Non-terminals
B.str C.str Synthesized attributes
⇡
Top of Stack
After reductuon occurs(A—> BC)
A Non-terminals
A.str Synthesized attributes
⇡
Top of stack

Question 11

Difference between SDD and SDT

Answer 11

Syntax directed translation refers to the translation of a string into an array of actions Syntax directed definition is a context-free grammar where attributes and rules are combined together and associated with grammar symbols and productions respectively.