Computer Science Engineering (CSE) Exam  >  Computer Science Engineering (CSE) Notes  >  Compiler Design  >  A Translator for Simple Expressions: Simple Syntax Directed Translator

A Translator for Simple Expressions: Simple Syntax Directed Translator | Compiler Design - Computer Science Engineering (CSE) PDF Download

A Translator for Simple Expressions

1 Abstract and Concrete Syntax

2 Adapting the Translation Scheme

3 Procedures for the Nonterminals

4 Simplifying the Translator

5 The Complete Program

Using the techniques of the last three sections, we now construct a syntax-directed translator, in the form of a working Java program, that translates arithmetic expressions into postfix form. To keep the initial program manage-ably small, we start with expressions consisting of digits separated by binary plus and minus signs. We extend the program in Section 2.6 to translate ex-pressions that include numbers and other operators. It is worth studying the translation of expressions in detail, since they appear as a construct in so many languages.

A syntax-directed translation scheme often serves as the specification for a translator. The scheme in Fig. 2.21 (repeated from Fig. 2.15) defines the translation to be performed here.

A Translator for Simple Expressions: Simple Syntax Directed Translator | Compiler Design - Computer Science Engineering (CSE)

Often, the underlying grammar of a given scheme has to be modified before it can be parsed with a predictive parser. In particular, the grammar underlying the scheme in Fig. 2.21 is left recursive, and as we saw in the last section, a predictive parser cannot handle a left-recursive grammar.

We appear to have a conflict: on the one hand we need a grammar that facilitates translation, on the other hand we need a significantly different gram-mar that facilitates parsing. The solution is to begin with the grammar for easy translation and carefully transform it to facilitate parsing. By eliminating the left recursion in Fig. 2.21, we can obtain a grammar suitable for use in a predictive recursive-descent translator.

 

1. Abstract and Concrete Syntax

A useful starting point for designing a translator is a data structure called an abstract syntax tree. In an abstract syntax tree for an expression, each interior node represents an operator; the children of the node represent the operands of the operator. More generally, any programming construct can be handled by making up an operator for the construct and treating as operands the semantically meaningful components of that construct.

In the abstract syntax tree for 9 - 5 + 2 in Fig. 2.22, the root represents the operator +. The subtrees of the root represent the subexpressions 9 - 5 and 2. The grouping of 9 - 5 as an operand reflects the left-to-right evaluation of operators at the same precedence level. Since - and + have the same precedence, 9 - 5 + 2 is equivalent to ( 9 - 5 ) + 2 .

Abstract syntax trees, or simply syntax trees, resemble parse trees to an extent. However, in the syntax tree, interior nodes represent programming constructs while in the parse tree, the interior nodes represent nonterminals. Many nonterminals of a grammar represent programming constructs, but others are "helpers" of one sort of another, such as those representing terms, factors, or other variations of expressions. In the syntax tree, these helpers typically are not needed and are hence dropped. To emphasize the contrast, a parse tree is sometimes called a concrete  syntax tree,  and the underlying grammar is called a  concrete  syntax for the  language.

In the syntax tree in Fig.  2.22,  each interior node is associated with an operator,  with  no "helper"  nodes  for  single  productions  (a production  whose body consists of a single nonterminal, and nothing else) like expr —»• term or for e-productions like rest -> e.

It is desirable for a translation scheme to be based on a grammar whose parse trees are as close to syntax trees as possible. The grouping of subexpressions by the grammar in Fig. 2.21 is similar to their grouping in syntax trees. For example, subexpressions of the addition operator are given by expr and term in the production body expr+ term.

 

2. Adapting the Translation Scheme

The left-recursion-elimination technique sketched in Fig. 2.20 can also be ap-plied to productions containing semantic actions. First, the technique extends to multiple productions for A. In our example, A is expr, and there are two left-recursive productions for expr and one that is not left recursive. The technique transforms the productions 

A Translator for Simple Expressions: Simple Syntax Directed Translator | Compiler Design - Computer Science Engineering (CSE) 

Second, we need to transform productions that have embedded actions, not just terminals and nonterminals. Semantic actions embedded in the productions are simply carried along in the transformation, as if they were terminals.

Example 2 . 1 3 :  Consider the translation scheme of Fig. 2.21.  Let

 A Translator for Simple Expressions: Simple Syntax Directed Translator | Compiler Design - Computer Science Engineering (CSE)

Then the left-recursion-eliminating transformation produces the translation scheme in Fig. 2.23. The expr productions in Fig. 2.21 have been transformed into the productions for expr, and a new nonterminal rest plays the role of R.

The productions for term are repeated from Fig. 2.21.  Figure 2.24 shows how 9-5+2 is translated using the grammar in Fig. 2.23. •

A Translator for Simple Expressions: Simple Syntax Directed Translator | Compiler Design - Computer Science Engineering (CSE)A Translator for Simple Expressions: Simple Syntax Directed Translator | Compiler Design - Computer Science Engineering (CSE)

A Translator for Simple Expressions: Simple Syntax Directed Translator | Compiler Design - Computer Science Engineering (CSE)
A Translator for Simple Expressions: Simple Syntax Directed Translator | Compiler Design - Computer Science Engineering (CSE)

Left-recursion elimination must be done carefully, to ensure that we preserve the ordering of semantic actions. For example, the transformed scheme in Fig. 2.23 has the actions { print ('+') } and { print(' - ') } in the middle of a production body, in each case between nonterminals term and rest. If the actions were to be moved to the end, after rest, then the translations would become incorrect. We leave it to the reader to show that 9-5+2 would then be translated incorrectly into 952+-, the postfix notation for 9-(5+2), instead of the desired 95-2+, the postfix notation for (9-5)+2.

 

3. Procedures for the Nonterminals

Functions expr, rest, and term in Fig. 2.25 implement the syntax-directed trans-lation scheme in Fig. 2.23. These functions mimic the production bodies of the  corresponding nonterminals.  Function  expr implements  the  production expr ->  term  rest by the calls term() followed  by  rest().

A Translator for Simple Expressions: Simple Syntax Directed Translator | Compiler Design - Computer Science Engineering (CSE)

Function rest implements the three productions for nonterminal rest in Fig. 2.23. It applies the first production if the lookahead symbol is a plus sign, the second production if the lookahead symbol is a minus sign, and the production rest e in all other cases. The first two productions for rest are implemented by the first two branches of the if-statement in procedure rest. If the lookahead symbol is +, the plus sign is matched by the call match('+'). After the call term(), the semantic action is implemented by writing a plus character. The second production is similar, with - instead of +. Since the third production for rest has e as its right side, the last else-clause in function rest does nothing.

The ten productions for term generate the ten digits. Since each of these productions generates a digit and prints it, the same code in Fig. 2.25 imple-ments them all. If the test succeeds, variable t saves the digit represented by lookahead so it can be written after the call to match. Note that match changes the lookahead symbol, so the digit needs to be saved for later printing.5

 

4. Simplifying the Translator

Before showing a complete program, we shall make two simplifying transfor-mations to the code in Fig. 2.25. The simplifications will fold procedure rest into procedure expr. When expressions with multiple levels of precedence are translated, such simplifications reduce the number of procedures needed.

First, certain recursive calls can be replaced by iterations. When the last statement executed in a procedure body is a recursive call to the same proce-dure, the call is said to be tail recursive. For example, in functionrest, the calls of rest() with lookahead + and - are tail recursive because in each of these branches, the recursive call to rest is the last statement executed by the given call of rest.

For a procedure without parameters, a tail-recursive call can be replaced simply by a jump to the beginning of the procedure. The code for rest can be rewritten as the pseudocode of Fig. 2.26. As long as the lookahead symbol is a plus or a minus sign, procedure rest matches the sign, calls term to match a digit, and continues the process. Otherwise, it breaks out of while loop and returns from  rest.

A Translator for Simple Expressions: Simple Syntax Directed Translator | Compiler Design - Computer Science Engineering (CSE)

Second, the complete Java program will include one more change. Once the tail-recursive calls to rest in Fig. 2.25 are replaced by iterations, the only remaining call to rest is from within procedure expr. The two procedures can therefore be integrated into one, by replacing the call restQ by the body of procedure rest.

A Translator for Simple Expressions: Simple Syntax Directed Translator | Compiler Design - Computer Science Engineering (CSE) 

5. The Complete Program

The complete Java program for our translator appears in Fig. 2.27. The first line of Fig. 2.27, beginning withimport, provides access to the package j ava. io for system input and output. The rest of the code consists of the two classes Parser and Postfix. Class Parser contains variable lookaheadand functions

 Parser, expr, term, and match.

Execution begins with function main, which is defined in class Postfix. Function main creates an instance parse of class Parser and calls its function expr to parse an expression.  

The function Parser, with the same name as  its class,  is a  constructor, it is called automatically when an object of the class is created. Notice from its definition at the beginning of class Parser that the constructor Parser initializes variable lookahead by reading a token. Tokens, consisting of single characters, are supplied by the system input routine read, which reads the next character from the input file. Note that lookahead is declared to be an integer, rather than a character, to anticipate the fact that additional tokens other than single characters will be introduced in later sections.

Function expr is the result of the simplifications discussed in Section 2.5.4; it implements nonterminals expr and rest in Fig. 2.23. The code for expir in Fig. 2.27 calls term and then has a while-loop that forever tests whether lookahead matches either ' + ' or ' - ' . Control exits from this while-loop when it reaches the return statement. Within the loop, the input/output facilities of the System class are used to write a character.

Function term uses the routine isDigit from the Java class Character to test if the lookahead symbol is a digit.  The routine  isDigit expects to be applied to a character; however, lookahead is declared to be an integer, anticipating future extensions. The construction (char) lookahead casts or coerces lookahead to be a character. In a small change from Fig. 2.25, the semantic action of writing the lookahead character occurs before the call to match.

The function match checks terminals; it reads the next input terminal if the lookahead symbol is matched and signals an error otherwise by executing  throw new  Error("syntax error");

This  code creates a new exception of class Error and supplies it the string syntax error as an error message. Java does not require Error exceptions to be declared in a throws clause, since they are meant to be used only for abnormal events that should never occur.6 6 Error handling can be streamlined using the exception-handling facilities of Java. One ap-proach is to define a new exception, say SyntaxError, that extends the system class Exception. Then, throw SyntaxError instead of Error when an error is detected in either term or match. Further, handle the exception in main by enclosing the call parse.expr() within a try state-ment that catches exception SyntaxError, writes a message, and terminates. We would need to add a class SyntaxError to the program in Fig. 2.27. To complete the extension, in addition to IOException, functions match and term must now declare that they can throw SyntaxError. Function expr, which calls them, must also declare that it can throw SyntaxError.

 A Translator for Simple Expressions: Simple Syntax Directed Translator | Compiler Design - Computer Science Engineering (CSE)
A Translator for Simple Expressions: Simple Syntax Directed Translator | Compiler Design - Computer Science Engineering (CSE)

A Few Salient Features of Java

Those unfamiliar with Java may find the following notes on Java helpful in reading the code in Fig. 2.27:

A class in Java consists of a sequence of variable and function defi-nitions.

 Parentheses enclosing function parameter lists are needed even if there are no parameters; hence we write expr() and term(). These functions are actually procedures, because they do not return values, signified by the keyword void before the function name.

  • Functions communicate either by passing parameters "by value" or by accessing shared data. For example, the functions expr() and term() examine the lookahead symbol using the class variable lookaheadthat they can all access since they all belong to the same class Parser.

Like C, Java uses = for assignment, == for equality, and != for in-equality.

The clause "throws IOException" in the definition of term() de-clares that an exception calledIOException can occur. Such an exception occurs if there is no input to be read when the functionmatch uses the routine read. Any function that calls match must also declare that anIOException can occur during its own execution.

The document A Translator for Simple Expressions: Simple Syntax Directed Translator | Compiler Design - Computer Science Engineering (CSE) is a part of the Computer Science Engineering (CSE) Course Compiler Design.
All you need of Computer Science Engineering (CSE) at this link: Computer Science Engineering (CSE)
26 videos|66 docs|30 tests

Top Courses for Computer Science Engineering (CSE)

FAQs on A Translator for Simple Expressions: Simple Syntax Directed Translator - Compiler Design - Computer Science Engineering (CSE)

1. What is a syntax-directed translator?
Ans. A syntax-directed translator is a computer program that translates source code from one language to another based on the syntax rules of both languages. It generates the target code while parsing the input source code, making it an efficient and automatic way to translate programs.
2. How does a syntax-directed translator work?
Ans. A syntax-directed translator works by associating translation rules with the productions of a grammar. These translation rules are usually embedded within the grammar and specify the actions to be taken during parsing. As the input source code is parsed, the translator applies the translation rules to generate the corresponding target code.
3. What is the role of a simple syntax-directed translator in computer science engineering?
Ans. A simple syntax-directed translator plays a crucial role in computer science engineering by facilitating the translation of source code between different programming languages. It helps software developers to convert programs written in one language to another language, enabling cross-platform compatibility and code reuse.
4. How does a syntax-directed translator handle simple expressions?
Ans. In the context of a syntax-directed translator, simple expressions are typically handled by defining translation rules for each type of expression. For example, a rule may specify that an arithmetic expression should be translated into a sequence of target code instructions that perform the corresponding computation.
5. What are some advantages of using a syntax-directed translator for translating simple expressions?
Ans. Some advantages of using a syntax-directed translator for translating simple expressions include: - Automation: Syntax-directed translation automates the process of converting source code, saving time and effort for software developers. - Accuracy: Syntax-directed translation follows strict syntax rules, minimizing the chances of translation errors. - Efficiency: By translating source code during parsing, a syntax-directed translator can generate target code in an efficient manner. - Flexibility: Syntax-directed translation allows for easy modification and extension of translation rules, making it adaptable to different programming languages and expressions.
26 videos|66 docs|30 tests
Download as PDF
Explore Courses for Computer Science Engineering (CSE) exam

Top Courses for Computer Science Engineering (CSE)

Signup for Free!
Signup to see your scores go up within 7 days! Learn & Practice with 1000+ FREE Notes, Videos & Tests.
10M+ students study on EduRev
Related Searches

Free

,

A Translator for Simple Expressions: Simple Syntax Directed Translator | Compiler Design - Computer Science Engineering (CSE)

,

A Translator for Simple Expressions: Simple Syntax Directed Translator | Compiler Design - Computer Science Engineering (CSE)

,

past year papers

,

pdf

,

mock tests for examination

,

study material

,

Summary

,

Previous Year Questions with Solutions

,

shortcuts and tricks

,

Extra Questions

,

Exam

,

Sample Paper

,

MCQs

,

Important questions

,

ppt

,

Viva Questions

,

A Translator for Simple Expressions: Simple Syntax Directed Translator | Compiler Design - Computer Science Engineering (CSE)

,

Semester Notes

,

video lectures

,

Objective type Questions

,

practice quizzes

;