Compilers: Erste und Folgen Sätze einer Grammatik, die nicht enthält epsilon

Question

In meinem aktuellen Compiler-Kurs habe ich verstanden, wie man die erste und folgen Sätze einer Grammatik und bisher alle Grammatiken, die ich behandelt habe habe epsilon enthalten. Jetzt werde ich gebeten, die ersten und folgen Sätze einer Grammatik ohne Epsilon zu finden, und zu bestimmen, ob es LR (0) und SLR ist. Nicht zu haben, dass epsilon mich rausgeworfen hat, also weiß ich nicht, ob ich es richtig gemacht habe. Ich würde schätzen, keine Kommentare, ob ich auf dem richtigen Weg mit dem ersten und folgen Sätze, und wie die Bestimmung beginnen, wenn es LR (0)

Betrachten Sie die folgende Grammatik beschreibt Lisp-Arithmetik:

S - > E // S ist Symbol beginnen, E ist Ausdruck

E -> (FL) // F ist mathematische Funktion, L eine Liste

L -> LI | I // I ist ein Artikel in einer Liste

I -> n | E // ein Element ist eine Zahl n oder ein Ausdruck E

F -> + | - | *

FIRST:

FIRST (S) = FIRST (E) = {(}

FIRST (L) = FIRST (i) = {n, (}

FIRST (F) = {+ -, *}

FOLLOW:

FOLLOW (S) = {$}

FOLLOW (E) = FOLLOW (L) = {), n, $}

FOLLOW (I) = {), $}

FOLLOW (F) = {), $}

Answer 1

Die ersten Sätze sind richtig, aber die Folgesätze sind nicht korrekt.

Der FOLLOW (S) = {$} ist richtig, obwohl dies technisch für die erweiterte Grammatik S '-> S $ ist.

E erscheint auf der rechten Seite von S -> E und I -> E, beide bedeuten, dass die Folge dieser Menge in der Folge von E ist, also: FOLGE (E) = FOLGE (S) ∪ FOLGE (I).

L erscheint auf der rechten Seite von L -> LI, was FOLLOW (L) ⊇ FIRST (I) und E -> (FL) gibt, was FOLLOW (L) ⊇ {)} ergibt.

Ich erscheint auf der rechten Seite von L -> LI | I, was FOLGT (I) = FOLGT (L) ergibt.

F erscheint auf der rechten Seite in E -> (FL), die FOLLOW (F) gibt = FIRST (L)

Die Lösung für diese gibt:

FOLLOW (F) = {n, (}

FOLGE (L) = das erste (I) ∪ {)} = {n, (,)}

FOLGE (i) = {n, (,)}

FOLGE (E) = {$} ∪ {n, (,)} = { n, (,), $}