Scribd
Upload
11 views5 pages

Task 2

The document outlines the design of a programming language called CalcScript that supports arithmetic expressions with proper precedence and balanced parentheses. It includes tasks such as deriving a specific string using leftmost derivation, analyzing ambiguity in the grammar, and designing a parser using a bottom-up technique. The document also provides a C++ code implementation for evaluating expressions in CalcScript.

Uploaded by

Sk Shehzad
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
11 views5 pages

Task 2

The document outlines the design of a programming language called CalcScript that supports arithmetic expressions with proper precedence and balanced parentheses. It includes tasks such as deriving a specific string using leftmost derivation, analyzing ambiguity in the grammar, and designing a parser using a bottom-up technique. The document also provides a C++ code implementation for evaluating expressions in CalcScript.

Uploaded by

Sk Shehzad
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 5

UNIVERSITY OF ENGINEERING AND TECHNOLOGY MARDAN

CS-503 THEORY OF PROGRAMMING LANGUAGES


Task# 02
nd
MS CS 2 Semester Spring 2025
Name: Shehzad Khan Submitted to: Dr. Bilal Khan
Registration No: 24MFCS033 Date: 13-03-2025

Scenario:
You are designing a programming language called CalcScript that supports arithmetic
expressions with addition (+), multiplication (*), parentheses, and variables (id). The
language requires proper precedence (multiplication before addition) and balanced
parentheses.

 Non-terminals: {𝐸, 𝑇, 𝐹}
The grammar is:

 Start symbol: 𝐸
 Terminals: {+,*,(,),𝑖𝑑}

 Production rules:
1. E → E + T | T
2. T → T * F | F
3. F → (E) | id
Tasks:
Derivation and Parse Tree:
 Derive the string "id + id * (id + id)" using the leftmost derivation.
 Draw the corresponding parse tree.
Ambiguity Analysis:
 Check if the CFG is ambiguous with examples.
 If ambiguous, modify the CFG to resolve ambiguity while preserving precedence and
associativity.
Parser Design:
 Choose a parsing technique (top-down or bottom-up) and justify it.
 Outline a parser implementation strategy for CalcScript.

Derivation and Parse Tree


Given String:
id + id * (id + id)
Leftmost Derivation:
Starting from E:
1. E → E + T
2. E → T + T
3. T → F + T
4. F → id + T
5. T → T * F
6. T → F * F
7. F → id * F

1|Page
8. F → (E)
9. E → E + T
10. E → T + T
11. T → F + T
12. F → id + T
13. T → id
Thus, the full derivation is:
id + id * (id + id)
Parse Tree:
The parse tree follows operator precedence (multiplication before addition):

Ambiguity Analysis
A grammar is ambiguous if there exists more than one valid parse tree for the same string.
Checking Ambiguity:
Consider the string:
id + id * id
Two possible parse trees:
1. Parse Tree 1 (Correct Precedence)

2|Page
2. Parse Tree 2 (Incorrect Precedence, Addition First)

Since we get multiple parse trees, this grammar is ambiguous.

Resolving Ambiguity
To enforce multiplication before addition, we rewrite the grammar:

3|Page
E → E + T | T
T → T * F | F
F → id | (E)
By enforcing T * F at a lower level, multiplication is evaluated before addition.

Parser Design
We choose Bottom-Up Parsing (LR Parser) because:
 It naturally handles operator precedence.
 It constructs the parse tree from leaves to the root.
 It works well with left-recursive grammars.
Parser Implementation Strategy:
1. Lexical Analysis:
o Tokenize input (id, +, *, (, ))
2. Syntax Analysis (Parsing):
o Use Shift-Reduce Parsing (LR Parser)
o Reduce expressions using the grammar rules.
3. Evaluation (Semantic Analysis):
o Maintain a stack to evaluate expressions.

Code Implementation (C++)


#include <iostream>
#include <stack>
#include <cctype>
#include <string>
using namespace std;
// Function to evaluate expressions
int evaluate(string expr) {
stack<int> values; // Stack to store numbers
stack<char> ops; // Stack to store operators
auto applyOperator = [&](char op) {
int val2 = values.top(); values.pop();
int val1 = values.top(); values.pop();
values.push((op == '+') ? (val1 + val2) : (val1 * val2));
};
for (int i = 0; i < expr.length(); i++) {
char curr = expr[i];
if (isdigit(curr)) {
values.push(curr - '0'); // Convert char to int
}
else if (curr == '(') {
ops.push(curr);
}
else if (curr == ')') {
while (ops.top() != '(') {
applyOperator(ops.top());
ops.pop();

4|Page
}
ops.pop(); // Remove '('
}
else if (curr == '+' || curr == '*') {
while (!ops.empty() && ops.top() == '*' && curr == '+') {
applyOperator(ops.top());
ops.pop();
}
ops.push(curr);
}
}
// Apply remaining operators
while (!ops.empty()) {
applyOperator(ops.top());
ops.pop();
}
return values.top();
}
int main() {
string expression = "3+2*(1+4)"; // Example input
cout << "Result: " << evaluate(expression) << endl;
return 0;
}

5|Page

You might also like