question grammaire, problème avec FIRST

Question

grammaire envisager de suivre:

A → BC 
B → Ba | epsilon 
C → bD | epsilon 
D → … 
… 

Le problème ici est que la règle B peut dériver epsilon et à gauche récursif ainsi. Je cherche FIRST(B).
Mais je suis resté sur FIRST(B), car il est récursive à gauche.

Alors qu'est-ce que FIRST(B)? Et FIRST(A)?
Ma version est:

FIRST(B) → {a, epsilon} 
FIRST(A) → {a, b, epsilon} 

Est-ce exact?

Answer 1

Oui, vous avez raison. Une récursivité gauche ne contribue pas à FIRST, car lorsque Ba est associé à B, le B dans Ba doit commencer par quelque chose que B peut commencer par - parce que c'est un B, après tout. :)

Vous pouvez également factoriser la récursivité gauche en premier.