Как вывести Последователей нетерминалов в синтаксических произведениях?

Вот набор Syntax Productions:

S -> SA | T
A -> +S | S | *
T -> (S) | a

при устранении левой рекурсии я получил следующее:

S -> TB
B -> AB | ε
A -> +S | TB | *
T -> (S) | a

а затем я пытаюсь получить в нем Первых и Последующих нетерминалов, следуя шагам, описанным в книге драконов. Я правильно получил Firsts:

first(T) = [(, a]
first(A) = [+, *, (, a]
first(B) = [ε, +, *, (, a]
first(S) = [(, a]

Но я не могу понять, как получить Follows. Так может ли кто-нибудь показать, как это сделать конкретно?


parsing syntax production compiler-construction grammar
person Eric Huang    schedule 28.05.2015    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Чтобы вычислить FOLLOW(Non-Terminal), применяйте следующие правила до тех пор, пока ничего нельзя будет добавить к набору FOLLOW: - // Взято из Dragon Book

  1. Поместите $ в FOLLOW (Start_Symbol), где $ — правый конечный маркер ввода.
  2. Если есть продукция A->XBY, то все в FIRST(Y), кроме ε, находится в FOLLOW(B).
  3. Если существует продукция A->XB или продукция A->XBY, где ПЕРВЫЙ(Y) содержит ε, то все в СЛЕДУЮЩЕМ(A) находится в СЛЕДУЮЩЕМ(B).

Итак, теперь, следуя правилам, мы получаем FOLLOW() всех нетерминалов здесь.

FOLLOW(S) = {),$} Так как S является начальным символом, FOLLOW(S) должен содержать $. Четвертое тело производственного номера (S) объясняет, почему в FOLLOW(S) правильные круглые скобки.

FOLLOW(B) = {),$} Так как B появляется только на концах тел S-продукции (а не A-продукции, обсуждаемой далее в разделе ОБСУЖДЕНИЕ).

FOLLOW(A) = {+,*,(,a,),$} Поскольку A появляется в телах только после B, таким образом, все, кроме ε, которое находится в FIRST(B), должно быть в FOLLOW(A). Однако, поскольку FIRST(B) содержит ε, а B получено из S в исходной продукции, следовательно, все в FOLLOW(S) также должно быть в FOLLOW(A). Это объясняет символы $ и ).

FOLLOW(T) = {+,*,(,a,),$} Поскольку T появляется в телах только после B, таким образом, все, кроме ε, которое находится в FIRST(B), должно быть в FOLLOW(T). Однако, поскольку FIRST(B) содержит ε, а B — это целая строка, следующая за T в телах S продукций, все в FOLLOW(S) также должно быть в FOLLOW(T). Это объясняет символы $ и ).

ОБСУЖДЕНИЕ:-

Теперь, говоря о каком-то конфликте, возникающем из-за 3-го произведения, A -> +S | TB | *, вы могли бы легко заменить S вместо TB, из-за чего вы можете запутаться.

Как по мне, вы должны оставить постановки как: -

S -> TB
B -> AB | ε
A -> +S | S | *  //substitute S for understanding FOLLOW(B) without any confusion
T -> (S) | a
person Am_I_Helpful    schedule 29.05.2015
comment
Этот вопрос является упражнением 4.4.1 d) книги дракона. Но на самом деле я не получил официального ответа на эту книгу. Единственный ответ, который я могу найти, находится здесь ссылка . Этот ответ довольно странный. Не могли бы вы объяснить это? - person Eric Huang; 30.05.2015
comment
@EricHuang- Я также думаю, что этот ответ сам по себе запутан. Не могу сказать точно, но, похоже, какая-то ошибка. Если бы вы могли проверить от своего профессора, это было бы так признательно с вашей стороны. - person Am_I_Helpful; 30.05.2015