Анализ живой переменной, верно ли мое объяснение?

Question

stackexchange не имеют больше тегов о тегах компилятора, поэтому я отправляю здесь этот вопрос.

---

переменной х называется жить в заявлении Si в программе, если выполняются следующие три условия выполняются одновременно:

1. There exists a statement Sj that uses x 
2. There is a path from Si to Sj in the flow 
    graph corresponding to the program 
3. The path has no intervening assignment to x 
    including at Si and Sj 

Переменные, которые живут как на в базовом блоке 2 и в заявлении в базовом блоке 3 приведенного выше диаграммы потока управления:

1. р, з, и
2. г, з, и
3. г, и
4. д, v

---

Я пытаюсь объяснить:

---

Как wikipedia говорит: «Просто сказано: переменная живая, если она содержит значение, которое может понадобиться в будущем».

Согласно определению, данному в вопросе, переменная является живой, если она используется в будущем перед любым новым назначением. Блок 2 имеет «r» и «v» как переменные. поскольку они используются в блоке 4 перед любым новым значением, полученным для них. Обратите внимание, что переменная 'u' не является живым в блоке 2, поскольку «u» назначается новое значение в блоке 1, прежде чем оно будет использоваться в блоке 3. Переменные «p», «s» и «q» также не живут в блоке 2 по той же причине. Блок 3 имеет только переменную «r» как переменную, так как каждой другой переменной перед использованием назначается новое значение.

---

Другое объяснение, как:

---

Только г.

p, s и u назначены в 1, и до этого их промежуточное использование не применяется. Следовательно, p, s и u не являются живыми как в 2, так и в 3. q назначается в 4 и, следовательно, не является живым как в обоих, так и в 2 и 3.

v живет в 3, но не в 2. Только r составляет 2 и 3.

Но официальный ключ GATE сказал как r, так и u.

Answer 1

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

Во-первых, в списке условий для живых переменных нет ограничений, указывающих на то, что Si != Sj, поэтому это делает определения немного неточными в моем сознании.

Во-вторых, ваше утверждение «Обратите внимание, что переменная« u »не является живым в блоке 2, поскольку« u »назначается новое значение в блоке 1, прежде чем оно будет использоваться в блоке 3."

Как я смотрел бы на это было бы так:

1. После входа в блок 2, перед оператором v = r + u выполняется (представьте себе не-оп пустое заявление, вставленный в качестве входа к каждому блоку, а другой в качестве выхода из блока), то оба r и uдолжны быть живыми, потому что существуют предстоящее заявление , который использует оба, и есть путь в коде от записи до этот оператор, который не содержит промежуточных присвоений. Вместо того, представляя эти дополнительные пустые заявления, используя оригинальные семантики определений, то мы просто говорим о случае, когда Si == Sj, потому что оба относятся к заявлению v = r + u - есть тривиальный путь от утверждения к себе , не содержащий дополнительных заданий в этом смысле. Мне было легче подумать об этом с дополнительными пустым оператором ввода и выхода, .

2. После выполнения v = r + u, однако, на воображаемой блок выхода пустого оператора, теперь можно безопасно рассматривать u не жить (в качестве альтернативы, мертв), потому что ничего в блоке 4 не использует его, и это переназначен в блоке 1, прежде чем он когда-либо снова использовать в любом блоке 2 или 3.

Таким образом, часть путаницы, кажется, думает ли переменная жить в определенном блоке, который Безразлично» t действительно соответствует определениям - y ou нужно подумать о том, находится ли переменная в реальном времени в точке конкретного заявления. Вы могли бы сделать так, чтобы переменная u была жива и мертва в блоке 2, в зависимости от того, смотрите ли вы ее перед выполнением одиночного оператора или после ...