die FOLLOW Computing setzt

Question

Meine Aufgabe ist es, zunächst zu berechnen und FOLLOW-Sets für die folgende Grammatik:

P ::= S CS . 
S ::= (int , int) 
CS ::= C CS | epsilon 
C ::= left int | right int | low C 

Ich habe die folgenden ersten Sätze:

FIRST(S) = {'('} 
FIRST(C) = {left,right,low} 
FIRST(CS) = {left,right,low,epsilon} 
FIRST(P) = FIRST(S) = {'('} 

Für folgende Sätze I berechnet:

Ich versuchte meine Lösung mit ersten und folgen Sätze Generator und was ich mit FOLLOW (S) bekam war: FOLLOW(S) = {'.', left, right, low}. Ist die Lösung des Generators richtig und warum? Ich berechnete meine Lösung mit Formel: FOLLOW(S) = FIRST({left,right,low} concat FOLLOW(P)) = {left, right, low}. Kann mir bitte jemand erklären, warum meine/generator Lösung nicht stimmt und überprüfen ob ich alles andere richtig verstanden habe? Ich möchte auch wissen, warum ich int in keinem ersten oder folgen Satz habe und ob das mit Bau Parser später in Ordnung sein wird. Danke

Answer 1

Wenn Sie FOLLOW-Sets berechnen, müssen Sie mit leeren Produktionen vorsichtig sein.

In diesem Fall hat eine leere CS Produktion, was bedeutet, dass S könnte durch eine . in P → S CS . folgen. In ähnlicher Weise könnte die C in C CS am Ende der Produktion sein, so C auch durch ein .

int kann erst nach einem left oder right Token erscheinen verfolgt werden kann. Es kann niemals am Anfang eines Nom-Terminals oder unmittelbar nach einem Nicht-Terminal erscheinen. Es ist also völlig zu erwarten, dass es sich nicht um einen ERSTEN oder FOLGENDEN Satz handelt.