Парсер рекурсивного спуска с возвратом для грамматики

10

Может кто-то просветить меня, почему парсер рекурсивного спуска с возвратом, который пробует продукцию и (в этом порядке), не распознает язык, образованный грамматикой .SaSaSaaSaSa | aa

Похоже, он разбирает только слова из языка .{a2n | n1}

Я сгенерировал такой синтаксический анализатор, используя этот ABNF Parser Generator с рабочим правилом, S = "a" S "a" / "aa"и синтаксический анализатор, например, не распознает слово aaaaaa.

Я ожидаю, что он будет использовать производствоSaSa до тех пор, пока конкатенация конечных узлов дерева разбора слева не начнется с 7 a, а затем поднимется вверх по дереву разбора, выбрав вместо этого производственную пока дерево не будет выглядеть как это:Saa

   S 
 / | \
a  S  a
 / | \
a  S  a
  / \
 a   a
meribold
источник
2
Почему вы думаете, что это не может разобрать это слово?
Юваль Фильмус
@Yuval, я думаю, что это должно разобрать, так что я что-то упустил.
Мериболд
Ах, теперь вопрос имеет больше смысла; спасибо за редактирование! Если то, что вы пишете, правда (я не проверял), похоже, в генераторе есть ошибка. (Или это не указано для вашей грамматики; я думаю, что это маловероятно, поскольку грамматика является элементарной и однозначной.
Рафаэль
@ Рафаэль, я снова отредактировал вопрос (надеюсь, не меняя смысла). На самом деле мне поручено объяснить, почему такой парсер не распознает слово aaaaaa.
Мериболд
Где ты взял это дерево? Я не получаю много от этого генератора парсера ABNF. Дерево, которое вы даете, не имеет особого смысла. Но строка aaaaaaдолжна анализировать и не делает. Но aaaaразбирает ли. Вы, очевидно, правы относительно способностей 2. Это должно быть ошибочно. разбирает только aaс S = "aa" / "a" [S] "a". Можете ли вы отследить, что делает парсер?
Бабу

Ответы:

6

Это не очень хороший ответ, но деревья разбора не соответствуют обычным комментариям.

Ваша грамматика должен проанализировать строку a a a a a a .SaSa | aaaaaaaa

Но дерево разбора имеет следующую форму:

      S 
     /|\
    / S \
   / /|\ \
  / / S \ \
 / / / \ \ \
a a a   a a a

или, если вы предпочитаете эту презентацию, с терминалами на разных линиях

     S 
   / | \
  a  S  a
   / | \
  a  S  a
    / \
   a   a

Я проверил, что генератор синтаксического анализатора ABNF, кажется, не работает, но я не знаю, как отследить, что он делает.

Похоже, это действительно распознает множество что не соответствует грамматике.{a2n | n1}

Немного удивительно иметь такой сложный сайт вокруг разбитого парсера, который, кроме того, использует совершенно неинтересную технику разбора.


После дальнейшего взгляда на это:

Я думаю, что нашел один источник проблемы. Квадратные скобки означают необязательно .

Так что ваша грамматика должна быть написана либо S = "a" S "a" / "aa" или S = "a" [S] "a". Тогда, кажется, работает правильно.

Но система, по-видимому, теряется, если иметь два одинаковых правила в разных формах. Я не уверен почему.

Я не нашел страницу, объясняющую эти синтаксические проблемы для определения грамматики.

Я все еще считаю, что глючит.

Babou
источник
1
Уч. Да. Я не знаю, о чем я думал, когда писал это дерево разбора. Я отредактирую свой вопрос и вставлю ваш.
Мериболд
Я нашел еще один рекурсивный спуск, возвраты генераторов парсеров с онлайн демо здесь , и он показывает такое же поведение с этим правилом:S ::= 'a'<S>'a' | 'a''a'
meribold
Это все еще не анализирует aaaaaaпри использовании S = "a" S "a" / "aa", но вы, кажется, правы в скобках.
Мериболд
Я не вижу смысла исследовать рекурсивный спуск, возвращая парсер.
Бабу
вы правы насчет S = "a" S "a" / "aa"... я проверил слишком быстро, и нажал на генерацию вместо разбора.
Бабу
3

s1()SaSatrues()s2()Saa

Подумайте о aaaaaaповторном разборе слова . В какой-то момент дерево разбора будет выглядеть так:

   S 
 / | \
a  S  a
 / | \
a  S  a    <--
 / | \
a  S  a
  / \
 a   a

s()trueSSaa

   S 
 / | \
a  S  a
  / \
 a   a

Я склонен считать это проблемой с моей реализацией, а не с рекурсивными анализаторами обратного спуска вообще.

#include <iostream>

char* next;    
bool term(char token) {
    if (*next != '\0')
        return *next++ == token;
    else
        return false;
}

bool s();    
bool s1() {
    return term('a') && s() && term('a');
}    
bool s2() {
    return term('a') && term('a');
}    
bool s() {
    auto save = next;
    return s1() or (next = save, s2());
}    

int main(int argc, char* argv[]) {
    next = "aaaaaa";
    if (s() && *next == '\0') {
        std::cout << "match";
    }
    else
        std::cout << "no match";
}
meribold
источник
2

Это особенность, а не ошибка

Внимательно посмотрите, когда и где происходит возврат:

     1.           2.          3.          4.          5.          6.          7.          8.          9.          10.         11.         12.

     S            S           S           S           S           S           S           S           S           S           S           S      
   / | \        / | \       / | \       / | \       / | \       / | \       / | \       / | \       / | \       / | \       / | \       / | \
  a  S  a      a  S  a     a  S  a     a  S  a     a  S  a     a  S  a     a  S  a     a  S  a     a  S  a     a  S  a     a  S  a     a  S  a
                / | \       / | \       / | \       / | \       / | \       / | \       / | \       / | \       / | \       / | \       /   \
               a  S  a     a  S  a     a  S  a     a  S  a     a  S  a     a  S  a     a  S  a     a  S  a     a  S  a     a  S  a     a     a
                            / | \       / | \       / | \       / | \       / | \       / | \       / | \       / | \       / | \
                           a  S  a     a  S  a     a  S  a     a  S  a     a  S  a     a  S  a     a  S  a     a  S  a     a  S  a
                                        / | \       / | \       / | \       / | \       / | \       / | \       / | \       /   \
                                       a  S  a     a  S  a     a  S  a     a  S  a     a  S  a     a  S  a     a  S  a     a     a
                                                    / | \       / | \       / | \       / | \       / | \       /   \
                                                   a  S  a     a  S  a     a  S  a     a  S  a     a  S  a     a     a
                                                                / | \       / | \       / | \       /   \   
                                                               a  S  a     a  S  a     a  S  a     a     a
                                                                            / | \       /   \
                                                                           a  S  a     a     a



w[] = 'aaaaaa'  //input
l[] = ''        //current tree leafs


 1. tree:   The parser starts with the start symbol S and tries first alternative S->aSa:       Result: w[0]  = l[0]     w = aaaaaa    l = aSa
 |          -- S->aSa works                                                                         | |     | | 
 6. tree:   The parser matches a after a:                                                       Result: w[6]  = l[6]     w = aaaaaa    l = aaaaaaSaaaaaa
 7. tree:   The parser tries S->aSa again but there is no match!                                Result: w[7] != l[7]     w = aaaaaa    l = aaaaaaaSaaaaaaa 
 8. tree:   The parser tries S->aa but there is still no match!                                 Result: w[7] != l[7]     w = aaaaaa    l = aaaaaaaaaaaaaa
 9. tree:   Backtracking after the last symbol that matched => Backtracking at l[7]             Result: w[7] != l[7]     w = aaaaaa    l = aaaaaaaaaaaa
10. tree:   Backtracking after the last symbol that matched => Backtracking at l[7]             Result: w[7] != l[7]     w = aaaaaa    l = aaaaaaaaaa
11. tree:   Backtracking after the last symbol that matched => Backtracking at l[7]             Result: w[7] != l[7]     w = aaaaaa    l = aaaaaaaa
12. tree:   Backtracking after the last symbol that matched => Backtracking at l[7]             Result: w[7] != l[7]     w = aaaaaa    l = aaaa

Важным моментом здесь является то, что парсер возвращается после позиции, где был найден последний соответствующий символ. Вот почему он «прыгает» с дерева 11 с l = aaaaaaaa на 12-е дерево с l = aaaa , используя S -> aa на l [7].

Sebbas
источник
Наконец-то пришло время его отредактировать! ;)
Себбас