First & Suivre défini pour les expressions arithmétiques

Question

Je veux savoir si mon premier et suivi ensemble j'ai fait pour cette grammaire est correcte ou non

S -> TS' 
S' -> +TS' | -TS' | epsilon 
T -> UT' 
T' -> *UT' | /UT' | epsilon 
U -> VX 
X -> ^U | epsilon 
V -> (W) | -W | W | epsilon 
W -> S | number 

---

FIRST(S) = FIRST(T) = FIRST(U) = FIRST(V) = FIRST(W) = { (, - , + , number ,  epsilon } 
FIRST(T') = { *,/, epsilon} 
FIRST(S') = { + , - , epsilon} 
FIRST(X) = {^, epsilon} 

FOLLOW(S) = FOLLOW(S') = FOLLOW(V) = {$} 
FOLLOW(T) = {+ , - , $ } 
FOLLOW(T')= {+, - , $ } 
FOLLOW(U) = FOLLOW(X) = { * ,/, + , - ,$ } 
FOLLOW(W) = {) , $ } 

Answer 1

Juste une remarque:

Vous avez dit:

FIRST(U) = FIRST(V) 

Ce qui est correct, mais, V peut être epsilon qui signifie PREMIER (U) = PREMIER (V) + PREMIER (X)

Et X peut être epsilon à.

Ces epsilons peuvent être assez frustrants parfois.

Il y a un peu plus à dire. Juste quelques règles: - Les majuscules sont non-terminales - les minuscules sont les bornes - epsilon est utilisé pour une règle vide - $ est utilisé pour noter la fin de l'entrée.

• d'abord (a) = {a}
• First (A, B) = D'abord (A), si epsilon est pas en premier (A)
• First (A, B) = D'abord (A) + First (B), si epsilon en premier (A)

• First (A | B) = First (A) + First (B)

• Suivre (T) comprend $ si T est la symbole de début

• Suivre (T) inclut Premier (A) s'il y a une règle avec ..TA ..
• Suivre (T) comprend Suivre (A) s'il y a une règle A -> ..T
• Suivre (T) inclut Suivre (A) s'il y a une règle A -> ..TB et B peuvent être epsilon
• Suivre (T) ne comprend jamais epsilon

Exemple:

E = TE' 
E' = +TE'|epsilon 
T = FT' 
T' = *FT' | epsilon 
F = (E) | id 

First(E) = First(T) = First(F) = {(, id} 
First(E') = {+, epsilon} 
First(T) = First(F) = {(, id} 
First(T') = {*, epsilon} 
First(F) = {(, id} 

Follow(E) = {$,)} 
Follow(E') = Follow(E) = {$,)} 
Follow(T) = First(E') + Follow(E') = {$,), +} 
Follow(T') = Follow(T) = {$,), +} 
Follow(F) = First(T') + Follow(T') + Follow(T) = {*, $,), +} 

Votre grammaire est beaucoup plus complexe et un peu bizarre (êtes-vous sûr qu'il n'y a pas d'erreurs dans la grammaire?), mais vous pouvez suivre les règles.