Информационный сайт

 

Реклама
bulletinsite.net -> Книги на сайте -> Программисту -> Непейвода Н.Н. -> "Основания программирования " -> 242

Основания программирования - Непейвода Н.Н.

Непейвода Н.Н., Скопин И.Н. Основания программирования — Институт компьютерных исследований , 2002. — 919 c.
Скачать (прямая ссылка): osnovanprogramm2002.pdf
Предыдущая << 1 .. 236 237 238 239 240 241 < 242 > 243 244 245 246 247 248 .. 316 >> Следующая

ри модификации грамматики вариант правил переписыва тся в виде так называемых регулярных выражений, которые образуются из исход-
7 Обсуждение вопросов, связанных с преобразованием сложно структурированных данных см. в главе, посвященной сентенциальным методам.
11.6. РЕКУРСИЯ В ТРАНСЛИРУЮЩИХ ПРОГРАММАХ
693
Выражение Вывод-порождение выражения
a E =/-1,1 M =/-2.1 T =/-3,11 =/-4.1 L =/-5,1 a
b E ==1^ M =2д T =3д I =4д L =^2 b
a + b E =l2 M + E =/-2д T + E =/-3д I + E =/-4д L + E =5д a + E a + M =2д a + T =3д a + I =4д a + L =^2 a + b
ac * ( a - b ) E = 1.1 M = 2.2 T * M = 3.1 I * M = 4.2 LI * M = 5.1 aI * M =53 ac * M =2д ac * T =^2 ac * (E) =l3 ac * (M-E) =* ac * (a - E) = ac * (a - M) ==* ac * (a - b)
( a - b ) * E M =^2 T * M =^2 (E) * M =* ( a - b ) * M =* ( a
( c + d ) - b) * ( c + d )
ac * bd E =L1 M =^2 T * M {В предыдущих примерах для очередного порождения использовалось самое левое из понятий строки; сейчас демонстрируется возможность продолжать вывод из любого понятия, имеющегося в строке (в данном случае это M, второе понятие, из которого получено T). оскольку грамматика вра ения контекстно-свободная, результат вывода не зависит от выбора правил.} =3.1 T * I =4.2 Т * LI =5.2 T * bI =* ac * bd
Таблица 11.1. Примеры вывода выражений
694
ГЛАВА 11. МЕТОДЫ, ОСНОВАННЫЕ НА РЕКУРСИИ
ной грамматики путем объединения вариантов. Эта модификация приводит к тому, что каждое правило новой грамматики может быть распознано во входном потоке по первому символу: ситуация, когда первый символ соответствует грамматике, а последующие нет, гарантирует, что входная строка не принадлеит язку.
Регулярне выра ения зада тся в следуей нотации:
• в фигурные скобки "{" и "}" заключаются объединяемые части вариантов;
• внутри фигурных скобок возможно использование символа "|" со старым смыслом (он указывает на возможность вариантов выбора порождения);
• если непосредственно после фигурных скобок употреблен символ "+" или "*", то это означает, что возможно повторение обрамленной фигурными скобками части строки. Символ "*" указывает на необязательность обрамленной фигурными скобками части — повторение нуль и более раз, а символ "+" на то, что эта часть в порождении должна появиться по крайней мере один раз.
анная нотация регулярнх выра ений более традиционна для теоретических рассмотрений регулярных выражений, чем та, что использовалась в § 2.1. В новой редакции грамматика упрощенных арифметических выражений выглядит следуим образом:
E::=M{+E | - E}* (1)
M::=T{*M | / M}* (2)
T ::= I | (E) (3)
I ::= { a | b | c | ... | z}+ ( 4 )
ервое правило состоит в том, что E (вра ение) есть M (простое вра-ение), за которм, бть мо ет, следу т "+ E" или "- E", повторенные нуль и более раз. налогично, второе правило читается: M есть T (терм), за которым, быть может, следуют "* E" или "/ E", повторенные нуль и более раз. Определение терма (правило 3) не изменилось. Четвертое и пятое правило объединены. Теперь I (имя переменной) есть буква, повторенная один и более раз.
окаите эквивалентность двух определений простых вра ений.
11.6. РЕКУРСИЯ В ТРАНСЛИРУЮЩИХ ПРОГРАММАХ
695
В соответствии с новой грамматикой процесс распознавания того, является ли входная строка выражением, задается с помощью комплекта логических функций: E, M, T и I. Они выясняют, распознается ли некоторая часть строки как выражение (E), простое выражение (M), терм (T) и имя переменной (I), и тогда вырабатывают значение true, а в противном случае — false.
ля наглядности программ этих функций поименованы так е, как правила грамматики. Они составляются систематическим переписыванием правил, при котором понятия, появляиеся в правиле, превраа тся в вызовы соответствуих им функций, а обрамленне фигурными скобками части оформля тся как циклы.
Обработка символов, из которых строится выражение (букв, знаков "+", "*", "/", скобок), задается как сравнение этих символов с значением литеры из входного потока. Это значение поставляется специальной процедурой Scan, которая записвает его в глобальну переменну S. В представленной ни е программе Scan осуествляет чтение литеры из файла ввода и печатает пробел под очереднм читаемым символом (чтоб в случае ошибки можно было бы отметить этот символ в вводимой строке). Как правило, подобные действия сопровождаются другими дополнительными вычислениями лексического характера, например, распечаткой читаемой последовательности символов, удалением незначащих пробелов и др. Тем самым в программе синтаксического анализа вделяется часть, отвечаая за проведение лексических вычислений, главная цель которых — выработка лексем (в предлагаемой программе это значения переменной S), передаваемых для вполнения собственно синтаксических вычислений без избыточной информации. бучаемому предлагается модифицировать программу с тем, чтоб указанне вые дополнительные лексические вычисления осуествлялись.
Переменная S и процедура Scan включены в комплект подпрограмм синтаксического распознавания.
оследнее предварительное замечания касается использования в программе конструкции #13 языка Turbo Pascal. Она обозначает символьное значение, которое нельзя представить графически, в данном случае это символ перехода на нову строку, который позволяет узнавать, действительно ли вся входная последовательность прочитана.
Предыдущая << 1 .. 236 237 238 239 240 241 < 242 > 243 244 245 246 247 248 .. 316 >> Следующая
Реклама
Авторские права © 2009 AdsNet. Все права защищены.
Rambler's Top100