ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 07.11.2023
Просмотров: 78
Скачиваний: 1
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
сканировать входной текст до тех пор, пока следующая пара лексем не совпадёт с запятой и ид. Такая запись устраняет проблему рекурсии, а также решает вопрос выбора из двух альтернатив.
Грамматика языка, к которому принадлежит предложение, представленное на рис. 1, имеет вид, представленный на рис. 6.
Рис. 6
Приведем примеры алгоритмов синтаксического анализа методом рекурсивного спуска для некоторых предложений исходной программы с использованием приведенной грамматики.
Имеем предложение исходной программы: READ (a).
Тогда процедура разбора этого предложения может иметь вид:
procedure <ввод>;
begin
BP := false;
if t = read then
begin
перейти к следующей лексеме;
if t = ( then
begin
перейти к следующей лексеме;
if <список переменных> закончилась успешно then
if t = ) then
begin
BP := true;
перейти к следующей лексеме;
end; {if )}
end; {if (}
end; {if read}
if BP = true then успешное завершение
else неудачное завершение;
end;
В приведенной процедуре BP – вспомогательная переменная, а t- переменная, определяющая тип лексемы. Процедура, соответствующая нетерминальному символу <ввод> вызывает процедуру <список переменных>:
procedure <список переменных>;
begin
BP := false;
if t=ид then
begin
BP := true;
перейти к следующей лексеме;
while ( t = , ) and ( BP = true ) do
begin
перейти к следующей лексеме;
if t = ид then перейти к следующей лексеме
else BP := false;
end; {while}
if BP = true then успешное завершение
else неудачное завершение;
end;
На рис. 7 графически представлен процесс грамматического разбора методом рекурсивного спуска для предложения READ. На фрагменте а) изображен вызов процедуры <ввод>, которая обнаружила лексемы READ и ) во входном потоке (штриховая линия). На фрагменте б) процедура <ввод> вызывает процедуру <список переменных> (сплошная линия), которая обработала лексему ид. На фрагменте в) процедура <список переменных> закончила работу, передала управление процедуре <ввод> с признаком успешного завершения; процедура <ввод> обработала входную лексему ). На этом анализ входного предложения завершён.
Рис. 7
Приведём ещё один пример. Имеем предложение из исходной программы:
REZ := SUM DIV 100 – A * A
Представим алгоритмы разбора этого предложения методом рекурсивного спуска:
procedure <присваивание>
begin
BP := false;
if t = ид then
begin
перейти к следующей лексеме;
if t = := then
begin
перейти к следующей лексеме;
if <арифметическое выражение> завершилось
успешно then
BP := true;
end; {if :=}
end; {if ид.}
if BP = true then успешное завершение
else неудачное завершение;
end;
Процедура присваивание в процессе работы вызывает процедуру <арифметическое выражение>:
procedure арифметическое выражение;
begin
BP:=false;
if <слагаемое> завершилось успешно then
begin
BP:=true;
while (t = + или t = - ) and ( BP=true ) do
begin
Перейти к следующей лексеме;
if <слагаемое> завершилось неудачно then
BP:=false;
end; {while}
end; {if слагаемое}
if BP = true then успешное завершение
else неудачное завершение;
end;
Процедура <арифметическое выражение>, в соответствии с грамматикой вызывает процедуру <слагаемое>:
procedure <слагаемое> ;
begin
BP:=false;
if <значение> завершилось успешно then
begin
BP:=true;
while (t = * или t = div ) and ( BP=true ) do
begin
Перейти к следующей лексеме;
if <значение> завершилось неудачно then
BP:=false;
end; {while}
end; {if значение}
if BP=true then успешное завершение
else неудачное завершение;
end;
И, наконец, процедура <слагаемое> вызывает процедуру <значение>, которая распознает переменные, константы или вызывает процедуру <арифметическое выражение>. Алгоритм процедуры <значение> имеет вид:
procedure значение;
begin
BP:=false;
if t = ид или t = конст then
begin
BP:=true;
Перейти к следующей лексеме;
end {if ид или конст}
else
if t = ( then
begin
Перейти к следующей лексеме;
if <арифметическое выражение> завершилось
успешно then
if t = ) then
begin
BP:=true;
Перейти к следующей лексеме;
end; {if )}
end; {if (}
if BP = true then успешное завершение
else неудачное завершение;
end;
Графически разбор этого предложения методом рекурсивного спуска выглядит так:
Рис. 8
Рис. 9
Грамматика языка, к которому принадлежит предложение, представленное на рис. 1, имеет вид, представленный на рис. 6.
| <программа> <имя программы> var <раздел переменных> begin <раздел операторов> end. <имя программы> ид <раздел переменных> <список переменных>:<тип> <список переменных> ид {, ид } <тип> integer <раздел операторов> <оператор> {;<оператор>} <оператор> <присваивание>/<ввод>/<вывод>/<цикл> <присваивание> ид := <арифметическое выражение> <арифметическое выражение> <слагаемое> {+<слагаемое>}{-<слагаемое>} <слагаемое> <значение> {*<значение>} {div <значение>} <значение> ид/ конст/(<арифметическое выражение>) <ввод> read (<список переменных>) <вывод> write (<список переменных>) <цикл> for <выражение цикла> to <тело цикла> <выражение цикла> ид :=<арифметическое выражение> do <арифметическое выражение> <тело цикла> <оператор>/ begin <раздел операторов> end |
Рис. 6
Приведем примеры алгоритмов синтаксического анализа методом рекурсивного спуска для некоторых предложений исходной программы с использованием приведенной грамматики.
Имеем предложение исходной программы: READ (a).
Тогда процедура разбора этого предложения может иметь вид:
procedure <ввод>;
begin
BP := false;
if t = read then
begin
перейти к следующей лексеме;
if t = ( then
begin
перейти к следующей лексеме;
if <список переменных> закончилась успешно then
if t = ) then
begin
BP := true;
перейти к следующей лексеме;
end; {if )}
end; {if (}
end; {if read}
if BP = true then успешное завершение
else неудачное завершение;
end;
В приведенной процедуре BP – вспомогательная переменная, а t- переменная, определяющая тип лексемы. Процедура, соответствующая нетерминальному символу <ввод> вызывает процедуру <список переменных>:
procedure <список переменных>;
begin
BP := false;
if t=ид then
begin
BP := true;
перейти к следующей лексеме;
while ( t = , ) and ( BP = true ) do
begin
перейти к следующей лексеме;
if t = ид then перейти к следующей лексеме
else BP := false;
end; {while}
if BP = true then успешное завершение
else неудачное завершение;
end;
На рис. 7 графически представлен процесс грамматического разбора методом рекурсивного спуска для предложения READ. На фрагменте а) изображен вызов процедуры <ввод>, которая обнаружила лексемы READ и ) во входном потоке (штриховая линия). На фрагменте б) процедура <ввод> вызывает процедуру <список переменных> (сплошная линия), которая обработала лексему ид. На фрагменте в) процедура <список переменных> закончила работу, передала управление процедуре <ввод> с признаком успешного завершения; процедура <ввод> обработала входную лексему ). На этом анализ входного предложения завершён.
Рис. 7
Приведём ещё один пример. Имеем предложение из исходной программы:
REZ := SUM DIV 100 – A * A
Представим алгоритмы разбора этого предложения методом рекурсивного спуска:
procedure <присваивание>
begin
BP := false;
if t = ид then
begin
перейти к следующей лексеме;
if t = := then
begin
перейти к следующей лексеме;
if <арифметическое выражение> завершилось
успешно then
BP := true;
end; {if :=}
end; {if ид.}
if BP = true then успешное завершение
else неудачное завершение;
end;
Процедура присваивание в процессе работы вызывает процедуру <арифметическое выражение>:
procedure арифметическое выражение;
begin
BP:=false;
if <слагаемое> завершилось успешно then
begin
BP:=true;
while (t = + или t = - ) and ( BP=true ) do
begin
Перейти к следующей лексеме;
if <слагаемое> завершилось неудачно then
BP:=false;
end; {while}
end; {if слагаемое}
if BP = true then успешное завершение
else неудачное завершение;
end;
Процедура <арифметическое выражение>, в соответствии с грамматикой вызывает процедуру <слагаемое>:
procedure <слагаемое> ;
begin
BP:=false;
if <значение> завершилось успешно then
begin
BP:=true;
while (t = * или t = div ) and ( BP=true ) do
begin
Перейти к следующей лексеме;
if <значение> завершилось неудачно then
BP:=false;
end; {while}
end; {if значение}
if BP=true then успешное завершение
else неудачное завершение;
end;
И, наконец, процедура <слагаемое> вызывает процедуру <значение>, которая распознает переменные, константы или вызывает процедуру <арифметическое выражение>. Алгоритм процедуры <значение> имеет вид:
procedure значение;
begin
BP:=false;
if t = ид или t = конст then
begin
BP:=true;
Перейти к следующей лексеме;
end {if ид или конст}
else
if t = ( then
begin
Перейти к следующей лексеме;
if <арифметическое выражение> завершилось
успешно then
if t = ) then
begin
BP:=true;
Перейти к следующей лексеме;
end; {if )}
end; {if (}
if BP = true then успешное завершение
else неудачное завершение;
end;
Графически разбор этого предложения методом рекурсивного спуска выглядит так:
-
Вызывается процедура присваивание, которая обнаружила лексемы ид и := во входном потоке (рис. 8, а). -
Процедура <присв> вызывает процедуру <арифметическое выражение> (рис. 8. б)
Рис. 8
Рис. 9
-
Процедура <арифметическое выражение> вызывает процедуру <слагаемое> (рис. 9, а). -
Процедура <слагаемое>. вызывает процедуру <значение>, которая обнаруживает лексему ид. Управление возвращается в процедуру <слагаемое> (рис. 9, б). -
Процедура <слагаемое> обнаруживает лексему div и вызывает процедуру <значение>, которая обнаруживает лексему конст. и передаёт управление в процедуру <слагаемое>, которая передаёт управление в процедуру <арифметическое выражение> (рис. 10, a). -
Процедура <арифметическое выражение> распознаёт лексему – , затем вызывает процедуру <слагаемое>, которая вызывает процедуру <значение>, которая распознаёт лексему ид и передаёт управление в процедуру <слагаемое> (рис. 10, б). -
Процедура <слагаемое> распознаёт лексему * , затем вызывает процедуру <значение>, которая распознаёт лексему ид. Следующая лексема читается в процедуре <значение>. Эта лексема не относится к данному предложению. Управление передаётся в процедуру <слагаемое>, которая формирует признак успешного завершения и передаёт управление в процедуру <арифметическое выражение>. Эта процедура, в свою очередь, успешно заканчивается и передаёт управление в процедуру <присваивание>, которая формирует признак успешного завершения. На этом разбор этого предложения заканчивается (рис. 11).