Unit - 3

Syntax-directed Translation

Q1) Distinguish the parse tree and syntax tree?

A1) Differences are:

Q2) Translate the following expression to quadruple, triple

m + n x o / p ↑ q + n x o

A2) The code with three addresses is as follows:

T1 = p ↑ q

T2 = n x o

T3 = T2 / T1

T4 = n x m

T5 = m + T3

T6 = T5 + T4

These statements are expressed as follows by quadruples:

These statements are expressed as follows by triples:

Q3) What are the syntax-directed translation schemes?

A3) Syntax directed translation schemes -

In syntax-directed translation, certain informal notations are associated with the grammar and these notations are called semantic rules.

Therefore, we may say that

Grammar + semantic rule = SDT (syntax directed translation) 

●      In syntax-directed translation, depending on the form of the attribute, each non-terminal may get one or more attributes, or sometimes 0 attributes.

●      Semantic rules aligned with the output rule determine the value of these attributes.

●      Whenever a construct meets in the programming language in Syntax driven translation, it is translated according to the semantic rules specified in that particular programming language.

Example:

One of E's attributes is E.val.

The attribute returned by the lexical analyzer is num.lexval.

Q4) What do you mean by declaration?

A4) Declaration

We need to layout storage for the declared variables when we encounter declarations.

You can manage declaration with a list of names as follows:

D T id; D | ε

T B C | record ‘{‘D’}’

B int | float

C ε | [ num] C

●      A declaration sequence is generated by Nonterminal D.

●      A fundamental, array, or record form is generated by nonterminal T.

●      One of the basic int or float types is generated by nonterminal B.

●      Nonterminal C produces a string of zero or more integers, each surrounded by brackets for "component"

We create an ST (Symbol Table) entry for every local name in a procedure, containing:

Production:

D →    integer, id 

   D →   real, id 

   D →   D1, id 

For declarations, an appropriate transformation scheme would be:

ENTER is used to enter the table of symbols and ATTR is used to trace the form of data.

Q5) Describe a procedure call and case statement?

A5) Procedure call

❏      Procedure for a compiler is a significant and widely used programming construct. It is used to produce good code for calls and returns for processes.

❏      The run-time routines that manage the passing, calling, and returning of procedure arguments are part of the packages that support run-time.

Calling sequence:

A series of acts taken on entry and exit from each procedure is part of the translation for a call. In the calling sequence, the following actions take place:

●      When a procedure call occurs, space for the activation record is allocated.

●      Review the so-called method statement.

●      Develop environment pointers to allow data in enclosing blocks to be accessed by the named procedure.

●      Save the state of the calling process so that after the call it can restart execution.

●      Save the return address as well. It is the address of the place to which, after completion, the so-called routine must be moved.

●      Finally, the calling procedure creates a hop to the beginning of the code.

Case statement 

In some languages, the "switch" or "case" statement is available. The syntax for switch-statement is as shown below:

Switch-statement syntax s with expression

begin

   case value: statement

case value: statement

..

case value: statement

default: statement

end

There is a selector expression to be evaluated, followed by n constant values that may be taken by the expression, including a default value that, if no other value does, always matches the expression. Code to: is the intended translation of a turn.

1. Assess an expression.

2. Find which value is equivalent to the value of the expression in the list of cases.

3. Conduct the assertion that is correlated with the found meaning.

Find the following paragraph about the switch:

switch E

begin

case V1: S1

case V2: S2

case Vn-1: Sn-1

default: Sn

end

This case statement is translated into an intermediate code in the following form: Translation of a case statement.

code to analyze E into t goto test

goto TEST 

                L1:         code for S1 

                              goto NEXT 

                L2:         code for S2 

                              goto NEXT 

                              . 

                              . 

                              . 

                Ln-1:      code for Sn-1 

                              goto NEXT 

                Ln:         code for Sn 

goto NEXT 

                TEST:      if T = V1 goto L1      

                               if T = V2 goto L2 

                               . 

                               . 

                               . 

                               if T = Vn-1 goto Ln-1 

                               goto  

NEXT: 

A new temporary T and two new label tests are created when the switch keyword is seen, and next.

When the case keyword happens, a new label Li is generated and inserted into the symbol table for each case keyword. A stack is put with the Vi value of each case constant and a pointer to this table-symbol entry.

Q6) Define the parse tree and syntax tree?

A6) Parse tree

It contains more information than needed when you build a parse tree. It's very hard, therefore, to decode the parse tree compiler.

According to some context-free grammar, the parse tree reflects the syntactic structure of a string. It defines the input language's syntax. For various types of constituents, the parse tree does not use separate symbol forms.

Phrase structure grammars or dependency grammars are the basis for constructing a parse tree. Parse trees can be created for natural language phrases and when processing programming languages.

Take the following tree as an example:

●      The bulk of the leaf nodes in the parse tree are single-child to their parent nodes.

●      We may delete this extra information in the syntax tree.

●      A version of the parse tree is a syntax tree. Interior nodes are operators in the syntax tree and leaves are operands.

●      The syntax tree is typically used when the tree structure describes a programme.

Syntax Tree

The abstract syntactic structure of source code written in a programming language is represented by a syntax tree. Rather than elements such as braces, semicolons that end sentences in some languages, it focuses on the laws.

It is also a hierarchy divided into many parts with the elements of programming statements. The tree nodes denote a construct that exists in the source code.

A form id + id * id will have the following tree of syntax:

It is possible to represent the Abstract Syntax Tree as:

In a compiler, abstract syntax trees are significant data structures. It includes the least information that is redundant.

Q7) What is the Boolean expression?

A7) Boolean expression

There are two main uses of Boolean expressions. They are used in the estimation of logical values. They are often used when using if-then-else or while-do as a conditional expression.

Consider the grammar

E → E OR E 

E → E AND E 

E → NOT E  

E → (E) 

E → id relop id 

E → TRUE 

E → FALSE 

The relop is denoted by <, >, <, >

The AND and OR are still related. NOT has a higher precedent than AND and OR, ultimately.

To generate the three address codes, the EMIT function is used and the newtemp() function is used to generate the temporary variables.

The next state is found in the E → id relop id2 and provides the index of the next three address statements in the output sequence.

Here is an example of how the three-address code is created using the above translation scheme.

p>q AND r<s OR u>r 

     100: if p>q goto 103 

     101: t1: =0 

     102: goto 104 

     103: t1: =1 

     104: if r>s goto 107 

     105: t2: =0 

     106: goto 108 

     107: t2: =1 

     108: if u>v goto 111 

     109: t3: =0 

     110: goto 112 

     111: t3: = 1 

     112: t4: = t1 AND t2 

     113: t5: = t4 OR t3 

Q8) Explain top-down parser?

A8) Top-down parser

The top-down parsing technique parses the input and begins to construct a parse tree from the root node, moving progressively down to the leaf nodes.

Recursive Descent Parsing

A top-down parsing technique that builds the parse tree from the top and reads the input from left to right is recursive descent. For any terminal and non-terminal entity, it uses procedures. The input is recursively parsed by this parsing technique to make a parse tree, which may or may not require back-tracking.

But the related grammar (if not left-faced) does not prevent back-tracking. Predictive parsing is known as a form of recursive-descent parsing that does not require any back-tracking.

Back-tracking

Top-down parsers start with the root node (start symbol) and match the production rules with the input string to replace them (if matched). Take the following CFG example to grasp this.

S → rXd | rZd

X → oa | ea

Z → ai

A top-down parser, for an input string: read, will function like this:

It will start with S from the rules of production and match its yield to the input's leftmost letter, i.e., 'r'. The very development of S (S→ rXd) corresponds to it. So, the top-down parser progresses to the next letter of input (i.e., 'e'). The parser attempts to extend the 'X' non-terminal and verifies its output from the left X, (x → oa). It does not fit the input symbol next to it.

So, the backtracks of the top-down parser to obtain the next X, (X→ ea) output guideline.

Now, in an ordered way, the parser matches all the input letters. The string has been approved

Predictive Parser

The Predictive Parser is a recursive descent parser that can predict which output is to be used to replace the input string. Backtracking does not suffer from the predictive parser.

The predictive parser uses a look-ahead pointer to accomplish its functions, which points to the following input symbols. The predictive parser places certain restrictions on the grammar to make the parser back-tracking free and accepts only a grammar class known as LL(k) grammar.

In recursive descent parsing, for a single instance of input, the parser can have more than one output to choose from, while in the predictive parser, each stage has at most one production to choose from. There may be instances where the input string does not fit the production, making the parsing procedure fail.

LL Parser

LL grammar is approved by an LL Parser. To achieve simple implementation, LL grammar is a subset of context-free grammar but with certain constraints to get the simpler version.

The parser of LL is denoted as LLL (k). The first L in LL(k) parses the input from left to right, the second L in LL(k) is the left-most derivation, and the number of looks ahead is expressed by k itself. In general, k = 1, so LL(k) can also be written as LL(k) (1)

Q9) What is the postfix translation?

A9) Postfix translation

The translation rule of A.CODE in development A alpha consists of the concatenation of the translations of the CODE of the non-terminals in alpha in the same order as the non-terminals appear in alpha.

Postfix translation of while statement

Production

S   → while M1 E do M2 S1

This can be measured as:

S →    C S1 

   C →    W E do 

   W →    while 

A perfect solution for transformation would be

Postfix translation of for statement

Production

S     for L = E1 step E2 to E3 do S1

This can be measured as:

F →    for L 

   T →   F = E1 by E2 to E3 do 

   S →   T S1 

Q10) What is the intermediate code?

A10) Intermediate code

To convert the source code into the computer code, intermediate code is used. Between the high-level language and the computer language lies the intermediate code.

Fig 2: the position of the intermediate code generator

❏      If the compiler converts the source code directly into the machine code without creating intermediate code, then each new machine needs a complete native compiler.

❏      For all compilers, the intermediate code holds the research section the same, which is why it does not require a complete compiler for each specific machine.

❏      Input from its predecessor stage and semantic analyzer stage is obtained by the intermediate code generator. This takes feedback in the form of an annotated tree of syntax.

❏      The second stage of the compiler synthesis process is modified according to the target machine by using the intermediate code.

Intermediate representation:

It is possible to represent the intermediate code in two ways:

The intermediate code of the high level can be interpreted as the source code. We can easily add code modifications to boost the performance of the source code. Yet there is less preference for optimizing the goal machine.

2.     Low-level intermediate code:

The low-level intermediate code is similar to the target computer, making it ideal for registering and allocating memory, etc. It is used for optimizations depending on the machine.