Работа с бесконечными циклами при построении состояний для разбора LR (1) - PullRequest
Новая
       64

Работа с бесконечными циклами при построении состояний для разбора LR (1)

0 голосов
/ 28 апреля 2010

В настоящее время я строю состояния LR (1) из следующей грамматики. 

S->AS
S->c
A->aA
A->b

where A,S are nonterminals and a,b,c are terminals.

Это конструкция I0 

I0: S' -> .S, epsilon
    ---------------
    S -> .AS, epsilon
    S -> .c, epsilon
    ---------------
    S -> .AS, a
    S -> .c, c
    A -> .aA, a
    A -> .b, b

И I1. 

From S, I1: S' -> S., epsilon  //DONE

И так далее.Но когда я добираюсь до построения I4 ... 

From a, I4: A -> a.A, a
        -----------
        A -> .aA, a
        A -> .b, b

Проблема в том, что A -> .aA

Когда я пытаюсь построить следующее состояние из a, я собираюсь один разснова получить точно такое же содержимое I4, и это продолжается бесконечно.Аналогичный цикл происходит с 

S -> .AS

Итак, что я делаю не так?Должна быть какая-то деталь, которую я упускаю, но я просмотрел свои заметки и мою книгу и либо не могу найти, либо просто не понимаю, что здесь не так.Любая помощь?

1 Ответ

0 голосов
/ 28 апреля 2010

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

...