Rekursiver Abstiegsparser mit Backtracking für die Grammatik

10

Kann mich jemand aufklären, warum ein rekursiver Abstiegsparser mit Backtracking, der die Produktionen und S a a (in dieser Reihenfolge) versucht, die durch die Grammatik S a S a | gebildete Sprache nicht erkennt a a .SaSaSaaSaSa | aa

Es scheint nur Wörter aus der Sprache zu analysieren n 1 } .{a2n | n1}

Ich habe einen solchen Parser mit diesem ABNF-Parser-Generator mit der Produktionsregel generiert, S = "a" S "a" / "aa"und der Parser erkennt das Wort aaaaaabeispielsweise nicht.

Ich würde erwarten, dass die Produktion bis die Verkettung der Endknoten des Analysebaums von links mit 7 beginnt , und dann den Analysebaum hinaufgehen und stattdessen die Produktion S a a auswählen, bis der Baum aussieht so was:SaSaaSaa

   S 
 / | \
a  S  a
 / | \
a  S  a
  / \
 a   a
meribold
quelle
2
Warum kann es dieses Wort nicht analysieren?
Yuval Filmus
@ Yuval, ich denke, es sollte es analysieren, also muss mir etwas fehlen.
Meribold
Ah, jetzt macht die Frage mehr Sinn; danke für die bearbeitung! Wenn das, was Sie schreiben, wahr ist (ich habe es nicht überprüft), scheint der Generator einen Fehler zu haben. (Oder es ist nicht für Ihre Grammatik spezifiziert; ich denke, dass dies unwahrscheinlich ist, da die Grammatik elementar und eindeutig ist.
Raphael
@ Raphael, ich habe die Frage erneut bearbeitet (hoffentlich ohne die Bedeutung zu ändern). Ich muss erklären, warum ein solcher Parser das Wort nicht erkennt aaaaaa.
Meribold
Woher hast du diesen Baum? Ich bekomme nicht viel von diesem ABNF-Parser-Generator. Der Baum, den Sie geben, macht nicht viel Sinn. Aber die Zeichenfolge aaaaaasollte analysiert werden und nicht. Aber aaaaanalysiert. Sie haben anscheinend Recht mit Potenzen von 2. Das Ding muss abgehört werden. es analysiert nur aamit S = "aa" / "a" [S] "a". Können Sie verfolgen, was der Parser tut?
Babou

Antworten:

6

Dies ist keine gute Antwort, aber die Analysebäume passen nicht zu den normalen Kommentaren.

SaSa | aaaaaaaa

Der Analysebaum hat jedoch die folgende Form:

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

oder wenn Sie diese Präsentation bevorzugen, mit den Terminals in verschiedenen Zeilen

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

Ich habe überprüft, ob der ABNF-Parser-Generator nicht zu funktionieren scheint, aber ich weiß nicht, wie ich verfolgen soll, was er tut.

{a2n | n1}

Es ist ein bisschen überraschend, eine so aufwändige Site um einen Buggy-Parser herum zu haben, der außerdem eine völlig uninteressante Parsing-Technik verwendet.


Nach einem weiteren Blick darauf:

Ich glaube, ich habe eine Ursache für das Problem gefunden. Die eckigen Klammern bedeuten optional .

Ihre Grammatik sollte also entweder S = "a" S "a" / "aa" oder geschrieben sein S = "a" [S] "a". Dann scheint es richtig zu funktionieren.

Aber das System geht anscheinend verloren, wenn es zweimal dieselbe Regel in verschiedenen Formen gibt. Ich bin mir nicht sicher warum.

Ich habe keine Seite gefunden, auf der diese syntaktischen Probleme zur Angabe der Grammatik erläutert werden.

Ich betrachte diesen Buggy immer noch.

babou
quelle
1
Autsch. Ja. Ich weiß nicht, was ich dachte, als ich diesen Analysebaum schrieb. Ich werde meine Frage bearbeiten und Ihre einfügen.
Meribold
Ich habe eine anderen rekursiven Abstieg findet, Parser - Generator mit einem Rückzieher Online - Demo hier , und es zeigt das gleiche Verhalten mit dieser Regel:S ::= 'a'<S>'a' | 'a''a'
meribold
aaaaaaBei der Verwendung S = "a" S "a" / "aa"wird immer noch nicht analysiert , aber Sie scheinen mit den Klammern Recht zu haben.
Meribold
Ich sehe keinen Sinn darin, rekursiven Abstieg zu erforschen und Parser zurückzuverfolgen.
Babou
Sie haben Recht mit S = "a" S "a" / "aa"... Ich habe zu schnell getestet und auf "Generieren" geklickt, anstatt zu analysieren.
Babou
3

s1()SaSatrues()s2()Saa

Erwägen Sie, das Wort aaaaaaerneut zu analysieren . An einem Punkt sieht der Analysebaum folgendermaßen aus:

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

s()trueSSaa

   S 
 / | \
a  S  a
  / \
 a   a

Ich neige dazu, dies als Problem bei meiner Implementierung zu betrachten und nicht als Rückverfolgung von Parsern rekursiver Abstammung im Allgemeinen.

#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
quelle
2

Es ist eine Funktion, kein Fehler

Sehen Sie sich genau an, wann und wo Backtracking stattfindet:

     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

Der entscheidende Punkt hierbei ist, dass der Parser nach der Position zurückverfolgt, an der das letzte übereinstimmende Zeichen gefunden wurde. Deshalb "springt" es von Baum 11 mit l = aaaaaaaa zum 12. Baum mit l = aaaa, indem es S -> aa bei l [7] verwendet.

Sebbas
quelle
Endlich Zeit, es zu bearbeiten! ;)
Sebbas