Sind reguläre Ausdrücke $ LR (k) $?

  • Wenn ich eine Grammatik vom Typ 3 habe, kann sie auf einem Pushdown-Automaten dargestellt werden (ohne eine Operation auf dem Stapel auszuführen), sodass ich reguläre Ausdrücke mit kontextfreien Sprachen darstellen kann. Aber kann ich wissen, ob eine Typ-3-Grammatik $ LR (1) $, $ LL (1) $, $ SLR (1) $ usw. ist, ohne irgendwelche Analysetabellen zu erstellen?

    18 July 2012
    Raphael
2 answers
  • Alle regulären Sprachen verfügen über LL (1) - Grammatiken. Um eine solche Grammatik zu erhalten, nehmen Sie einen beliebigen DFA für die reguläre Sprache (indem Sie beispielsweise die aus dem regulären Ausdruck erhaltene Teilmengenkonstruktion für den NFA erstellen), und konvertieren Sie sie in eine rekursive reguläre Grammatik. Diese Grammatik ist dann LL (1), da jedes Paar von Produktionen für dasselbe Nichtterminal entweder mit verschiedenen Symbolen beginnt oder eines mit ε erzeugt und $ als Lookahead-Token verwendet. Folglich sind alle regulären Sprachen auch LR (1), da jede LL (1) -Grammatik LR (1) ist. Wenn Sie ein wichtiges Ergebnis dieses Dokuments verwenden, können Sie außerdem zeigen, dass jede LR (1) -Sprache eine SLR (1) - Grammatik, was bedeutet, dass jede reguläre Sprache eine SLR (1) - Grammatik hat.

    Die regulären Sprachen sind jedoch nicht alle LR (0 ). Die LR (0) -Sprachen haben sehr spezifische Eigenschaften - insbesondere müssen sie frei von Präfixen sein. Daher ist die reguläre Sprache {a, aa} nicht LR (0), obwohl sie eindeutig regulär ist (Regex a | (aa)). Die LR (0) -Sprachen sind jedoch nicht ordnungsgemäß in den regulären Sprachen enthalten. diese Grammatik für {0 n 21 n | n ≥ 1} ist LR (0), aber die Sprache ist nicht normal:

    S -> E E -> 0E1 | 2

    Ich hoffe, das hilft !

    12 July 2012
    templatetypedef
  • (Normaler reiner) regulärer Ausdruck Syntax (Sie sagten "Darstellung") ist LR (0). Sie benötigen keinen Lookahead, um eine Zeichenfolge zu analysieren, die einen regulären Ausdruck darstellt. Sie können dies leicht entscheiden, indem Sie einen Parser-Generator mit einer Grammatik für reguläre Ausdrücke ausführen: -} Sie können auch einen einfachen rekursiven Abstieg (LL (0)) -Parser für reguläre Ausdrücke codieren. alles, was LL (0) ist, ist LR (0).

    Ich weiß nicht, ob die Syntax von komplizierteren sogenannten "Regexxps" wie Perl so ist. Aber Perls Regexx sind strikt mächtiger als Regexx, also sind sie keine einfachen alten Regexxse.

    Um zu bestimmen, ob eine Grammatik eine Eigenschaft hat, müssen Sie eine Art Prädikat ausführen > Um zu bestimmen, ob es (S) LR (k) ist, müssen Sie ein Prädikat ausführen, das nach dieser Eigenschaft suchen kann. Tatsächlich muss ein solches Prädikat aufgrund seiner Definition tatsächlich die Analysetabellen erstellen.

    11 July 2012
    Ira Baxter