Welche guten Notationen für deterministische kontextfreie und sichtbar Pushdown-Sprachen gibt es?

Deterministische kontextfreie Sprachen (DCFL) und sichtbar Pushdown-Sprachen (VPL) sind beide Sätze formaler Sprachen zwischen kontextfreien Sprachen (CFL) und regulären Sprachen (REG). Gibt es eine lesbare Notation, die in einfachem ASCII ausgedrückt werden kann, wie Backus-Naur-Form für CFL und reguläre Ausdrücke für REG?

$q,z,a\to q',\gamma$$q,q'$$Q$$z$$\gamma$$a$ein Eingabesymbol oder die leere Zeichenfolge. Die Notation selbst erzwingt keinen Determinismus, ist jedoch leicht zu überprüfen. Wenn Sie eine kontextfreie grammatikalische Notation (als BNF) verwenden, werden Sie auf Probleme stoßen, da DCFLs eine geeignete Unterklasse von CFLs sind. Wie von DaniCL festgestellt, können Sie bei einem CFG im Allgemeinen nicht entscheiden, ob seine Sprache deterministisch ist.

$A\to a\alpha b$$A$$a$$b$$\alpha$

$a$$b$

Um eine kanonische Darstellung zu finden, betrachten Sie Folgendes: Die Klasse der DCFL entspricht der Klasse der Sprachen, die durch LR (k) -Grammatiken erzeugt werden, was wiederum LR (1) entspricht. Dies bedeutet, dass Sie für jede DCFL eine LR (1) -Grammatik finden können. Natürlich ist eine LR (1) -Grammatik immer noch eine kontextfreie Grammatik, aber mit einer besonderen Eigenschaft: Aus LR (1) -Grammatiken können wir leicht Analysetabellen erstellen, um einen deterministischen Parser zu führen (mit Lookahead von 1 Symbol, daher LR (1)). Diese Analysetabellen wären eine andere Darstellung, wenn auch etwas weniger lesbar.

Denken Sie übrigens daran, dass es unentscheidbar ist, ob eine bestimmte kontextfreie Sprache deterministisch ist (Satz von Greibach).

Ich muss zugeben, dass ich noch nie von VPL gehört habe.