Разбор сверху вниз - сначала и следуй - PullRequest
Новая
       26

Разбор сверху вниз - сначала и следуй

0 голосов
/ 28 января 2012

У меня есть следующая грамматика, на которой я пытаюсь научиться делать сначала и следовать. Я думаю, что у меня есть первый правильный. Тем не менее, СЛЕДУЮЩАЯ путаница из-за нетерминала C.

Вот грамматика: 

S --> ABC
A --> a | Cb |ε 
B --> C | dA | ε
C --> e | f

ПЕРВЫЙ: 

First(S) = First(A)-{ε} + First(C) = { a,f, e, ε}
First(B) = First(C) = {d,e,f,ε}

ДЛЯ СЛЕДУЮЩИХ: 

Follow(S) = {ε}
Follow(A) = First(B)-{ε} + First(C) = {a,e,f}
Follow(B) = Follow(C) = Follow(S) = { $}
Follow(C) = Follow(B) = Follow(S) = {b, $}

У меня проблемы, так как в производстве А и В есть два С, один? Я близок к этому?

Ответы [ 2 ]

0 голосов
/ 01 февраля 2014

Я отвечаю на следующие вопросы по грамматике.Поскольку первые ответы уже получены правильно. 

follow(S) = {$};
follow(A) = {$,d,e,f};
follow(B) = {$,e,f};
follow(C) = {$,b,e,f};

Причина включения «$» в следующие за A, B и C:Если в грамматике есть произведение A ---> ABC, где C обнуляемо, тогда все в Follow (A) будет Follow of (B).

0 голосов
/ 28 января 2012

Я думаю, что Первое уже неверно.

Поскольку A и B являются необязательными, а C имеет непустое первое: 

First(S) = First(A) + First(B) + First(C) - {ε}
First(A) = {a} + First(C) + {ε}
First(B) = First(C) + {d, ε}
First(C) = {e, f}

=> 

First(A) = {a, e, f, ε}
First(B) = {d, e, f, ε}

=> 

First(S) = {a, d, e, f}

Сначала, когда за вхождением следует nt, Следуйте правилу в конце. 

Follow(S) = {$}
Follow(A) = First(B) - {ε} + Follow(B) = {d, e, f}
Follow(B) = First(C) = {e, f}
Follow(C) = Follow(S) + Follow(B) + {b} = {b, e, f, $}

(надеюсь, я получил этосправа.)

Подробно: 

Follow(S) = {$}            [Start rule]

Follow(A) = First(B) - {ε} [S --> A.BC]
          + First(C)       [S --> AB.C as B or First(B) contains ε]
          + Follow(B)      [B. --> C | dA. | ε]

Follow(B) = First(C)       [S --> AB.C as C does not contain ε stops]

Follow(C) = Follow(S)      [S. --> ABC.]
          + {b}            [A --> a | C.b |ε]
          + Follow(B)      [B. --> C. | dA | ε]

Точка на LHS, как X. ->... приводит к Follow (S);

Точка на RHS похожа на ... -> ... .X ... приводит к First (X) - {ε} Пока естьε-production для X, продолжайте: ... -> ... X. ...

Помните, что это "мои" правила, ваша книга может использовать немного другую алгебру.

...