Конспект лекций Рекомендовано Учебно-методи
Скачать 1.01 Mb.
|
| Внутри процедуры Getsym описана локальная процедура чте- ния очередной литеры : Getch. В тексте используется внешняя процедура обработки ошибок: Error. Для хранения служебных слов учебного языка PL/0 предназ- начен массив word. Дополнительно, в массиве wsym хранятся типы (символы), приписанные служебным словам, а в массиве ssym хра- нятся типы разделителей, таких как "равно", "запятая", "точка" и пр. В следующем фрагменте приведены некоторые описания. Const norw=11; {количество служебных слов} txmax=100; {длина таблицы имен} nmax=14; {максимальное количество цифр в записи числа} al=10; {максимальная длина идентификатора} Type symbol=(nul, ident, number, plus, minus, times, slash, oddsym, eql, lss, gtr, lparen, rparen, comma, semicolon, period, becomes, beginsym, endsym, ifsym, thensym, whilesym, dosym, callsym, constsym, varsym, procsym); alfa = packed array [1..al] of char; - 35 - Var ch:char; {последняя прочитанная литера входной строки} sym:symbol; {последний опознанный символ языка} id:alfa; {последний прочитанный идентификатор} num:integer; {последнее прочитанное число} res_words: array [1..norw] of alfa;{ зарезервированные слова } wsym: array [1..norw] of symbol; ssym: array [char] of symbol; Прежде чем воспользоваться процедурой Getsym, необходимо выполнить некоторые начальные присваивания, а, именно, запол- нить массивы res_words, wsym и ssym. Ниже приведен соответс- твующий фрагмент программы: for i:=0 to 255 do ssym[ord(i)]:=nul; ssym['+']:=plus; ssym['-']:=minus; ssym['*']:=times; ssym['/']:=slash; ssym['(']:=lparent; ssym[')']:=rparent; ssym['=']:=eql; ssym[',']:=comma; ssym['.']:=period; ssym['>']:=gtr; ssym['<']:=lss; ssym[';']:=semicolon; { В оригинале заполнены также односимвольные элементы: "меньше либо равно", "больше либо равно", "не равно" (такое может быть в некоторых реализациях) } res_words[1] :='BEGIN '; res_words[2] :='CALL '; res_words[3] :='CONST '; res_words[4] :='DO '; res_words[5] :='END '; res_words[6] :='IF '; res_words[7] :='ODD '; res_words[8] :='PROCEDURE '; res_words[9] :='THEN '; res_words[10]:='VAR '; res_words[11]:='WHILE '; wsym[1] :=beginsym; wsym[2] :=callsym; wsym[3] :=constsym; wsym[4] :=dosym; wsym[5] :=endsym; wsym[6] :=ifsym; wsym[7] :=oddsym; wsym[8] :=procsym; wsym[9] :=thensym; wsym[10]:=varsym; wsym[11]:=whilesym; Getch; { чтение очередной литеры входной строки } - 36 - Перейдем к основной процедуре обсуждаемой темы - процеду- ре Getsym. (Процедуру Getch оставим для самостоятельного на- писания.) procedure Getsym: var i,j,k : integer; procedure Getch: begin { текст процедуры Getch здесь опущен } end; begin while ch=' ' do Getch; { пропуск "лишних" пробелов } if ch in ['A'..'Z'] then begin { опознание идентификатора или служебного слова } k:=0; repeat if k begin k:=k+1; a[k]:=ch end; Getch { лишние (сверх al) литеры игнорируются } until not(ch in ['A'..'Z','0'..'9']); { Следующая строка отличается от оригинала } for i:=k+1 to al do a[k]:=' ';{дополнение пробелами} id:=a; i:=1; j:=norw; repeat k:=(i+j) div 2; if id <= res_words[k] then j:=k-1; if id >= res_words[k] then i:=k+1 until i>j; if (i-1)>j then sym:=wsym[k] else sym:=ident end - 37 - else { распознавание числа } if ch in ['0'..'9'] then begin k:=0; num:=0; sym:=number; repeat num:=10*num + (ord(ch)-ord('0')); k:=k+1; Getch; { Внимание! Контроля за переполнением здесь нет! } until not (ch in ['0'..'9']); if k>nmax then Error end else { распознавание многолитерных разделителей } if ch = ':' then begin Getch; if ch = '=' then begin sym:=becomes; Getch end else sym:=nul end else begin sym:=ssym[ch]; Getch end end; { Getsym } 2Упражнение 0. Добавьте в процедуру Getsym распознавание двухлитерных разделителей. - 38 - 24.5. Выход из лексического анализатора Прочитанные анализатором символы заносятся в различные таблицы: идентификаторы заносятся в таблицу идентификаторов, константы заносятся в таблицу констант и т.д. При этом могут осуществляться различные проверки. Например, недопустимо двой- ное описание идентификатора на одном уровне и тому подобное. Служебные таблицы могут иметь специальную структуру, ускоряю- щую работу с ними. Должна быть предусмотрена проверка на воз- можное переполнение служебных таблиц. В последнем случае долж- но выдаваться соответствующее сообщение. Иногда лексическому анализатору приходится заглядывать немного вперед. Приведем пример, ставший классическим. В языке Фортран допустима следующая конструкция: 'DO 7 I=1,10' - это пример оператора цикла, задающего повторение действий до стро- ки с номером 7 при I, изменяющемся от 1 до 10. Так как пробелы в Фортране незначащие, то этот оператор эквивалентен строке: 'DO7I=1,10'. С другой стороны, оператор присваивания в Фортра- не имеет вид: <идентификатор>=<выражение>. Следовательно, лексический анализатор не в состоянии правильно идентифициро- вать оператор цикла, пока он не прочитает запятую после знака равенства. В истории программирования ошибка, связанная с заменой запятой в операторе цикла на десятичную точку, известна как самая дорогая. Цикл при этом превращается в оператор присваи- вания с правой частью - вещественной константой: 'DO7I=1.10'. Причем, синтаксически эта конструкция вполне корректна (естественно, для Фортрана!). Обнаружение подобных ошибок обойдется слишком дорого, а еще дороже - если они не будут об- наружены вовсе. Горький опыт того, как космический корабль "Маринер", запущенный на Венеру, потерялся из-за отсутствия обязательного объявления (описания) переменных в Фортране учит нас тому, что избыточность в современных языках благое дело. Как уже упоминалось, на стадии лексического анализа обыч- но исключаются комментарии, кроме прагматических, которые несут информацию для следующих фаз компиляции. . - 39 - 25. АВТОМАТЫ С МАГАЗИННОЙ ПАМЯТЬЮ И КС-ГРАММАТИКИ Контекстно-свободные грамматики традиционно служат осно- вой для синтаксического анализа. Реальный язык программирова- ния не описывается полностью КС-грамматикой, однако, нам вы- годнее все-таки, может быть, с какими-то ограничениями, но описать синтаксис средствами КС-грамматик. Тогда некоторые особенности языка придется контролировать дополнительными средствами. Следовательно, нам нужно уметь определять, является ли данный язык КС-языком. Следующая лемма дает возможность опре- делить это [11]. 2ЛЕММА ПОДКАЧКИ. 0 Для любого КС-языка L существует такая константа k, что любое предложение z языка L, длина которого превышает k, можно записать в виде z = uvwxy , где l(vwx)<=k, l(v)>0, l(x)>0, а строка u((v)^i)w((x)^i)y - принадлежит языку L при любом i>=0. 2Упражнение. 0 Пусть L={xx}, где x - произвольная цепочка, состоящая из нулей и единиц. Докажите, что язык L не является контекстно-свободным. 2Упражнение. 0 Покажите, что для скобочного языка выполня- ется условие леммы подкачки. Если для распознавания регулярных языков было достаточно конечных автоматов, то для распознавания контекстно-свободных языков требуются конечные автоматы с магазинной памятью (МП-автоматы). Между КС-языками и МП-автоматами существует полное соответствие; то есть всякий допускаемый МП-автоматом язык является КС-языком и, наоборот, для всякого КС-языка мож- но сконструировать МП-автомат, распознающий этот язык. Однако следует иметь в виду, что, как и конечные автоматы, МП-автома- ты могут быть детерминированными и недетерминированными. Можно показать, что не всегда по недетерминированному МП-автомату возможно построить детерминированный МП-автомат, распознающий тот же язык. Соответственно, КС языки можно разделить на языки детерминированные и недетерминированные. Дадим 2определение 0 МП-автомата. Под МП-автоматом понимается следующая шестерка: 1) конечное множество состояний, 2) конечный входной алфавит, - 40 - 3) конечный алфавит символов магазина, 4) начальное состояние, 5) граничный маркер магазина, 6) множество переходов. Множество переходов задает, как по текущему состоянию, символу магазина и символу на входной ленте определяются новое состояние и символы на вершине магазина. В начальный момент времени автомат находится в начальном состоянии, в магазине (стеке) находится граничный маркер и во входной строке разме- щена анализируемая цепочка. 2Определение. 0 Говорят, что детерминированный автомат до- пускает входную цепочку, если на каждом его шаге работы опре- делен переход, и по концу анализа магазин содержит только мар- кер конца. Соответственно можно определить, когда детерминиро- ванный автомат не допускает входную цепочку. 2Определение. 0 Говорят, что недетерминированный МП-автомат допускает входную цепочку, если существует последовательность переходов, после которых входная цепочка исчерпана, и в мага- зине находится только маркер. В противном случае МП-автомат не допускает цепочку. 2Пример. 0 Построим МП-автомат для распознавания языка, по- рождаемого следующей КС грамматикой: 1) E -> aa 2) E -> bb 3) E -> aEa 4) E -> bEb Понятно, что успешный анализ любой цепочки данного языка требует определения середины цепочки, после чего можно прове- рить соответствие левой и правой половин. При разовом просмот- ре входной цепочки невозможно установить, в какой половине мы находимся. Следовательно, наш МП-автомат будет недетерминиро- ванным. В таблице 2 представлен пример задания множества перехо- дов МП-автомата. При этом, входной алфавит {a,b}, алфавит ма- газина - {#,A,B), множество состояний {0,1}. Начальное состоя- ние 0 соответствует просмотру левой половины цепочки, а состо- яние 1 означает просмотр правой половины. . - 41 - 2Таблица 2 2Пример задания множества переходов МП-автомата ш1 ┌─────────┬───────────┬────────────┬───────────┬──────────┐ │ Символ │ Текущее │ Символ │ Новое │ Новые │ │ входной │ состояние │ на вершине │ состояние │ символы │ │ цепочки │ автомата │ магазина │ автомата │ магазина │ ├─────────┼───────────┼────────────┼───────────┼──────────┤ │ a │ 0 │ # │ 0 │ #A │ ├─────────┼───────────┼────────────┼───────────┼──────────┤ │ b │ 0 │ # │ 0 │ #B │ ├─────────┼───────────┼────────────┼───────────┼──────────┤ │ a │ 0 │ A │ 1 │ │ ├─────────┼───────────┼────────────┼───────────┼──────────┤ │ b │ 0 │ B │ 1 │ │ ├─────────┼───────────┼────────────┼───────────┼──────────┤ │ a │ 1 │ A │ 1 │ │ ├─────────┼───────────┼────────────┼───────────┼──────────┤ │ b │ 1 │ B │ 1 │ │ ├─────────┼───────────┼────────────┼───────────┼──────────┤ │ a │ 0 │ A │ 0 │ AA │ ├─────────┼───────────┼────────────┼───────────┼──────────┤ │ a │ 0 │ B │ 0 │ BA │ ├─────────┼───────────┼────────────┼───────────┼──────────┤ │ b │ 0 │ A │ 0 │ AB │ ├─────────┼───────────┼────────────┼───────────┼──────────┤ │ b │ 0 │ B │ 0 │ BB │ └─────────┴───────────┴────────────┴───────────┴──────────┘ ш0 Попытка перейти в состояние 1 предпринимается только тог- да, когда читаемый символ входной ленты соответствует символу на вершине магазина. Считается, что верхний символ магазина согласно приведенной таблице заменяется на символы, указанные в последнем столбце. Если в этом столбце символы отсутствуют, то значит верхний символ магазина удаляется из него. 2Упражнение. 0 Опишите детерминированный МП-автомат для распознавания скобочного языка. 2Упражнение. 0 Докажите, что по любой КС-грамматике может быть построен МП-автомат, распознающий язык, порождаемый этой грамматикой. 2Упражнение. 0Покажите, что любой недетерминированный МП-автомат распознает КС-язык. 26. СИНТАКСИЧЕСКИЙ АНАЛИЗ. МЕТОД РЕКУРСИВНОГО СПУСКА Метод рекурсивного спуска относится к числу самых простых методов синтаксического анализа. Он может быть запрограммиро- - 42 - ван достаточно быстро при наличии грамматики или синтакси- ческих диаграмм заданного языка. Однако, забегая вперед, отме- тим, что грамматика должна обладать определенными свойствами. Рассмотрим следующий язык, заданный через БНФ: <Программа> ::= program <Имя> <Операторы> <Значения>. │ program <Имя> <Операторы> . <Операторы> ::= <Выражение> -> <Имя> │ <Выражение> -> <Имя> ; <Операторы> <Значения> ::= where <Константы> <Константы> ::= <Имя> = <Число> │ <Имя> = <Число> , <Константы> <Выражение> ::= <Слагаемое> │ <Слагаемое> + <Выражение> <Слагаемое> ::= <Имя> │ <Число> Конструкции <Имя> и <Число> будем считать терминалами. Синтаксический анализатор по методу рекурсивного спуска состоит из набора процедур: каждому нетерминалу соответствует своя процедура. Будем считать, что у нас имеются процедуры Getsym (см. 4.4) и Error. Последняя процедура печатает сообще- ние об ошибке, после чего обработка программы прекращается. Ниже приводится набросок программы анализатора. program Analis; procedure Prog; { анализ конструкции <Программа> } begin if sym=Progsym then begin Getsym; if sym=ident then begin Getsym; Statements; if sym<>pointsym then begin Value; if sym<>pointsym then Error end end - 43 - else Error end else Error end; procedure Statements; { анализ конструкции <Операторы> } var flag : boolean; begin flag:=false; repeat Expression; if sym=assignsym then Getsym else Error; if sym=ident then Getsym else Error; if sym=semicolon then Getsym else flag:=true until flag end; procedure Expression; { анализ конструкции <Выражение> } begin if (sym=ident) or (sym=number) then Getsym else Error; if sym=plus then begin Getsym; Expression end; end; procedure Value; { анализ конструкции <Значения> } begin if sym=wheresym then ListConst else Error; end; procedure ListConst; { анализ конструкции <Константы> } var flag : boolean; begin flag:=false; repeat if sym=ident then Getsym else Error; - 44 - if sym=eqlsym then Getsym else Error; if sym=number then Getsym else Error; if sym=comma then Getsym else flag:=true until flag end; begin Getsym; Prog end. Перед первым вызовом процедуры Prog определяется началь- ная лексема. Далее всякая процедура при успешном завершении анализа через Getsym читает следующую лексему. 27. LL - ГРАММАТИКИ 27.1. Безвозвратный анализ по первому символу При нисходящем анализе без возвратов нам необходимо вся- кий раз по очередному символу входной цепочки делать правиль- ный выбор правила вывода. Обсудим эту проблему выбора на сле- дующих примерах [3]. 2Пример 1. 0Рассмотрим грамматику: S->aA, A->c, A->bA, по- рождающую язык L={a(b*)c}. Будем строить дерево вывода для це- почки x=abbc (рис. 10). Обратите внимание, при построении дерева вывода по оче- редному символу входной цепочки однозначно выбирается необхо- димое правило вывода. S ┌────────┤ a A ┌─────┤ b A ┌──┤ b A │ c Рис. 10. Дерево вывода для грамматики из примера 1 - 45 - 2Пример 2. 0Рассмотрим грамматику: S->A, S->B, A->aA, A->b, B->aB, B->c, порождающую язык L={a*(b│c)}={a*b│a*c}. Если мы сейчас попробуем построить дерево вывода для цепочки x=aaac, то на первом же шаге возникает проблема выбора правила вывода. Допустим, мы выберем первое правило вывода, тогда дерево при- мет вид, приведенный на рис 11. S │ A ┌────────┤ a A ┌─────┤ a A ┌──┤ a A │ ? Рис. 11. Дерево вывода для грамматики из примера 2 Оказалось, что мы попали в тупик. Здесь возможны два ва- рианта: или цепочка не принадлежит языку, или где-то раньше было выбрано неверно правило вывода. Следовательно, необходимо возвращаться назад. Для того, чтобы исключить возвраты, наложим на грамматики два ограничения. 2Ограничение 1. 0 Для каждого нетерминала, для которого есть несколько правил вывода, потребуем, чтобы множества начальных терминальных символов (определяемых для каждой правой части правила вывода) попарно не пересекались. Такое множество по отношению к цепочке x, обозначается через first(x). 2Пример 3. 0 Грамматику из предыдущего примера легко переде- лать так, чтобы остался прежний язык, и грамматика удовлетво- ряла ограничению 1: S->C, S->aS, C->b, C->c. Здесь множества начальных терминальных символов попарно не пересекаются. Для нетерминала S: first(C)={b,c}, first(aS)={a}. Для нетерми- нала C: first(b)={b}, first(c)={c}. . - 46 - 2Пример 4. 0Рассмотрим грамматику: S->Aa, A->Aa, A-> 7e 0. По- пытаемся построить дерево вывода для цепочки x=a. Первый сим- вол входной цепочки - "a". Для начального символа грамматики S существует всего одно правило вывода, применяем его: S ├───┐ A a │ ? Какое выбрать продолжение? Первым символом по-прежнему является символ "a", поэтому из двух правил для нетерминала A выбираем то, во множестве first которого присутствует "a". При этом мы попадаем в тупик, так как оказывается, что входная це- почка закончилась, а в дереве вывода присутствует еще один символ несопоставленный "a". S ├───┐ A a │ a Трудность возникла из-за того, что символ A является уко- рачивающим (то есть из него возможен вывод пустой цепочки). Поэтому нам потребуется еще одно ограничение. 2Ограничение 2. 0 Для каждого укорачивающего нетерминала N (то есть N=*> 7e 0) потребуем, чтобы множества first(N) и follow(N) не пересекались, где follow(N) - это множество тер- минальных символов, следующих за N среди всех цепочек, выводи- мых в грамматике. 2Пример 5. 0 Рассмотрим грамматику: S->A, S->SA, S-> 7e 0, A->a. Легко видеть, что здесь нарушено ограничение 2. Следующая УКС-грамматика: { S-> 7e 0, S->AS, A->a } - порождает тот же язык, и при этом выполняется ограничение 2. К сожалению, не всегда удается переработать грамматику таким образом, чтобы сохранились язык и синтаксическая струк- тура всех цепочек, и при этом были бы выполнены ограничения 1 и 2. - 47 - 27.2. Грамматики и синтаксические диаграммы Процесс написания синтаксического анализатора можно фор- мализовать. Можно предложить следующий порядок: сначала по грамматике с ограничениями 1 и 2 строится детерминированный синтаксический граф, а затем по графу выписывается программа анализатора [3]. Отметим, что можно сформулировать правила построения син- таксического графа (синтаксических диаграмм) по заданной грам- матике [3]. Рассмотрим второй этап (написание анализатора) поподроб- нее. Для этого сформулируем правила написания программы по имеющимся диаграммам. Будем считать, что анализируемая цепочка читается процедурой Getsym и в переменной sym хранится значе- ние последней прочитанной лексемы. Для каждой конструкции S заранее считается вычисленным множество first(S), содержащее начальные лексемы этой конструкции. 2Правила преобразования графа в программу 21. 0Уменьшить по возможности количество отдельных диаг- рамм, так как каждая диаграмма - это будущая процедура. 22. 0 Преобразовать каждую диаграмму в процедуру по правилам 3-7. 23. 0 Последовательность элементов S1, S2, ..., Sn в диаг- рамме: ш1 ┌────┐ ┌────┐ ┌────┐ ──────┤ S1 ├───┤ S2 ├─ . . . ───┤ Sn ├── └────┘ └────┘ └────┘ ш0 преобразуется в составной оператор: begin T(S1); T(S2); ...; T(Sn) end, где T(Si) - это оператор, получившийся после преобразования элемента Si. . - 48 - 24. 0 Выбор в диаграмме: ш1 ┌────┐ преобразуется в оператор выбора ┌─────┤ S1 ├── case sym of │ └────┘ L1 : T(S1); │ ┌────┐ L2 : T(S2); ─────┼─────┤ S2 ├── . . . . . │ └────┘ Ln : T(Sn) │ . . . else Error │ ┌────┐ где Li=first(Si) └─────┤ Sn ├── └────┘ 25. 0 Повторение: ─┬─────────┬──> │ ┌────┐ │ └<─┤ S ├─┘ └────┘ ш0 преобразуется в цикл while sym in first(S) do T(S) 26. 0 Ссылка на другую диаграмму: ш1 ┌────┐ ───┤ A ├─── заменяется вызовом процедуры A. └────┘ ш0 27. 0 Если в диаграмме встречается терминальный символ "a", то в программе записывается условный оператор: if sym=a_sym then Getsym else Error 2Упражнение. 0 Преобразуйте некоторую грамматику в синтакси- ческий граф, а затем составьте по графу программу анализатора. 27.3. Определение LL-грамматик 2Определение. 0Грамматика с ограничениями 1 и 2 называется LL(1)-грамматикой. В этом названии первая буква L обозначает чтение анализируемой цепочки слева направо, вторая буква L обозначает левосторонний разбор, а число 1 обозначает, что анализатор "заглядывает" на один символ вперед. 2Определение. 0Можно сформулировать ограничения 1 и 2 не для одиночных терминальных символов, а для цепочек длины k. Тогда соответствующая грамматика будет называться LL(k)-грам- матикой. - 49 - Естественно возникает вопрос: "Можно ли по заданной КС-грамматике, не являющейся LL(1) грамматикой определить, су- ществует ли эквивалентная ей (то есть порождающая тот же язык) LL(1)-грамматика?" К сожалению, в общем случае эта проблема алгоритмически неразрешима. Однако, можно формулировать неко- торые рекомендации по преобразованию грамматики к виду LL(1). В частности следует избегать использовать левую рекурсию. Одно из возможных решений - это использование правой рекурсии. Существуют специальные системы автоматического преобразо- вания грамматики к виду LL(1). Поэтому, если доступна подобная система, то можно порекомендовать такой путь: 1) по языку строим грамматику, 2) проверяем и при необходимости пытаемся преобразовать грамматику с помощью нашей системы к виду LL(1), 3) оставшиеся противоречия пытаемся устранить "вручную", 4) если последнее не удалось, то или переделываем исход- ный язык, или пишем для отдельных "плохих" конструкций специ- альные методы анализа (например, с заглядыванием на большее число символов вперед). 27.4. Таблично-управляемый анализатор для LL(1)-грамматик Пусть грамматика задана синтаксическим графом с ограни- чениями 1, 2. Наша задача: написать таблично-управляемый ана- лизатор. Для этого необходимо каким-либо образом представить информацию о грамматике. Нас по-прежнему интересуют, в первую очередь, безвозвратные методы. 2Пример 1. 0Рассмотрим следующий примитивный язык, описыва- емый синтаксическими диаграммами (рис. 12, 13). Представим эти синтаксические диаграммы в виде многосвяз- ной структуры. Узлы этой структуры представляют собой записи с вариантами. Один вариант будет соответствовать терминальному символу в диаграмме, а второй - нетерминальному. Ниже приведе- но соответствующее описание и графическое представление [3]. . - 50 - Type ref = ^ node node = record {Графическое представление узла:} alt, suc : ref; {┌─────────────┐} case terminal:boolean of {│ sym │} true : (tsym : sym ); {├──────┬──────┤} false: (nsym : ref ) {│ alt │ suc │} end {└──────┴──────┘} Поле sym используется для задания терминального символа (литерой) или нетерминала (соответствующей ссылкой на начало представления данной конструкции). Поле alt - это ссылка на альтернативный вариант продолжения в диаграмме (nil - отсутствие таковых). Поле suc - это ссылка на узел продолжения в диаграмме. Дополнительно вводится в рассмотрение специальный терминальный символ empty, обозначающий пустую последователь- ность. Иногда бывает удобно определить заголовок для каждого не- терминального символа. Его наличие позволяет в необходимых случаях ссылаться на имя разбираемой конструкции, что полезно для более полной диагностики ошибок. Соответствующее описание приведено ниже: Type hptr = ^ header; header = record entry : ref; name_sym : string end В описании узла node следует внести изменение: поле nsym будет иметь тип hptr: Type ref = ^ node node = record {Графическое представление узла:} alt, suc : ref; {┌─────────────┐} case terminal:boolean of {│ sym │} true : (tsym : sym ); {├──────┬──────┤} false: (nsym : hptr) {│ alt │ suc │} end {└──────┴──────┘} - 51 - Для набора синтаксических диаграмм можно сформулировать правила их преобразования в заполненные структуры данных. Отсылаем любознательного читателя в этом месте к первоисточни- ку [3]. Далее будет приведен пример такого представления наших диаграмм. ш1 2Выражение ┌─────────┐ ───┬─> ( ──┬──│выражение│──┬── ) ──┬────> │ │ └─────────┘ │ │ │ │ │ │ │ │ │ │ │ └────── + <─────┘ │ │ │ │ ┌─────────┐ 2 0 │ └─────────>│ имя │──────────┘ └─────────┘ Рис.12. Синтаксическая диаграмма "Выражение" 2Имя ┌─────> a ─────┐ │ │ │ │ │ │ ────┼─────> b ─────┼─────> │ │ │ │ │ │ └─────> c ─────┘ Рис.13. Синтаксическая диаграмма "Имя" ш0 2Пример 2. 0Вернемся к предыдущему примеру. Для описанных конструкций можно построить многосвязную структуру (рис. 14). В заголовке указано имя основной конструкции "Выр." (выраже- ние). Конструкция "Имя" исчезла после преобразования синтакси- ческих диаграмм. Символ "ref S" обозначает ссылку на элемент S, "nil" обозначает пустую (неопределенную) ссылку. Прочие обозначения ("(", ")", "а" и т.д.) соответствуют терминальным символам. 2Упражнение. 0Приведите пример фрагмента программы на Паскале для создания и заполнения структуры, изображенной на рисунке 14. - 52 - ш1 ┌───────┐ ─────>│ Выр. │<──────┐ └─┬───┬─┘ │ │ nil │ ┌──────────────────┐ ┌─┴─────┐ ┌─┴───┴─┐ ┌───────┐ │ │ ( │ ┌─>│ ref S │ ┌─>│ + │ │ └─┬───┬─┘ │ └─┬───┬─┘ │ └─┬───┬─┘ │ │ └────┘ nil └────┘ │ └───>┘ ┌─┴─────┐ ┌─┴─────┐ │ a │ │ ) │ └─┬───┬─┘ └─┬───┬─┘ │ nil nil nil ┌─┴─────┐ │ b │ └─┬───┬─┘ │ nil ┌─┴─────┐ │ c │ └─┬───┬─┘ nil nil Рис. 14. Многосвязная структура конструкции "Выражение" ш0 Приведем набросок процедуры анализатора [3]. Будем счи- тать, что при вызове анализатора через процедуру Getsym уже прочитан первый символ анализируемой строки: procedure Parse(goal:hptr; var match : boolean); { match - результат анализа (дословно: равняться, подходить)} var s : ref; begin s:=goal^.entry; repeat if s^.terminal then if s^.tsym=sym then begin match:=true; Getsym end else match:=(s^.tsym=empty) else Parse (s^.nsym, match); if match then s:=s^.suc - 53 - else s:=s^.alt until s=nil end Можно сказать, что описанная выше многосвязная структура по существу таблично задает исходный язык, поэтому анализатор и называется таблично управляемым. 28. ВОСХОДЯЩИЕ МЕТОДЫ АНАЛИЗА 28.1. LR - грамматики Синтаксический анализ предложения языка может выполняться по принципу снизу вверх, а именно: предложение читается анали- затором до тех пор, пока не появится возможность отождествить |
Похожие:
 | Конспект лекций Владимира Климентьева по истории философии, отредактированный... Рекомендовано Министерством общего и профессионального образования Российской федерации в качестве учебника для студентов высших... | | Курс лекций 2-е издание, стереотипное Минск 2005 удк 008(076. 6) Рекомендовано к изданию Комиссией по приемке и аттестации электронных версий учебных и учебно-методических материалов Академии управления... |
| С. П. Филин Концепции современного естествознания: конспект лекций Конспект лекций соответствует требованиям Государственного образовательного стандарта высшего профессионального образования РФ и... | | Учебно-методический комплекс Специальность: 080801. 65 (351400) Прикладная... С 56 Современная информационная культура: Учебно-методический комплекс / авт сост. С. Б. Голубцов – спб.: Ивэсэп, 2010. – 42 с |
| Конспект лекций раскрывает содержание и структуру учебной дисциплины... Налоговое право : конспект лекций / сост доцент Р. В. Бобринев; Кузбасский институт экономики и права. – Кемерово, 2011 – 144 с | | Тема Содержание Нормативно-правовые документы и учебно-методическое обеспечение к началу учебного года |
| Конспект лекций Анализ рынка Форекс Учебно-тематический план дисциплины «Учет и операционная деятельность в банках» 7 | | Учебно-методический комплекс по дисциплине «Философия права» Учебно-методический комплекс включает учебную программу курса, учебно-тематический план, конспект лекций, планы проведения семинарских... |
 | И. В. Кузьмин «29» августа 2013 года ... | | Организация производства курс лекций Рекомендовано к печати методической комиссией экономического факультета ггау, протокол №1 от 22. 09. 2004 г |
| Конспект лекций по философии Часть 1 Античная философия Новосибирск... Савостьянов А. Н. Конспект лекций по философии / Новосиб гос ун-т. Новосибирск, 2007. Ч. Античная философия. 68 с | | Информационный бюллетень новых поступлений книг за сентябрь 2011 года Амангельдиева Ж. А. Финансы: учебно-методи-ческий комплекс. Астана: Казату, 2010. 146с. 1 Сбо., 2 н а., 2 ч з., 1 оф., 59 уч а |
| Конспект лекций по курсу хозяйственного права тема Понятие хозяйственного права Кафедра Истории, социологии и права Назаров Андрей Александрович конспект лекций по курсу хозяйственного права | | Рабочая учебная программа по дисциплине конспект лекций по дисциплине Дисциплина входит в федеральный компонент профессионального цикла дисциплин специальности и является обязательной для изучения. Данный... |
| Рабочая учебная программа по дисциплине конспект лекций по дисциплине Дисциплина входит в цикл общих математических и естественнонаучных дисциплин специальности и является дисциплиной по выбору студента.... | | Конспект лекций по высшей математике. В 2 частях. Часть М.: Айрис-пресс,... Баранова Е. С., Васильева Н. В., Федотов В. Л. Практическое пособие по высшей математике. Типовые расчеты. Учебное пособие. — Спб:... |
