7

Лабораторная работа № 2

Представление арифметических выражений в польской записи

Цели работы: 1) ознакомление с методом распознавания в тексте исходной программы синтаксически корректных арифметических выра­жений, основанным на использовании формальных грамматик; 2) изучение, анализ и программная реализация алгоритма перевода арифметических выражений из инфиксной формы в польскую запись, который используются в процессе трансляции языков программирования высокого уровня.

1. Теоретическая часть

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

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

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

1.1. Распознавание арифметических выражений

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

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

Пусть длина строки  определяет число символов этой строки и обозначается как  . Например, ab  = 2, длина пустой строки  = 0. Если A - некоторый алфавит, то совокупность строк, состав­ленных в этом алфавите и имеющих длину n, обозначается как Aⁿ. Например, для алфавита A = {a, b, с} получаем A = {a, b, с}, A² = {aa, ab, ac, ba, bb, bс, са, сb, cc}, A= {aaa, abb, acc, aab, ...}. Необходимо отметить, что A = {}, где  - пустая строка.

Множество всех строк, составленных из символов алфавита A и имеющих длину n  1, обозначается как A⁺, где

A⁺ = A¹  А²  ...  Аⁿ  ... .

Множество всех строк, составленных из символов алфавита A и включающих пустую строку , обозначается через А^*, где

А^* = {}  А⁺ = А⁰  A¹  А²  ...  Аⁿ … .

Формальной грамматикой называется четверка G = {N, T, P, S}, где N - конечное множество (алфавит) нетерминальных символов; Т - конеч­ное множество (алфавит) терминальных символов; P - конечное мно­жество правил вывода (продукций) вида   , где  и  - строки символов, такие, что   (N Т )⁺,   (N Т )^*; S - начальный символ грамматики, причем всегда S  N.

Терминальные символы являются неделимыми единицами некоторого языка, из которых состоят строки или предложения этого языка. Нетерминальные символы иногда называют вспомогательными, так как они определяют вспомо­гательные синтаксические конструкции или понятия языка и использу­ются для получения предложений. Всегда N  T = , т.е. множества нетерминальных и терминальных символов не имеют общих элементов. Начальный символ S граммати­ки является исходным при получении любой строки языка.

Арифметические и логические выражения могут быть описаны с помощью контекстно-свободных грамматик (КС-грамматик). В таких грамматиках левые части всех правил вывода состоят из одного не­терминального символа, т.е. имеют вид B   , где B  N и   (N Т )^*. Здесь нетерминальный символ B можно заменить строкой  (возможно, пустой), не обращая внимания на контекст, в котором он встретился.

Рассмотрим КС-грамматику, описывающую арифметические выраже­ния, построенные с использованием знаков операций +, –,  , / и круглых скобок. Операнды могут состоять из одной буквы латинского алфавита или цифры. Терминальные симво­лы грамматики будем обозначать строчными буквами, нетерминальные - прописными. Такая грамматика может быть представлена как

G = (N, T, P, E),

где N = {E, T, F}, T = {+, –, , /, (, ), 0, 1, 2 ... 9, a, b, c, …, z}, а правила вывода, составляющие множество P, имеют следующий вид:

E  T Е + Т E – Т ;

Т  F Т  F T / F ;

F  ( Е ) 0 1 2 ... 9 а b с ... z .

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

(a - b)  c + d (1)

является правильным. Для этого пере­нумеруем правила вывода грамматики:

1: E  T ;	4: T  F ;	7: F  ( E ) ;
2: Е  Е + Т ;	5: T  T  F ;	8: F  0 1 2 ... 9 ;
3: E  E – T ;	6: T  T / F ;	9: F  a b c ... z .

Затем выполним вывод выражения (1) из начального символа E (рис. 1), указывая в скобках номера применяемых на каждом шаге правил. Порядок использования правил вывода также может быть представлен синтаксическим деревом, которое для данного примера имеет вид, показанный на рис. 2. Таким образом, выражение (1) является синтаксически корректным, поскольку существует конечная последовательность правил, применение кото­рых позволяет вывести это выражение.

Для описания синтаксиса языков программирования широкое при­мене­ние находит форма Бэкуса-Наура (БНФ), которая эквивалентна контекстно-свободным грамматикам, но отличается по форме записи. При использовании БНФ нетерминальные символы заключаются в угло­вые скобки < ... >, запись ::= означает "определяется как", а вертикальная черта читается как "или". Рассмотренная выше грамматика, описывающая арифметические выражения и представленная в форме Бэкуса-Наура, имеет следующий вид:

< выражение > ::= < терм > | < выражение > + < терм > | < выражение > – < терм > ;

< терм > ::= < множитель > | < терм >  < множитель > | < терм > / < множитель > ;

< множитель > ::= ( < выражение > ) | 0 | l | 2| ... | 9| a | b | ... | z .