WWW.DISUS.RU

БЕСПЛАТНАЯ НАУЧНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА - Авторефераты, диссертации, методички

 

Московский государственный университет им. М.В.Ломоносова

Факультет вычислительной математики и кибернетики

Волкова И.А., Руденко Т.В.

Формальные грамматики и языки.

Элементы теории трансляции

(издание второе, переработанное и дополненное)

1999

УДК 519.682.1+681.142.2

Приводятся основные определения, понятия и алгоритмы теории формальных

грамматик и языков, некоторые методы трансляции, а также наборы задач по каждой из рассматриваемых тем. Излагаемые методы трансляции проиллюстрированы на примере модельного языка.

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

Для студентов факультета ВМК в поддержку основного лекционного курса “Системное программное обеспечение” и для преподавателей, ведущих практические занятия по этому курсу.

Авторы выражают благодарность Пильщикову В.Н. за предоставленные материалы по курсу “Системное программное обеспечение”, ценные советы и замечания при подготовке пособия, а также благодарят Баландина К.А. за большую помощь в оформлении работы.

Рецензенты:

проф. Жоголев Е.А.

доц. Корухова Л.С.

Волкова И.А., Руденко Т.В. “Формальные грамматики и языки. Элементы теории трансляции. (учебное пособие для студентов II курса)” - издание второе (переработанное и дополненное) Издательский отдел факультета ВМиК МГУ (лицензия ЛР №040777 от 23.07.96), 1998.-62 с.

Печатается по решению Редакционно-издательского Совета факультета вычислительной математики и кибернетики МГУ им. М.В.Ломоносова ISBN 5-89407-032- Издательский отдел факультета вычислительной математики и кибернетики МГУ им. М.В.Ломоносова,

ЭЛ Е М Е Н Т Ы Т Е О Р И И

Ф О Р М А Л Ь Н Ы Х Я З Ы К О В И Г РА М М АТ И К

Введение.

В этом разделе изложены некоторые аспекты теории формальных языков, существенные с точки зрения трансляции. Здесь введены базовые понятия и даны определения, связанные с одним из основных механизмов определения языков грамматиками, приведена наиболее распространенная классификация грамматик (по Хомскому). Особое внимание уделяется контекстно-свободным грамматикам и, в частности, их важному подклассу - регулярным грамматикам. Грамматики этих классов широко используются при трансляции языков программирования. Здесь не приводятся доказательства сформулированных фактов, свойств, теорем, доказательства правильности алгоритмов; их можно найти в книгах, указанных в списке литературы.

Основные понятия и определения Определение: алфавит - это конечное множество символов.

Предполагается, что термин "символ" имеет достаточно ясный интуитивный смысл и не нуждается в дальнейшем уточнении.

Определение: цепочкой символов в алфавите V называется любая конечная последовательность символов этого алфавита.

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

Более формально цепочка символов в алфавите V определяется следующим образом:

(1) - цепочка в алфавите V;

(2) если - цепочка в алфавите V и a - символ этого алфавита, то a - цепочка в алфавите V;

(3) - цепочка в алфавите V тогда и только тогда, когда она является таковой в силу (1) и (2).

Определение: если и - цепочки, то цепочка называется конкатенацией (или сцеплением) цепочек и.

Определение: обращением (или реверсом) цепочки называется цепочка, символы которой записаны в обратном порядке.

Обращение цепочки будем обозначать R.

Например, если = abcdef, то R = fedcba.

Для пустой цепочки: = R.

Определение: n-ой степенью цепочки (будем обозначать n) называется конкатенация n цепочек.

Определение: длина цепочки - это число составляющих ее символов.

Например, если = abcdefg, то длина равна 7.

Длину цепочки будем обозначать | |. Длина равна 0.

Определение: язык в алфавите V - это подмножество цепочек конечной длины в этом алфавите.

Определение: обозначим через V* множество, содержащее все цепочки конечной длины в алфавите V, включая пустую цепочку.

Например, если V={0,1}, то V* = {, 0, 1, 00, 11, 01, 10, 000, 001, 011,...}.

Определение: обозначим через V+ множество, содержащее все цепочки конечной длины в алфавите V, исключая пустую цепочку.

Следовательно, V* = V+ {}.

Ясно, что каждый язык в алфавите V является подмножеством множества V*.

Известно несколько различных способов описания языков [3]. Один из них использует порождающие грамматики. Именно этот способ описания языков чаще всего будет использоваться нами в дальнейшем.

Определение: декартовым произведением A B множеств A и B называется множество { (a,b) | a A, b B}.

Определение: порождающая грамматика G - это четверка (VT, VN, P, S), где VT - алфавит терминальных символов ( терминалов ), VN - алфавит нетерминальных символов (нетерминалов), не пересекающийся с VT, P - конечное подмножество множества (VT VN)+ (VT VN)*; элемент (, ) множества P называется правилом вывода и записывается в виде, S - начальный символ (цель) грамматики, S VN.

Для записи правил вывода с одинаковыми левыми частями будем пользоваться сокращенной записью Каждое i, i = 1, 2,...,n, будем называть альтернативой правила вывода из цепочки.





Пример грамматики: G1 = ({0,1}, {A,S}, P, S), где P состоит из правил Определение: цепочка (VT VN)* непосредственно выводима из цепочки (VT VN)+ в грамматике G = (VT, VN, P, S) (обозначим ), если = 12, = 12, где 1, 2, (VT VN)*, (VT VN)+ и правило вывода содержится в P.

Например, цепочка 00A11 непосредственно выводима из 0A1 в грамматике G1.

Определение: цепочка (VT VN)* выводима из цепочки (VT VN)+ в грамматике G = (VT, VN, P, S) (обозначим ), если существуют цепочки 0, 1,..., n (n>=0), такие, что = 0 1... n=.

Определение: последовательность 0, 1,..., n называется выводом длины n.

Например, S 000A111 в грамматике G1 (см. пример выше), т.к. существует вывод S 0A1 00A11 000A111. Длина вывода равна 3.

Определение: языком, порождаемым грамматикой G = (VT, VN, P, S), называется множество L(G) = { VT* | S }.

Другими словами, L(G) - это все цепочки в алфавите VT, которые выводимы из S с помощью P.

Например, L(G1) = {0n1n | n>0}.

Определение: цепочка (VT VN)*, для которой S, называется сентенциальной формой в грамматике G = (VT, VN, P, S).

Таким образом, язык, порождаемый грамматикой, можно определить как множество терминальных сентенциальных форм.

Определение: грамматики G1 и G2 называются эквивалентными, если L(G1) = L(G2).

Например, эквивалентны, т.к. обе порождают язык L(G1) = L(G2) = {0n1n | n>0}.

Определение: грамматики G1 и G2 почти эквивалентны, если L(G1) {} = L(G2) {}.

Другими словами, грамматики почти эквивалентны, если языки, ими порождаемые, отличаются не более, чем на.

Например, почти эквивалентны, т.к. L(G1)={0n1n | n>0}, а L(G2)={0n1n | n>=0}, т.е. L(G2) состоит из всех цепочек языка L(G1) и пустой цепочки, которая в L(G1) не входит.

Классификация грамматик и языков по Хомскому (грамматики классифицируются по виду их правил вывода) Грамматика G = (VT, VN, P, S) называется грамматикой типа 0, если на правила вывода не накладывается никаких ограничений (кроме тех, которые указаны в определении грамматики).

Грамматика G = (VT, VN, P, S) называется неукорачивающей грамматикой, если каждое правило из P имеет вид, где (VT VN)+, (VT VN)+ и | | 0}).

(2) каждый КС-язык является КЗ-языком, но существуют КЗ-языки, которые не являются КС-языками ( например, L = {anbncn | n>0}).

(3) каждый КЗ-язык является языком типа 0.

Замечание: УКС-язык, содержащий пустую цепочку, не является КЗ-языком.

Замечание: следует подчеркнуть, что если язык задан грамматикой типа k, то это не значит, что не существует грамматики типа k’ (k’>k), описывающей тот же язык. Поэтому, когда говорят о языке типа k, обычно имеют в виду максимально возможный номер k.

Например, грамматика типа 0 G1 = ({0,1}, {A,S}, P1, S) и описывают один и тот же язык L = L(G1) = L(G2) = { 0n1n | n>0}. Язык L называют КС-языком, т.к. существует КС-грамматика, его описывающая. Но он не является регулярным языком, т.к. не существует регулярной грамматики, описывающей этот язык [3].

Замечание: если при описании грамматики указаны только правила вывода Р, то будем считать, что большие латинские буквы обозначают нетерминальные символы, S - цель грамматики, все остальные символы - терминальные.

2) Язык типа 1: L(G) = { an bn cn, n >= 1} 3) Язык типа 2: L(G) = {(ac)n (cb)n | n > 0} 4) Язык типа 3: L(G) = { | {a,b}+, где нет двух рядом стоящих а} Цепочка принадлежит языку, порождаемому грамматикой, только в том случае, если существует ее вывод из цели этой грамматики. Процесс построения такого вывода ( а, следовательно, и определения принадлежности цепочки языку) называется разбором.

С практической точки зрения наибольший интерес представляет разбор по контекстно-свободным (КС и УКС) грамматикам. Их порождающей мощности достаточно для описания большей части синтаксической структуры языков программирования, для различных подклассов КС-грамматик имеются хорошо разработанные практически приемлемые способы решения задачи разбора.

Рассмотрим основные понятия и определения, связанные с разбором по КСграмматике.

Определение: вывод цепочки (VT)* из S VN в КС-грамматике G = (VT, VN, P, S), называется левым (левосторонним), если в этом выводе каждая очередная сентенциальная форма получается из предыдущей заменой самого левого нетерминала.

Определение: вывод цепочки (VT)* из S VN в КС-грамматике G = (VT, VN, P, S), называется правым (правосторонним), если в этом выводе каждая очередная сентенциальная форма получается из предыдущей заменой самого правого нетерминала.

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

Например, для цепочки a+b+a в грамматике G = ({a,b,+}, {S,T}, {S T | T+S; T a | b}, S) можно построить выводы:

(1) ST+ST+T+ST+T+Ta+T+Ta+b+Ta+b+a (2) ST+Sa+Sa+T+Sa+b+Sa+b+Ta+b+a (3) ST+ST+T+ST+T+TT+T+aT+b+aa+b+a Здесь (2) - левосторонний вывод, (3) - правосторонний, а (1) не является ни левосторонним, ни правосторонним, но все эти выводы являются эквивалентными в указанном выше смысле.

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

Определение: дерево называется деревом вывода (или деревом разбора) в КСграмматике G = {VT, VN, P, S), если выполнены следующие условия:

(1) каждая вершина дерева помечена символом из множества (VN VT ), при этом корень дерева помечен символом S; листья - символами из (VT );

(2) если вершина дерева помечена символом A VN, а ее непосредственные потомки - символами a1, a2,..., an, где каждое ai (VT VN), то A a1a2...an правило вывода в этой грамматике;

(3) если вершина дерева помечена символом A VN, а ее единственный непосредственный потомок помечен символом, то A - правило вывода в этой грамматике.

Пример дерева вывода для цепочки a+b+a в грамматике G:

Определение: КС-грамматика G называется неоднозначной, если существует хотя бы одна цепочка L(G), для которой может быть построено два или более различных деревьев вывода.

Это утверждение эквивалентно тому, что цепочка имеет два или более разных левосторонних (или правосторонних) выводов.

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

Определение: язык, порождаемый грамматикой, называется неоднозначным, если он не может быть порожден никакой однозначной грамматикой.

Пример неоднозначной грамматики:

В этой грамматике для цепочки if b then if b then a else a можно построить два различных дерева вывода.

Однако это не означает, что язык L(G) обязательно неоднозначный.

Определенная нами неоднозначность - это свойство грамматики, а не языка, т.е.

для некоторых неоднозначных грамматик существуют эквивалентные им однозначные грамматики.

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

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

Проблема, порождает ли данная КС-грамматика однозначный язык (т.е.

существует ли эквивалентная ей однозначная грамматика), является алгоритмически неразрешимой.

Однако можно указать некоторые виды правил вывода, которые приводят к неоднозначности:

Пример неоднозначного КС-языка:

Интуитивно это объясняется тем, что цепочки с i = j должны порождаться группой правил вывода, отличных от правил, порождающих цепочки с j = k. Но тогда, по крайней мере, некоторые из цепочек с i = j = k будут порождаться обеими группами правил и, следовательно, будут иметь по два разных дерева вывода.

Доказательство того, что КС-язык L неоднозначный, приведен в [3, стр. 235-236].

Одна из грамматик, порождающих L, такова:

Очевидно, что она неоднозначна.

Дерево вывода можно строить нисходящим либо восходящим способом.

При нисходящем разборе дерево вывода формируется от корня к листьям; на каждом шаге для вершины, помеченной нетерминальным символом, пытаются найти такое правило вывода, чтобы имеющиеся в нем терминальные символы “проектировались” на символы исходной цепочки.

Метод восходящего разбора заключается в том, что исходную цепочку пытаются “свернуть” к начальному символу S; на каждом шаге ищут подцепочку, которая совпадает с правой частью какого-либо правила вывода; если такая подцепочка находится, то она заменяется нетерминалом из левой части этого правила.

Если грамматика однозначная, то при любом способе построения будет получено одно и то же дерево разбора.

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

Определение: символ x (VT VN) называется недостижимым в грамматике G = (VT, VN, P, S), если он не появляется ни в одной сентенциальной форме этой грамматики.

Алгоритм удаления недостижимых символов:

Вход: КС-грамматика G = (VT, VN, P, S) Выход: КС-грамматика G’ = (VT’, VN’, P’, S), не содержащая недостижимых символов, для которой L(G) = L(G’).

2. Vi = {x | x (VT VN), в P есть Ax и AVi-1,,(VTVN)} Vi-1.

3. Если Vi Vi-1, то i = i + 1 и переходим к шагу 2, иначе VN’ = Vi VN;

VT’ = Vi VT; P’ состоит из правил множества P, содержащих только символы из Vi; G’ = (VT’, VN’, P’, S).

Определение: символ A VN называется бесплодным в грамматике G = (VT, VN, P, S), если множество { VT* | A } пусто.

Алгоритм удаления бесплодных символов:

Вход: КС-грамматика G = (VT, VN, P, S).

Выход: КС-грамматика G’ = (VT, VN’, P’, S), не содержащая бесплодных символов, для которой L(G) = L(G’).

Рекурсивно строим множества N0, N1,...

3. Если Ni Ni-1, то i = i + 1 и переходим к шагу 2, иначе VN’ = Ni; P’ состоит из правил множества P, содержащих только символы из VN’ VT; G’ = (VT, VN’, P’, S).

Определение: КС-грамматика G называется приведенной, если в ней нет недостижимых и бесплодных символов.

Алгоритм приведения грамматики:

(1) обнаруживаются и удаляются все бесплодные нетерминалы.

(2) обнаруживаются и удаляются все недостижимые символы.

Удаление символов сопровождается удалением правил вывода, содержащих эти символы.

Замечание: если в этом алгоритме переставить шаги (1) и (2), то не всегда результатом будет приведенная грамматика.

Для описания синтаксиса языков программирования стараются использовать однозначные приведенные КС-грамматики.

1. Дана грамматика. Построить вывод заданной цепочки.

2. Построить все сентенциальные формы для грамматики с правилами:

3. К какому типу по Хомскому относится данная грамматика? Какой язык она порождает? Каков тип языка?

4. Построить грамматику, порождающую язык :

e) L = { цепочки из 0 и 1 с неравным числом 0 и 1} g) L = { | {0,1}+ и содержит равное количество 0 и 1, причем любая подцепочка, взятая с левого конца, содержит единиц не меньше, чем нулей}.

5. К какому типу по Хомскому относится данная грамматика? Какой язык она порождает? Каков тип языка?

6. Эквивалентны ли грамматики с правилами :

7. Построить КС-грамматику, эквивалентную грамматике с правилами:

8. Построить регулярную грамматику, эквивалентную грамматике с правилами:

9. Доказать, что грамматика с правилами:

порождает язык L = {an bn cn | n >= 1}. Для этого показать, что в данной грамматике 1) выводится любая цепочка вида an bn cn (n >= 1) и 2) не выводятся никакие другие цепочки.

10. Дана грамматика с правилами:

Построить восходящим и нисходящим методами дерево вывода для цепочки:

11. Определить тип грамматики. Описать язык, порождаемый этой грамматикой. Написать для этого языка КС-грамматику.

12. Построить регулярную грамматику, порождающую цепочки в алфавите {a, b}, в которых символ a не встречается два раза подряд.

13. Написать КС-грамматику для языка L, построить дерево вывода и левосторонний вывод для цепочки aabbbcccc.

14. Построить грамматику, порождающую сбалансированные относительно круглых скобок цепочки в алфавите { a, (, ), }. Сбалансированную цепочку определим рекуррентно: цепочка сбалансирована, если a) не содержит скобок, b) = (1) или = 1 2, где 1 и 2 сбалансированы.

15. Написать КС-грамматику, порождающую язык L, и вывод для цепочки aacbbbcaa в этой грамматике.

16. Написать КС-грамматику, порождающую язык L, и вывод для цепочки 110000111 в этой грамматике.

17. Дана грамматика G. Определить ее тип; язык, порождаемый этой грамматикой; тип языка.

18. Дан язык L = {13n+2 0n | n>=0}. Определить его тип, написать грамматику, порождающую L. Построить левосторонний и правосторонний выводы, дерево разбора для цепочки 1111111100.

19. Привести пример грамматики, все правила которой имеют вид A Bt, либо A tB, либо A t, для которой не существует эквивалентной регулярной грамматики.

20. Написать общие алгоритмы построения по данным КС-грамматикам G1 и G2, порождающим языки L1 и L2, КС-грамматики для Замечание: L = L1 * L2 - это конкатенация языков L1 и L2, т.е.L = { | L1, L2}; L = L1* - это итерация языка L1, т.е. объединение {} L1 L1*L L1*L1*L1...

21. Написать КС-грамматику для L={i 2 i+1R | i N, i=(i)2 - двоичное представление числа i, R - обращение цепочки }. Написать КС-грамматику для языка L* (см. задачу 20).

22. Показать, что грамматика неоднозначна. Как описать этот же язык с помощью однозначной грамматики?

23. Показать, что наличие в КС-грамматике правил вида где,, (VTVN)*, A VN, делает ее неоднозначной. Можно ли преобразовать эти правила таким образом, чтобы полученная эквивалентная грамматика была однозначной?

*24. Показать, что грамматика G неоднозначна. Какой язык она порождает?

Является ли этот язык однозначным?

25. Дана КС-грамматика G={VT, VN, P, S}. Предложить алгоритм построения множества определяющий, пуст ли язык L(G).

27. Написать приведенную грамматику, эквивалентную данной.

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

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

30. Доказать, что нециклическая КС-грамматика порождает конечный язык.

Замечание: Нетерминальный символ A VN - циклический, если в грамматике существует вывод A 1A2. КС-грамматика называется циклической, если в ней имеется хотя бы один циклический символ.

31. Показать, что условие цикличности грамматики (см. задачу 30) не является достаточным условием бесконечности порождаемого ею языка.

32. Доказать, что язык, порождаемый циклической приведенной КСграмматикой, содержащей хотя бы один эффективный циклический символ, бесконечен.

Замечание: Циклический символ называется эффективным, если A A, где |A| > 1; иначе циклический символ называется фиктивным.

ЭЛ Е М Е Н Т Ы Т Е О Р И И Т РА Н С Л Я Ц И И

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

лексический анализ синтаксический анализ семантический анализ генерация внутреннего представления программы оптимизация генерация объектной программы.

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

В этом разделе мы рассмотрим некоторые методы, используемые для построения анализаторов (лексического, синтаксического и семантического), язык промежуточного представления программы, способ генерации промежуточной программы, ее интерпретации. Излагаемые алгоритмы и методы иллюстрируются на примере модельного паскалеподобного языка ( М-языка ). Все алгоритмы записаны на Си.

Информацию о других методах, алгоритмах и приемах, используемых при создании трансляторов, можно найти в [1, 2, 3, 4, 5, 8].

Замечание:

a) запись вида {} означает итерацию цепочки, т.е. в порождаемой цепочке в этом месте может находиться либо, либо, либо, либо и т.д.

b) запись вида [ | ] означает, что в порождаемой цепочке в этом месте может находиться либо, либо.

c) P - цель грамматики; символ - маркер конца текста программы.

Контекстные условия:

1. Любое имя, используемое в программе, должно быть описано и только один раз.

2. В операторе присваивания типы переменной и выражения должны совпадать.

3. В условном операторе и в операторе цикла в качестве условия возможно только логическое выражение.

4. Операнды операции отношения должны быть целочисленными.

5. Тип выражения и совместимость типов операндов в выражении определяются по обычным правилам; старшинство операций задано синтаксисом.

В любом месте программы, кроме идентификаторов, служебных слов и чисел, может находиться произвольное число пробелов и комментариев вида {< любые символы, кроме } и >}.

True, false, read и write - служебные слова (их нельзя переопределять, как стандартные идентификаторы Паскаля).

Сохраняется паскалевское правило о разделителях между идентификаторами, числами и служебными словами.

Рассмотрим методы и средства, которые обычно используются при построении лексических анализаторов. В основе таких анализаторов лежат регулярные грамматики, поэтому рассмотрим грамматики этого класса более подробно.

Соглашение: в дальнейшем, если особо не оговорено, под регулярной грамматикой будем понимать леволинейную грамматику.

Напомним, что грамматика G = (VT, VN, P, S) называется леволинейной, если каждое правило из Р имеет вид A Bt либо A t, где A VN, B VN, t VT.

Соглашение: предположим, что анализируемая цепочка заканчивается специальным символом - признаком конца цепочки.

Для грамматик этого типа существует алгоритм определения того, принадлежит ли анализируемая цепочка языку, порождаемому этой грамматикой (алгоритм разбора):

(1) первый символ исходной цепочки a1a2...an заменяем нетерминалом A, для которого в грамматике есть правило вывода A a1 (другими словами, производим "свертку" терминала a1 к нетерминалу A) (2) затем многократно (до тех пор, пока не считаем признак конца цепочки) выполняем следующие шаги: полученный на предыдущем шаге нетерминал A и расположенный непосредственно справа от него очередной терминал ai исходной цепочки заменяем нетерминалом B, для которого в грамматике есть правило вывода B Aai (i = 2, 3,.., n);

Это эквивалентно построению дерева разбора методом "снизу-вверх": на каждом шаге алгоритма строим один из уровней в дереве разбора, "поднимаясь" от листьев к корню.

При работе этого алгоритма возможны следующие ситуации:

(1) прочитана вся цепочка; на каждом шаге находилась единственная нужная "свертка"; на последнем шаге свертка произошла к символу S. Это означает, что исходная цепочка a1a2...an L(G).

(2) прочитана вся цепочка; на каждом шаге находилась единственная нужная "свертка"; на последнем шаге свертка произошла к символу, отличному от S. Это означает, что исходная цепочка a1a2...an L(G).

(3) на некотором шаге не нашлось нужной свертки, т.е. для полученного на предыдущем шаге нетерминала A и расположенного непосредственно справа от него очередного терминала ai исходной цепочки не нашлось нетерминала B, для которого в грамматике было бы правило вывода B Aai. Это означает, что исходная цепочка a1a2...an L(G).

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

Допустим, что разбор на каждом шаге детерминированный.

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

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

Например, для грамматики G = ({a, b, }, {S, A, B, C}, P, S), такая таблица будет выглядеть следующим образом:

S C C A B S

Знак "-" ставится в том случае, если для пары "терминал-нетерминал" свертки нет.

Но чаще информацию о возможных свертках представляют в виде диаграммы состояний (ДС) - неупорядоченного ориентированного помеченного графа, который строится следующим образом:

(1) строят вершины графа, помеченные нетерминалами грамматики (для каждого нетерминала - одну вершину), и еще одну вершину, помеченную символом, отличным от нетерминальных (например, H). Эти вершины будем называть состояниями. H - начальное состояние.

(2) соединяем эти состояния дугами по следующим правилам:

a) для каждого правила грамматики вида W t соединяем дугой состояния H и W (от H к W) и помечаем дугу символом t;

б) для каждого правила W Vt соединяем дугой состояния V и W (от V к W) и помечаем дугу символом t;

Диаграмма состояний для грамматики G (см. пример выше):

Алгоритм разбора по диаграмме состояний:

(1) объявляем текущим состояние H;

(2) затем многократно (до тех пор, пока не считаем признак конца цепочки) выполняем следующие шаги: считываем очередной символ исходной цепочки и переходим из текущего состояния в другое состояние по дуге, помеченной этим символом. Состояние, в которое мы при этом попадаем, становится текущим.

При работе этого алгоритма возможны следующие ситуации (аналогичные ситуациям, которые возникают при разборе непосредственно по регулярной грамматике):

(1) прочитана вся цепочка; на каждом шаге находилась единственная дуга, помеченная очередным символом анализируемой цепочки; в результате последнего перехода оказались в состоянии S. Это означает, что исходная цепочка принадлежит L(G).

(2) прочитана вся цепочка; на каждом шаге находилась единственная "нужная" дуга; в результате последнего шага оказались в состоянии, отличном от S.

Это означает, что исходная цепочка не принадлежит L(G).

(3) на некотором шаге не нашлось дуги, выходящей из текущего состояния и помеченной очередным анализируемым символом. Это означает, что исходная цепочка не принадлежит L(G).

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

Диаграмма состояний определяет конечный автомат, построенный по регулярной грамматике, который допускает множество цепочек, составляющих язык, определяемый этой грамматикой. Состояния и дуги ДС - это графическое изображение функции переходов конечного автомата из состояния в состояние при условии, что очередной анализируемый символ совпадает с символом-меткой дуги.

Среди всех состояний выделяется начальное (считается, что в начальный момент своей работы автомат находится в этом состоянии) и конечное (если автомат завершает работу переходом в это состояние, то анализируемая цепочка им допускается).

Определение: конечный автомат (КА) - это пятерка (K, VT, F, H, S), где K - конечное множество состояний;

VT - конечное множество допустимых входных символов;

F - отображение множества K VT K, определяющее поведение автомата;

отображение F часто называют функцией переходов;

H K - начальное состояние;

S K - заключительное состояние (либо конечное множество заключительных состояний).

F(A, t) = B означает, что из состояния A по входному символу t происходит переход в состояние B.

Определение: конечный автомат допускает цепочку a1a2...an, если F(H,a1) = A1; F(A1,a2) = A2;... ; F(An-2,an-1) = An-1; F(An-1,an) = S, где ai VT, Aj K, j = 1, 2,...,n-1; i = 1, 2,...,n; H - начальное состояние, S - одно из заключительных состояний.

Определение: множество цепочек, допускаемых конечным автоматом, составляет определяемый им язык.

Для более удобной работы с диаграммами состояний введем несколько соглашений:

a) если из одного состояния в другое выходит несколько дуг, помеченных разными символами, то будем изображать одну дугу, помеченную всеми этими символами;

b) непомеченная дуга будет соответствовать переходу при любом символе, кроме тех, которыми помечены другие дуги, выходящие из этого состояния.

c) введем состояние ошибки (ER); переход в это состояние будет означать, что исходная цепочка языку не принадлежит.

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

Например, для грамматики G = ({a,b, }, {S,A,B,C}, P, S), где анализатор будет таким:

#include int scan_G(){ enum state {H, A, B, C, S, ER}; /* множество состояний */ enum state CS; /* CS - текущее состояние */ FILE *fp;/*указатель на файл, в котором находится анализируемая цепочка */ CS=H;

fp = fopen ("data","r");

c = fgetc (fp);

do {switch (CS) { case H: if (c == 'a') {c = fgetc(fp); CS = A;} case A: if (c == 'b') {c = fgetc(fp); CS = C;} case B: if (c == 'a') {c = fgetc(fp); CS = C;} case C: if (c =='a') {c = fgetc(fp); CS = A;} if (CS == ER) return -1; else return 0;

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

Например, для грамматики G = ({a,b, }, {S,A,B}, P, S), где разбор будет недетерминированным (т.к. у нетерминалов A и B есть одинаковые правые части - Bb).

Такой грамматике будет соответствовать недетерминированный конечный автомат.

Определение: недетерминированный конечный автомат (НКА) - это пятерка (K, VT, F, H, S), где K - конечное множество состояний;

VT - конечное множество допустимых входных символов;

F - отображение множества K VT в множество подмножеств K;

H K - конечное множество начальных состояний;

S K - конечное множество заключительных состояний.

F(A,t) = {B1,B2,...,Bn} означает, что из состояния A по входному символу t можно осуществить переход в любое из состояний Bi, i = 1, 2,...,n.

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

Один из наиболее важных результатов теории конечных автоматов состоит в том, что класс языков, определяемых недетерминированными конечными автоматами, совпадает с классом языков, определяемых детерминированными конечными автоматами.

Это означает, что для любого НКА всегда можно построить детерминированный КА, определяющий тот же язык.

Алгоритм построения детерминированного КА по НКА Вход: M = (K, VT, F, H, S) - недетерминированный конечный автомат.

Выход: M’ = (K’, VT, F’, H’, S’) - детерминированный конечный автомат, допускающий тот же язык, что и автомат М.

1. Множество состояний К’ состоит из всех подмножеств множества К.

Каждое состояние из К’ будем обозначать [A1A2...An], где Ai K.

2. Отображение F’ определим как F’ ([A1A2...An], t) = [B1B2...Bm], где для каждого 1 ] Контроль контекстных условий в выражении Пусть есть функция char *gettype (char *op, char *t1, char *t2), которая проверяет допустимость сочетания операндов типа t1 (первый операнд) и типа t2 (второй операнд) в операции op; если типы совместимы, то выдает тип результата этой операции; иначе - строку "no".

Типы операндов и обозначение операции будем хранить в стеке; для этого нам нужны функции для работы со стеком строк:

void spush (char *s); /* значение s - в стек */ char *spop (void); /* из стека - строку */ Если в выражении встречается лексема-целое_число или логические константы true или false, то соответствующий тип сразу заносим в стек с помощью spush("int") или spush("bool").

Если операнд - лексема-переменная, то необходимо проверить, описана ли она; если описана, то ее тип надо занести в стек. Эти действия можно выполнить с помощью функции checkid:

void checkid (void) if (TID [i].declare) /* описан? */ Тогда для контроля контекстных условий каждой тройки - "операндоперация-операнд" будем использовать функцию checkop:

void checkop (void) t2 = spop(); /* из стека - тип второго операнда */ op = spop(); /* из стека - обозначение операции */ t1 = spop(); /* из стека - тип первого операнда */ res = gettype (op,t1,t2); /* допустимо ? */ if (strcmp (res, "no")) spush (res); /* да! */ Для контроля за типом операнда одноместной операции not будем использовать функцию checknot:

void checknot (void) { if (strcmp (spop (), "bool")) ERROR();

Теперь главный вопрос: когда вызывать эти функции?

В грамматике модельного языка задано старшинство операций: наивысший приоритет имеет операция отрицания, затем в порядке убывания приоритета группа операций умножения (*, /, and), группа операций сложения (+,-,or), операции отношения.

Именно это свойство грамматики позволит провести синтаксическиуправляемый контроль контекстных условий.

Замечание: сравните грамматики, описывающие выражения, состоящие из символов +, *, (, ), i:

оцените, насколько они удобны для трансляции выражений.

Правила вывода выражений модельного языка с действиями для контроля контекстных условий:

E1 T { [ + | - | or ] < spush ( TD [curr_lex.value] ) > T < checkop() >} T F { [ * | / | and ] < spush ( TD [curr_lex.value] ) > F < checkop() >} F I < checkid() > | N < spush ("int") > | [ true | false ] < spush ("bool") > | Замечание: TD - это таблица ограничителей, к которым относятся и знаки операций; будем считать, что это массив #define MAXSIZE_TD char * TD[MAXSIZE_TD];

именно из этой таблицы по номеру лексемы в классе выбираем обозначение операции в виде строки.

Контроль контекстных условий в операторах 1) Оператор присваивания I := E Контекстное условие: в операторе присваивания типы переменной I и выражения E должны совпадать.

В результате контроля контекстных условий выражения E в стеке останется тип этого выражения (как тип результата последней операции); если при анализе идентификатора I проверить, описан ли он, и занести его тип в тот же стек ( для этого можно использовать функцию checkid() ), то достаточно будет в нужный момент считать из стека два элемента и сравнить их:

void eqtype (void) { if (strcmp (spop (), spop ())) ERROR();} Следовательно, правило для оператора присваивания:

2) Условный оператор и оператор цикла Контекстные условия: в условном операторе и в операторе цикла в качестве условия возможны только логические выражения.

В результате контроля контекстных условий выражения E в стеке останется тип этого выражения (как тип результата последней операции); следовательно, достаточно извлечь его из стека и проверить:

void eqbool (void) {if (strcmp (spop(), "bool")) ERROR();} Тогда правила для условного оператора и оператора цикла будут такими:

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

В качестве примера приведем функцию для нетерминала D (раздел описаний):

#define MAXSIZE_TID #define MAXSIZE_TD char * TD[MAXSIZE_TD];

struct record struct record TID [MAXSIZE_TID];

/* описание функций ERROR(), getlex(), id(), eq(char *), типа struct lex и переменной curr_lex - в алгоритме рекурсивного спуска для М-языка */ void ERROR(void);

struct lex {int class; int value;};

struct lex curr_lex;

struct lex getlex (void);

void ipush (int i);

int ipop (void);

void decid (int i, char *t) {if (TID [i].declare) ERROR();

else {TID [i].declare = 1; strcpy (TID [i].type, t);} while ((i = ipop()) != -1) decid (i,t);} if (!id()) ERROR();

else {ipush (curr_lex.value);

49. Написать для данной грамматики (предварительно преобразовав ее, если это требуется) анализатор, действующий методом рекурсивного спуска.

рекурсивного спуска, предварительно преобразовав ее.

51. Восстановить КС-грамматику по функциям, реализующим синтаксический анализ методом рекурсивного спуска. Можно ли было по этой грамматике вести анализ методом рекурсивного спуска?

a) #include int c; FILE *fp;

void A();

void ERROR();

void S (void) {c = fgetc(fp); S();

void A (void) {if (c == 'b') c = fgetc(fp);

void main() {fp = fopen("data", "r");

printf("O.K.!");

*b) #include int c; FILE *fp;

void A();

void ERROR();

void S (void) void A (void) { B(); while ( c == 'a' ) {c = fgetc(fp); B();}; B();

void B (void) void main() {fp = fopen("data", "r");

printf("O.K.!");

52. Предложить алгоритм, использующий введенные ранее преобразования (см. стр. 36-38), позволяющий в некоторых случаях получить грамматику, к которой применим метод рекурсивного спуска.

53. Какой язык порождает заданная грамматика? Провести анализ цепочки (a,(b,a),(a,(b)),b).

54. Есть грамматика, описывающая цепочки в алфавите {0, 1, 2, }:

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

55. Дана грамматика, описывающая цепочки в алфавите {a, b, c, }:

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

в цепочку должно входить не менее трех букв с ;

если встречаются подряд две буквы а, то за ними обязательно должна идти буква b.

56. Есть грамматика, описывающая цепочки в алфавите {0, 1}:

Дополнить эту грамматику действиями, исключающими из языка любые цепочки, содержащие подцепочку 101.

L = {a b c | m+k = n либо m-k = n}.

L = {1n 0m 1p | n+p > m, m >= 0}.

59. Дана грамматика с семантическими действиями:

Какой язык описывает эта грамматика ?

60. Дана грамматика:

Вставить в заданную грамматику действия, контролирующие соблюдение следующих условий:

1. уровень вложенности скобок не больше четырех;

2. на каждом уровне вложенности происходит чередование скобочных и бесскобочных элементов.

61. Включить в правила вывода действия, проверяющие выполнение следующих контекстных условий:

a) Пусть в языке L есть переменные и константы целого, вещественного и логического типов, а также есть оператор цикла Включить в это правило вывода действия, проверяющие выполнение следующих ограничений:

1. тип I и всех вхождений Е должен быть одинаковым;

2. переменная логического типа недопустима в качестве параметра цикла.

Для каждой используемой процедуры привести ее текст на Си.

*b) Дан фрагмент грамматики где I -идентификатор Вставить в грамматику действия, контролирующие выполнение следующих условий:

1. каждая метка, используемая в программе, должна быть описана и только 2. не должно быть одинаковых меток у различных операторов;

3. если метка используется в операторе goto, то обязательно должен быть оператор, помеченный такой меткой.

Для каждой используемой процедуры привести ее текст на Си.

62. Дана грамматика где I - идентификатор, N - целая константа, L - логическая константа.

Вставить в заданную грамматику действия, контролирующие соблюдение следующих условий:

1. все переменные, используемые в выражениях и операторах присваивания, должны быть описаны и только один раз;

2. тип левой части оператора присваивания должен совпадать с типом его правой части.

Замечания: а) все записи считаются переменными различных типов (даже если они имеют одинаковую структуру);

Генерация внутреннего представления программ Результатом работы синтаксического анализатора должно быть некоторое внутреннее представление исходной цепочки лексем, которое отражает ее синтаксическую структуру. Программа в таком виде в дальнейшем может либо транслироваться в объектный код, либо интерпретироваться.

Язык внутреннего представления программы Основные свойства языка внутреннего представления программ:

a) он позволяет фиксировать синтаксическую структуру исходной программы;

b) текст на нем можно автоматически генерировать во время синтаксического анализа;

c) его конструкции должны относительно просто транслироваться в объектный код либо достаточно эффективно интерпретироваться.

Некоторые общепринятые способы внутреннего представления программ:

a) постфиксная запись b) префиксная запись c) многоадресный код с явно именуемыми результатами d) многоадресный код с неявно именуемыми результатами e) связные списочные структуры, представляющие синтаксическое дерево.

В основе каждого из этих способов лежит некоторый метод представления синтаксического дерева.

Замечание: чаще всего синтаксическим деревом называют дерево вывода исходной цепочки, в котором удалены вершины, соответствующие цепным правилам вида A B, где A, B VN.

Выберем в качестве языка для представления промежуточной программы постфиксную запись (ее часто называют ПОЛИЗ - польская инверсная запись).

В ПОЛИЗе операнды выписаны слева направо в порядке их использования.

Знаки операций стоят таким образом, что знаку операции непосредственно предшествуют ее операнды.

Например, обычной (инфиксной) записи выражения соответствует такая постфиксная запись:

abc+*de-f/Замечание: обратите внимание на то, что в ПОЛИЗе порядок операндов остался таким же, как и в инфиксной записи, учтено старшинство операций, а скобки исчезли.

Более формально постфиксную запись выражений можно определить таким образом:

(1) если Е является единственным операндом, то ПОЛИЗ выражения Е - это этот операнд;

(2) ПОЛИЗом выражения Е1 Е2, где - знак бинарной операции, Е1 и Е2 операнды для, является запись E1’ E2’, где E1’ и E2’ - ПОЛИЗ выражений Е1 и Е2 соответственно;

(3) ПОЛИЗом выражения E, где - знак унарной операции, а Е - операнд, является запись E’, где E’ - ПОЛИЗ выражения Е;

(4) ПОЛИЗом выражения (Е) является ПОЛИЗ выражения Е.

Запись выражения в такой форме очень удобна для последующей интерпретации (т.е. вычисления значения этого выражения) с помощью стека:

выражение просматривается один раз слева направо, при этом (1) если очередной элемент ПОЛИЗа - это операнд, то его значение заносится в стек;

(2) если очередной элемент ПОЛИЗа - это операция, то на "верхушке" стека сейчас находятся ее операнды (это следует из определения ПОЛИЗа и предшествующих действий алгоритма); они извлекаются из стека, над ними выполняется операция, результат снова заносится в стек;

(3) когда выражение, записанное в ПОЛИЗе, прочитано, в стеке останется один элемент - это значение всего выражения.

Замечание: для интерпретации, кроме ПОЛИЗа выражения, необходима дополнительная информация об операндах, хранящаяся в таблицах.

Замечание: может оказаться так, что знак бинарной операции по написанию совпадает со знаком унарной; например, знак "-" в большинстве языков программирования означает и бинарную операцию вычитания, и унарную операцию изменения знака. В этом случае во время интерпретации операции "-" возникнет неоднозначность: сколько операндов надо извлекать из стека и какую операцию выполнять. Устранить неоднозначность можно, по крайней мере, двумя способами:

a) заменить унарную операцию бинарной, т.е. считать, что "-а" означает "0-а";

b) либо ввести специальный знак для обозначения унарной операции;

например, "-а" заменить на "&a". Важно отметить, что это изменение касается только внутреннего представления программы и не требует изменения входного языка.

Теперь необходимо разработать ПОЛИЗ для операторов входного языка.

Каждый оператор языка программирования может быть представлен как n-местная операция с семантикой, соответствующей семантике этого оператора.

Оператор присваивания в ПОЛИЗе будет записан как где ":=" - это двухместная операция, а I и Е - ее операнды; I означает, что операндом операции ":=" является адрес переменной I, а не ее значение.

Оператор перехода в терминах ПОЛИЗа означает, что процесс интерпретации надо продолжить с того элемента ПОЛИЗа, который указан как операнд операции перехода.

Чтобы можно было ссылаться на элементы ПОЛИЗа, будем считать, что все они перенумерованы, начиная с 1 (допустим, занесены в последовательные элементы одномерного массива).

Пусть ПОЛИЗ оператора, помеченного меткой L, начинается с номера p, тогда оператор перехода goto L в ПОЛИЗе можно записать как где ! - операция выбора элемента ПОЛИЗа, номер которого равен p.

Немного сложнее окажется запись в ПОЛИЗе условных операторов и операторов цикла.

Введем вспомогательную операцию - условный переход "по лжи" с семантикой Это двухместная операция c операндами B и L. Обозначим ее !F, тогда в ПОЛИЗе она будет записана как где p - номер элемента, с которого начинается ПОЛИЗ оператора, помеченного меткой L.

Семантика условного оператора с использованием введенной операции может быть описана так:

Тогда ПОЛИЗ условного оператора будет таким:

где pi - номер элемента, с которого начинается ПОЛИЗ оператора, помеченного меткой Li, i = 2,3.

Семантика оператора цикла while B do S может быть описана так:

Тогда ПОЛИЗ оператора цикла while будет таким:

где pi - номер элемента, с которого начинается ПОЛИЗ оператора, помеченного меткой Li, i = 0,1.

Операторы ввода и вывода М-языка являются одноместными операциями.

Пусть R - обозначение операции ввода, W - обозначение операции вывода.

Тогда оператор ввода read (I) в ПОЛИЗе будет записан как I R;

Постфиксная польская запись операторов обладает всеми свойствами, характерными для постфиксной польской записи выражений, поэтому алгоритм интерпретации выражений пригоден для интерпретации всей программы, записанной на ПОЛИЗе (нужно только расширить набор операций; кроме того, выполнение некоторых из них не будет давать результата, записываемого в стек).

Постфиксная польская запись может использоваться не только для интерпретации промежуточной программы, но и для генерации по ней объектной программы. Для этого в алгоритме интерпретации вместо выполнения операции нужно генерировать соответствующие команды объектной программы.

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

Существует несколько способов построения промежуточной программы.

Один из них, называемый синтаксически управляемым переводом, особенно прост и эффективен.

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

Содержательный пример - генерация внутреннего представления программы для М-языка, приведен ниже, а здесь в качестве иллюстрации рассмотрим более простой пример.

Пусть есть грамматика, описывающая простейшее арифметическое выражение:

Тогда грамматика с действиями по переводу этого выражения в ПОЛИЗ будет такой:

Этот метод можно использовать для перевода цепочек одного языка в цепочки другого языка (что, собственно, мы и делали, занимаясь переводами в ПОЛИЗ цепочек лексем).

Например, с помощью грамматики с действиями выполним перевод цепочек языка в соответствующие цепочки языка Язык L1 можно описать грамматикой Вставим действия по переводу цепочек вида 0n1m в соответствующие цепочки вида ambn :

Теперь при анализе цепочек языка L1 с помощью действий будут порождаться соответствующие цепочки языка L2.

Генератор внутреннего представления программы на М-языке Каждый элемент в ПОЛИЗе - это лексема, т.е. пара вида (номер_класса, номер_в_классе). Нам придется расширить набор лексем:

1) будем считать, что новые операции (!, !F, R, W) относятся к классу ограничителей, как и все другие операции модельного языка;

2) для ссылок на номера элементов ПОЛИЗа введем лексемы класса 0, т.е.

(0,p) - лексема, обозначающая p-ый элемент в ПОЛИЗе;

3) для того, чтобы различать операнды-значения-переменных и операндыадреса-переменных (например, в ПОЛИЗе оператора присваивания), операндызначения будем обозначать лексемами класса 4, а для операндов-адресов введем лексемы класса 5.

Будем считать, что генерируемая программа размещается в массиве P, переменная free - номер первого свободного элемента в этом массиве:

#define MAXLEN_P struct lex P [ MAXLEN_P];

Для записи очередного элемента в массив P будем использовать функцию put_lex:

void put_lex (struct lex l) Кроме того, введем модификацию этой функции - функцию put_lex5, которая записывает лексему в ПОЛИЗ, изменяя ее класс с 4-го на 5-й (с сохранением значения поля value):

void put_lex5 (struct lex l) { l.class = 5; P[ free++] = l;} Пусть есть функция struct lex make_op(char *op), которая по символьному изображению операции op находит в таблице ограничителей соответствующую строку и формирует лексему вида ( 2, i ), где i номер найденной строки.

Генерация внутреннего представления программы будет проходить во время синтаксического анализа параллельно с контролем контекстных условий, поэтому для генерации можно использовать информацию, "собранную" синтаксическим и семантическим анализаторами; например, при генерации ПОЛИЗа выражений можно воспользоваться содержимым стека, с которым работает семантический анализатор.

Кроме того, можно дополнить функции семантического анализа действиями по генерации:

void checkop_p (void) {char *op; char *t1; char *t2; char *res;

t2 = spop(); op = spop(); t1 = spop();

res = gettype (op,t1,t2);

if (strcmp (res, "no")) put_lex (make_op (op));} /* дополнение! - операция Тогда грамматика, содержащая действия по контролю контекстных условий и переводу выражений модельного языка в ПОЛИЗ, будет такой:

E E1 | E1 [ = | > | < ] < spush (TD [curr_lex.value] ) > E1< checkop_p() > E1 T { [ + | - | or] < spush (TD [curr_lex.value] ) >T < checkop_p() >} T F { [ * | / | and] < spush (TD [curr_lex.value] ) >F < checkop_p() >} F I < checkid(); put_lex ( curr_lex ) > | N < spush("int"); put_lex (curr_lex) > | [ true | false ] < spush ("bool"); put_lex (curr_lex) > | not F < checknot(); put_lex (make_op ("not")) > | (E) присваивания, также достаточно очевидны:

S I < checkid(); put_lex5 (curr_lex) > := E < eqtype(); put_lex (make_op (":=")) > При генерации ПОЛИЗа выражений и оператора присваивания элементы массива P заполнялись последовательно. Семантика условного оператора if E then S1 else S2 такова, что значения операндов для операций безусловного перехода и перехода "по лжи" в момент генерации операций еще неизвестны:

Поэтому придется запоминать номера элементов в массиве P, соответствующих этим операндам, а затем, когда станут известны их значения, заполнять пропущенное.

Пусть есть функция struct lex make_labl (int k), которая формирует лексему-метку ПОЛИЗа вида (0,k).

Тогда грамматика, содержащая действия по контролю контекстных условий и переводу условного оператора модельного языка в ПОЛИЗ, будет такой:

S if E < eqbool(); pl2 = free++; put_lex (make_op ("!F")) > then S < pl3 = free++; put_lex (make_op ("!")); P[pl2] = make_labl (free) > else S < P[pl3] = make_lable (free) > Замечание: переменные pl2 и pl3 должны быть локализованы в процедуре S, иначе возникнет ошибка при обработке вложенных условных операторов.

Аналогично можно описать способ генерации ПОЛИЗа других операторов модельного языка.

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

Идея алгоритма очень проста: просматриваем ПОЛИЗ слева направо; если встречаем операнд, то записываем его в стек; если встретили знак операции, то извлекаем из стека нужное количество операндов и выполняем операцию, результат (если он есть) заносим в стек и т.д.

Итак, программа на ПОЛИЗе записана в массиве P; пусть она состоит из N элементов-лексем. Каждая лексема - это структура struct lex {int class; int value;}, возможные значения поля class:

0 - лексемы-метки (номера элементов в ПОЛИЗе) 1 - логические константы true либо false ( других лексем - служебных слов в 2 - операции (других лексем-ограничителей в ПОЛИЗе нет) 3 - целые константы 4 - лексемы-идентификаторы ( во время интерпретации будет использоваться значение) 5 - лексемы-идентификаторы ( во время интерпретации будет использоваться адрес).

Считаем, что к моменту интерпретации распределена память под константы и переменные, адреса занесены в поле address таблиц TID и TNUM, значения констант размещены в памяти.

В программе-интерпретаторе будем использовать некоторые переменные и функции, введенные нами ранее.

void interpreter(void) { 64. Для следующих выражений в ПОЛИЗе дать обычную инфиксную запись:

65. Используя стек, вычислить следующие выражения в ПОЛИЗе:

66. Записать в ПОЛИЗе следующие операторы языка Си и, используя стек, выполнить их при указанных начальных значениях переменных:

*76. Построить регулярную грамматику для языка L1, вставить в нее действия по переводу L1 в L2.

78. Построить регулярную грамматику для языка L1, вставить в нее действия по переводу цепочек языка L1 в соответствующие цепочки языка L2.

L1 = {bi | bi =(i)2, т.е. bi -это двоичное представление числа i N} L2 = {(bi+1)R | bi+1=(i+1)2, R - перевернутая цепочка } 79. Построить грамматику, описывающую целые двоичные числа (допускаются незначащие нули). Вставить в нее действия по переводу этих целых чисел в четверичную систему счисления.

*80. Написать регулярную грамматику для языка L1. Вставить в нее действия по переводу цепочек языка L1 в соответствующие цепочки языка L2.

*81. Написать грамматику для языка L1. Вставить в нее действия по переводу цепочек языка L1 в соответствующие цепочки языка L2.

L2={ | = bnR, где n - количество символов b в цепочке, предшествующих первому вхождению символа a; R - реверс *82. Написать грамматику для языка L1. Вставить в нее действия по переводу цепочек языка L1 в соответствующие цепочки языка L2.

L1={ | {a,b}+, где содержится n символов a и m символов b, расположенных в произвольном порядке} *83. Написать грамматику для языка L1. Вставить в нее действия по переводу цепочек языка L1 в соответствующие цепочки языка L2.

L1={ | {0,1}+, рассматривается как (bi)R, т.е. реверс двоичного числа L2={ {/}*, = /i, т.е. количество /, равное значению i }

Л И Т Е РАТ У РА

1. Д.Грис. Конструирование компиляторов для цифровых вычислительных машин. - М., Мир, 1975.

2. Ф.Льюис, Д.Розенкранц, Р.Стирнз. Теоретические основы проектирования компиляторов. - М., Мир, 1979.

3. А.Ахо, Дж.Ульман. Теория синтаксического анализа, перевода и компиляции. - Т. 1,2. - М., Мир, 1979.

4. Ф.Вайнгартен. Трансляция языков программирования. - М., Мир, 1977.

5. И.Л.Братчиков. Синтаксис языков программирования. - М., Наука, 1975.

6. С.Гинзбург. Математическая теория контекстно-свободных языков. - М., Мир, 1970.

7. Дж.Фостер. Автоматический синтаксический анализ. - М., Мир, 1975.

8. В.Н.Лебедев. Введение в системы программирования. - М., Статистика, 1975.

9. Б.Ф.Мельников. Подклассы класса контекстно-свободных языков. - М., МГУ, 1995.

С ОД Е РЖ А Н И Е

ЭЛЕ МЕ НТЫ ТЕОРИИ ФОРМАЛЬНЫХ ЯЗЫКОВ И ГРАММАТИК...... ВВЕДЕНИЕ

ОСНОВНЫЕ ПОНЯТИЯ И ОПРЕДЕЛЕНИЯ

КЛАССИФИКАЦИЯ ГРАММАТИК И ЯЗЫКОВ ПО ХОМСКОМУ

ПРИМЕРЫ ГРАММАТИК И ЯЗЫКОВ.

ЗАДАЧА РАЗБОРА

ПРЕОБРАЗОВАНИЯ ГРАММАТИК

ЗАДАЧИ

ЭЛЕМЕНТЫ ТЕОРИИ ТРАНСЛЯЦИИ

ВВЕДЕНИЕ

Описание модельного языка

ЛЕКСИЧЕСКИЙ АНАЛИЗ

О недетерминированном разборе

Задачи лексического анализа

Лексический анализатор для М-языка

Задачи.

СИНТАКСИЧЕСКИЙ И СЕМАНТИЧЕСКИЙ АНАЛИЗ

Метод рекурсивного спуска

О применимости метода рекурсивного спуска

Синтаксический анализатор для М-языка

О семантическом анализе

Семантический анализатор для М-языка

Задачи.

ГЕНЕРАЦИЯ ВНУТРЕННЕГО ПРЕДСТАВЛЕНИЯ ПРОГРАММ

Язык внутреннего представления программы

Синтаксически управляемый перевод

Генератор промежуточной программы для М-языка

Интерпретатор ПОЛИЗа для модельного языка

Задачи.

ЛИТЕРАТУРА

СОДЕРЖАНИЕ




Похожие работы:

«Содержание 1. О серии НАГЛЯДНАЯ ШКОЛА 2. Руководство пользователя 2.1. Установка программы и системные требования 2.2. Управление просмотром пособия 2.3. Интерактивные элементы в пособии 3. Применение пособий серии НАГЛЯДНАЯ ШКОЛА в учебном процессе 4. Наглядные пособия по географии 4.1. Возможности интерактивных наглядных пособий 4.2. Перечень наглядных пособий по географии 5. Методическое содержание карт 5.1. Политическая карта мира 5.2. Государства Зарубежной Европы. Социально-экономическая...»

«Уважаемые выпускники! В перечисленных ниже изданиях содержатся методические рекомендации, которые помогут должным образом подготовить, оформить и успешно защитить выпускную квалификационную работу. Рыжков, И. Б. Основы научных исследований и изобретательства [Электронный ресурс] : [учебное пособие для студентов вузов, обучающихся по направлению подготовки (специальностям) 280400 — Природообустройство, 280300 — Водные ресурсы и водопользование] / И. Б. Рыжков.— Санкт-Петербург [и др.] : Лань,...»

«3 Содержание 1. Общие положения 1.1. Основная образовательная программа 1.2. Нормативные документы для разработки ООП 1.3. Общая характеристика основной образовательной программы высшего профессионального образования 1.4. Требования к уровню подготовки, необходимому для освоения ООП 2. Характеристики профессиональной деятельности выпускника ООП 2.1. Область профессиональной деятельности выпускника 2.2. Объекты профессиональной деятельности выпускника 2.3. Виды профессиональной деятельности...»

«Министерство образования и науки Российской Федерации федеральное государственное бюджетное образовательное учреждение высшего профессионального образования Тобольская государственная социальнопедагогическая академия им. Д.И. Менделеева Отчет о результатах самообследования федерального государственного бюджетного образовательного учреждения высшего профессионального образования Тобольская государственная социально-педагогическая академия им. Д. И. Менделеева Тобольск 2014 1 ОГЛАВЛЕНИЕ Введение...»

«Министерство образования и науки Краснодарского края Государственное бюджетное образовательное учреждение среднего профессионального образования АРМАВИРСКИЙ МАШИНОСТРОИТЕЛЬНЫЙ ТЕХНИКУМ Краснодарского края РАБОЧАЯ ПРОГРАММА УЧЕБНОЙ ДИСЦИПЛИНЫ ОП.07. Бухгалтерский учёт основной профессиональной образовательной программы по специальности СПО 100801 Товароведение и экспертиза качества потребительских товаров (по отраслям); базовой подготовки 2012 ОДОБРЕНА УТВЕРЖДАЮ методическим советом техникума...»

«Негосударственное образовательное учреждение высшего профессионального образования Институт государственного администрирования Утверждаю Проректор по учебной работе Н.Д. Бережнова __ 2013г. Рабочая программа учебной дисциплины Страхование (Наименование дисциплины) 080100.62 Экономика (Направление подготовки) Бакалавриат (уровень подготовки) Экономика и управление Факультет Экономики и мировой экономики Кафедра разработчик Трудоемкость дисциплины Очная Вид учебной деятельности Заочная форма...»

«Негосударственное образовательное учреждение высшего профессионального образования Институт государственного администрирования (НОУ ВПО ИГА) Учебно-методический комплекс Павлова О.Е. Основы генетики (специальность 031800 Логопедия) Москва 2013 УДК Л Учебно-методический комплекс рассмотрен и одобрен на заседании кафедры Психологии 31 августа 2013 г., протокол №1 Автор – Павлова О.Е., кандидат биологических наук, доцент кафедры психологии Рецензент – Павлова О.Е. Основы генетики:...»

«МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ Государственное образовательное учреждение высшего профессионального образования ГОРНО-АЛТАЙСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ Юридический факультет Кафедра уголовного, гражданского права и процесса СОГЛАСОВАНО УТВЕРЖДАЮ Декан ЮФ Проректор по УР В.Г. Крашенинина О.А.Гончарова __ 2008 г. _ 2008 г. УЧЕБНО-МЕТОДИЧЕСКИЙ КОМПЛЕКС ПО ДИСЦИПЛИНЕ Банковское право по специальности 030501 Юриспруденция Составитель...»

«Федеральное агентство по образованию Государственное образовательное учреждение высшего профессионального образования Казанский государственный технологический университет Э.Н. Островская, Т.В. Полякова РАСЧЕТ И КОНСТРУИРОВАНИЕ ХИМИЧЕСКИХ АППАРАТОВ С МЕШАЛКАМИ Учебное пособие Казань 2006 ББК 34.42 УДК 621.10 Расчет и конструирование химических аппаратов с мешалками: учебное пособие/Э.Н.Островская, Т.В. Полякова; Казан.гос.тех-нол.ун-т. Казань, 2006. ISBN 978-5-7882-0377-5 Учебное пособие...»

«Министерство образования и науки РФ ГОУ ВПО Ярославский государственный педагогический университет им. К.Д. Ушинского В.В. Афанасьев, А.В. Муравьев, И.А. Осетров, П.В. Михайлов Спортивная метрология Учебное пособие Ярославль 2009 УДК 519.22; 796:311 Печатается по решению ББК 75 в 631.8+22.172 редакционно-издательского А 94 совета ЯГПУ им. К.Д. Ушинского Рецензенты: доктор педагогических наук, профессор М.Н. Жуков доктор физико-математических наук, профессор ЯФ РОАТ В.А. Коромыслов Афанасьев...»

«МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ САМАРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ В. А. ОЛЬХОВСКАЯ РАСЧЕТ ПОКАЗАТЕЛЕЙ РАЗРАБОТКИ ОДНОРОДНОГО ПЛАСТА НА ОСНОВЕ МОДЕЛИ ДВУХФАЗНОЙ ФИЛЬТРАЦИИ ДЛЯ ЖЕСТКОГО ВОДОНАПОРНОГО РЕЖИМА ЗАДАЧА 1 ПЛОСКОРАДИАЛЬНОЕ ДВИЖЕНИЕ Методические указания Самара 2011 2 Составитель В.А.ОЛЬХОВСКАЯ УДК 622. Расчет показателей разработки однородного пласта на основе...»

«МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования Ивановская государственная текстильная академия (ИГТА) Кафедра конструирования швейных изделий РАЗРАБОТКА БАЗОВОЙ КОНСТРУКЦИИ ЖЕНСКИХ БРЮК ПО НОВОЙ РАЗМЕРНОЙ ТИПОЛОГИИ Методические указания к выполнению лабораторных работ по дисциплинам Конструирование изделий легкой промышленности, Конструирование женской и детской одежды, Конструирование...»

«Федеральное агентство по образованию Государственное образовательное учреждение высшего профессионального образования Уральский государственный технический университет – УПИ Нижнетагильский технологический институт (филиал) ВЫБОР ОПТИМАЛЬНОГО ИНВЕСТИЦИОННОГО ПРОЕКТА Методические указания к выполнению курсовой работы по дисциплине Инвестиционная стратегия для студентов всех форм обучения специальности 080502 – Экономика и управление на предприятии Нижний Тагил 2008 ББК У9(2)290-561 В92...»

«Министерство образования и науки Российской Федерации Федеральное государственное автономное образовательное учреждение высшего профессионального образования “Уральский федеральный университет имени первого Президента России Б.Н. Ельцина” Центр классического образования Физический факультет Лабораторный практикум по высшей геодезии Методические указания для студентов 3 курса Екатеринбург, 2011 1 Автор доцент Т.И. Левитская 2 СОДЕРЖАНИЕ Словарь терминов.. Лабораторная работа № 1 Исследование...»

«Министерство образования Санкт-Петербургский государственный политехнический университет Баденко В.Л., Гарманов В.В., Осипов Г.К. Государственный земельный кадастр Учебное пособие Под редакцией проф. Арефьева Н.В. Санкт-Петербург Издательство СПбГПУ 2002 УДК 332.33 (075*8) Государственный земельный кадастр. Учебное пособие / Баденко В.Л., Гарманов В.В., Осипов Г.К. Под ред. проф. Н.В.Арефьева СПб.: Изд-во СПбГПУ, 2002, 331 с. В пособии рассматриваются вопросы содержания и методики ведения...»

«СМОЛЕНСКИЙ ГУМАНИТАРНЫЙ УНИВЕРСИТЕТ Молчанова Н.В. ЮРИДИЧЕСКАЯ ПСИХОЛОГИЯ Учебно-методическое пособие (для студентов, обучающихся по специальности 021100 Юриспруденция - очная и заочная форма обучения) Смоленск, 2008 1 1. СОДЕРЖАНИЕ УЧЕБНОЙ ДИСЦИПЛИНЫ Раздел I. Предмет и система юридической психологии. Социальные нормы и формирование правосознания личности. Тема 1. ПРЕДМЕТ, МЕТОДЫ И СИСТЕМА ЮРИДИЧЕСКОЙ ПСИХОЛОГИИ. Предмет юридической психологии, ее место в системе психологической науки....»

«Московский международный институт эконометрики, информатики, финансов и права Фомина А.С. История модернизации в России Москва, 2003 УДК 32:9 ББК 63.3 Ф 762 Фомина А.С. История модернизации в России. / Московский международный институт эконометрики, информатики, финансов и права. - М., 2003. - 42 с. © Фомина А.С., 2003 г. © Московский международный институт эконометрики, информатики, финансов и права, 2003 г. 2 Содержание Введение 1. Теория модернизации и постмодернизации 1.1. Модернизация и...»

«Государство в условиях глобализации, 2007, Владимир Сергеевич Малахов, 5982272531, 9785982272539, Университет Книжный дом, 2007 Опубликовано: 13th September 2009 Государство в условиях глобализации СКАЧАТЬ http://bit.ly/1cAye18 Beyond the Nation-state Functionalism and International Organization, Ernst B. Haas, Jan 1, 1964, Political Science, 595 страниц.. Globalization The Human Consequences, Zygmunt Bauman, 1998, Business & Economics, 136 страниц. 1 Time and Class. Propaganda: the art of...»

«Учреждение образования БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНОЛОГИЧЕСКИЙ УНИВЕРСИТЕТ ЭКОНОМИКА ПРЕДПРИЯТИЯ ОТРАСЛИ Учебно-методическое пособие для студентов специальности 1-25 01 07 Экономика и управление на предприятии специализации 1-25 01 07 25 Экономика и управление в полиграфической промышленности Минск 2006 УДК 658:66(075.8) ББК 65.9я73 Э 40 Рассмотрено и рекомендовано к изданию редакционноиздательским советом университета Составители: С. А. Касперович, Е. М. Шикуть Рецензенты: ст....»

«основные события 8 апреля Открытие кОнференции работа межсекционных круглых столов Социальное пространство 11.15, зал Ученого совета города Организация общественных пространств в историческом 11.15, Красный зал и новом городе Проблемы устойчивого развития 13.30, зал Ученого совета и экологии в архитектуре Творческие концепции архитектурной деятельности: теория, 11.15, ауд. 233 процесс, воплощение 15.00-15.30, фойе Красного зала регистрация участников торжественное открытие Красный зал пленарное...»










 
2014 www.av.disus.ru - «Бесплатная электронная библиотека - Авторефераты, Диссертации, Монографии, Программы»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.