Wenn ich eine Typ-3-Grammatik habe, kann sie auf einem Pushdown-Automaten dargestellt werden (ohne dass eine Operation auf dem Stapel ausgeführt wird), sodass ich reguläre Ausdrücke mithilfe kontextfreier Sprachen darstellen kann. Aber kann ich wissen, ob eine Typ-3-Grammatik , L L ( 1 ) , S L R ( 1 ) usw. ist, ohne Analysetabellen zu erstellen?
Alle regulären Sprachen haben LL (1) Grammatiken. Um eine solche Grammatik zu erhalten, nehmen Sie einen beliebigen DFA für die reguläre Sprache (möglicherweise durch Ausführen der Teilmengenkonstruktion für den aus dem regulären Ausdruck erhaltenen NFA) und konvertieren Sie ihn dann in eine rechtsrekursive reguläre Grammatik. Diese Grammatik ist dann LL (1), weil jedes Produktionspaar für dasselbe Nichtterminal entweder mit verschiedenen Symbolen beginnt oder man ε erzeugt und $ als Lookahead-Token hat. Folglich sind alle regulären Sprachen auch LR (1), da jede LL (1) -Grammatik LR (1) ist. Anhand eines wichtigen Ergebnisses dieser Arbeit können Sie außerdem zeigen, dass jede LR (1) -Sprache eine SLR (1) -Grammatik hat, 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 Präfix-frei 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 regulär:
S -> E
E -> 0E1 | 2
Hoffe das hilft!
Die (einfache alte) Syntax für reguläre Ausdrücke (Sie sagten "Darstellung") ist LR (0). Sie brauchen keine Vorschau, um eine Zeichenfolge zu analysieren, die einen regulären Ausdruck darstellt. Sie können dies leicht entscheiden, indem Sie einen Parser-Generator für eine Grammatik für reguläre Ausdrücke ausführen: -} Sie können auch leicht einen einfachen Parser für rekursiven Abstieg (LL (0)) für reguläre Ausdrücke codieren; alles, was LL (0) ist, ist LR (0).
Ich weiß nicht, ob die Syntax komplizierterer sogenannter "regulärer Ausdrücke" wie der von Perl so ist. Perls reguläre Ausdrücke sind jedoch strikt leistungsfähiger als reguläre Ausdrücke, sodass es sich nicht um normale reguläre Ausdrücke handelt.
Um festzustellen, ob eine Grammatik eine Eigenschaft hat, müssen Sie eine Art Prädikat ausführen. Um festzustellen, ob es sich um (S) LR (k) handelt, müssen Sie ein Prädikat ausführen, das diese Eigenschaft überprüfen kann. Tatsächlich muss ein solches Prädikat die Analysetabellen aufgrund der Art und Weise, wie sie definiert sind, erstellen.
quelle
a|(aa)beschreibt jedoch eine Sprache, die nicht frei von Präfixen ist. Darüber hinaus können LR (0) -Sprachen keine Grammatiken mit Epsilon-Produktionen verarbeiten, sodass die reguläre Sprache {epsilon, a} nicht LR (0) ist. Die regulären Sprachen sind jedoch LL (1), da Sie sie als reguläre Grammatiken schreiben können und daher alle LR (1) sind. Da jede LR (1) -Sprache eine SLR (1) -Grammatik hat, bedeutet dies, dass alle regulären Sprachen SLR (1) sind.