## Tuesday, March 14, 2006

CONTENTS

1. CONVERSION OF R.E TO NFA

3. TOP DOWN PARSING

4. SHIFT REDUCE PARSING

5. E-CLOSURE

6. CODE GENERATION

7. TOKEN SEPARATION

Ex.No:1 CONVERSION OF REGULAR EXPRESSION TO NFA

Aim:
To write a program in C order to convert the given regular expression to NFA.

Algorithm:

Step 1: Start
Step 2: Get the regular expression as a string.
Step 3: If the given expression is f there is no transition.
Step 4: If when e is the input string then the transition takes place from start
To the next state.
Step 5: If the input symbol is 0 or 1 then the transition takes place from
Start to next intermediate State.
Step 6: If the operator scanned is * then to the next immediate state and to
the third state from the start
Step 7: From the second state the transition is made to the third state on
getting the input symbol.
Step 8: From the third state the e transition are made to the second and
immediate next state.
Step 9: If the operator is 1 then the transition is made from the start state to
next state on accepting the first input and then on accepting e on
the next state from that state it moves to the final state.
Step 10: If the operator involved is e then an e transition is made to the
second and fourth state.
Step 11: On accepting input after the operator the transition is made from
the fourth to fifth state.
Step 12: e transitions are made from third and fourth to final state.
Step 13: Stop.

RESULT:
Thus the program has been successfully verified.

Ex.No:2 LEADING AND TRAILING OF A GRAMMAR

Aim
To write a program to find leading and trailing of a grammar.

Algorithm
Step1: Start.
Step2: Get the no of production and calculate the length of each
production.
Step3: With a variable val for checking the valid non terminals if they are
duplicated get all Non terminals in an array.
Step4: In each production check the first accurate of terminals and take
that terminal and add it to leading of non terminal in array and exit
the loop.
Step5: Scan the production and find the last terminal and add it to
respective trailing array of associated non terminal &exit the loop.
Step6: Consider production with a non terminal on right side and check the
leading of that non terminal associated production and also trailing
and add it to the leading and trailing of left side non terminal.
Step7: Write the leading and trailing terminals for each non terminal.

Step8: Stop.

RESULT
Thus the program has been successfully executed.

Ex.No:3 TOP - DOWN PARSING

Aim:
To write a compiler program in C to illustrate the top down parsing.

Algorithm:

Step1: Start.
Step2: Get the grammar to be used.
Step3: Get the string to be derived.
Step4: Get the string to be expanded.
Step5: All to the precedence of operator present in the string to be derived
the appropriate grammar is applied to string.
Step6: The expanded string is added to the stack.
Step7: Until the string to be derived is obtained in the stack the above steps
are represented.
Step8: Thus by comparing the obtained string and derived string we have
to confirm the successful string.
Step9: Thus actions performed string all to the grammar are displayed all to
respective parsing steps.
Step10: Stop.

RESULT:

Thus the program has been successfully executed.

Ex.No:4 SHIFT REDUCE PARSING

Aim:
To Write a compiler program in C to implement a shift reduce parsing
on a regular expression.

Algorithm:
Step 1: Start.
Step 2: Get the string to be parsed as input.
Step 3: Check whether the string has a , +, or *. If so the string is correct
else the string is wrong.
Step 4: The string obtained is parsed to the stack by character.
Step 5: When a is the shifted character then it is converted to E and then
next action shift is Specified.
Step 6: A null character is added to the stack after each shifting.
Step 7: After the operator e another a is shifted other a is converted to E.
Step 8: The formed string is the stack with 2 operands as E as a single
operator inside is considered to E again due to the handle
E -> E * E / E + E
Step 9: Again any other consecutive operator is shifted and the rest of the
reduction continues by following the 7th and 8th step.
Step 10: Finally the step should have \$ and the E symbol to signify the
acceptance of the string.
Step 11: Stop.

RESULT:
Thus the program has been successfully executed.
Ex.No:5 E - CLOSURE OF A GRAMMAR

Aim:
To write program to find closure of given grammar.

Algorithm:

Step 1: Start.
Step 2: Get the e transition of each state of given grammar.
Step 3: Write state no : State and on the closure of that state write state no
of the state itself.
Step 4: Pass the state no as argument for a function E-closure that
calculate the closure of the States that can be reached on e-
transition from state passed as argument.
Step 5: Repeat step 4 until e-transition of any state is 0.
Step 6: Repeat step 3,4 and 5 until e-closure of all states are calculated.
Step 7: Stop.

Result:
Thus the program has been successfully executed.

Ex.No:6 CODE GENERATION

Aim:
To write a program to generate machine code for given three address
code.

Algorithm:

Step 1: Start.
Step 2: Enter the three address codes.
Step 3: If the code constitutes only memory operands they are moved to
the register and according to the operation the corresponding
assembly code is generated.
Step 4: If the code constitutes immediate operands then the code will have
a # symbol proceeding the number in code.
Step 5: If the operand or three address code involve pointers then the code
generated will constitute pointer register. This content may be
stored to other location or vice versa.
Step 6: Appropriate functions and other relevant display statements are
executed.
Step 7: Stop.

Result:
Thus the program has been successfully executed.

Ex.No:7 TOKEN SEPERATION

Aim:
To separate the tokens of the given input string.

Algorithm:

Step 1: Start.
Step 2: Declare necessary files in and out and the write respectively.
Step 3: While the end of input file is not reached fix a[p]=getc[in].
Step 4: Fix the value of i is + or – or * or / or = print it as operator.
Step 5: If array of i from 0 to p-1 increment its value by one.
Step 6: If value of array[i] is ( or ; or ) or [ or ] or { or } print it as operator.
Step 7: Check necessary conditions for “keywords” and “identifiers” and
print them.
Step 8: Stop.

Result:
Thus the program has been successfully executed.