Первый и последующий набор для арифметических выражений - PullRequest
Новая
       11

Первый и последующий набор для арифметических выражений

1 голос
/ 14 марта 2009

Я хочу знать, правильный ли мой первый и следующий набор, который я сделал для этой грамматики, или нет 

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) = { ) , $ }

1 Ответ

5 голосов
/ 14 марта 2009

Просто замечание:

Вы сказали: 

FIRST(U) = FIRST(V)

Что правильно, но, V может быть эпсилоном, что означает ПЕРВЫЙ (U) = ПЕРВЫЙ (V) + ПЕРВЫЙ (X)

И X может быть эпсилон к.

Эти эпсилоны иногда могут быть довольно неприятными.

Есть еще кое-что сказать. Всего несколько правил: - Столицы нетерминальные - строчные терминалы - эпсилон используется для пустого правила - $ используется для обозначения конца ввода.

  • Первый (а) = {а}
  • Первый (А, В) = Первый (А), если эпсилон отсутствует в Первом (А)
  • First (A, B) = First (A) + First (B), если эпсилон в First (A)

  • Первый (A | B) = Первый (A) + Первый (B)

  • Follow (T) включает $, если T - начальный символ

  • Follow (T) включает First (A), если есть правило с ..TA ..
  • Follow (T) включает Follow (A), если есть правило A -> ..T
  • Follow (T) включает Follow (A), если есть правило A -> ..TB и B может быть epsilon
  • Follow (T) никогда не включает эпсилон
* +1037 * Пример: 
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) = {*, $, ), +}

Ваша грамматика намного сложнее и немного странна (вы уверены, что в грамматике нет ошибок?), Но вы можете следовать правилам.

...