Kann man angesichts einer LR-Grammatik G und einer Zeichenfolge w schnell alle Teilzeichenfolgen in w finden, die sich in L (G) befinden?

  • Angenommen, ich habe eine LR-Grammatik G und eine Zeichenfolge w . Ich weiß, dass ich überprüfen kann, ob w in der Sprache von G in linearer Zeit ist. Was aber, wenn w sich nicht in der Sprache von G befindet, ich möchte jedoch alle Teilzeichenfolgen von w finden, die in der Sprache von G ? Und kann ich für diese Teilzeichen Parsing-Bäume erhalten? Was wäre die zeitliche Komplexität für diese Dinge?

    12 September 2012
    GillesTimeless
0 answers