Write a program to eliminate left recursion from a production of a grammar using JavaScript in Compiler Design
In this article, we present a JavaScript program that removes left recursion from a production of a grammar. We'll provide an overview of the theory behind left recursion and its elimination, delve into the code implementation, and showcase input/output examples.
A production of grammar is said to have left recursion if the leftmost variable of its RHS is same as variable of LHS.
If we have the left-recursive pair of productions:
A → Aα / β
where β does not begin with an A.
Then, we can eliminate left recursion by replacing the pair of productions with:
A → βA’
A’ → αA’ / ∈.
Eliminate left recursion from a production of a grammar in JavaScript:
Let's explore the JavaScript code that eliminates left recursion from a grammar production:
const RemoveLeftRecursion = (nonTerminal, productionRule) => {
let output1 = '';
let output2 = '';
let productions = productionRule.split('|').filter(e => e !== '#');
for (let production of productions) {
if (!production.startsWith(nonTerminal)) {
output1 += `${production}${nonTerminal}'|`;
console.log(`Production ${productions.indexOf(production) + 1} does not have left recursion`);
} else {
output2 += production.replace(nonTerminal, '').concat(`${nonTerminal}'|`);
console.log(`Production ${productions.indexOf(production) + 1} has left recursion`);
}
}
console.log(`The output is:`);
output1 = output1.slice(0, output1.length - 1);
console.log(`${nonTerminal} --> ${output1}`);
console.log(`${nonTerminal}' --> ${output2}#`);
}
let nonTerminal = 'E';
let productions = 'Ea|Eb|z';
console.log(`The given grammar is: ${nonTerminal} --> ${productions}`);
RemoveLeftRecursion(nonTerminal, productions);
Input/Output:
Explanation:
Let's go through the code step by step to understand how it eliminates left recursion from a production of a grammar:
The code begins with a function RemoveLeftRecursion, which takes a non-terminal symbol and a production rule as input. The production rule consists of multiple productions separated by '|' (pipe) characters.
The code then splits the production rule into individual productions and iterates over them. For each production, it checks if it starts with the non-terminal symbol. If it does not, it is added to output1 with the non-terminal symbol followed by a prime ('), indicating no left recursion. If it starts with the non-terminal symbol, it is added to output2 after removing the non-terminal symbol, followed by the non-terminal symbol with a prime ('), indicating left recursion.
After processing all productions, the code prints the output, showing which productions have left recursion and which do not. It displays the modified productions without left recursion for the given non-terminal symbol.
Conclusion:
In this article, we have explored the elimination of left recursion from grammar productions using a JavaScript program. We have discussed the theory behind left recursion and its impact on parsing. The provided code demonstrates a practical implementation of the left recursion elimination algorithm.
0 Response to Write a program to eliminate left recursion from a production of a grammar using JavaScript in Compiler Design
Post a Comment