Является ли пример Википедии с наборами FOLLOW() при разборе LR(1) неправильным?

Я не могу сказать, то ли я неправильно понимаю, что происходит, то ли объяснение Википедии неверно.

Википедия говорит:

FOLLOW(k,B) набора элементов k и нетерминала B представляет собой объединение следующих наборов всех элементов в K, где за '•' следует B.

Их пример грамматики выглядит так:

S → E
E → T
E → ( E )
T → n
T → + T
T → T + n

где они обнаружили, что элемент LR (0) установил 0 следующим образом:

[S → • E]
[E → • T]
[E → • ( E )]
[T → • n]
[T → • + T]
[T → • T + n] 

Это означает, что FOLLOW(0,T) является объединением следующих наборов всех элементов в наборе элементов 0, где за '•' следует T.

Применяя их логику, мы получаем, что "элементы в наборе элементов 0, где за '•' следует T", на самом деле являются этими двумя элементами:

  • [E → • T]
  • [T → • T + n]

Однако здесь я застрял:
Следующий набор второго включает символ ), потому что элемент [E → • ( E )] может производить [E → • ( T )], что означает, что ) должен быть в следующем наборе.

Однако Википедия говорит, что FOLLOW(0,T) = { $, '+' }.

Что я делаю неправильно?


person user541686    schedule 20.12.2012    source источник


Ответы (1)


Я нашел описание «Алгоритма закрытия Уоршалла» в этой книге.

Борнат: понимание и написание компиляторов

быть полезным здесь. (В целом я нашел эту книгу более читабельной и практически полезной, чем более известные книги по проектированию компиляторов!)

Могут быть и другие хорошие описания алгоритма.

РЕДАКТИРОВАТЬ: я ржавый, но я считаю, что статья в Википедии правильная в этом отношении:

Помните, что это Follow(0,T).
Теперь вы явно правы в том, что ')' может следовать за T в некоторых обстоятельствах.

Однако не с начальной точки 0 ... это означало бы выражение формы n) или n+n) или n+n+n), которые, явно написанные таким образом, являются очевидными синтаксическими ошибками.

(Что мне действительно понравилось в этой книге, так это сделать эти вещи явными, а не похоронить их в математических обозначениях!)

person user_1818839    schedule 20.12.2012