Implementing a Parser in C

 IMPLEMENTING A RECURSIVE DESCENT PARSER

AIM:

            To implement a Recursive Descent Parser in C that can analyze and evaluate an expression consisting of simple arithmetic operations.

 

ALGORITHM:

1.      Get the input expression from the user

2.      Declare and implement the functions exp(), term() and factor() for analyzing the structure of the given expression.

3.      Call the functions from appropriate places. For instance, the function exp() is called from main() and the function term() is called from exp().

4.      Then write the code for implementing the operations ‘+’ and ‘-’ and print the result.

5.      Implement and call the function error() when an error is found in the syntactical structure of the given expression.

 

PROGRAM:

#include <stdio.h>

#include <stdlib.h>

#include <ctype.h>

char token;

int expr(void);

int term(void);

int factor(void);

void error(void)

{

fprintf(stderr, "Error\n");

exit(1);

}

void match(char expectedToken)

{

if(token == expectedToken)

token = getchar();

else

error();

}

int main()

{

int result;

token = getchar();

result = expr();

if (token == '\n')

printf("Result = %d\n", result);

else

error();

return 0;

}

int expr(void)

{

int temp = term();

while ((token == '+') || (token == '-'))

switch (token)

{

case '+':

match('+');

temp += term();

break;

case '-':

match('-');

temp -= term();

break;

}

return temp;

}

int term(void)

{

int temp = factor();

while (token == '*')

{

match('*');

temp *= factor();

}

return temp;

}

int factor(void)

{

int temp;

if (token == '(')

{

match('(');

temp = expr();

match(')');

}

else if (isdigit(token))

{

ungetc(token, stdin);

scanf("%d", &temp);

token = getchar();

}

else error();

return temp;

}

Sample Output:

Continue reading →

Implement A LEXICAL ANALYZER using FLEX and C

 AIM:

To create a simple scanner using FLEX (Fast LEXical analyzer) for recognizing and displaying the tokens like identifier, number, operator and delimiters used in Declaration and Assignment Statements.

 

ALGORITHM:

1. Declare constants for the tokens like Identifier (ID), number (NUM), operator (OP), and delimiter (DELIM).

2. Include the option noyywrap.

3. Specify the tokens using Regular Expression (R.E.) notations.

4. Return the corresponding constant at the recognition of each and every token in main().

5. Declare the variable ‘id’ for holding the return value

6. Call the function yylex() to get the next token from the lexical analyzer and store it in ‘id’.

7. Check the value of ‘id’.  If it is greater than 0 (id>0) then conclude that the next token is a valid one.

8. Use switch case statement for taking appropriate action for each and every token identified.

 

PROGRAM SPECIFICATION:

/*** Definition Section ***/

%{

#include <stdio.h>

#include <stdlib.h>

#define NUM 1

#define KEYWD 2

#define OP 3

#define DELIM 4

#define ID 5

%}

/* This tells flex to read only one input file */

%option noyywrap

dgt [0-9]

id [a-zA-Z][a-zA-Z0-0]* 

%%

{dgt}+|{dgt}+.{dgt}+ { return(NUM); }

int|float { return(KEYWD); }

{id} { return(ID); }

\+ { return(OP); }

- { return(OP); }

\* { return(OP); }

= { return(OP); }

; { return(DELIM); }

. { /* Ignore all other characters */ }

%%

/*** C Code Section ***/

int main(void)

{

int tid;

 

/* Call the lexer, then quit. */

while((tid = yylex()) >0)

{

switch(tid)

{

case 1:

printf("NUM ");

break;

case 2:

printf("KEY ");

break;

case 3:

printf("OP ");

break;

case 4:

printf("DELIM ");

break;

case 5:

printf("ID ");

break;

default:

printf("Unknown: %s", yytext);

}

}

return 0;

}

 

PROCEDURE:

1. Store the specification given above in a file named with the extension .l (ScanDigit.l)

2. Compile the file by passing the file name as a parameter to the Flex tool as follows:

Flex ScanDigit.l

3. The FLEX tool will generate a C file with the name lex.yy.c

4. Compile the generated C file with a C compiler and then Execute to run the Scanner

Link for Accessing Tools:

1.  Flex Tool

2.  gcc for Windows

3.  yacc Tool

Continue reading →

C program to identify a line of comment in a Program

C Program that Identifies C Type Comments

#include<stdio.h>
void main()            
{
 char com[50], ch;
 int i=2,a=0;
 printf("\n Enter C style comment:");
 scanf("%[^\n]%*c",com);
 printf("%s", com);

 if(com[0]=='/')  
 {
        if(com[1]=='/')
          printf("\n This is a comment\n");
        else if(com[1]=='*')   
    {
            for(i=2;i<=50;i++)
            {
               if(com[i]=='*' && com[i+1]=='/')
               {
           printf("\n This is a comment\n");
                   a=1;
                   break;
           }
               else
                 continue;  
        }
        if(a==0)
              printf("\n This is not a comment\n");
        }   
        else
             printf("\n This is not a comment\n");
  }
  else
     printf("\n This is not a comment\n");
}

Algorithm:

1. Read a line of characters from keyboard
2. Check whether the line begins with ‘//’.  If so, determine that the given line is a comment
   
3. Check for first two characters.  If they are ‘/*’ then check whether there exists '*/' at the end of the line
4. Based on the result of the condition check, output whether the given line is a comment or not

 

Sample Output:

 Enter C style comment:

//This is a single line comment
 This is a comment

 Enter C style comment:

/This is a C Program
 This is not a comment

 Enter C style comment:

/*Multiline comment begins like this
 This is not a comment

 Enter C style comment:

/* A Program written in C for Scanning */
 This is a comment

Continue reading →

Need for Translators in Porgramming!

THE ROLE OF A TRANSLATOR!

The Role of a Translator

A translator is a program that takes as input a program written in one programming language (the source language) and produces as output a program in another language (the object or target language). If the source language is a high-level language such as FORTRAN, PL/1 or COBOL and the object language is a low-level language such as an assembly language or machine language, then such a translator is called a Compiler.

 The first step involved in executing a program written in a high-level language is to translate or compile the source program into an object program. Then the resulting object program is loaded into memory for execution.

Types of Translators

Interpreter: Interpreter is a translator that transforms a source program written in a high level language into an object program containing intermediary code.  The intermediate code is then executed by the interpreter.  In some cases, the source language itself can be an intermediate language.  In that case, the interpreter executes the statements written in the source program line by line.
Interpreters are often smaller than compilers and facilitate the implementation of complex programming language constructs.  However, the main disadvantage of interpreter is that the execution time of an interpreted program is usually slow than that of a corresponding compiled object program.

Preprocessor: Preprocessors are one kind of translators that take programs is one high level language and produce equivalent programs in another high level language.  For example there are many FORTRAN preprocessors that map ‘structured’ versions of FORTRAN into conventional FORTRAN.

Assembler: An assembler is a translator, which takes an assembly language program as input and converts it into a machine language program.

Need for Translators

Using machine language, programmers communicate directly with the computer in terms of bits, registers and very primitive machine operations. The instructions are given in the form of 0’s and 1’s.   This makes programming a tedious and time consuming task when the complexity of the algorithm is increased.

All operations and operands are specified in a numeric code and hence, the programs written in machine language are cryptic. This makes the code impossible to modify in a convenient manner.

Symbolic Assembly Language

In an assembly language, we use mnemonic names for both operation codes and data addresses.  For example,

ADD X,Y

is an assembly language instruction for adding the content of X and Y registers. Such programs are easier to write and understand than machine language programs. Because, numeric codes for addresses and operations (in machine language) are replaced with more meaningful symbolic codes.

A computer however, can’t execute a program written in assembly language. That program has to be first translated to machine language, using a program called assembler. The major drawback of writing programs in assembly language is that the programmer must be intimately concerned with how and where data is represented within the machine.

High-Level Programming Language

A High-Level programming language allows a programmer to express algorithms in a more natural notation that avoids many of the details of how a specific computer functions. For example “A+B” is an expression in a high-level language that instructs a computer to add the contents of variables A and B. COBOL, FORTRAN, PL/1, ALGOL, SNOBOL, APL, PASCAL, LISP and C are some of the more common high-level languages.

A high-level language makes the programming task simpler, but requires a program to translate its code to the corresponding machine code for its execution.

Continue reading →

Model Questions for PCD

ANNA UNIVERSITY :: CHENNAI – 600 025

MODEL QUESTION PAPER

B.E. COMPUTER SCIENCE AND ENIGNEERING

CS337 - PRINCIPLES OF COMPLIER DESIGN

Time: Three Hours Maximum: 100 Marks

Answer All The Questions

PART – A (10 x 2 = 20 Marks)

1. List any two complier construction tools, indicating their inputs and outputs.

2. Briefly explain any two language conventions that impact the difficulty of lexical analysis.

3. Write regular definition for the following language over {0,1} A string of 0’s and 1’s, which has 0 at the third position when counted from night.

4. Formally define a nondeterministic finite automation (NFA)

5. Prove that the following grammar is ambiguous: S→ aSbS │bSaS│ Є

6. Write down the predictive parsing algorithm.

7. Give the algorithm for generating the closure of a set of LR (0) items.

8. Translate the expression : - (a+b) * (a+b+c) into quadruples and indirect triples.

9. Give the grammar for generating binary numbers. Add semantic rules to the above grammar to compute the decimal equivalent of the binary number, generated.

10. Write down the algorithm that partitions the given sequence of three-address statements into basic books.

Part – B (5 x 16 = 80 Marks)

11. Draw the transition diagram for the lexical analyzer that recognize the following tokens.

Identifiers, relational operators. Use the following rules to form the identifier

• begins with an alphabet
• consists of alphabets, digits and hyphen
• should not end with an hyphen
• not two hyphens appear together

12.a) Draw the NFA for the following regular expression using Thompson’s Construction and then convert it into an equivalent DFA.

(a/b) * (a/c) * b

(or)

12.b)i) List the tasks performed by a lexical analyzer

ii) Give the complete algorithm that takes a NFA and converts it into an equivalent DFA.

13.a) Remove left recursion from the following grammar and build the predictive parsing table.

S → (L) │a

L → (L, S) │S

(or)

13.b) Build LR(1) parsing table for the grammar:

S → Aa │bAc │Bc │bBa

A → d

B → d

14.a) Write down the translation scheme for generating three address code for evaluating Boolean expressions using back patching. Explain the attributes used. Use the above and generate three address code for:

While ( (a<b) and (c>d) ) do

begin

if(p=q) then p = 1

else p = 2

While (p>q) do

Begin

P: = x+y

q: = x-y

end

end

(or)

14.b) Explain how declarations are processed by the computer. Take into consideration nested procedures also. Explain clearly the attributes used. Show with an example how the symbol tables are formed.

15.a)i) Explain how ‘next use’ information about names in basic blocks can be collected.

ii) Discuss about the actions performed by a simple code generator while generating code for a typical three-address statement of a form x: = y op z.

(or)

15.b)i) Write the syntax directed definition that computers and prints the post-fix equivalent of the given infix expression.

ii) Write down the unambiguous CFG for generating Boolean expressions.

Continue reading →