Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология
Образование Политология Производство Психология Стандартизация Технологии


Теорема Достаточные условия применимости метода рекурсивного спуска



 

Метод рекурсивного спуска применим к грамматике, если правила вывода грамматики имеют один из следующих видов:

1) A®a, где aÎ (TÈ N)*, и это единственное правило вывода для этого нетерминала;

2) A®a1a1 | a2a2|…| anan, где ai Î T для каждого i=1, 2, …, n; ai¹ aj для i¹ j, aiÎ (TÈ N)*, т.е. если для нетерминала А несколько правил вывода, то они должны начинаться с терминалов, причем эти терминалы должны быть различными.

Данные требования являются достаточными, но не являются необходимыми. Можно применить эквивалентные преобразования КС-грамматик, которые способствуют приведению грамматики к требуемому виду, но не гарантируют его достижения (см. лабораторную работу № 4) /11/.

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

 

L®a | a, L или в сокращенной форме L®a{, a}.

 

Формально здесь не выполняются условия метода рекурсивного спуска, т.к. две альтернативы начинаются одинаковыми терминальными символами. Но если принять соглашения, что в подобных ситуациях выбирается самая длинная подцепочка, выводимая из нетерминала L, то разбор становится детерминированным, и метод рекурсивного спуска будет применим к данному правилу грамматики. Соответствующая правилу процедура будет иметь вид:

 

procedure L;

begin

if CH< > ’a then Err else gc;

while CH=’, ’ do

begin

gc;

if CH< > ’a then Err else gc

end

end;

 

Пример Построим синтаксический анализатор методом рекурсивного спуска для модельного языка М.

 

Вход – файл лексем в числовом представлении.

Выход – заключение о синтаксической правильности программы или сообщение об имеющихся ошибках.

Введем обозначения:

1) LEX – переменная, содержащая текущую лексему, считанную из файла лексем;

2) gl – процедура считывания очередной лексемы из файла лексем в переменную LEX;

2) EQ(S) – логическая функция, проверяющая, является ли текущая лексема LEX лексемой для S;

3) ID – логическая функция, проверяющая, является ли LEX идентификатором;

7) NUM - логическая функция, проверяющая, является ли LEX числом.

Процедуры, проверяющие выполнение правил, описывающих язык М и составляющие синтаксический анализатор, будут иметь следующий вид:

 

1)для правила Р® program D1 В.

procedure Р;

begin

if EQ(`program`) then gl else ERR;

D1;

B;

if not EQ(‘.’) then ERR

end;

 

2) для правила Dvar D{; D}

procedure D1;

begin

if EQ(‘var’) then gl else ERR;

D;

while EQ(‘; ’) do

begin

gl; D

end

end;

 

3) для правила D® I{, I}: (int | bool)

procedure D;

begin

I;

while EQ(‘, ’) do

begin

gl; I

end;

if EQ(‘: ’) then gl else ERR;

if EQ(‘int’) or EQ(‘bool’) then gl else ERR

end;

 

4) для правила F® I|N|L|Ø F|(E)

procedure F;

begin

if ID or NUM or EQ(‘true’) or EQ(‘false’) then gl

else

if EQ(‘Ø ’)

then begin

gl; F

end

else

if EQ(‘(‘)

then begin

gl; E;

if EQ(‘)’) then gl else ERR

end

else ERR

end;

 

Аналогично составляются оставшиеся процедуры.

 

Семантический анализ программы

В ходе семантического анализа проверяются отдельные правила записи исходных программ, которые не описываются КС-грамматикой. Эти правила носят контекстно-зависимый характер, их называют семантическими соглашениями или контекстными условиями.

Рассмотрим пример построения семантического анализатора (СеА) для программы на модельном языке М. Соблюдение контекстных условий для языка М предполагает три типа проверок:

1) обработка описаний;

2) анализ выражений;

3) проверка правильности операторов.

В оптимизированном варианте СиА и СеА совмещены и осуществляются параллельно. Поэтому процедуры СеА будем внедрять в ранее разработанные процедуры СиА.

Вход: файл лексем в числовом представлении.

Выход: заключение о семантической правильности программы или о типе обнаруженной семантической ошибки.

 

Обработка описаний

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

Таблица идентификаторов, введенная на этапе лексического анализа, расширяется, приобретая вид таблицы 4.1. Описание таблицы идентификаторов будет иметь вид:

 

type ---

tabid = record

id : string;

descrid : byte;

typid : string[4];

addrid : word

end;

var

TI: array[1.. n] of tabid;

 

 

Таблица 4.1 – Таблица идентификаторов на этапе СеА

 

Номер Идентификатор Описан Тип Адрес
K Int
Sum

 

Поле «описан» таблицы на этапе лексического анализа заполняется нулем, а при правильном описании переменных на этапе семантического анализа заменяется единицей.

При выполнении процедуры D вводится стековая переменная-массив, в которую заносится контрольное число 0. По мере успешного выполнения процедуры I в стек заносятся номера считываемых из файла лексем, под которыми они записаны в таблице идентификаторов. Как только при считывании лексем встречается лексема «: », из стека извлекаются записанные номера и по ним в таблице идентификаторов проставляется 1 в поле «описан» (к этому моменту там должен быть 0). Если очередная лексема будет «int» или «bool», то попутно в таблице идентификаторов поле «тип» заполняется соответствующим типом.

Пример Пусть фрагмент описания на модельном языке имеет вид: var k, sum: int … Тогда соответствующий фрагмент файла лексем: (1, 2) (4, 1) (2, 3) (4, 2)…Содержимое стека при выполнении процедуры D представлено на рисунке 2.7.

 

 
 

 

 


Рисунок 4.5 – Содержимое стека при выполнении процедуры D

 

Для реализации обработки описаний введем следующие обозначения переменных и процедур:

1) LEX – переменная, хранящая значение очередной лексемы, представляющая собой одномерный массив размером 2, т.е. для лексемы (n, k) LEX[1]=n, LEX[2]=k;

2) gl – процедура считывания очередной лексемы в переменную LEX;

3) inst(l) - процедура записи в стек числа l;

4) outst(l) – процедура вывод из стека числа l;

5) instl – процедура записи в стек номера, под которым лексема хранится в таблице идентификаторов, т.е. inst(LEX[2]);

6) dec(t) - процедура вывода всех чисел из стека и вызова процедуры decid(1, t);

7) decid(l, t) – процедура проверки и заполнения поля «описан» и «тип» таблицы идентификаторов для лексемы с номером l и типа t.

Процедуры dec и decid имеют вид:

 

procedure decid (l:..; t:...);

begin

if TI[l].descrid =1 then ERR

else begin

TI[l].descrid: = 1;

TI[l].typid: = t

end

end;

procedure dec(t: ...);

begin

outst(l);

while l< > 0 do

begin

decid(l, t);

outst(l)

end

end;

Правило и процедура D с учетом семантических проверок принимают вид:

 

D ® < inst(0)> I < instl> {, I < instl> }: ( int < deс(‘int’)> | bool < dec(‘bool’)> )

 

procedure D;

begin

inst(0);

I;

instl;

while EQ(‘, ’) do

begin

gl; I; instl

end;

if EQ(‘: ’) then gl else ERR;

if EQ(‘int’) then

begin

gl; dec(‘int’)

end

else

if EQ(‘bool’)

then

begin

gl; dec(‘bool’)

end

else ERR

end;

 

Анализ выражений

 

Задача анализа выражений - проверить описаны ли переменные, встречающиеся в выражениях, и соответствуют ли типы операндов друг другу и типу операции.

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

Для реализации анализа выражений введем следующие обозначения процедур и функций:

1) checkid - процедура, которая для лексемы LEX, являющейся идентификатором, проверяет по таблице идентификаторов TI, описан ли он, и, если описан, то помещает его тип в стек;

2) checkop – процедура, выводящая из стека типы операндов и знак операции, вызывающая процедуру gettype(op, t1, t2, t), проверяющая соответствие типов и записывающая в стек тип результата операции;

3) gettype(ор, t1, t2, t) – процедура, которая по таблице операций TOP для операции ор выдает тип t результата и типы t1, t2 операндов;

4) checknot – процедура проверки типа для одноместной операции «Ø ».

 

Таблица 4.2 – Фрагмент таблицы двуместных операций TOP

 

Операция Тип 1 Тип 2 Тип результата
+ > … int int int int int bool

 

Перечисленные процедуры имеют следующий вид:

 

procedure checkid;

begin

k: =LEX[2];

if TI[k].descrid = 0 then ERR;

inst(TI[k].typid)

end;

procedure checkop;

begin

outst(top2); outst(op); outst(top1);

gettype(op, t1, t2, t);

if (top1< > t1) or (top2< > t2) then ERR;

inst(t)

end;

 

procedure checknot;

begin

outst(t);

if t< > bool then ERR;

inst(t)

end;

 

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

 

Е ® Е1 {( > | < | = ) < instl> E1 < checkop> }

EТ {(+ | - | Ú ) < instl> T < checkop> }

T® F {( * | / | Ù ) < instl> F< checkop> }

F® I < checkid> | N< inst(‘int’)> | L < inst(‘bool’)> | Ø F < checknot> |(E)

Пример Дано выражение a+5*b. Дерево разбора выражения и динамика содержимого стека представлены на рисунке 4.6.

 
 

 


 

int + int * int  

1)

 

 

int + int      

2)

 

 

int          

3)

 

Рисунок 4.6 – Анализ выражения a+5*b

 


Поделиться:



Популярное:

  1. I. С учетом условия развития, особенности инфицирования и состояния иммунитета
  2. Адаптация структурной схемы к условиям, обеспечивающим достоверную симуляцию рабочих процессов
  3. Б1.Б.4 «Физическая культура. Здоровьесбережение в условиях Крайнего Севера»
  4. Базисные условия международного коммерческого контракта
  5. Безопасность и опасность: свойства и условия возникновения. Этапы защиты от опасностей.
  6. В Германии Х1Х в. развитие экономической мысли шло своим путем, что в немалой степени объясняется своеобразными условиями экономического и оциально-политического развития страны.
  7. В условиях применения компьютерной обработки данных
  8. В условиях развитой рыночной экономики потребитель имеет возможность выбора оптимального поставщику Продавец со своих позиций стремится найти и заключить сделку наиболее устраивающим его покупателем.
  9. В.Н. Иванов, М.М. Назаров. Массовая коммуникация в условиях глобализации
  10. Верны ли следующие суждения об условиях, способных повлиять на снижение уровня безработицы?
  11. Внешняяя среда ведения бизнеса в современных условиях
  12. Внутренние условия для действительности завещательных распоряжений


Последнее изменение этой страницы: 2016-04-11; Просмотров: 798; Нарушение авторского права страницы


lektsia.com 2007 - 2024 год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! (0.072 с.)
Главная | Случайная страница | Обратная связь