INTRODUCTION
LEX
Lex is a program designed to generate scanners, also known as
tokenizers, which recognize lexical patterns in text. It helps in writing
programs whose control flow is directed by instances of regular expression in
the input stream.
Lex is
a tool for automatically generating a lexer or scanner given a lex
specification ( .l file )
A Lexer or Scanner
is used to perform lexical analysis, or the breaking up of an input stream into
meaningful units, or tokens. For example, consider breaking a text file up into
individual words.
Skeleton
of a Lex Specification ( .l file)
The Rules Section :
%%
[RULES SECTION]
<pattern> {
<action to take when matched> }
<pattern> {
<action to take when matched> }
…
%%
Patterns are specified by regular expressions.
For example:
%%
[A-Za-z]* {
printf(“this is a word”); }
%%
Regular Expression Basics:
. : matches
any single character except \n
* : matches 0 or more instances
of the preceding regular expression
+ : matches 1 or more instances
of the preceding regular expression
? : matches 0 or 1 of the
preceding regular expression
| : matches the preceding or
following regular expression
[ ] : defines a character class
() : groups enclosed regular
expression into a new regular expression
“…”: matches everything within the “ “ literally
Lex
Regular Expression :
x|y x or y
{i} definition of i
x/y x, only if followed by y (y
not removed from input)
x{m,n} m to n occurrences of x
Ù x x, but only at
beginning of line
x$ x, but only at end of line
"s" exactly what is in
the quotes (except for "\" and
following
character)
A regular expression finishes with a space, tab
or newline
Regular Expression Examples:
Ø an integer: 12345
[1-9][0-9]*
Ø a word: cat
[a-zA-Z]+
Ø a (possibly) signed integer: 12345 or -12345
[-+]?[1-9][0-9]*
Ø a floating point number: 1.2345
[0-9]*”.”[0-9]+
Ø a delimiter for an English sentence
“.” | “?” | ! OR
[“.””?”!]
Ø C++ comment: // call foo() here!!
“//”.*
Ø white space
[ \t]+
Ø English sentence: Look at
this!
([ \t]+|[a-zA-Z]+)+(“.”|”?”|!)
Special Functions:
Ø yytext
Where text matched most recently is stored
Ø yyleng
Number of characters in text most recently matched
Ø yylval
Associated value of current token
Ø yymore()
Append next string matched to current contents of yytext
Ø yyless(n)
Remove from yytext all but the first n characters
Ø unput(c)
Return character c to input stream
Ø yywrap()
May be replaced by user
The yywrap method is called by the lexical analyzer whenever it
inputs an EOF as the first character when trying to match a regular expression
Compiling
commands
lex
file.l
cc lex.yy.c –ll
./a.out
Yacc:
A tool for automatically generating a parser given a
grammar written in a yacc specification (.y file)
A grammar specifies a set of production rules, which
define a language. A production rule specifies a sequence of symbols,
sentences, which are legal in the language.
Structure of yacc File
Definition
section
Declarations of tokens
Type of values used on parser stack
Rules section
List of grammar rules with semantic routines
User code
Skeleton of a yacc specification (.y file)
The Production Rules Section
%%
production
: symbol1 symbol2 … { action }
| symbol3 symbol4 … { action }
| …
production: symbol1 symbol2 { action }
%%
An example
Defining
Values:
expr : expr '+' term { $$ = $1 +
$3; }
| term { $$ = $1; }
;
term : term '*' factor { $$ = $1 *
$3; }
| factor { $$ = $1; }
;
factor : '(' expr ')' {
$$ = $2; }
| ID
| NUM
;
Example
Scanner
.l file
%{
#include
<stdio.h>
#include "y.tab.h"
%}
id [_a-zA-Z][_a-zA-Z0-9]*
wspc [ \t\n]+
semi [;]
comma [,]
%%
int { return INT; }
char { return CHAR; }
float { return FLOAT; }
{comma} { return COMMA; } /* Necessary? */
{semi} { return SEMI; }
{id} { return ID;}
{wspc} {;}
.y file
%{
#include
<stdio.h>
#include
<stdlib.h>
%}
%start line
%token CHAR, COMMA, FLOAT, ID, INT, SEMI
%%
Compiling Commands
Yacc filename.y
cc yy.tab.c
./a.out
UNIX PROGRAMMING
Unix is multi user multi tasking OS. It was written in C
at Bell labs.
Most of the servers run on unix. Todays unix flvors are Solaris, HP, AIX,
Linux.
Architecture:
Unix File System :
An upside-down Tree
Ø Changing permissions
§ chmod g+w empl.txt
§ chmod 754 empl.txt
Ø Changing ownership
§ chown gcdv_dev empl.txt
Ø Changing group
§ chgrp develp empl.txt
Shell:
Ø Command interpreter that waits for
commands, executes them and displays the results
Ø Bourne shell
§ Developed by Steve Bourne at
AT&T
Ø Korn shell
§ Developed by David Korn at
AT&T
Ø C-shell
§ Developed by Bill Joy for Berkeley Unix
Working of a shell:
Ø Shell displays a prompt.
Ø Type in a command.
Ø Press the return key.
Ø The shell interprets the commands typed and tries to find the
correct programs to run.
Ø The kernel runs the requested programs and returns the results to
the shell.
Ø The shell displays the command prompt again
Shell system variables:
Ø PATH = Defines path shell must
search in order to execute any command or file.
Ø HOME = Indicates default working
directory of the user.
Ø PS1 = System prompt 1.
Ø PS2 = System prompt 2, default
value is “>”.
UNIX Shell Programming:
Shell Script (Shell Procedure) :
A program written in shell
programming language is known as a shell script or shell procedure.
Shell Programming Language :
The shell programming language
is a command language with a lot of features common to many computer
programming languages, including the structured language constructs: sequence,
selection, and iteration.
Command Languages :
Ø Command languages are interpreted languages
Ø It allows then use of Unix commands in scripts
Shell scripting keywords :
Please Note : Script variables shouldn’t be same as keywords.
Ø Looping constructs, to be discussed in coming slides.
Ø set, unset
Ø Readonly
Ø Exit
Ø Ulimit
Ø Umask
Create - Simple Hello World shell script.
#!/bin/sh
echo "Hello World“
Make Files Executable
$ chmod 777 HelloWorld.sh
Execute the shell script
Observe the output ‘Hello World’ will be between two command
prompts.
$ HelloWorld.sh
Passing parameters to a Shell script
Ø Consider Welcome.sh, & we are sending name as parameter
to a Shell Script.
Welcome.sh Vikram
Welcome.sh Vikram
Ø think If you want to send First name & Last name as one
parameter.
In above case 0th parameter value considered will be script name.
1st parameter value considered will be name, i.e.Vikram.
In above case 0th parameter value considered will be script name.
1st parameter value considered will be name, i.e.Vikram.
Accessing parameters in a Shell script
Ø Parameter to a shell script starts from index 1. Its value is
retrieved by using $1 & so on. … Think how you will access parameter beyond
9th parameter.
Shell Positional Variable
$0 : command itself
$1 : first parameter
$n : nth
parameter
$# : no. of parameters
$? : exit status of last command executed
$* : all
parameters
$$ :
process number of shell
$! : PID of last background
process
Compiling Commands
Sh filename.sh
COMPILER
DESIGN :
A Compiler is a program takes
a program written in a source language and translates it into an equivalent
program in a target language
Source Program Compiler
Target Program 
(Generally written in a
High level language)
Error Messages
Major Parts
of Compilers :
Ø There are two major parts of a compiler: Analysis and Synthesis
Ø In analysis phase, an intermediate representation is created from
the given source program.
-- Lexical Analyzer, Syntax Analyzer and Semantic Analyzer are the
parts of this
phase.
Ø In synthesis phase, the equivalent target program is created from
this intermediate representation.
-- Intermediate Code Generator, Code Generator, and Code Optimizer
are the parts of this phase.
Phases of a
Compiler
Source
Lexical Semantic Intermediate Code Target Progrm Analyzer Analyzer Code Generator Optimizer Program
Ø Each phase transforms the source program from one representation
into another
representation.
Ø They communicate with error
handlers.
Ø They communicate with the
symbol table.
Intermediate
Code Generation
Ø A compiler may produce an explicit intermediate codes
representing the source program.
Ø These intermediate codes are generally machine (architecture
independent). But the level of intermediate codes is close to the level of machine codes.
Ø Ex:
newval :=
oldval * fact + 1
id1
:= id2 * id3 + 1
MULT
id2, id3,temp1
ADD temp1,#1,temp2
MOV
temp2,,id1
Code
Generator
Ø Produces the target language in a
specific architecture.
Ø The target program is normally is
a relocatable object file containing the machine codes.
Ø Ex: ( assume that we have an architecture with instructions whose at
least one of its operands is a machine register)
MOVE id2,R1
MULT id3,R1
ADD #1,R1
MOVE R1,id1
Compiling Commands
cc
pgmname.c
./a.out
PART-A
LEX Programs
1a) Program to
count number of characters, words, spaces and lines in a given input file
%{
#include<stdio.h>
int c=0;
int w=0;
int b=0;
int l=0;
int t=0;
%}
Word [^ \t\n]+
EOL \n
%%
{Word} { w++;
c=c+yyleng; }
{EOL} { l++;
c++; }
[ ] { b++; c++;}
[\t] {
t++;c=c+4; }
%%
main(int
argc,char *argv[])
{
if(argc==2)
{
yyin=fopen(argv[1],""r);
if(!yyin)
{
printf("Could
not open %s file \n",argv[1]);
exit(0);
}
yylex();
fclose(yyin);
printf("------------------------------------------------\n");
printf("Number
of Lines =%d \n",l);
printf("Number
of Words = %d\n",w);
printf("Number
of tab spaces =%d\n",t);
printf("Number
of white spaces =%d \n",b);
printf("Number
of charaters =%d\n ",c);
printf("--------------------------------------------------\n");
}
else
printf("Usage
: %s <srcfile>\n",argv[0]);
}
1.b) Program to count the number of comment lines in a
given C program. Also eliminate them and copy that file into another file
%{
int c=0;
%}
%%
("/*")((.)*|\n)*("*/") c++;
("//")(.)* c++;
. ECHO;
%%
main(int argc
,char *argv[])
{
if(argc<3)
{
printf("Usage:%s
<srcfile> <destfile> \n",argv[0]);
exit(0);
}
yyin=fopen(argv[1],"r");
if(!yyin)
{
printf("Error
in opening the file 0\n");
exit(0);
}
yyout=fopen(argv[2],"w");
yylex();
fclose(yyin);
fclose(yyout);
printf("---------------------------------------------------------------\n");
printf("The
number of comment lines present in the source file =%d \n",c);
printf("---------------------------------------------------------------\n");
return 0;
}
2.a) Program to recognize a valid arithmetic
expression and identify the identifiers and operators present. Print them
separately.
/*valid
arithmetic expression*/
%{
int id=0;
int numid=0;
int op=0;
int valid=1;
int
p=0;
%}
%%
\( {
if(id==0)
{
p++;
}
else
valid=0;
}
\) {
if(id && valid)
{
p--;
}
else
valid=0;
}
[a-zA-Z0-9]+ {
if(!id && valid)
{
id=1;
numid++;
printf("identifier=%s\n",yytext);
}
else
valid=0;
}
[-+*/] {
if(id && valid)
{
id=0;
op++;
printf("operator =%s\n",yytext);
}
else
valid=0;
}
%%
main()
{
printf("Enter the expression");
yylex();
if(p==0 && op==numid-1 &&
valid==1)
{
printf("Valid arithmetic exp");
printf("Number of identifier
=%d\n",numid);
printf("Number
of operator =%d\n",op);
}
else
printf("Invalid
arithmatic exp\n");
}
2. b) Program to recognize whether a given sentence is
simple or compound
/*simple or
compound sentence*/
%{
int vsim=0;
int vcom=0;
%}
semi [;]
ob [{]
cb [}]
any [^{}]+
%%
{any}{semi} {
vsim=1;}
{any}{ob}{any}*{cb}{semi}*
{vcom=1;}
%%
main()
{
printf("ENTER
THE STATEMENT\n");
yylex();
if(vcom)
{
printf("COMPOUND
STATEMENT\n");
}
if(vsim)
{
printf("SIMPLE
STATEMENT\n");
}
else
printf("invalid
statement\n");
}
OR
/*simple or
compound sentence*/
%{
%}
%%
[ ][Aa][Nn][Dd][
] |
[ ][oO][rR][ ] |
[ ][bB][uU][Tt][ ] |
[ ][Nn][eE][vV][eE][rR][tT][hH][lL][eE][sS]+[ ] |
[ ][bB][eE][cC][aA][uU][sS][eE][ ] {
printf("Compound sentance\n");exit(0); }
. ;
%%
main()
{
printf("
Enter a statement \n");
yylex();
printf("Simple
sentance \n");
}
}
3) Program to recognize and count the number of
identifiers of a given input file
%{
#include<stdio.h>
int count=0;
char srcfl[100];
%}
letter [a-zA-Z_]+
digit [0-9]*
id {letter}*|({letter}{digit})+
notid ({digit}{letter})+|{digit}*
arr
("["[0-9]*"]")
fun [();]
%%
[\t\n]+
("int")
|
("void")
|
("char")
|
("float")
|
("double") {
printf("%s is a keyword\n", yytext); }
{id}{fun}*{arr}*
{ printf("%s is a identifier\n", yytext); count++; }
{notid} {
printf("%s not an identifier\n", yytext); }
. ;
%%
int main(int
argc, char *argv[])
{
if(argc>1)
{
yyin=fopen(argv[1],"r");
}
else
{
printf("enter the src file name\n");
scanf("%s",srcfl);
yyin=fopen(srcfl,"r");
}
yylex();
printf("identifier
count is %d",count);
return 0;
}
YACC
4. a) Program to recognize a valid arithmetic
expression that uses operators +,-,*, and
YACC part
%{
#include <stdio.h>
%}
%left '+' '-'
%left '*' '/'
%token ID
%%
lines:
| lines e
| lines '\n'
e: e '+' e
| e '-' e
| e '*' e
| e '/' e
| '(' e ')'
| ID
%%
int main()
{
printf ("This Yacc program
validates a given math expression.");
printf ("\nEnter the expression
and terminate with ENTER key:\n");
if (!yyparse())
printf ("Valid
expression.\n");
return 0;
}
int yyerror()
{
printf ("Invalid
expression.\n");
return 1;
}
int yylex()
{
int c;
c = getchar();
if (c == '\n')
return 0;
if (isalnum(c))
return ID;
return c;
}
4. b) Program to recognize a valid variable, which
starts with a letter, followed by any number of letters or digits.
%{
#include <stdio.h>
#include <ctype.h>
%}
%token DIGIT
ALPHA
%%
line: '\n'
;
| var '\n' { printf
("Valid identifier.\n"); return; }
var: ALPHA
| var alphanum
alphanum: DIGIT
| ALPHA
%%
int main()
{
printf ("This Yacc program
validates a C identifier.");
printf ("\nEnter the
variable:\n");
yyparse();
}
int yylex()
{
char c;
c = getchar();
if (isdigit (c))
return
DIGIT;
else if (isalpha (c) || c == '_')
return ALPHA;
return c;
}
int yyerror()
{
printf ("Invalid
identifier.\n");
}
5. a) Program
to evaluate an arithmetic expression involving operators +,-,* and /
%{
#include <stdio.h>
#define YYSTYPE double
%}
%token NUMBER
%left '+' '-'
%left '*' '/'
%%
start:
|
start expr '\n' { printf ("Value: %f\n", $2); return 0; }
| start '\n'
expr: expr '+' expr { $$ = $1 + $3; }
| expr '-' expr { $$ =
$1 - $3; }
| expr '*' expr { $$ =
$1 * $3; }
| expr '/' expr { $$ =
$1 / $3; }
| '(' expr ')' { $$ = $2; }
| NUMBER { $$ = $1; }
%%
main()
{
printf ("This Yacc program evaluates a
math expression.\n");
printf ("Enter the
expression:\n");
yyparse();
}
yylex()
{
char c;
while ((c=getchar()) == ' ')
;
if (isdigit(c)) {
ungetc (c, stdin);
scanf ("%lf",
&yylval);
return NUMBER;
}
return c;
}
yyerror()
{
printf ("Expression
invalid.\n");
}
5. b) Program to recognize strings ‘aaab’, ‘abbb’,’ab’
and ‘a’ using grammer (anbn,n>0)
%token A B
%%
start:
|
A start B
%%
yyerror()
{
printf ("String unacceptable for
the grammar (a^n)(b^n).\n");
exit (1);
}
yylex()
{
char c;
c = getchar();
if (c
== 'a') return A;
if (c == 'b') return B;
if (c == '\n') return 0;
return c;
}
main()
{
printf ("This Yacc
program checks if a string can");
printf (" be
accepted by the grammar (a^n)(b^n).\n");
printf ("Enter a string to
check:\n");
yyparse();
printf ("String acceptable for the
grammar (a^n)(b^n).\n");
}
6) Program to
recognize the grammar (anbn, n>=10)
%{
%}
%token A B
%%
LINE : A A A A A
A A A A A START B'\n' { printf("Accepted \n");exit;}
START :
| A START
;
%%
#include<stdio.h>
#include<ctype.h>
Main()
{
Printf("Enter
the grammer \n");
Yyparse();
}
Yylex()
{
Int c;
C=getchar();
If(c==EOF)
return 0;
If(c=='a')
return A;
If(c=='b')
return B;
Return c;
}
Yyerror()
{
Printf("Not
accpted \n");
}
PART B
Unix Programming:
1. a) Non recursive shell script that accepts any
number of arguments and print them in reverse order
#reverse the
arguments
c=$#
echo -e
"The argument's when reversed look like this : "
while [ $c -ne 0
]
do
eval echo \$$c
c=`expr $c - 1`
done
1. b) C program to create child process to read
commands from standard input and execute them.
#include<stdio.h>
#include<stdlib.h>
main()
{
char cmd[10];
int x,i=0;
x=fork();
if(x==0)
do
{
printf("Enter
the command:");
scanf("%s",cmd);
system(cmd);
printf("
1->continues\n 0->stop\n");
scanf("%d",&i);
}
while(i!=0);
wait();
printf("Child
process is over\n");
}
2. a) Shell script that accepts two file names as arguments, checks if the permissions are
identical and if the permissions are identical, output the common permissions,
otherwise output each file name followed by its permission.
#check file
permissions
file1=$1
file2=$2
set -- `ls -l
$file1`
x=$1
set -- `ls -l
$file2`
y=$1
if [ $x = $y ]
then echo -e
"\n Identical permission's
$x\n"
else
echo -e "\n Different permission's
\n $file1 = $x \n $file2 = $y\n"
fi
2. b) C program to create a file with 16 bytes of
arbitrary data from the beginning and another 16 bytes of arbitrary data from
an offset of 48
/*check file
hole*/
//prog 2.b
#include<stdio.h>
#include<sys/types.h>
#include<unistd.h>
#include<sys/stat.h>
int main()
{
char buf1[] =
"0123456789ABCDEF";
char buf2[] =
"GHIJKLMNOPQRSTUV";
int fd;
fd =
creat("filehole.dat",0);
write(fd,buf1,16);
lseek(fd,48,SEEK_SET);
write(fd,buf2,16);
exit(0);
}
3. a) Shell function that takes a valid directory
names as an argument and recursively desends all the subdirectories, finds the
maximum length of any file in that hierarchy and writes this maximum value to
standard output
echo "Enter
the directory name"
read dir
ls -lR $dir |
tee list1
cut -c 26-32
list1>list2
sort -n
list2>list3
echo
"Maximum file length is"
tail -1 list3
3. b) C program that accepts valid file names as
command line arguments and for each of the arguments, prints the type of the
file
#include<stdio.h>
#include<sys/types.h>
#include<unistd.h>
#include<sys/stat.h>
int main(int
argc,char *argv[])
{
int i=1;
struct stat buf;
char *ptr;
for(i=1;i<argc;i++)
{
printf("
file name =%s",argv[i]);
if(lstat(argv[i],&buf)<0)
{
printf("stat error");
exit(1);
}
if(S_ISREG(buf.st_mode))
ptr="Regular file";
else
if(S_ISDIR(buf.st_mode))
ptr="Directory file";
else
if(S_ISLNK(buf.st_mode))
ptr="Symbolic link";
else
if(S_ISSOCK(buf.st_mode))
ptr="socket file";
else
if(S_ISCHR(buf.st_mode))
ptr="character file";
else
if(S_ISFIFO(buf.st_mode))
ptr="fifo";
printf("\n
%s:%s\n",argv[i],ptr);
}
}
4. a) Shell script that accepts file names specified as
arguments and creates a shell script that contains this file as well as the
code to recreate these files. Thus if the script generated by this script ids
executed, it would recreate the original file.
#prog 4a
for i
do
echo "echo $i"
echo "cat > $i <<*"
cat $i
echo "*"
done
4.b) C program to do the following: Using fork()
create a child process. The child process prints its own pid and id of its
parent and then exists. The parent process waits for its child process and then
exists
/*c program to
print its child and parent id*/
#include<stdio.h>
#include<sys/types.h>
#include<unistd.h>
main()
{
int pid=0;
pid=fork();
/*if(pid==-1)
{
printf("Sorry
cant create child proces \n");
exit(0);
}*/
if(pid==0)
{
printf("I'm
child,my parent id is %d\n",getppid());
printf("My
pid is %d\n",getpid());
}
else
{
wait(200);
printf("\nI'am
parent,my pid is %d\n",getpid());
printf("My
child's pid is %d\n",pid);
}
}
COMPILER DESIGN
5. Write a C program to implement the syntax-directed
definition of “if E then S1” and “if E then S1 else S2”.
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int parsecondition(char[],int ,char *,int);
void
gen(char[],char[],char[],int);
int main()
{
int
counter=0,stlen=0,elseflag=0;
char stmt[60];
char strB[54];
char strS1[50];
char strS2[45];
printf("format
of if statement\n example............\n");
printf("if(a<b)then(s,a);\n");
printf("if(a<b)then(s,a)
else (s,b);\n\n");
printf("enter
the statement\n");
scanf("%s",&stmt);
stlen=strlen(stmt);
counter=counter+2;
counter=parsecondition(stmt,counter,strB,stlen);
if(stmt[counter]==')')
counter++;
counter=counter+3;
counter=parsecondition(stmt,counter,strS1,stlen);
if(stmt[counter+1]==';')
{
printf("\n parsing the input
statement...\n");
gen(strB,strS1,strS2,elseflag);
return 0;
}
if(stmt[counter]==')')
counter++;
counter=counter+3;
counter=parsecondition(stmt,counter,strS2,stlen);
counter=counter+2;
if(counter==stlen)
{
elseflag=1;
printf("\n parsing the input
statement");
gen(strB,strS1,strS2,elseflag);
return 0;
}
return 0;
}
int parsecondition(char input[],int cntr ,
char *dest, int totallen)
{
int index=0,pos=0;
while(input[cntr]!='(' &&
cntr<=totallen)
cntr++;
if(cntr>=totallen)
return 0;
index=cntr;
while(input[cntr]!=')')
cntr++;
if(cntr>=totallen)
return 0;
while(index<=cntr)
dest[pos++]=input[index++];
dest[pos]='\0';
return cntr;
}
void gen(char
B[],char S1[],char S2[],int elsepart)
{
int
Bt=101,Bf=102,Sn=103;
printf("\n\t
if %s goto %d",B,Bt);
printf("\n\t
goto %d",Bf);
printf("\n
%d:",Bt);
printf("%s",S1);
if(!elsepart)
printf("\n
%d:",Bf);
else
{
printf("\n\t goto %d",Sn);
printf("\n %d : %s",Bf,S2);
printf("\n %d:",Sn);
}
}
6. Write a yacc program that accepts a regular
expression as input and produce its parse tree
%{
#include<ctype.h>
char str[20];
int i=0;
%}
%token id
%left
'+''/''*''-'
%%
E:S
{infix_postfix(str);}
S:S'+'T|S'-'T
|T
T:T'*'F|T'/'F
|F
F:id|'('S')'
;
%%
#include<stdio.h>
main()
{
printf("\n
Enter the grammar:");
yyparse();
}
yyerror()
{
printf("invalid");
}
yylex()
{
char ch=' ';
while(ch!='\n')
{
ch=getchar();
str[i++]=ch;
if(isalpha(ch)) return id;
if(ch=='+'||ch=='*'||ch=='-'||ch=='/')
return ch;}
str[--i]='\0';
return(0);
exit(0);
}
void push(char
stack[],int *top, char ch)
{
stack[++(*top)]=ch;
}
char pop(char
stack[],int *top)
{
return(stack[(*top)--]);
}
int prec(char
ch)
{
switch(ch)
{
case '/' :
case '*' : return 2;
case '+' :
case '-' : return 1;
case '(' : return 0;
default :
return -1;
}
}
void
infix_postfix(char infix[])
{
int
top=-1,iptr=-1,pptr=-1;
char
postfix[20],stack[20],stksymb,cursymb;
push(stack,&top,'\0');
while((cursymb=infix[++iptr])!='\0')
{
switch(cursymb)
{
case '(' : push(stack,&top,cursymb);
break;
case ')' :
stksymb=pop(stack,&top);
while(stksymb!='(')
{
postfix[++pptr]=stksymb;
stksymb=pop(stack,&top);
}
break;
case '*' :
case '/' :
case '+' :
case '-' : while
(prec(stack[top])>=prec(cursymb))
postfix[++pptr]=pop(stack,&top);
push(stack,&top,cursymb);
break;
default :
if(isalnum(cursymb)==0)
{
printf("error in input:");
exit(0);
}
postfix[++pptr]=cursymb;
}
}
while(top!=-1)
postfix[++pptr]=pop(stack,&top);
printf("%s\n",postfix);
}
Viva Questions
System Software
1. What
is a System?
Systems
have interconnectivity; the various parts of a system have functional as
well as structural relationships to each other.
2. What
is System software?
System software is computer
software designed to operate the computer hardware and to
provide a platform for running application software.
3. Difference between System software and
application software.
·
System
software gets installed when the operating system is installed on the computer
while application software is installed according to the requirements of the
user.
·
System
software includes programs such as compilers, debuggers, drivers, assemblers
while application software includes media players, word processors, and
spreadsheet programs.
·
Generally,
users do not interact with system software as it works in the background
whereas users interact with application software while doing different
activities.
·
A computer
may not require more than one type of system software while there may be a
number of application software programs installed on the computer at the same
time.
·
System
software can run independently of the application software while application
software cannot run without the presence of the system software.
4. What is an Assembler?
Assembler for an assembly language, a computer program to
translate between lower-level representations of computer programs.
OR
An assembler converts basic computer instructions into a
pattern of bits which can be easily understood by the computer and the
processor can use it to perform its basic operations.
5. What is an editor?
Text editors are often provided
with operating systems or software development packages, and can be
used to change configuration files and language source.
6. What
is a linker?
Linker (computing), a computer program that
takes one or more objects generated by a compiler and combines them
into a single executable program.
7. What
is a compiler?
A compiler is
a computer program (or set of programs) that transforms source
code written in a programming language (the source
language) into another computer language (the target language,
often having a binary form known as object code). The most common
reason for wanting to transform source code is to create
an executable program.
8. What
is a Loader?
A loader is the part of an operating system that is
responsible for loading programs. Loading
a program involves reading the contents of executable file, the file containing the program text, into memory, and
then carrying out other required preparatory tasks to prepare the executable
for running.
9.
What is a Debugger?
A debugger or debugging
tool is a program that is used to test and debug other programs (the "target" program).
10.
What is a
Interpreter?
An interpreter normally
means a computer
program that executes,
i.e. performs, instructions
written in a programming
language. An interpreter may
be a program that either executes the source code directly
and translates source code into some efficient intermediate
representation (code)
and immediately executes.
Lex and Yacc
11. Explain lex
and yacc tools:-
Lex: - scanner that can identify those tokens
Yacc: - parser.yacc takes a concise description of a grammar and
produces a C routine that can parse that grammar.
12. Give the
structure of the lex program:-
Definition section- any intitial ‘c’ program code
% %
Rules section- pattern and action separated by white space
%%
User subroutines section-concsit of any legal code.
13. The lexer
produced by lex in a ‘c’ routine is called yylex()
14. Explain yytext:- contains the text that
matched the pattern.
15. The yacc
produced by parser is called yyparse().
16. Why we have
to include ‘y.tab.h’ in lex?
Y.tab.h contains token definitions eg:- #define letter 258.
17. Explain the structure of a yacc program?
Defn section- declarations of the tokens used in the grammar
%%
The rules section-pattern action
%%
Users subroutines section
18. Explain
yyleng?
Yyleng-contains the length of the string our lexer recognizes.
19. Define
action?
The C code
associated with a lex pattern or a yacc rule. When the pattern or rule matches
an input sequence, the action code
is executed.
20. Define
Pattern?
In a
lex lexer, a regular expression that the lexer matches against the input.
21. What
is an Alphabet?
A set of
distinct symbols .For example, the ASCII character set is a collection of 128
different symbols. In a lex specification, the alphabet is the native character
set of the computer, unless you use “%T” to define a custom alphabet.
22. Define
ASCII?
American
Standard Code for Information Interchange, a collection of 128 symbols
representing the common symbols found in the American alphabet: lower and upper
case letters, digits and punctuation, plus additional characters for formatting
and control of data communication links.
23. What
is an Ambiguity?
An Ambiguous grammar is one with more than
one rule or set of rules that match the same input.
24. Define
Finite Automaton?
An abstract
machine which consists of a finite number if instructions. Finite automata are
useful in modeling many commonly occurring computer processes and have useful
mathematical properties.
25. Define
Input.
A stream of data
read by a program. For instance, the input to a lex scanner is a sequence of
bytes, while the input to a yacc parser is a sequence of tokens.
26. Define
Language.
A well-defined
set of strings over some alphabet; informally, some set of instructions for
describing tasks which can be executed by a computer.
27. Define
Precedence.
The
order in which some particular operation is performed.
28. What
is a Parser?
A Parser for a
Grammar
is a program which takes in the Language string as it's input and produces
either a corresponding Parse tree or an Error.
29. What is the Syntax of a Language?
The Rules which tells whether a string is a valid Program or not are called the Syntax.
The Rules which tells whether a string is a valid Program or not are called the Syntax.
30. What is the Semantics of a Language?
The Rules which gives meaning to programs are called the Semantics of a language.
The Rules which gives meaning to programs are called the Semantics of a language.
31. What are
tokens?
When a string representing a program is broken into sequence of
substrings, such that each substring represents a constant, identifier,
operator, keyword etc of the language, these substrings are called the tokens
of the Language.
32. What is the Lexical Analysis?
The Function of a lexical Analyzer is to read
the input stream representing the Source program, one character at a time and
to translate it into valid tokens.
33. How can we represent a token in a language?
The Tokens in a
Language are represented by a set of Regular Expressions. A regular expression specifies a set of strings
to be matched. It contains text characters and operator characters. The Advantage
of using regular expression is that a recognizer can be automatically
generated.
34. How are the tokens recognized?
The tokens which
are represented by an Regular Expressions are recognized in an input string by
means of a state transition Diagram and Finite Automata.
35. Are Lexical Analysis and Parsing two different
Passes?
These two can form two different passes of a Parser. The Lexical
analysis can store all the recognized tokens in an intermediate file and give
it to the Parser as an input. However it is more convenient to have the
lexical Analyzer as a co-routine or a subroutine which the Parser calls
whenever it requires a token.
36. What are the Advantages of using Context-Free
grammars ?
It is precise
and easy to understand.
It is easier to determine syntactic ambiguities and conflicts in the grammar.
It is easier to determine syntactic ambiguities and conflicts in the grammar.
37. What are Terminals and non-Terminals in a
grammar?
Terminals:- All the basic symbols or
tokens of which the language is composed
of are called Terminals. In a
Parse Tree the Leafs represents the Terminal Symbol.
Non-Terminals:- These are syntactic variables in the grammar which represents a set of strings the grammar is composed of. In a Parse tree all the inner nodes represents the Non-Terminal symbols.
Non-Terminals:- These are syntactic variables in the grammar which represents a set of strings the grammar is composed of. In a Parse tree all the inner nodes represents the Non-Terminal symbols.
UNIX Shell &
System Programming
38. What is an internal command? Give an example?
Command which is shell built-in eg:echo
39. What is an external command? Give a example?
Command which resides in other
directories-eg:cd in /bin
40. What is an
absolute path name? Give an example?
A File name identification with respect to
the root. Eg:- /home/kumar/f1
41 What is an relative path name?
A
file identification not with respect to the root.
42. Differentiate the commands cp and mv?
Cp- copy the files
mv- renaming the file.
43. Shell- it is
a command interpreter.
Kernel- is the core of the
operating system.
44. What does $$
represents?
$$ represents the value of the left hand side.
45. What are
shell scripts?
Using a program, we can run more than one
command.
46. What is the usage of grep command?
Grep command is used to search a pattern in a
database.
47. What is exit
status command?
Exit
0- return success, command executed successfully.
Exit 1 – return failure.
48. What are
daemons?
They are one system processes
Uname: - tells
you the name of the unix system you are using.
Umask: - tells
unix which permissions to give to files and directories you create.
Tty- displays
the device name of your terminal
Vi editor- (visual editor)- used to write programs.
49.
Difference between fork() and vfork().
The only way a new process is
created by the Unix kernel is when an existing process calls the fork function.
The new process created by fork is called the child process. This function is
called once but returns twice. The only difference in the return value in the
child is 0 while the return value in the parent is the process ID of the new
child.
The
function vfork has the same calling sequence and same return values as fork.
But the semantics of the two functions differ. vfork is intended to create a
new process when the purpose of the new process is to exec a new program.
50. Difference
between wait() and waitpid()
wait can block
the caller until a child process terminates, while waitpid has an option that
prevents it from blocking.
waitpid
doesn’t wait for the first child to terminate, it has a number of options
that control which process it waits for.
51.
Define Job Control.
Job
control allows starting multiple jobs from a single terminal and controlling
which jobs can access the terminal and
which jobs are to run in the background.
52. Define
Process.
A process is an instance of
a computer program that is being executed. It contains the program code and its
current activity.
53. Difference
between Network Login and Terminal Login.
In
terminal login users logged in to the host using RS-232 connections. The
terminals were either local (directly
connected) or remote(connected through a modem). These logins came through a
terminal device driver in the kernel.
In
network login all the logins come through the kernel’s network interface
drivers (eg: the Ethernet driver).
Instead of having a process waiting for each possible login, now have to wait
for a network connection request to arrive.
54. Define
API’s
An application
programming interface (API)
is a source code based
specification
intended to be used as an interface by software components to communicate with
each other.
55. Explain
Different types of Files.
·
Regular file – is a text file or a
binary file. These files may be read or written to by users with the
appropriate access permission.
·
Directory file – It is like a file
folder that contains other files, including subdirectory files.
·
FIFO file – It is a special pipe device
file which provides a temporary buffer for two or more processes to communicate
by writing data to and reading data from the buffer.
·
Character device file – It represents a
physical device that transmits data in a character-based.
·
Block device file – It represents a
physical device that transmits data in a block at a time.
56. Define
Interpreter files.
Interpreter files are text files that
begin with a line of the form.
#! pathname
[optional-argument]
The space between the exclamation point
and the pathname is optional. The most common of these begin with the line
#!/bin/sh
The pathname is normally an absolute
pathname, no special operations are performed on it. The recognition of these
files is done within the kernel as part of processing the exec system call.
57. Define
Race Condition.
Race condition
occurs when multiple processes are trying to do something with shared data and
the final outcome depends on the order in which the processes run.
58. Define
Environment Variables.
The environment strings are usually of
the form
name=value
Environment variables ina shell start-up
file to control the shell’s actions. Use getenv to fetch a specific value from
the environment.
Eg: HOME, MAILPATH, USER
59. Explain
lseek().
Every open file
has an associated “current file offset.” This is a nonnegative integer that
measures the number of bytes from the beginning of the file. Read and write
operations normally start at the current file offset and cause the offset to be
incremented by the number of bytes read or written.
The interpretation of the offset depends
on the value of the whence argument.
· SEEK_SET
– The file’s offset is set to offset bytes from the beginning of the file.
· SEEK-CUR
– The file’s offset is set to its current value plus the offset.
· SEEK_END
– The file’s offset is set to the size of the file plus the offset.
60. Define
Sessions.
A session is a
collection of one or more process groups. A process establishes a new session
by calling the setsid function. The process groups within a session can be
divided into a single foreground process group and one or more background
process groups.
61. Define
Process groups.
Each process
also belongs to process groups. A process group is a collection of one or more
processes. Each process group has a unique process group ID. Process group IDs
are similar to process IDs they are positive integers and they can be stored in
a pid_t data type.
62. Explain
exit funtions
exit and _exit
functions is done by passing an exit status as the argument to these two functions.
The exit status is converted into a termination status by the kernel when _exit
is called. There are three ways for a process to terminate:
a. Normal
termination:
Executing a return from main function.
Calling the exit function
Calling the _exit function
b. Abnormal
termination:
Calling abort
When the process receives certain signals.
63. Explain
exec and list six different exec functions.
One use of the
fork function was to create a new process that then causes another program to
be executed by calling one of the exec functions. When a process calls one of
the exec functions, that process is completely replaced by the new program, and
the new program starts executing as its main function.
The six different exec functions are:
· execl
· execv
· execle
· execve
· execlp
· execvp
very good
ReplyDeleteit's sweet and short
very helpful for last day revision for lab exams