LL(1) parser

Let’s take a real-world example of interpreting a simple arithmetic expression in a calculator using an LL(1) parser. Imagine you have a small calculator program that can evaluate expressions involving addition and multiplication, such as:

3 + 5 * 2

The calculator uses an LL(1) parser to process and evaluate the input expression by building a parse tree. Here's how this works step by step.

Grammar Definition

For this simple calculator, we can define the grammar (syntax rules) to represent expressions involving numbers, addition, and multiplication. The grammar follows typical arithmetic precedence, where multiplication has higher precedence than addition:

E  → T E'          (E for Expression)
E' → + T E' | ε     (E' for Expression Prime)
T  → F T'          (T for Term)
T' → * F T' | ε     (T' for Term Prime)
F  → ( E ) | num    (F for Factor)

• E: Represents an entire expression, such as 3 + 5 * 2.
• E': Handles the continuation of the expression after a term, for example, dealing with the + in 3 + 5 * 2.
• T: Represents a term, such as 5 * 2.
• T': Handles the continuation of a term after a factor, for example, dealing with the * in 5 * 2.
• F: Represents a factor, which can be a number (e.g., 3, 5, or 2) or a parenthesized expression (e.g., (3 + 5)).

---

Real-World Example: Parsing 3 + 5 * 2

Let’s see how an LL(1) parser would process the expression 3 + 5 * 2.

1. Lookahead Input:
   Input: 3 + 5 * 2 $
   Stack: E $ (Start with the start symbol E)

2. Expand E (Expression):

   • The parser sees E and applies the production E → T E'.
   • Stack: T E' $
   • Input: 3 + 5 * 2 $

3. Expand T (Term):

   • The parser sees T and applies T → F T'.
   • Stack: F T' E' $
   • Input: 3 + 5 * 2 $

4. Expand F (Factor):

   • The parser sees F and applies F → num (since 3 is a number).
   • Stack: num T' E' $
   • Input: 3 + 5 * 2 $

5. Match num:

   • The parser matches the num with 3.
   • Stack: T' E' $
   • Input: + 5 * 2 $

6. Expand T' (Term Prime):

   • The parser sees T' and applies the epsilon production T' → ε (because the lookahead is +, and T' doesn’t expand for +).
   • Stack: E' $
   • Input: + 5 * 2 $

7. Expand E' (Expression Prime):

   • The parser sees E' and applies the production E' → + T E' (since the lookahead is +).
   • Stack: + T E' $
   • Input: + 5 * 2 $

8. Match +:

   • The parser matches the +.
   • Stack: T E' $
   • Input: 5 * 2 $

9. Expand T (Term):

   • The parser sees T and applies T → F T' (since the lookahead is 5).
   • Stack: F T' E' $
   • Input: 5 * 2 $

10. Expand F (Factor):

    • The parser sees F and applies F → num (since 5 is a number).
    • Stack: num T' E' $
    • Input: 5 * 2 $

11. Match num:

    • The parser matches the num with 5.
    • Stack: T' E' $
    • Input: * 2 $

12. Expand T' (Term Prime):

    • The parser sees T' and applies T' → * F T' (since the lookahead is *).
    • Stack: * F T' E' $
    • Input: * 2 $

13. **Match ***:

    • The parser matches the *.
    • Stack: F T' E' $
    • Input: 2 $

14. Expand F (Factor):

    • The parser sees F and applies F → num (since 2 is a number).
    • Stack: num T' E' $
    • Input: 2 $

15. Match num:

    • The parser matches the num with 2.
    • Stack: T' E' $
    • Input: $

16. Expand T' (Term Prime):

    • The parser sees T' and applies the epsilon production T' → ε (because the lookahead is $, the end of the input).
    • Stack: E' $
    • Input: $

17. Expand E' (Expression Prime):

    • The parser sees E' and applies the epsilon production E' → ε.
    • Stack: $
    • Input: $

At this point, the stack and input both have $, indicating that the parsing is successful, meaning the input expression 3 + 5 * 2 is syntactically valid.

---

Why LL(1) Parsers?

In this example, the LL(1) parser successfully processes the input by looking ahead one symbol at a time and predicting which rule to apply based on the current input token and the parser’s state. This technique is fast and efficient for simple grammars like arithmetic expressions.

Real-World Scenario:

This parsing technique is widely used in programming languages to parse arithmetic expressions, function calls, or other syntactically constrained constructs. For example, in your calculator app:

• You input 3 + 5 * 2.
• The parser uses an LL(1) strategy to break down the expression into its components (3, +, 5, *, 2).
• Based on the grammar rules, it ensures that the operations are executed in the correct order (multiplication before addition), and the expression is evaluated correctly to return the result:
  3 + (5 * 2) = 3 + 10 = 13

=========================================================================================

QUIZ Questions

=========================================================================================

Here are 10 multiple-choice questions (MCQs) on LL(1) Parsers suitable for GATE CSE preparation:

---

1. What does the "1" in LL(1) stand for?

A. One leftmost derivation step
B. One lookahead symbol
C. One production rule
D. One terminal symbol

Answer: B. One lookahead symbol

---

2. Which of the following is NOT a characteristic of an LL(1) parser?

A. It constructs a leftmost derivation of the input
B. It uses a bottom-up parsing strategy
C. It requires a single lookahead token to make parsing decisions
D. It generates a predictive parsing table

Answer: B. It uses a bottom-up parsing strategy

---

3. Which of the following statements is true for an LL(1) grammar?

A. The grammar must be ambiguous
B. The grammar cannot have left recursion
C. The grammar allows arbitrary lookahead
D. The grammar must have right recursion only

Answer: B. The grammar cannot have left recursion

---

4. What is the main reason left recursion must be eliminated in LL(1) parsers?

A. It reduces the size of the parsing table
B. Left recursion causes infinite recursion in top-down parsing
C. It improves the efficiency of parsing
D. Left recursion causes conflicts in the follow set

Answer: B. Left recursion causes infinite recursion in top-down parsing

---

5. For a grammar to be LL(1), which condition must hold for every non-terminal A with productions $A → α_1 | α_2 | ... | α_n$?

A. $FIRST(α_i) \cap FIRST(α_j) = \emptyset$ for all $i \neq j$
B. $FOLLOW(A) \cap FIRST(α_i) = \emptyset$
C. $FIRST(α_i) \cap FOLLOW(A) = \emptyset$
D. $FIRST(A) \cap FOLLOW(A) = \emptyset$

Answer: A. $FIRST(α_i) \cap FIRST(α_j) = \emptyset$ for all $i \neq j$

---

6. What is the purpose of the predictive parsing table in an LL(1) parser?

A. To store all possible productions for each non-terminal
B. To guide the parser in selecting the correct production based on the lookahead symbol
C. To resolve ambiguities in the grammar
D. To store the parsing stack during the parsing process

Answer: B. To guide the parser in selecting the correct production based on the lookahead symbol

---

7. Which of the following statements is true regarding the FIRST set in an LL(1) parser?

A. FIRST set contains only terminal symbols
B. FIRST set is used to determine the follow set of non-terminals
C. FIRST set is used to handle epsilon (ε) productions
D. FIRST set contains the start symbol of the grammar

Answer: A. FIRST set contains only terminal symbols

---

8. Given the following grammar, which of the following FIRST sets is correct for non-terminal A?

A → B C | ε
B → a | ε
C → b

A. FIRST(A) = {a, b, ε}
B. FIRST(A) = {a, ε}
C. FIRST(A) = {a, ε, b}
D. FIRST(A) = {a, b}

Answer: C. FIRST(A) = {a, ε, b}

---

9. Which of the following grammars is NOT suitable for LL(1) parsing?

A. A → a A'
A' → b | ε
B. A → A a | b
C. S → A b
A → c | ε
D. A → B C
B → b
C → c | ε

Answer: B. A → A a | b

---

10. What should be the entry in the LL(1) parsing table for non-terminal A and terminal 'b' if $FIRST(A)$ contains 'a', and $FOLLOW(A)$ contains 'b'?

A. Error
B. A → ε
C. A → a A
D. A → b

Answer: B. A → ε

Linear Algebra

                                 Matrices

• Square Matrix
• Diagonal Marix
• Scalar Matrix
• Identity Matrix
• Upper Triangular Matrix
• Lower Triangular Matrix
• Idempotent Matrix
• Involuntary Matrix
• Nilpotent Matrix
• Singular Matrix

Addition of Matrices

Multiplication of Matrices

Trace of a Matrix

Conjugate of a Matrix

Classification of Matrices

Symmetric Matrix

skew-Symmetric atri

Orthogonal Matrix

Adjoint properties

Inverse of Matrix properties

Rank of Matrix

Linear Dependent and Linear Independent Vectors

System of Homogeneous Linear Equations

System of Non-Homogeneous Linear Equations

Eigen Values & Eigen Vectors

Properties of Eigen Values

Cayley Hamilton theorem

Similar Matrices and Properties

Diagonalisation of Matrix

Calculus

Limits

Continuity

Differentiability

Mean Values Theorems

Rolle's Theorem

Lagranges Theorem

Rules of Differentiation

Integrals

Double Integrals

React JS

 Tutorial

Intro

- It is a fronted javascript library

- Created by Facebook

- A tool for building UI Components

How it works?

- Creates a virtual DOM Memory

- only changes what needs to be changed

-To use react, we need npm and Node.js installed.

- For production we need to set up a react environment.

Setting up a react environment and run react

If you have npx and Node.js installed, you can create a React application by using create-react-app

cd my-react-app

npm start

Modify the react Application

Look in the my-react-app directory, and you will find a src folder. Inside the src folder there is a file called App.js, open it.

Classes:

A class is a type of function, but instead of using the keyword function to initiate it, we use the keyword class, and the properties are assigned inside a constructor() method.

Create a class named "Model" which will inherit the methods from the "Car" class:

class Car {
  constructor(name) {
    this.brand = name;
  }

  present() {
    return 'I have a ' + this.brand;
  }
}

class Model extends Car {
  constructor(name, mod) {
    super(name);
    this.model = mod;
  }  
  show() {
      return this.present() + ', it is a ' + this.model
  }
}
const mycar = new Model("Ford", "Mustang");
mycar.show();

The super() method refers to the parent class.

By calling the super() method in the constructor method, we call the parent's constructor method and get access to the parent's properties and methods.

Arror Functions

- Allows us to write shorter function syntax.

hello = function() {
  return "Hello World!";
}

With Arrow Function:

hello = () => {
  return "Hello World!";
}

If the function has only one statement, and the statement returns a value, you can remove the brackets and the return keyword:

hello = () => "Hello World!";

If you have parameters, you pass them inside the parentheses:

hello = (val) => "Hello " + val;

What About this?

The handling of this is also different in arrow functions compared to regular functions.

In short, with arrow functions there is no binding of this.

In regular functions the this keyword represented the object that called the function, which could be the window, the document, a button or whatever.

With arrow functions, the this keyword always represents the object that defined the arrow function.

Variables

Now, with ES6, there are three ways of defining your variables: var, let, and const

If you use var outside of a function, it belongs to the global scope.

If you use var inside of a function, it belongs to that function.

If you use var inside of a block, i.e. a for loop, the variable is still available outside of that block.

let is the block scoped version of var, and is limited to the block (or expression) where it is defined.

If you use let inside of a block, i.e. a for loop, the variable is only available inside of that loop.

const is a variable that once it has been created, its value can never change

Array Methods

One of the most useful in React is the .map() array method.

The .map() method allows you to run a function on each item in the array, returning a new array as the result.

In React, map() can be used to generate lists.

const myArray = ['apple', 'banana', 'orange'];

const myList = myArray.map((item) => <p>{item}</p>)

Destructuring

To illustrate destructuring, we'll make a sandwich. Do you take everything out of the refrigerator to make your sandwich? No, you only take out the items you would like to use on your sandwich.

Destructuring is exactly the same. We may have an array or object that we are working with, but we only need some of the items contained in these.

Destructuring makes it easy to extract only what is needed.

Before:

const vehicles = ['mustang', 'f-150', 'expedition'];

// old way
const car = vehicles[0];
const truck = vehicles[1];
const suv = vehicles[2];

With destructuring:

const vehicles = ['mustang', 'f-150', 'expedition'];

const [car, truck, suv] = vehicles;

If we only want the car and suv we can simply leave out the truck but keep the comma:

const vehicles = ['mustang', 'f-150', 'expedition'];

const [car,, suv] = vehicles;

Spread Operator

The JavaScript spread operator (...) allows us to quickly copy all or part of an existing array or object into another array or object.

const numbersOne = [1, 2, 3];
const numbersTwo = [4, 5, 6];
const numbersCombined = [...numbersOne, ...numbersTwo];

Combine these two objects:

const myVehicle = {
  brand: 'Ford',
  model: 'Mustang',
  color: 'red'
}

const updateMyVehicle = {
  type: 'car',
  year: 2021, 
  color: 'yellow'
}

const myUpdatedVehicle = {...myVehicle, ...updateMyVehicle}

Profit and Loss

 Profit and Loss Tricks:

Youtube

-----------------------------------------------------------------------------------------------------------------------------

Profit% = (SP - CP / CP) *100

Loss% = (CP - SP/CP)*100

Examples:

1Q. : Bala buys chess boards in bulk for 15 each. He sells them for 40 each. Calculate the profit on each board in rupees, and as a percentage of the cost price.

SOL: Given:
cost price = 15, selling price = 40, 
profit = selling price - cost price
40 – 15 = 25
Profit % = 25*100/15 = 166.7%

Permutation and Combination GATE Questions

 Permutation and Combination GATE Questions

1Q. How many five digit numbers with distinct digits can be formed using the digit 1, 2, 3, 4, 5?

Solution: The number of distinct arrangements of 5 digits is calculated using the factorial of the number of digits:

$$5! = 5 \times 4 \times 3 \times 2 \times 1 = 120$$==========================================================================

2Q. How many three digit numbers can be formed using the digits 1, 2, 3, 4, 5 without repetition of digits?

Solution: 

1. Choose the first digit: There are 5 options (1, 2, 3, 4, or 5).
2. Choose the second digit: After selecting the first digit, there are 4 remaining options.
3. Choose the third digit: After selecting the first and second digits, there are 3 remaining options.

Thus, the total number of three-digit numbers can be calculated as follows:

$$\text{Total} = 5 \times 4 \times 3 = 60$$==========================================================================

3Q. How many three-digit odd numbers can be formed using the digits 1, 2, 3, 4, 5, when each digit occurs at most once in any of the numbers?

solution:

1. Choose the last digit: The last digit can be one of the odd digits: 1, 3, or 5. This gives us 3 options for the last digit.

2. Choose the first digit: After choosing the last digit, we have to select the first digit. The first digit can be any of the remaining digits (4 choices remaining).

3. Choose the second digit: After selecting the first and last digits, we have 3 remaining digits available for the second digit.

Total Combinations

Now, we can calculate the total number of three-digit odd numbers as follows:

• Choosing the last digit: 3 choices (1, 3, or 5).
• Choosing the first digit: 4 remaining choices.
• Choosing the second digit: 3 remaining choices.

Putting it all together, the total number of three-digit odd numbers can be calculated as:

$$\text{Total} = 3 \times 4 \times 3 = 36$$==========================================================================

Discreate Mathematics

 Proposition and Connectives

Satisfiable, Valid Questions

converse, inverse, contra-positive

Predicates and Quantifiers

Statements into Symbolic forms

Semigroup, monoid, group, abelian 

Poset, Hasse diagram

lattice

=========================================================================

Practice Questions

=========================================================================

1Q. Let A be a set with six elements. Which of the following cannot exist?
 (a) A subset of the power set of A with six elements.
 (b) An element of the power set of A with six elements.
 (c) An element of A containing six elements.
 (d) Any of the above can exists, for suitable sets A

Solution: 

(a) A subset of the power set of A with six elements:

• The power set of A contains all the subsets of A. The number of subsets in the power set of A is 26=642^6 = 6426=64. It's possible to form a subset of the power set containing six elements, so this option can exist.

(b) An element of the power set of A with six elements:

• The power set of A contains subsets of A, but the subsets must have between 0 and 6 elements, since A itself has 6 elements. A subset of A with six elements is just the set A itself. Therefore, this option can exist.

 (c) An element of A containing six elements:

• This cannot exist because the elements of A are not sets; they are individual elements. The set A has 6 elements, but no single element of A can contain 6 elements. So, this option cannot exist.

(d) Any of the above can exist, for suitable sets A:

• This is false because (c) cannot exist as discussed

========================================================================

2Q. Two finite sets have „m‟ and „n‟ elements respectively. The total number of subsets of „m‟ is 56 more than the total number of subsets of „n‟. The product of„m‟ and „n‟ is? _____

Solution:

According to the given information, the total number of subsets of the set with $m$ elements is 56 more than the total number of subsets of the set with $n$ elements. This gives the equation:

$$2^m = 2^n + 56$$=========================================================================

3Q. How many positive integers are there that are not larger than 1500 and are neither perfect squares nor perfect cubes? ________

Solution:

Step 1: Count the perfect squares

The number of perfect squares less than or equal to 1500 is the number of integers $n$ such that $n^2 \leq 1500$. The largest such $n$ is $\lfloor \sqrt{1500} \rfloor = 38$, because $38^2 = 1444$ and $39^2 = 1521$ exceeds 1500.

Thus, there are 38 perfect squares.

Step 2: Count the perfect cubes

The number of perfect cubes less than or equal to 1500 is the number of integers $n$ such that $n^3 \leq 1500$. The largest such $n$ is $\lfloor \sqrt[3]{1500} \rfloor = 11$, because $11^3 = 1331$ and $12^3 = 1728$ exceeds 1500.

Thus, there are 11 perfect cubes.

Step 3: Count the perfect sixth powers (numbers that are both squares and cubes)

A number that is both a perfect square and a perfect cube is a perfect sixth power. The number of perfect sixth powers less than or equal to 1500 is the number of integers $n$ such that $n^6 \leq 1500$. The largest such $n$ is $\lfloor \sqrt[6]{1500} \rfloor = 3$, because $3^6 = 729$ and $4^6 = 4096$ exceeds 1500.

Thus, there are 3 perfect sixth powers.

Step 4: Apply the principle of inclusion and exclusion

The number of integers up to 1500 that are either perfect squares or perfect cubes can be found using inclusion and exclusion:

$$\text{Number of squares or cubes} = (\text{Number of squares}) + (\text{Number of cubes}) - (\text{Number of sixth powers})$$ $$= 38 + 11 - 3 = 46$$

Step 5: Subtract from total numbers

The total number of positive integers up to 1500 is 1500. The number of integers that are neither perfect squares nor perfect cubes is:

$$1500 - 46 = 1454$$=========================================================================

5Q. Two finite sets have p and q elements given that p and q are consecutive prime numbers the total number of subsets of 1st set is 24 less than the total number of subsets of 2nd set. Find p + q. _______?

Solution:

According to the given information, the total number of subsets of the first set is 24 less than the total number of subsets of the second set. This gives the equation:

$$2^q - 2^p = 24$$=========================================================================

6Q. A set of mn objects can be partitioned into `m` sets of size `n` in _____different ways.

Solution:

The number of ways to partition $mn$ objects into $m$ sets of size $n$ is:

$$\frac{(mn)!}{(n!)^m \cdot m!}$$

• $(mn)!\; accounts\; for\; all\; possible\; permutations\; of\; the$$mn$ objects.
• $(n!)^m$ accounts for the fact that the elements within each subset can be arranged in $n!$ ways, but since the order of elements in each subset does not matter, we divide by $n!$ for each subset.
• $m!$ accounts for the fact that the order of the $m$ subsets does not matter, so we divide by $m!$.

=========================================================================

7Q. What will be expected cardinally of the subset of A, if cardinality of A= 10? __________

Solution:

Step 1: Number of Subsets

The total number of subsets of a set with $n$ elements is $2^n$. For $A$, with 10 elements, the total number of subsets is $2^{10} = 1024$.

Step 2: Expected Cardinality of a Subset

For each element of $A$, when forming a subset, there are two possibilities: either the element is included in the subset or it is not. Each element is included in a subset with a probability of $\frac{1}{2}$, because there are two equally likely outcomes for each element (in or out).

Therefore, the expected size (cardinality) of a randomly chosen subset of $A$ is:

$$\text{Expected cardinality} = \sum_{i=1}^{10} \mathbb{P}(\text{element } i \text{ is in the subset}) = 10 \times \frac{1}{2} = 5$$

$$==========================================================================$$

$$8Q.\; How\; many\; integers\; between\; 1\; and\; 1200\; inclusive\; do\; not\; share\; a\; common\; factor\; with\; 180,\; That\; is,\; are\; relative\; prime\; to\; other?\; \_\_\_\_\_\_\_\_$$

$$solution:$$

$$9Q.\; What\; is\; largest\; possible\; cardinality\; of\; A,\; if\; A\; is\; a\; collection\; of\; subsets\; of\; \{1,2,3---n\}such\; that\; no\; two\; elements\; of\; A\; are\; disjoint?\; (a)\; 2n-1\; (b)2n-1\; (c)\; 2n\; (d)2n/2$$

$$Solution:$$