Рефакторинг на граматиката за анализиране на LL

В прост пример, объркан съм как да превърна тази граматика в LL, като премахна лявата рекурсия. Всякакви съвети са добре дошли.

G = {
      A -> A a | A B | a
      B -> b
    }

Получавам следното, като прилагам този алгоритъм:

G = {
      A -> a X
      X -> e | A | B X
      B -> b
    }

Това изглежда работи за генериране на C псевдокод за анализатора:

void A() {
    switch (token) {
        case 'a' : next(); X(); break;
    }
}

void X() {
    switch (token) {
        case 'e' : finish(); break;
        case 'a' : A(); break;
        case 'b' : B(); X(); break;
    }
}

void B() {
    next();
}

И за генериране на дърво за анализ на думата: aabab:

A ---+
|    |
a    X
     |
     A ---+
     |    |
     a    X ---+
          |    |
          B    X
          |    |
          b    A ---+
               |    |
               a    X ---+
                    |    |
                    B    X
                    |    |
                    b    e

Е, просто не съм сигурен дали е правилно...


grammar ll
person vmassuchetto    schedule 10.10.2012    source източник

Отговори (1)


arrow_upward
1
arrow_downward

Първо, вашата граматика изглежда приема поредици от as, разделени от единични bs, така че нито едно 2 b не се събира. (aaa...abaaaaa...abaaa...a) Това трябва да е еквивалентно на нещо като:

Q -> P | P b P
P -> a | a P
person Vlad    schedule 10.10.2012
comment
Съжалявам, че не казах. Трябва да поддържам някаква структура на оригиналната граматика. Разгледайте редакцията. =D - person vmassuchetto; 10.10.2012
comment
@Vinicius: добре, граматиката, която представихте (втората), изглежда правилна. Единствените промени в псевдокода биха били (1) случай по подразбиране в превключвателите, създаващ грешка, (2) 'e' не трябва да бъде символ, а EOF или каквото и да е, което маркира края на входния поток. - person Vlad; 10.10.2012