Write a program to eliminate left factoring from a production of a grammar using JavaScript in Compiler Design

 In this article, we will explore left factoring and present a JavaScript program that eliminates left factoring from a production of a grammar. We will explain the theory behind left factoring, delve into the code implementation, and provide input/output examples.

Left factoring is a grammar transformation technique that involves identifying common prefixes among two or more productions and factoring them out into a separate production. 

For example, A -> α β | α γ 

After left factoring:

A -> α A'

A' -> β | γ

This process helps in avoiding ambiguity and redundancy in the grammar. The goal of left factoring is to simplify the grammar by removing unnecessary repetition.

Remove left factoring from a production of a grammar in JavaScript:

Let's explore the JavaScript code that eliminates left factoring from a grammar production:

let nonTerminal = 'S';
let productions = 'iEtS|iEtSeS|a|iES';
console.log(`The given grammar is: ${nonTerminal} --> ${productions}`);

const LeftFactoring = (productions) => {
  let words = productions.split('|').filter(e => e !== '');
  if (words.length > 1) {
    const counts = words.reduce((acc, w) => {
      let prefix = '';
      for (let i = 0; i < w.length; i++) {
        prefix += w[i];
        acc[prefix] = (acc[prefix] || 0) + 1;
      }
      return acc;
    }, {});

    try {
      const alpha = Object.entries(counts)
        .filter(([_, v]) => v > words.length / 2.0)
        .sort((a, b) => b[0].length - a[0].length)[0][0];

      let nonTerminalPrime = '';
      words.filter(word => word.includes(alpha))
        .map(word => word.replace(alpha, ''))
        .filter(e => e !== '')
        .forEach(e => nonTerminalPrime += e + '|');
      let gamma = words.filter(word => !word.includes(alpha));
      console.log(`${nonTerminal} --> ${alpha}${nonTerminal}'${gamma ? `|${gamma}` : ''}`);
      console.log(`${nonTerminal}' --> ${nonTerminalPrime}#`);

      nonTerminal = `${nonTerminal}'`;
      LeftFactoring(nonTerminalPrime);
    } catch {
      console.log('...................');
    }
  }
}

console.log(`After Left Factoring:`);
LeftFactoring(productions);

Input/Output:

Explanation:

Let's go through the code step by step to understand how it eliminates left factoring from a production of a grammar:

The code begins by initializing the non-terminal symbol (nonTerminal) and the productions (productions) as input. The productions are split into individual words, separated by the '|' (pipe) character.

The LeftFactoring function is then defined to handle the left factoring process. It starts by checking if there are multiple productions. If so, it counts the occurrences of prefixes in the productions. The most frequent prefix (alpha) is identified as the common prefix to be factored out.

Next, the function creates a new non-terminal symbol (nonTerminalPrime) and generates the remaining suffixes by replacing the common prefix with an empty string. The suffixes are then added as alternatives to the new non-terminal symbol.

The function prints the modified productions, replacing the common prefix with the new non-terminal symbol (nonTerminal'). It also calls itself recursively, passing the new non-terminal symbol to handle further left factoring.

The program outputs the transformed grammar with left factoring applied.

Conclusion: 

In this article, we have explored the concept of left factoring in grammar productions and provided a JavaScript program that eliminates left factoring. The JavaScript code presented demonstrates the practical implementation of left factoring.   

Happy coding!

Previous Article:

Write a program to eliminate left recursion from a production of a grammar using JavaScript in Compiler Design

 

Ashraf Compiler Design