compiler design lab experiments

List of Programs

Set-A : Implementation of Lexical Analyzer

Set-B : Implementation of Parsers (Syntax Analyzers)

Set-C : Syntax Directed Translation (Using YACC Tool)

Acknowledgements

Department of Computer Science and Engineering 'in association with' Teaching Learning Centre A Higher Education Teaching Learning Scheme 'under' Pandit Madan Mohan Malaviya National Mission on Teachers and Teaching

About this Lab

Course objectives:.

• To develop Undergraduate Level Laboratory Manual for Compiler Design course in a Learner-Centered Approach.
• To enable the students to understand conceptually the experiments in this course.
• To provide the student with both audio and video recordings of the entire process of working with experiments.
• To encourage the students to write programs by themselves.
• To enable the students to write their own compiler.

Course Outcomes:

• Implement simple Lexical Analyzers.
• Generate predictive parsing tables for CFGs.
• Apply LEX and YACC tools.
• Design and Implement LR parser.
• Implement Intermediate code generation for subset C language.

In this Lab course, we have given a total of 30 questions, the outcome for each of these questions, their answers and a video recording to show the execution of the code. All these 30 questions are made into three sets, where each set covers a particular topic of Compiler Design: Lexical Analysis, Syntax Analysis and Syntax Directed Translation.

The programming languages used here are C/C++, LEX and YACC tools. Those who want to execute the programs can directly copy the code from the pdf document given here and execute them. The videos are also given to show the execution process. These programs are written by us or our students.

All these programs require standard C/C++ compiler and some may require additional compiler tools LEX and YACC. Dev-C++, LEX and YACC tools can be downloaded from the following links.

Flex (Fast Lexical analyser)

Bison (Improved Yacc)

GNU C/C++ compiler is available on all Linux systems. On ubuntu Linux system directly flex and bison tools can be installed using "apt". If any other distribution is used follow suitable instructions for installation of flex and bison.

$ sudo apt install flex

$ sudo apt install bison

Students/Users are encouraged to download the programs, modify and experiment with them.

A1: Implementation of CYK Algorithm (you have studied in ‘Theory of Computation’).

Outcome: It gives the students exposure to implement dynamic programming based parser for Chomsky Normal Form (CNF) of context free grammars.

Solution Execution Video

A2: Write a program to design Lexical Analyzer in C/C++ Language (to recognize any five keywords, identifiers, numbers, operators and punctuations).

Outcome: It gives the students a feel of how a lexical analyzer for a typical regular language is written.

A3: Write a program in LEX to recognize Floating Point Numbers

Outcome: It gives the students an idea about how to specify regular expressions for covering all possible formats of floating point numbers.

A4: Write a program in LEX to recognize different tokens: Keywords, Identifiers, Constants, Operators and Punctuation symbols.

Outcome: It gives the students, a knowledge of using LEX tool to recognize all kinds of tokens of C language.

A5: Write a LEX program that copies file, replacing each nonempty sequence of white spaces by a single blank.

Outcome: It makes the students to know how a LEX tool can be used in general to process the text.

• If the first letter is a constant, move it to the end of the word and then add ay .
• If the first letter is a vowel, just add ay to the end of the word. All non-letters are copied intact to the output.

Outcome: It makes the students to know how a LEX tool may be used to process the content of files.

• The set of all string ending in 00.
• The set of all strings with three consecutive 222's.
• The set of all string such that every block of five consecutive symbols contains at least two 5's.
• The set of all strings beginning with a 1 which, interpreted as the binary representation of an integer, is congruent to zero modulo 5.
• The set of all strings such that the 10 th symbol from the right end is 1.
• The set of all four digits numbers whose sum is 9
• The set of all four digital numbers, whose individual digits are in ascending order from left to right.

Outcome: It will provide students with how to write regular expressions for different patterns.

A8: “The auxiliary procedure part of a LEX program can be complied separately and loaded with lexical analyzer”. Test and show that, the given statement is valid.

Outcome: This assignment provides the insight of how a LEX compiler works and how to manage the lengthy code written in LEX language.

A9: Implement Question A7 using JFLEX: http://jflex.de/manual.html

Outcome: Students can learn and understand how JFLEX tool works and it is very important for them as Java is one of the programming languages which is commonly used in IT industry.

• Write a LEX program to find maximal features in d' M and surround them by parentheses. A maximal feature is not a proper substring of any other feature.
• Display the longest maximal feature of each row.

Outcome: Students can learn how to apply the knowledge about various components of a compiler in other domains as well. Here it is shown how a lexical analysis process can be used to solve an image processing problem.

The First three programs (B1, B2 and B3) gives the feeling of understanding ‘Backtracking’ and ‘Trying with other alternatives’. To understand this see the video given for Question-B2 and the detailed output given for Question B3.

• Recursive Descent Parsing with back tracking (Brute Force Method) S → cAd A → ab / a
• Recursive Descent Parsing with back tracking (Brute Force Method) S → cAd A → a / ab

Outcome: This assignment gives students an insight of how a typical parser is developed and how it works. Further, with the help of this assignment they can understand the limitation of Brute Force Method of parsing practically.

• S → aaSaa | aa
• S → aaaSaaa | aa
• S → aaaaSaaaa | aa
• S → aaaSaaa | aSa | aa

Outcome: This assignment also provides the implementation of Recursive-Descent parser however it uses a different context-free grammar with more number of productions compared to earlier assignment B1. Here the students can understand the difference between ‘Backtracking’ and ‘Trying with other alternatives in a production’.

B3: Write a program to implement: Recursive Descent Parsing without back tracking. Give with detailed output, to show that it is working with other alternatives but no backtracking.

Outcome: This assignment provides the insight of how a parser works without backtracking and without trying with other alternatives in a production.

• Write a program to find FIRST
• Write a program to find FOLLOW
• Implementation of LL(1) Parsing Table

Outcome: This assignment provides implementation of computing two important sets First and Follow, and also the implementation of LL (1) parser. These functions are very important for developing not only LL (1) parser but also for LR (1) parsers, that are used extensively in practical compilers.

B5: An RR(1) parser is similar to an LL(1) parser except that it works from right-to-left, tracing out a top-down, rightmost derivation. The parser continuously consults the rightmost symbol of the derivation and the rightmost symbol of the input string that has not yet been matched to make its decisions about what production to use. The construction and operation of this parser is analogous to the LL(1) case, except that instead of having FIRST and FOLLOW sets we have LAST and PRECEDE sets, where LAST(A) is the set of terminals that could come at the end of a production of A (plus ε if A can derive the empty string), and PRECEDE(A) is the set of the terminals that could come before a production of A in some sentential form. Similarly, instead of having an end-of-input marker, we have a beginning -of-input marker, which we denote $ . Write a program to implement RR(1) parsing.

Outcome: Here RR(1) parser is implemented which is very similar to LL(1) parser but works from right-to-left rather than the traditional way of using left-to-right. The RR(1) parser is not commonly used in practice, however it will help students to understand and differentiate the two scanning approaches – left-to-right and right-to-left. Also they will be able to implement two more functions - Last and Precede.

B6: Write a program to implement operator precedence parsing. (Precedence table construction and parsing from precedence table)

Outcome: This assignment covers one more parsing method - Operator-precedence parsing which is a bottom-up approach and very useful for parsing the construct – expression. The expression is a very common syntactic construct present in almost all of the programming languages.

B7: Write a program to implement Simple Precedence. (Precedence table construction and parsing from precedence table)

Outcome: This assignment is a kind of extension parsing w.r.t. B6. Here in addition to terminals, the precedence relations among both Terminals and Non Terminals of the grammar, are used for getting the parsing actions.

B8: Write a program to design SLR parsing.

Outcome: The last three assignments in this set are very much related to each other as these provide the solutions for all three approaches – SLR(1), CLR(1) and LALR(1) parsing. Students will get to know that how to obtain LR(0) items, FIRST, FOLLOW, Parsing Table Construction and usage of the table for parsing a given input.

B9: Write a program to design CLR parsing.

Outcome: This assignment is a variant of LR(1) parsing. Students can learn about how to obtain LR(1) items, FIRST, FOLLOW, Parsing Table Construction and usage of the table for parsing a given input using CLR parser.

B10: Write a program to design LALR parsing.

Outcome: This assignment is a variant of LR(1) parsing. Students can learn about how to obtain LR(1) items, grouping of LR(1) items with common core, FIRST, FOLLOW, Parsing Table Construction and usage of the table for parsing a given input using LALR parser.

C1: Write a program to design LALR parsing using YACC.

Outcome: This assignment is same as given in the assignment B10 but here the YACC tool is used. Students find this assignment very useful as they can feel the power of the YACC tool and how it reduces the efforts of writing a parser.

C2: Use YACC to Convert Binary to Decimal (including fractional numbers).

Outcome: This assignment shows how a problem which is not directly related to the Compiler can also be solved conveniently using the YACC tool.

C3: Use YACC to implement, evaluator for arithmetic expressions (Desktop calculator).

Outcome: This assignment gives how an expression is parsed and how syntax-directed translation is carried out on the same. It is found to be a very useful problem as an expression is a very common construct in programming languages.

C4: Use YACC to convert: Infix expression to Postfix expression.

Outcome: The students can learn about the conversion of infix to postfix using YACC tool. With this knowledge they are ready for other conversion i.e. infix to prefix form also.

C5: Use YACC to generate Syntax tree for a given expression.

Outcome: The students can obtain syntax tree for a given sequence of statements based on the grammar. The syntax tree is one of the intermediate form used in the development of a typical compiler. It is very much similar to the parse tree and therefore students can correlate both these tree structures.

C6: Use YACC to generate 3-Address code for a given expression.

Outcome: The students can obtain intermediate code: three-address code, which is commonly used intermediate code in practical implementation of compilers.

C7: Use YACC to generate the following 3-Address code which contains Arrays.

Outcome: This assignment is an extension to the previous assignment C6 by including the array construct along with the expressions. With this assignment the students are able to handle the arrays also while generating three-address code.

• A context-free grammar that generates all strings of a’s, b’s and c’s
• Semantic attributes for the grammar symbols
• For each production of the grammar a set of rules for evaluation of the semantic attributes.

Outcome: This assignment deals with the problem of string and pattern matching. It is shown here how this kind of problem can also be solved using the method of syntax-directed translation.

C9: YACC to generate DAG for expression grammar.

Outcome: With the help of this assignment students can know about, how DAG (Directed Acyclic Graph) construct is used and generated practically and further enhance their knowledge and practical skills for writing an optimized compiler.

C10: Write a YACC “desk calculator” program that will evaluate Boolean expressions, consists of ¬, ∧, ∨ → and ↔ where, ¬ is highest precedence and ↔ is with lowest precedence. INPUT : ¬T ∧ F → (T ∨ F)    OUTPUT : T

Outcome: This assignment gives how a Boolean expression is parsed and how syntax-directed translation is carried out on the same.

Academia.edu no longer supports Internet Explorer.

To browse Academia.edu and the wider internet faster and more securely, please take a few seconds to  upgrade your browser .

Enter the email address you signed up with and we'll email you a reset link.

• We're Hiring!
• Help Center

COMPILER DESIGN LAB MANUAL

Related Papers

Clark Turner

When Cal Poly created an undergraduate software engineering program, the challenge was to package the "ten pounds" of science, computer science and engineering into the "five pound" capacity of a bachelor's degree. On top of this, we needed to add preparation for the management roles required of a professional software engineer.

The introduction of engineering design in the first year of the curriculum has become commonplace in order to provide students with early experiences in engineering principles and exposure to realworld applications. Many different approaches to the development and implementation of these courses are used but regardless of the method or specific emphasis, students enrolled in engineering design classes are expected to be problem solvers and to communicate effectively, both verbal and written. We have adapted and integrated a problem-solving and program development methodology originally used in a computer science environment to an introductory engineering design class which helps beginning engineering students develop these important skills. We have also conducted a baseline study in this engineering design course to evaluate this methodology and its impact on students' problem-solving abilities, skills, knowledge, and attitudes in a first-year course on engineering design.

Tom Cochrane

Tony Marjoram

Gustavo R Alves

Johan Malmqvist , W. Lucas

Loading Preview

Sorry, preview is currently unavailable. You can download the paper by clicking the button above.

RELATED PAPERS

Muhammad Zeeshan Rafique

Proceedings of the 10th International Conference on Computer Supported Education

Neusa Oliveira

Jorge Mendoza

Kevin O'Connor , Reed Stevens

2014 ASEE Annual Conference & Exposition Proceedings

Edwin Schmeckpeper

QScience Proceedings

Nausheen Pasha-Zaidi

Klara Kövesi

Proceedings of the Third Regional Symposium of the Systems Engineering Society of Australia

David Cropley

Pau Fonseca i Casas

Hadina Habil

ralph giffin

Journal of Statistical Software

Lisa Gommer

2017 ASEE Annual Conference & Exposition Proceedings

Aidsa Santiago-román

Leonard Lye

jose juan hernandez rangel

Steve Rowlinson

beatriz amante

VIJAYA RAJA V

European Journal of Engineering Education

Luis Santos

Engineering for Rural Development

Irina Arhipova

2007 Annual Conference & Exposition Proceedings

Carlos Tobar

•   We're Hiring!
•   Help Center
• Find new research papers in:
• Health Sciences
• Earth Sciences
• Cognitive Science
• Mathematics
• Computer Science
• Academia ©2024

Navigation Menu

Search code, repositories, users, issues, pull requests..., provide feedback.

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly.

To see all available qualifiers, see our documentation .

• Notifications You must be signed in to change notification settings

Compiler Design Lab KTU 2020

AbhayVAshokan/Compiler-Design-Lab

Folders and files.

Repository files navigation

Compiler design lab, list of experiments.

• Design and implement a lexical analyzer for given language using C. The lexical analyzer should ignore redundant spaces, tabs and newlines.
• Implementation of Lexical Analyzer using Lex Tool.
• Generate YACC specification for a few syntactic categories.
• Program to recognize a valid arithmetic expression that uses operator +, –, * and /.
• Implementation of Calculator using LEX and YACC.
• Convert the BNF rules into YACC form and write code to generate abstract syntax tree.
• Write program to find ε – closure of all states of any given NFA with ε transition
• Write program to convert NFA with ε transition to NFA without ε transition.
• Write program to convert NFA to DFA.
• Write program to minimize any given DFA.
• Develop an operator precedence parser for a given language.
• Write program to Simulate First and Follow of any given grammar.
• Construct a recursive descent parser for an expression.
• Construct a Shift Reduce Parser for a given language.
• Write a program to perform loop unrolling.
• Write a program to perform constant propagation.
• Implement Intermediate code generation for simple expressions.
• Implement the back end of the compiler which takes the three address code and produces the 8086 assembly language instructions that can be assembled and run using an 8086 assembler. The target assembly instructions can be simple move, add, sub, jump etc.

• Perm Krai Tourism
• Perm Krai Hotels
• Perm Krai Bed and Breakfast
• Flights to Perm Krai
• Perm Krai Restaurants
• Things to Do in Perm Krai
• Perm Krai Travel Forum
• Perm Krai Photos
• Perm Krai Map
• All Perm Krai Hotels
• Perm Krai Hotel Deals

Trains bypassing Perm-2 - Perm Krai Forum

• Europe    
• Russia    
• Volga District    
• Perm Krai    

Perm Krai Capital of Culture

• Support of regional and other partners
• Working groups
• Policy papers
• Newsletters
• Main themes
• Social and cultural integration
• Citizenship and civil society
• Historical heritage
• Music and cinema

Youth policy

• External Cooperation
• Testimonials

Project initators: 

“ Cultural Planning will help to ensure the Perm region will remain distinctive and unique” , Mr. Protasevich said. “It will mean planning ways to support and preserve our heritage, developing appealing opportunities for artists and musicians regardless of age, and generating education and employment. It will mean building a creative community with a buzz.”

“Some of the identified objectives of “Perm krai international:young journalists@school” project include facilitating greater communication and cooperation among young community and official organizations in Perm krai”, said the Vice-Minister of Perm krai.

“Perm Krai International: young journalistes@school”

…………………………………………………………………………………………………..

The international children festival of theatre arts “Long Break”

What is the international child festival of theatre arts “Long Break”? It is a real holiday for young spectators and their parents. The international child festival of theatre arts “Long Break” will be hold from the 30th of April to the 5th of May. It will be in Perm and Lysva. It will be hold under the aegis of the Ministry of Culture of the Russian Federation and the Ministry of Culture, Youth Politics and Mass Communications of Perm Krai. The program of the festival is prepared by Russian and foreign experts of child theatre. There are the most interesting for children events of the world arts. The “Long Break” familiarizes children with actual artists. It is the platform where people communicate with people using the language of modern arts which is understandable for a new generation.

The festival “The White Nights in Perm”

• The participants of the festival of land art “Ural Myths” will create art objects using natural materials. The objects will have the same mythological idea.
• During the festival of bears “MedveDay” the masters Teddy-makers will tell gripping stories about a symbol of the city. They will organize some exhibitions of teddy bears and they will give master classes.

• The exhibition “Mammoth’s track” will gather mammoths from different corners of Russia on Perm’s territory. There will be even a famous mammoth Dima.
• And at last the international festival of street arts «Open sky» will represent the various program: carnival processions, a 5-day master class «Mask Art», street shows and performances, performances of Russian and foreign street theatres.

The IX International festival “Heavenly Fair of Ural”

From the 26th to the 3rd of July the IX International festival “Heavenly Fair of Ural” takes place in Kungur. There will be a fight for the I Privolzhski Federal Disctrict Cup for aerostatics and the VII Perm Krai Open Cup for aerostatics.This year Kungur won’t hold rating competitions which results are taking into general account of the pilots. They counted on creating entertainment activities “Air battles over Kungur”. There will be the representatives of sub-units of ultralight aviation, detachment of parachute troops and water means. All the battles will take place straight over the city. And natives will take part in the festival too.According to initial data 15 aeronauts and about 50 ultralight aviation pilots expressed willingness to take part at the festival. And a dirigible pilot confirmed his participation.Ultralight aviation pilots will take part in the “Air games” within the festival. As last year a campsite of ultralight aviation will base in an area near a village Milniki.

Share this:

Our Facebook Page

Our Twitter

Create a free website or blog at WordPress.com.

• Already have a WordPress.com account? Log in now.
• Subscribe Subscribed
• Copy shortlink
• Report this content
• View post in Reader
• Manage subscriptions
• Collapse this bar

Verkhne-Chusovskie Gorodki, Perm Krai , Russia i Regional Level Types Verkhne-Chusovskie Gorodki - not defined - Perm Krai Krai Russia Country function showexplain() { $("#locexplain").toggle(); if (typeof movemap === "function") movemap(); }

Select Mineral List Type

Mineral list.

ⓘ Thermonatrite

Detailed Mineral List:

List of minerals arranged by Strunz 10th Edition classification

List of minerals arranged by Dana 8th Edition classification

List of minerals for each chemical element

Localities in this Region

• Gorodki oil field

Other Regions, Features and Areas containing this locality

• ⭔ Ural Economic Region Economic Region