LL(1) Grammer Parser Algorithm

LL.js

class LL1Parser {
  constructor() {
    this.index = 0;
  }

  parse(input) {
    this.tokens = input.split(' ');
    this.index = 0;

    try {
      this.S();
      if (this.index === this.tokens.length) {
        console.log(`\nResult: "${input}" is a valid syntax which parsed successfully.`);
      } else {
        throw new Error('Invalid input');
      }
    } catch (error) {
      console.error(`\nResult: "${input}" is not a valid syntax. Parsing error: ${error.message}`);
    }
  }

  match(token) {
    if (this.tokens[this.index] === token) {
      this.index++;
      console.log(`Matched ${token}`);
    } else {
      throw new Error(`Expected ${token} but found ${this.tokens[this.index]}`);
    }
  }

  S() {
    console.log('S -> E');
    this.E();
  }

  E() {
    console.log('E -> T EPrime');
    this.T();
    this.EPrime();
  }

  EPrime() {
    if (this.tokens[this.index] === '+') {
      console.log('EPrime -> + T EPrime');
      this.match('+');
      this.T();
      this.EPrime();
    } else {
      console.log('EPrime -> ε');
    }
  }

  T() {
    console.log('T -> F TPrime');
    this.F();
    this.TPrime();
  }

  TPrime() {
    if (this.tokens[this.index] === '*') {
      console.log('TPrime -> * F TPrime');
      this.match('*');
      this.F();
      this.TPrime();
    } else {
      console.log('TPrime -> ε');
    }
  }

  F() {
    if (this.tokens[this.index] === '(') {
      console.log('F -> ( E )');
      this.match('(');
      this.E();
      this.match(')');
    } else if (this.tokens[this.index] === 'id') {
      console.log('F -> id');
      this.match('id');
    } else {
      throw new Error('Invalid input');
    }
  }

  // Method to print the grammar table
  printGrammarTable() {
    console.log('Grammar Table:');
    console.log('--------------\n');
    console.log('Non-Terminals: S, E, EPrime, T, TPrime, F');
    console.log('Productions: E, T EPrime, + T EPrime | ε,\n\t\t\t F TPrime, * F TPrime | ε,\n\t\t\t (E) | id');
    console.log('Terminals: id, +, *, (, )\n');
  }
}

// Usage example
const parser = new LL1Parser();
const input = 'id + id * id';
parser.printGrammarTable(); // Print the grammar table
console.log('Parsing Steps:');
console.log('--------------\n');
parser.parse(input);

Converted to Python

class LL1Parser:
    def __init__(self):
        self.index = 0

    def parse(self, input):
        # Split the input into tokens
        self.tokens = input.split(' ')
        self.index = 0

        try:
            self.S()  # Start parsing by invoking the S() method
            if self.index == len(self.tokens):
                print(f'\nResult: "{input}" is a valid syntax which parsed successfully.')
            else:
                raise ValueError('Invalid input')
        except Exception as error:
            print(f'\nResult: "{input}" is not a valid syntax. Parsing error: {str(error)}')

    def match(self, token):
        # Check if the current token matches the expected token
        if self.tokens[self.index] == token:
            self.index += 1
            print(f'Matched {token}')
        else:
            raise ValueError(f'Expected {token} but found {self.tokens[self.index]}')

    def S(self):
        # Production rule: S -> E
        print('S -> E')
        self.E()  # Invoke the E() method

    def E(self):
        # Production rule: E -> T EPrime
        print('E -> T EPrime')
        self.T()  # Invoke the T() method
        self.EPrime()  # Invoke the EPrime() method

    def EPrime(self):
        if self.tokens[self.index] == '+':
            # Production rule: EPrime -> + T EPrime
            print('EPrime -> + T EPrime')
            self.match('+')  # Match the '+' token
            self.T()  # Invoke the T() method
            self.EPrime()  # Invoke the EPrime() method
        else:
            # Production rule: EPrime -> ε (epsilon)
            print('EPrime -> ε')

    def T(self):
        # Production rule: T -> F TPrime
        print('T -> F TPrime')
        self.F()  # Invoke the F() method
        self.TPrime()  # Invoke the TPrime() method

    def TPrime(self):
        if self.tokens[self.index] == '*':
            # Production rule: TPrime -> * F TPrime
            print('TPrime -> * F TPrime')
            self.match('*')  # Match the '*' token
            self.F()  # Invoke the F() method
            self.TPrime()  # Invoke the TPrime() method
        else:
            # Production rule: TPrime -> ε (epsilon)
            print('TPrime -> ε')

    def F(self):
        if self.tokens[self.index] == '(':
            # Production rule: F -> ( E )
            print('F -> ( E )')
            self.match('(')  # Match the '(' token
            self.E()  # Invoke the E() method
            self.match(')')  # Match the ')' token
        elif self.tokens[self.index] == 'id':
            # Production rule: F -> id
            print('F -> id')
            self.match('id')  # Match the 'id' token
        else:
            raise ValueError('Invalid input')

    def printGrammarTable(self):
        # Print the grammar table
        print('\nGrammar Table:\n')
        print('-----------------------------------')
        print('Non-Terminals | Productions')
        print('-----------------------------------')
        print('      S       |      E')
        print('      E       |      T EPrime')
        print('   EPrime     | + T EPrime | ε')
        print('      T       |      F TPrime')
        print('   TPrime     | * F TPrime | ε')
        print('      F       |   ( E )    |   id')
        print('-----------------------------------')
        print('Terminals: id, +, *, (, )')
        print('-----------------------------------\n')


# Usage example
parser = LL1Parser()
input = 'id + id * id'
parser.printGrammarTable()  # Print the grammar table
print('Parsing Steps:')
print('--------------\n')
parser.parse(input)