Experiment No.

Aim: Lex program to evaluate arithmetic expression.

Theory: YACC (Yet Another Compiler Compiler) is a computer program developed

for the Unix operating system. It provides a tool to generate a parser for a given
grammar. It is specifically designed to compile a LALR (1) grammar. YACC
generates the source code for the syntactic analyzer of a language defined by a
LALR (1) grammar. The input to YACC consists of the rules or grammar, and its
output is a C program.

YACC serves as a powerful grammar parser and generator. In essence, it functions

as a tool that takes in a grammar specification and transforms it into executable code
capable of meticulously structuring input tokens into a coherent syntactic tree,
aligning seamlessly with the prescribed grammar rules.
YACC was developed by Stephen C. Johnson in the 1970s. Initially, the YACC was
written in the B programming language and was soon rewritten in C. It was originally
designed to be complemented by Lex.
In addition to that, YACC was also rewritten in OCaml, Ratfor, ML, ADA, Pascal,
Java < Python, Ruby and Go.

Purpose of YACC:

●​ Converts a formal grammar into a parser.​

●​ Helps in syntax analysis in compiler design.​

●​ Used in conjunction with Lex to form complete lexical + syntactic analyzers.

Parts of a YACC Program in Compiler Design:

/* definitions */
....
%%
/* rules */
....
%%

/* auxiliary routines */
....

Definitions: These include the header files and any token information used in the
syntax. These are located at the top of the input file. Here, the tokens are defined
using a modulus sign. In the YACC, numbers are automatically assigned for tokens.

Rules: The rules are defined between %% and %%. These rules define the actions
for when the token is scanned and are executed when a token matches the
grammar.

Auxiliary Routines: Auxiliary routines contain the function required in the rules
section. This Auxiliary section includes the main() function, where the yyparse()
function is always called.

Execution Steps of YACC Program:

1.​ Create Lex and YACC files: Typically with .l and .y extensions respectively.​

2.​ Use Lex to generate lex.yy.c:

lex file.l

3.​ Use YACC to generate y.tab.c and y.tab.h:

yacc -d file.y

4.​ Compile both files:

​
gcc lex.yy.c y.tab.c -o parser

5.​ Run the parser:​

​
./parser
YACC Terminologies:

$$ → Value of the current non-terminal (LHS).​

$1, $2, ... → Value of the corresponding symbols on RHS.​

%token → Used to declare terminals/tokens.​

%left, %right, %nonassoc → Define associativity and precedence of operators.

Lex Program:

%{
#include "y.tab.h"
#include <math.h>
extern yylval;
%}
%%
[0-9]+ { yylval = atoi(yytext); return NUM; }
[+] { return '+'; }
[-] { return '-'; }
[*] { return '*'; }
[/] { return '/'; }
[\t]+ ;
[\n] { return 0; }
. { return yytext[0]; }
%%

YACC Program:

%{
#include <stdio.h>
%}
%token NUM
%left '+' '-'
%right '*' '/'
%%
start: exp { printf("%d\n", $$); }
;

exp: exp '+' exp { $$ = $1 + $3; }

| exp '-' exp { $$ = $1 - $3; }
| exp '*' exp { $$ = $1 * $3; }
| exp '/' exp
{
if ($3 == 0)
yyerror("error");
else
$$ = $1 / $3;
}
| '(' exp ')' { $$ = $2; }
| NUM { $$ = $1; }
;
%%
main()
{
printf("Enter the Expr. in terms of integers\n");
if (yyparse() == 0)
printf("Success\n");
}

yywrap() {}
yyerror()
{
printf("Error\n");
}

Execution Steps:

lex calci.l
yacc -d calci.y
gcc lex.yy.c y.tab.c -o calci
./calci

Output:

Enter the expression in terms of integers: 5*8+3 (press enter)

43
Success

Conclusion:
We have successfully performed Implementation of yacc parser to evaluate
arithmetic expressions involving +, -, *, /.
 Experiment No: 6

Aim: Stack implementation of SR parser.

Theory:

A Shift-Reduce Parser is a type of bottom-up parser used in syntax analysis

during compilation. It constructs the parse tree from the leaves (input symbols) and
works its way up to the root (start symbol). This parser reads the input string from left
to right and applies shift and reduce operations to derive the start symbol of the
grammar.

It is called shift-reduce because:

●​ It shifts symbols from the input buffer to the stack.​

●​ It reduces a sequence of stack symbols using grammar rules.

Purpose:

The purpose of an SR parser is to determine whether a given input string belongs to

a particular grammar. If it does, the parser builds the corresponding parse tree. SR
parsers are typically used in compiler design to process programming language
syntax.

Main Components of SR Paarsers:

1.​ Input Buffer: Holds the input string to be parsed.​

2.​ Stack: Stores grammar symbols and helps with shift and reduce operations.​

3.​ Parsing Table (optional): Guides the parser on whether to shift, reduce,
accept, or report an error.​

4.​ Parser Program: Implements the logic to simulate the parsing process.

Basic Operations Performed:

1.​ Shift: Move the next input symbol from the input buffer to the stack.​

2.​ Reduce: Replace a substring of the stack (called a handle) that matches the
right-hand side of a grammar rule with its left-hand side non-terminal.​
 3.​ Accept: Successfully parsed the string when the input buffer is empty and the
stack contains only the start symbol.​

4.​ Error: Occurs when the parser cannot proceed with either shift or reduce.

SR Conflict:

SR Conflict occurs when the parser is confused between shifting the next input
symbol and reducing the existing symbols in the stack. It is one of the most common
conflicts that arises while working with shift-reduce parsers. This happens mainly
when the grammar is not properly defined or when it allows for more than one
interpretation at a certain point. In such situations, the parser cannot decide whether
to perform a shift operation, i.e., move the next input symbol to the stack, or to
reduce the symbols in the stack based on a production rule.

This conflict arises due to ambiguity in the grammar. For example, in arithmetic
expressions like id + id * id, the parser may be unsure whether to reduce id +
id first (due to the addition operator) or to shift and include the multiplication
operator * which has higher precedence. Without clearly defined precedence and
associativity rules, such confusion is natural for the parser.

SR Conflict makes the parsing process incorrect or incomplete, and hence, such
conflicts must be resolved either by rewriting the grammar to be more specific or by
assigning proper precedence and associativity to the operators used in the grammar.
In tools like YACC, operator precedence declarations help the parser resolve such
conflicts automatically and parse the input correctly.

Steps to Execute SR Parsers:

1.​ Understand the Grammar: Choose a simple unambiguous grammar suitable

for SR parsing.​
​
Example Grammar:​
​
E → E + E | E → E * E | E → ( E ) | E → id

2. Simulate Shift-Reduce Parsing:​

○​ a) Shift: Push the current input symbol onto the stack.​

○​ b) Reduce: If the top of the stack matches a production rule's

right-hand side, replace it with the left-hand side non-terminal.​
 ○​ c) Accept: If the entire input is consumed and the stack has only the
start symbol, the string is accepted.​

○​ d) Error: If no valid shift/reduce operation is possible, the string is

rejected.​

3. Write a Program for Simulation:​

○​ Use a stack to store symbols.​

○​ Read the input using a buffer.​

○​ Implement logic to shift, reduce, accept, or reject based on stack

contents and grammar.

Program:

//C program for SR parser

#include <stdio.h>

#include <string.h>

#define MAX 100

char stack[MAX]; // Stack for parsing

char input[MAX]; // Input string

int top = -1; ​ // Stack pointer

// Function to push to stack

void push(char c) {

stack[++top] = c;

// Function to pop from stack

void pop() {
 top--;

// Function to display current stack and input

void display() {

printf("\nStack: ");

for (int i = 0; i <= top; i++)

printf("%c", stack[i]);

printf("\tInput: %s", input);

// Function to check for a possible reduction

int reduce() {

if (top >= 2) {

// Check for E+E or E*E

if ((stack[top-2] == 'E') && (stack[top] == 'E') && (stack[top-1] == '+' ||

stack[top-1] == '*')) {

printf("\nReduce by E → E %c E", stack[top-1]);

pop(); pop(); pop();

push('E');

return 1;

​ }

if (top >= 2 && stack[top-2] == '(' && stack[top-1] == 'E' && stack[top] == ')') {

printf("\nReduce by E → (E)");
 pop(); pop(); pop();

push('E');

return 1;

​ }

if (top >= 0 && stack[top] == 'i') {

printf("\nReduce by E → id");

pop();

push('E');

return 1;

​ }

return 0;

// Function to perform shift-reduce parsing

void shiftReduceParser() {

int i = 0;

printf("\nShift-Reduce Parsing:");

while (1) {

display();

if (input[i] != '\0') {

printf("\nShift: %c", input[i]);

push(input[i]);

input[i] = ' ';

i++;

}
 while (reduce()); // Perform reductions if possible

if (top == 0 && stack[top] == 'E' && input[i] == '\0') {

printf("\n\nString Accepted!");

return;

if (input[i] == '\0' && !reduce()) {

printf("\n\nString Rejected!");

return;

​ }

// Main function

int main() {

printf("Enter input string (e.g., i+i*i or (i+i)): ");

scanf("%s", input);

shiftReduceParser();

return 0;

Output:
Enter input string (e.g., i+i*i or (i+i)): i+i*i

Shift-Reduce Parsing:
Stack: Input: i+i*i
Shift: i
Reduce by E → id
Stack: E Input: +i*i
Shift: +
Stack: E+ Input: i*i
Shift: i
Reduce by E → id
Stack: E+E Input: *i
Reduce by E → E + E
Stack: E Input: *i
Shift: *
Stack: E* Input: i
Shift: i
Reduce by E → id
Stack: E*E Input:
Reduce by E → E * E
Stack: E Input:

String Accepted!

Conclusion: Thus we have successfully studied and implemented stack

implementation of SR Parser.
 Experiment No: 7
Aim:Implementation of LR(0) Parser

Theory:

An LR(0) parser is a type of bottom-up parser used in compiler design.

It processes the input from left to right and constructs a rightmost derivation in
reverse.​

LR(0) stands for:​

●​ L: Left-to-right scanning of input​

●​ R: Rightmost derivation​

●​ 0: No lookahead used during parsing

It uses LR(0) items and a finite automaton to decide the parsing action (shift or
reduce).
It can handle a subset of context-free grammars and is a base for more powerful
parsers like SLR, LALR, and Canonical LR.

Terminology:

●​ Canonical Items: A production with a dot (.) representing the parser’s

position in the input.
○​ Example: B → •BB, B → B•B
●​ Augmented Grammar: The original grammar is modified by adding a new
start symbol to help define the initial state.
○​ Example: If S is the start symbol, then augmented grammar will have
S' → S
●​ Automaton (DFA): A deterministic finite automaton is constructed using the
canonical LR(0) items to drive parsing.

Steps to Use LR(0) Parser:

1.​ Augment the grammar by introducing a new start symbol.​

2.​ Create LR(0) items for each production.​

3.​ Construct the DFA (Automaton):​

 ○​ Use closure and goto functions to create the DFA states.​

4.​ Build the Parsing Table (ACTION and GOTO):​

○​ ACTION: shift, reduce, accept or error​

○​ GOTO: transitions on non-terminals​

5.​ Parse the string using the stack, input buffer, and parsing table.

Program:

// c program for LR(0) parser

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#define MAX 100

typedef struct Node {

char symbol[10];

struct Node *left, *right;

} Node;

Node* stack[MAX]; // Stack for parse tree nodes

char input[MAX]; // Input string

int top = -1;

// Create a new node for the parse tree

Node* createNode(char *symbol, Node *left, Node *right) {

 Node* newNode = (Node*)malloc(sizeof(Node));

strcpy(newNode->symbol, symbol);

newNode->left = left;

newNode->right = right;

return newNode;

// Push to stack

void push(Node* node) {

stack[++top] = node;

// Pop from stack

Node* pop() {

return stack[top--];

// Display current stack and input

void display() {

printf("\nStack: ");

for (int i = 0; i <= top; i++)

printf("%s ", stack[i]->symbol);

printf("\tInput: %s", input);

}
// Shift operation

void shift(char c) {

printf("\nShift: %c", c);

char str[2] = {c, '\0'};

push(createNode(str, NULL, NULL));

memmove(input, input + 1, strlen(input)); // Move input pointer

// Reduce operation

int reduce() {

if (top >= 2) {

// E → E + E or E → E * E

if ((strcmp(stack[top - 2]->symbol, "E") == 0) &&

(strcmp(stack[top]->symbol, "E") == 0) &&

(strcmp(stack[top - 1]->symbol, "+") == 0 || strcmp(stack[top - 1]->symbol, "*")

== 0)) {

printf("\nReduce by E → E %s E", stack[top - 1]->symbol);

Node *right = pop();

Node *op = pop();

Node *left = pop();

push(createNode("E", left, right));

return 1;

​ }
 if (top >= 2 && strcmp(stack[top - 2]->symbol, "(") == 0 &&

strcmp(stack[top - 1]->symbol, "E") == 0 &&

strcmp(stack[top]->symbol, ")") == 0) {

printf("\nReduce by E → (E)");

Node *right = pop();

pop(); // Remove "("

Node *left = pop();

push(createNode("E", left, right));

return 1;

​ }

if (top >= 0 && strcmp(stack[top]->symbol, "i") == 0) {

printf("\nReduce by E → id");

Node *id = pop();

push(createNode("E", id, NULL));

return 1;

​ }

return 0;

// Recursive function to print parse tree

void printParseTree(Node* root, int level) {

if (root == NULL) return;

printParseTree(root->right, level + 1);

 for (int i = 0; i < level; i++)

printf(" ");

printf("%s\n", root->symbol);

printParseTree(root->left, level + 1);

// LR(0) Parsing Function

void lrParser() {

int i = 0;

printf("\nLR(0) Parsing:");

while (1) {

display();

if (input[i] != '\0') {

shift(input[i]);

input[i] = ' ';

i++;

while (reduce());

if (top == 0 && strcmp(stack[top]->symbol, "E") == 0 && input[i] == '\0') {

printf("\n\nString Accepted!\n");

printf("\nParse Tree:\n");

printParseTree(stack[top], 0);

return;
 }

if (input[i] == '\0' && !reduce()) {

printf("\n\nString Rejected!");

return;

​ }

// Main function

int main() {

printf("Enter input string (e.g., i+i*i or (i+i)): ");

scanf("%s", input);

lrParser();

return 0;

Output:
Enter input string (e.g., i+i*i or (i+i)): i+i*i

LR(0) Parsing:
Stack: Input: i+i*i
Shift: i

Stack: i Input: +i*i

Reduce by E → id

Stack: E Input: +i*i

Shift: +

Stack: E + Input: i*i

Shift: i
Stack: E + i Input: *i
Reduce by E → id

Stack: E + E Input: *i
Shift: *

Stack: E + E * Input: i
Shift: i

Stack: E + E * i Input:
Reduce by E → id

Stack: E + E * E Input:
Reduce by E → E * E

Stack: E + E Input:
Reduce by E → E + E

Stack: E Input:

String Accepted!

Parse Tree:
E
E
E
E
i
+
E
E
i
*
E
i

Conclusion: Thus we have successfully studied and implemented LR(0) Parser.

 Experiment No. 8

Aim: Implementation of Operator Precedence Parser.

Theory:

An Operator Precedence Parser is a type of bottom-up parser that uses a

precedence relation between pairs of terminals to guide the parsing process. It
works by applying shift and reduce operations depending on the precedence
relationship between symbols on the stack and the next input symbol.

Description:

1.​ Operator Precedence:

●​ Defines rules for resolving ambiguity in expressions with multiple operators
(e.g., which operator to apply first).​

●​ A precedence table is used to compare operators (+, *, id, $) and determine

parsing actions.​

2.​ Operator Relation Table:​

●​ A table defining relations like <, =, > between pairs of terminals.​

●​ Helps the parser decide whether to shift or reduce.​

3.​ Parsing Table Construction:​

●​ Input symbols and stack symbols are compared using the precedence table.​

●​ If the stack top precedence < input, shift operation is performed.​

●​ If the stack top precedence > input, reduce operation is performed.​

4.​ Shift and Reduce Actions:​

●​ Shift: Push the input symbol onto the stack and move to the next symbol.​

●​ Reduce: Replace the handle (e.g., T * T) on the stack with its corresponding
non-terminal (e.g., T).​

5.​ Acceptance:​
 ●​ The string is accepted if, after all reductions, the stack contains the start
symbol and the input is $.

Program:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char *input;
int i = 0;
char lasthandle[6], stack[50], handles[][5] = {")E(", "E*E", "E+E", "i", "E^E"};
int top = 0, l;

char prec[9][9] = {
/*input + - * / ^ i ( ) $ */
/*stack +*/ {'>', '>', '<', '<', '<', '<', '<', '>', '>'},
/* -*/ {'>', '>', '<', '<', '<', '<', '<', '>', '>'},
/* **/ {'>', '>', '>', '>', '<', '<', '<', '>', '>'},
/* / */{'>', '>', '>', '>', '<', '<', '<', '>', '>'},
/* ^ */{'>', '>', '>', '>', '<', '<', '<', '>', '>'},
/* i */{'>', '>', '>', '>', '>', 'e', 'e', '>', '>'},
/* ( */{'<', '<', '<', '<', '<', '<', '<', '>', 'e'},
/* ) */{'>', '>', '>', '>', '>', 'e', 'e', '>', '>'},
/* $ */{'<', '<', '<', '<', '<', '<', '<', '<', '>'}
};

int getindex(char c) {
switch (c) {
case '+': return 0;
case '-': return 1;
case '*': return 2;
case '/': return 3;
case '^': return 4;
case 'i': return 5;
case '(': return 6;
case ')': return 7;
case '$': return 8;
default: return -1;
}
}

int shift() {
stack[++top] = *(input + i++);
 stack[top + 1] = '\0';
return 1;
}

int reduce() {
int len, found, t;
for (int i = 0; i < 5; i++) {
len = strlen(handles[i]);
if (stack[top] == handles[i][0] && top + 1 >= len) {
found = 1;
for (t = 0; t < len; t++) {
if (stack[top - t] != handles[i][t]) {
found = 0;
break;
}
}
if (found == 1) {
stack[top - t + 1] = 'E';
top = top - t + 1;
strcpy(lasthandle, handles[i]);
stack[top + 1] = '\0';
return 1;
}
}
}
return 0;
}

void dispstack() {
for (int j = 0; j <= top; j++)
printf("%c", stack[j]);
}

void dispinput() {
for (int j = i; j < l; j++)
printf("%c", *(input + j));
}

int main() {
input = (char *)malloc(50 * sizeof(char));
if (input == NULL) {
printf("Memory allocation failed!\n");
return 1;
}
 printf("\nEnter the string:\n");
scanf("%s", input);
input = strcat(input, "$");
l = strlen(input);
strcpy(stack, "$");

printf("\nSTACK\tINPUT\tACTION");

while (i < l) {
shift();
printf("\n");
dispstack();
printf("\t");
dispinput();
printf("\tShift");
while (prec[getindex(stack[top])][getindex(input[i])] == '>') {
if (reduce()) {
printf("\n");
dispstack();
printf("\t");
dispinput();
printf("\tReduced: E->%s", lasthandle);
}
}
}

if (strcmp(stack, "$E$") == 0)
printf("\nAccepted;");
else
printf("\nNot Accepted;");

free(input);
return 0;
}

Output:
Enter the string:
i+i*i

STACK​ INPUT​ ACTION

$i​ +i*i$​ Shift
$E​ +i*i$​ Reduced: E->i
$E+​ i*i$​ Shift
$E+i​ *i$​ Shift
$E+E​ *i$​ Reduced: E->i
$E+E*​i$​ Shift
$E+E*i​ $​ Shift
$E+E*E​ $​ Reduced: E->i
$E+E​ $​ Reduced: E->E*E
$E​ $​ Reduced: E->E+E
Accepted;

Conclusion: Thus, we have successfully studied and implemented Operator

Precedence Parser.