wali.su
 
Набережные Челны
Тел.: +7 8552 397129

Сопоставление планов с программой

 
 

Теперь посмотрим, как планы и цели используются для понимания программы. План, рассматриваемый в программе, приведенной на рис. 1,а, был реализован без ошибок. Вы увидите, как в системе PROUST возникает предположение относительно плана, реализация которого, возможно, преследуется данной программой, и как затем происходит сопоставление этого плана с программой. В нашем случае сопоставление успешно, поскольку рассматриваемый план реализован безошибочно. В следующем разделе мы исследуем, что происходит, когда из-за ошибок в студенческой программе план в соответствие с ней не приводится.

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

При анализе программы система PROUST по очереди выбирает цели из описания задачи. Предположим, что первой выбрана цель (Сигнально-Контролируемый-Вход ?Следующий ?Сигнальный). В это целевое выражение система подставляет все объекты, значения которых уже известны. На рассматриваемом этапе единственная информация, известная об объектах ?Слсдующий и ?Сигнальный,— это те сведения, которые содержатся в описании программы. Там указано, что значением ?Сигнальный является 99999, а значение объекта ?Следующий не дано. Поэтому в целевое выражение вместо ?Сигнальный подставляется его значение, а объект ?Следующий остается без изменения. В результате получаем: (Сигнально-Контролируемый-Вход ?Следующий 99999).

Теперь системе PROUST необходимо извлечь из базы знаний о программировании те планы, которые можно было бы использовать для достижения цели Сигнально-Контролируемый-Вход. При этом извлекается заполнитель для слота Примеры в соответствии с определением для такой цели, показанным в табл. 2. Этот заполнитель представляет собой список из пяти элементов: Обработка-Чтение-While, Чтсние-Обработка-While, Чтение-Обработка-Повторение и Цикл-с-Счетчиком. Каждый из этих элементов является названием определенного плана. Система PROUST начинает с первого плана из этого списка, а именно с плана Обработка-Чтение-While, который, таким образом, служит начальной гипотезой относительно того, как в студенческой программе осуществляется достижение цели Сигнально-Контролируемый-Вход.

Поскольку в целевое выражение (Сигнально-Контролируемый-Вход ?Следующий ?Сигнальный) подставлялись известные значения объектов, то теперь тс же подстановки необходимо сделать и в выбранном плане. Чтобы разобраться в характере подстановок, система изучает слот. Форма в определении цели Сигнально-Контролируемый-Вход, т. е. (Сигнально-Контролируемый-Вход ?Вход ?Стоп). Этот слот указывает, какие образцы переменных используются в планах, реализующих данную цель. Сравнивая слот Форма с анализируемой целью, система PROUST решает, что каждый раз объект ?Вход в выбранном плане должен быть заменен на значение объекта ?Следующий, а объект ?Стоп—на значение объекта ?Сигнальный, т. е. 99999. Поскольку значение ?Следующий остается неизвестным, система просто заменяет объект ?Вход на имя переменной ?Следующий. При этом предполагается, что значение объекта ?Следующий определится потом, в ходе сопоставления плана с программой студента.

На рис. 3 показано, как происходит сопоставление плана Обработка-Чтение-While, с примером программы, показанным на рис. 1, а. Сопоставление начинается с цикла, содержащего WHILE. Образец, который содержится в плане для цикла с WHILE, имеет вид (WHILE (<> ?Следующий 99999) ...), а в программе имеются два цикла, содержащие WHILE (Комбинация <> (как и комбинация < = ) здесь используется как единый символ, эквивалентный математическому знаку ≠ («не равно»): WHILE Val <> 99999 DO ... и WHILE Val < = 0 DO ... .

   

 

Рис. 3. Сопоставление плана Обработка-Чтение-While с программой, показанной на рис. 1,a.

Система PROUST обычно пытается привести в соответствие каждый образец с каждым из этих мест в программе. (WHILE (<> ?Следующий 99999) ...) сопоставляется с WHILE Val <> 99999 DO... при условии, что Val подставляется вместо ?Следующий. В то же время (WHILE (<> ?Следующий 99999) ...) не сопоставляется с WHILE Val <=0 DO так как здесь используется проверка вида <= вместо <> и сравнение производится с нулем, а не с 99999. Поэтому система PROUST в качестве сопоставимой пары для образца, содержащегося в плане, останавливается на WHILE Val <> 99999 DO ... . Поскольку такое сопоставление достигается при подстановке Val вместо объекта ?Следующий, делается запись, что значением ?Следующий является Val. Впоследствии в любом компоненте этого плана, содержащем объект ?Следующий, последний всегда будет заменяться на Val.

Следующим компонентом плана, который система PROUST сопоставляет с программой, является (BEGIN...). В программе имеется несколько утверждений с BEGIN, которые могли бы быть сопоставлены с таким образцом. Однако в шаблоне, описывающем план, образец (BEGIN...) появляется внутри образца с WHILE, который перед этим был подвергнут сопоставлению с программой. Это значит, что оператор BEGIN должен быть расположен внутри компонента программы WHILE Val <-> 99999 DO... . Следовательно, остается лишь одно по-настоящему сопоставимое утверждение в программе, которое содержит оператор BEGIN.

Когда система PROUST начинает сопоставлять компоненты вида (ПОДЦЕЛЬ (Вход ?Следующий)), возникает необходимость прибегнуть к рассуждениям иного рода. Такие компоненты плана представляют собой цели, и, чтобы провести их сопоставление с данной программой, система PROUST должна обратиться к тому же самому процессу выбора плана, который был использован при выборе плана Обработка-Чтение-While. Однако сначала подставляются все переменные-образцы в целевом выражении, которые получили значения. Поскольку объект ?Следующий имеет в качестве своего значения Val, то подцелевое выражение приобретает вид (Вход Val). Затем система PROUST извлекает из базы данных планы, реализующие Вход. Одним из таких планов является план ЧТЕНИЕ, в котором для задания следующего значения используется оператор чтения (Read) языка Паскаль. Этот план успешно сопоставляется с элементами программы, содержащими оператор Read.

Приведенный пример показывает, что система PROUST анализирует программы путем предсказания, какие планы могли быть использованы в программе, и последующей проверки этих предсказаний. Осуществляя выбор из определенного набора планов и под планов для каждой цели, система PROUST способна предложить разнообразные способы достижения каждой цели. Поскольку в системе сначала реализуется возможный вариант программы, который затем сопоставляется с действительной программой, можно сказать, что система PROUST осуществляет анализ путем синтеза. В общем случае выработка гипотез для планов и сопоставление их с программами — процесс значительно более сложный, чем рассмотренный здесь сценарий.

 
 

 
 
Copyright © 2008 Валеев Ильшат
Тел.:(8552) 397129
Создание и продвижение сайтов