left recursion program in c++

#include <iostream>
#include <string>

using namespace std;

bool S(string input, int& index);

bool A(string input, int& index) {
    if (input[index] == 'a') {
        index++;
        if (S(input, index)) {
            if (input[index] == 'd') {
                index++;
                return true;
            }
        }
    }
    return false;
}

bool S(string input, int& index) {
    if (A(input, index)) {
        return true;
    }
    return false;
}

int main() {
    string input;
    cout << "Enter a string: ";
    cin >> input;

    int index = 0;
    if (S(input, index) && index == input.length()) {
        cout << "Input string is in the language.\n";
    } else {
        cout << "Input string is not in the language.\n";
    }

    return 0;
}

Explanation:

• S and A are two non-terminal symbols representing rules in a grammar.
• S represents the left recursive rule in the grammar.
• The bool S(string input, int& index) function checks if the input string satisfies the rule defined by S.
• The bool A(string input, int& index) function checks if the input string satisfies the rule defined by A.
• The A rule checks if the input starts with the character 'a', followed by the rule S and then ends with the character 'd'.
• Inside A, it checks for 'a', and if found, increments the index and proceeds to check the rule S. If S is valid, it checks for 'd' at the end.
• The S rule simply calls the A rule. This introduces left recursion, as S indirectly references itself.
• The main function reads an input string from the user.
• It initializes the index to 0 and checks if the input string satisfies the rule S.
• If the input string satisfies the rule S completely (i.e., the entire string is consumed), it outputs that the input string is in the language; otherwise, it indicates that the input string is not in the language.