Разработка учебного транслятора с упрощенного текстового языка высокого уровня

1. Методы грамматического разбора

1.1 Разбор сверху-вниз

1.1.1 LL (k) — языки и грамматики

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

1.2 Разбор снизу-вверх

1.2.1 LR (k) — грамматики

1.2.1.1 LR (0) — грамматики

1.2.2 LALR (1) — грамматики

2. Разработка транслятора

2.1 Анализ требований

2.2 Проектирование

2.2.1 Проектирование лексического анализатора

2.2.2 Проектирование магазинного автомата

2.2.4 Программная реализация синтаксического анализатора

2.2.4 Разработка модуля интерпретации

2.3 Кодирование

2.4 Тестирование

Заключение

Список использованных источников

Приложение А. Листинг программного текста транслятора

Приложение Б. Результаты тестирования

Приложение В. Схема программы транслятора

Давно уже прошли те времена, когда прежде чем написать программу надо было понять и запомнить не один десяток машинных инструкций. Современный программист формулирует свои задачи на языках программирования высокого уровня и использует язык ассемблера лишь в исключительных случаях. Как известно, алгоритмические языки становятся доступными программисту лишь после создания трансляторов с этих языков. [2−6]

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

Языки программирования являются инструментами для решения задач в разных предметных областях, что определяет специфику их организации и различия по назначению. В качестве примера можно привести такие языки как Фортран, ориентированный на научные расчеты, C, предназначенный для системного программирования, Пролог, эффективно описывающий задачи логического вывода, Лисп, используемый для рекурсивной обработки списков. Эти примеры можно продолжить. Каждая из предметных областей предъявляет свои требования к организации самого языка. Поэтому можно отметить разнообразие форм представления операторов и выражений, различие в наборе базовых операций, снижение эффективности программирования при решении задач, не связанных с предметной областью. Языковые различия отражаются и в структуре трансляторов. Лисп и Пролог чаще всего выполняются в режиме интерпретации из-за того, что используют динамическое формирование типов данных в ходе вычислений. Для трансляторов с языка Фортран характерна агрессивная оптимизация результирующего машинного кода, которая становится возможной благодаря относительно простой семантике конструкций языка — в частности, благодаря отсутствию механизмов альтернативного именования переменных через указатели или ссылки. Наличие же указателей в языке C предъявляет специфические требования к динамическому распределению памяти.

Структура языка характеризует иерархические отношения между его понятиями, которые описываются синтаксическими правилами. Языки программирования могут сильно отличаться друг от друга по организации отдельных понятий и по отношениям между ними. Язык программирования PL/1 допускает произвольное вложение процедур и функций, тогда как в C все функции должны находиться на внешнем уровне вложенности. Язык C++ допускает описание переменных в любой точке программы перед первым ее использованием, а в Паскале переменные должны быть определены в специальной области описания. Еще дальше в этом вопросе идет PL/1, который допускает описание переменной после ее использования. Или описание можно вообще опустить и руководствоваться правилами, принятыми по умолчанию. В зависимости от принятого решения, транслятор может анализировать программу за один или несколько проходов, что влияет на скорость трансляции.

Семантика языков программирования изменяется в очень широких пределах. Они отличаются не только по особенностям реализации отдельных операций, но и по парадигмам программирования, определяющим принципиальные различия в методах разработки программ. Специфика реализации операций может касаться как структуры обрабатываемых данных, так и правил обработки одних и тех же типов данных. Такие языки, как PL/1 и APL поддерживают выполнение матричных и векторных операций. Большинство же языков работают в основном со скалярами, предоставляя для обработки массивов процедуры и функции, написанные программистами. Но даже при выполнении операции сложения двух целых чисел такие языки, как C и Паскаль могут вести себя по-разному.

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

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

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

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

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

Для любого языка определяется:

— множество символов, которые можно использовать для записи правильных программ (алфавит), основные элементы,

— множество правильных программ (синтаксис),

— «смысл» каждой правильной программы (семантика).

Независимо от специфики языка любой транслятор можно считать функциональным преобразователем F, обеспечивающим однозначное отображение X в Y, где X — программа на исходном языке, Y — программа на выходном языке. Поэтому сам процесс трансляции формально можно представить достаточно просто и понятно: Y = F (X).

Формально каждая правильная программа X — это цепочка символов из некоторого алфавита A, преобразуемая в соответствующую ей цепочку Y, составленную из символов алфавита B.

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

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

Другой характерной особенностью всех языков является их семантика. Она определяет смысл операций языка, корректность операндов. Цепочки, имеющие одинаковую синтаксическую структуру в различных языках программирования, могут различаться по семантике (что, например, наблюдается в C++, Pascal, Basic). Знание семантики языка позволяет отделить ее от его синтаксиса и использовать для преобразования в другой язык (осуществить генерацию кода).

Целью данной курсовой работы является разработка учебного транслятора с заданного упрощенного текстового языка высокого уровня.

1. Методы грамматического разбора

Рассмотрим основные методы грамматического разбора. [7−11]

1.1 Разбор сверху-вниз

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

1.1.1 LL (k) — языки и грамматики

Рассмотрим дерево вывода в процессе получения левого вывода цепочки. Промежуточная цепочка в процессе вывода состоит из цепочки из терминалов w, самого левого нетерминала A, недовыведенной части x:

— S—

/ -А-x;

/ |

— w—-u——

Pисунок 1

Для продолжения разбора требуется заменить нетерминал A по одному из правил вида A: y. Если требуется, чтобы разбор был детерминированным (без возвратов), это правило требуется выбирать специальным способом. Говорят, что грамматика имеет свойство LL (k), если для выбора правила оказывается достаточно рассмотреть только wAx и первые k символов непросмотренной цепочки u. Первая буква L (Left, левый) относится к просмотру входной цепочки слева направо, вторая — к используемому левому выводу.

Определим два множества цепочек:

а) FIRST (x) — множество терминальных цепочек, выводимых из x, укороченных до k символов.

б) FOLLOW (A) — множество укороченных до k символов терминальных цепочек, которые могут следовать непосредственно за A в выводимых цепочках.

Грамматика имеет свойство LL (k), если из существования двух цепочек левых выводов:

S: wAx: wzx: wu

S: wAx: wtx: wv

из условия FIRST (u)=FIRST (v) следует z=t.

В случае k=1 для выбора правила для А, достаточно знать только нетерминал A и, а — первый символ цепочки u:

— следует выбрать правило A: x, если, а входит в FIRST (x),

— следует выбрать правило A: е, если, а входит в FOLLOW (A).

LL (к)-свойство накладывает довольно сильные ограничения на грамматику. Например, LL (2) грамматика S: aS | a не обладает свойством LL (1), т.к. FIRST (aS)=FIRST (a)=a. В данном случае можно понизить величину k с помощью «факторизации» (вынесения множителя за скобку):

S: aA

A: S | e

Любая LL (k)-грамматика однозначна. Леворекурсивная грамматика не принадлежит классу LL (k) ни для какого k. Иногда удается преобразовать не LL (1)-грамматику в эквивалентную ей LL (1)-грамматику с помощью устранения левой рекурсии и факторизации. Однако проблема существования эквивалентной LL (k)-грамматики для произвольной не LL (k)-грамматики неразрешима.

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

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

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

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

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

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

1.2 Разбор снизу-вверх

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

— S—

/-x;

/ |

—w—b—u;

Рисунок 2

Промежуточный вывод имеет вид xbu, где x — цепочка терминалов и нетерминалов, из которой выводится просмотренная часть терминальной цепочки w, bu — непросмотренная часть терминальной цепочки, b — очередной символ. Чтобы продолжить разбор, можно либо добавить символ b к просмотренной части цепочки (выполнить так называемый «сдвиг»), либо выделить в конце x такую цепочку z (x=yz), что к z можно применить одно из правил грамматики B: z и заменить x на цепочку yB (выполнить так называемую «свертку»):

— S— -S—

/ /

/-x-b- /yB;

/ | / |

—w—b—u- —w—b—u;

Рисунок 3 — После сдвига Рисунок 4 — После свертки

Если свертку применять только к последним символам x, то мы будем получать правые выводы цепочки. Такой разбор получил название LR, где символ L (Left, левый) относится к просмотру цепочки слева направо, а R (Right, правый) относится к получаемым выводам.

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

1.2.1 LR (k) — грамматики

Если в процессе LR-разбора принять детерминированное решение о сдвиге/свертке удается, рассматривая только цепочку x и первые k символов непросмотренной части входной цепочки u (эти k символов называют аванцепочкой), говорят, что грамматика обладает LR (k)-свойством.

— S—

/-x;

—w——u—

Рисунок 5

Различие между LL (k) — и LR (k)-грамматиками в терминах дерева вывода:

— S;

/ |

/ A

/ /

— w—-v—-u;

Рисунок 6

В случае LL (k)-грамматик однозначно определить правило, примененное к A, можно по w и первым k символам vu, а в случае LR (k)-грамматик — по w, v и первым k символам u. Это нестрогое рассуждение показывает, что LL (k)-языки < LR (k)-языки (при k > 0).

1.2.1.1 LR (0) — грамматики

Рассмотрим вначале наиболее простые грамматики этого класса — LR (0). При разборе строки LR (0)-языка можно вообще не использовать аванцепочку — выбор между сдвигом и сверткой делается на основании цепочки x. Так как в процессе разбора она изменяется только с правого конца, ее называют стеком. Будем считать, что в грамматике нет бесполезных символов и начальный символ не встречается в правых частях правил — тогда свертка к начальному символу сигнализирует об успешном завершении разбора. Попробуем описать множество цепочек из терминалов и нетерминалов, появляющихся в стеке в процессе всех LR-разборов (другими словами — всех правых выводов из грамматики).

Определим следующие множества:

L (A:v) — левый контекст правила A: v — множество состояний стека, непосредственно перед сверткой v в A в ходе всех успешных LR-разборов. Очевидно, каждая цепочка из L (A:v) кончается на v. Если у всех таких цепочек отрезать хвост v, то получится множество цепочек, встречающихся слева от A в процессе всех успешных правых выводов. Обозначим это множество L (A) — левый контекст нетерминала A.

Построим грамматику для множества L (A). Терминалами новой грамматики будут терминалы и нетерминалы исходной грамматики, нетерминалы новой грамматики обозначим ,… — их значениями будут левые контексты нетерминалов исходной грамматики. Если S — начальный символ исходной грамматики, то грамматика левых контекстов будет содержать правило: e — левый контекст S содержит пустую цепочку Для каждого правила исходной грамматики, например, A: B C d E

и добавим в новую грамматику правила:

: — L (B) включает L (A)

: B — L© включает L (A) B

: B C d — L (E) включает L (A) B C d

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

— регулярны. Из этого следует, что принадлежность цепочки левому контексту какого-либо нетерминала можно вычислять индуктивно с помощью конечного автомата, просматривая цепочку слева направо. Опишем этот процесс конструктивно.

Назовем LR (0)-ситуацией правило грамматики с одной отмеченной позицией между символами правой части правила. Например, для грамматики S: A; A: aAA; A: b существуют следующие LR (0)-ситуации: S:_A; S: A_; A:_aAA; A: a_AA; A: aA_A; A: aAA_; A:_b; A: b_. (позиция обозначена символом подчеркивания).

Будем говорить, что цепочка x согласована с ситуацией А: b_c, если x=ab и a принадлежит L (A). (Другими словами, LR-вывод может быть продолжен x_… = ab_…: abc_…: aA_…: S_.) В этих терминах L (A:b) — множество цепочек, согласованных с ситуацией A: b_, L (A)

— цепочки, согласованные с ситуацией A:_b, для любого правила A: b.

Пусть V (u) — множество ситуаций, согласованных с u. Покажем, что функция V — индуктивна.

Если в множество V (u) входит ситуация A: b_cd, то ситуация A: bc_d принадлежит V (uc). (c — терминал или нетерминал; b, d — последовательности (может быть пустые) терминалов и нетерминалов). Других ситуаций вида A: b_d, с непустым b в V (uc) нет. Осталось добавить в V (uc) ситуации вида C:_…, для каждого нетерминала C, левый контекст которого содержит uc. Если ситуация A:…_C… (C-нетерминал) принадлежит множеству V (uc), то uc принадлежит L© и V (uc) включает в себя ситуации вида C:_… для всех C-правил грамматики.

V (e) содержит ситуации S:_… (S-начальный символ), а также ситуации A:_…, если нетерминал A встречается непосредственно после _ в ситуациях, уже включенных в V (e).

Наконец, мы готовы дать определение LR (0)-грамматики. Пусть u — содержимое стека в процессе LR-разбора, V (u)-множество LR (0) ситуаций, согласованных с u. Если V (u) содержит ситуацию вида А: x_ (x-последовательность терминалов и нетерминалов), то u принадлежит L (A:x) и допустима свертка x в A. Если V (u) содержит ситуацию A:…_a… (а-терминал), то допустим сдвиг. Говорят о конфликте сдвиг-свертка, если для одной цепочки u допустимы и сдвиг, и свертка. Говорят о конфликте свертка-свертка, если допустимы свертки по различным правилам.

Грамматика называется LR (0), если для всех состояний стека в процессе LR-вывода нет конфликтов сдвиг-свертка или свертка-свертка.

1.2.1.2 LR (k) — грамматики

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

Будем включать в левый контекст правила также аванцепочку. Если в правом выводе применяется вывод wAu: wvu, то пара wv, FIRSTk (u) принадлежит Lk (A:v), а пара w, FIRSTk (u) — Lk (A). Множество левых контекстов, как и в случае LR (0), можно вычислять с помощью индукции по левой цепочке. Назовем LR (k)-ситуацией пару: правило грамматики с отмеченной позицией и аванцепочку длины не более k. Отделять правило от аванцепочки будем вертикальной чертой.

Будем говорить, что цепочка x согласована с ситуацией А: b_c|t если существует LR-вывод: x_yz = ab_yz: abc_z: aA_z: S_, и FIRSTk (z)=t. Правила индуктивного вычисления множества состояний Vk следующие:

Vk (e) содержит ситуации S:_a|e для всех правил S: a, где S-начальный символ. Для каждой ситуации А:_Ba|u из Vk (e), каждого правила B: b и цепочки x, принадлежащей FIRSTk (au), надо добавить в Vk (e) ситуацию B:_b|x.

Если в Vк (w) входит ситуация A: b_cd|u, то ситуация A: bc_d|u будет принадлежать Vk (wc). Для каждой ситуации А: b_Cd|u из Vk (wc), каждого правила C: f и цепочки x, принадлежащей FIRSTk (du) надо добавить в Vk (wc) ситуацию C:_f|x.

Используем построенные множества LR (k)-состояний для разрешения вопроса сдвиг-свертка. Пусть u — содержимое стека, а x — аванцепочка. Очевидно, что свертка по правилу A: b может быть проведена, если Vk (u) содержит ситуацию A: b_|x. Решение вопроса о допустимости сдвига требует аккуратности, если в грамматике имеются e-правила. В ситуации A: b_c|t (c не пусто) сдвиг возможен, если c начинается с терминала и x принадлежит FIRSTk (ct). Неформально говоря, можно занести в стек самый левый символ правой части правила, подготавливая последующую свертку. Если c начинается с нетерминала (ситуация имеет вид A: b_Cd|t), то занести в стек символ, подготавливая свертку в C, можно только в случае, если C не порождает пустую цепочку. Например, в состоянии V (e)= S:_A|e; A:_AaAb|e, a, A:_|e, a нет допустимых сдвигов, т.к. при выводе из A терминальных цепочек на некотором шаге требуется применить правило A: e к нетерминалу A, находящемуся на левом конце цепочки.

Определим множество EFFk (x), состоящее из всех элементов множества FIRSTk (x), при выводе которых нетерминал на левом конце x (если он есть) не заменяется на пустую цепочку. В этих терминах сдвиг допустим, если в множестве Vk (u) есть ситуация А: b_c|t, c не пусто и x принадлежит EFFk (ct).

Грамматика называется LR (k)-грамматикой, если ни одно LR (k) состояние не содержит двух ситуаций A: b_|u и B: c_d|v, таких что u принадлежит EFFk (dv). Такая пара соответствует конфликту свертка-свертка, если d пусто, и конфликту сдвиг-свертка, если d не пусто.

На практике LR (k)-грамматики при k>1 не применяются. На это имеются две причины. Первая: очень большое число LR (k) состояний. Вторая: для любого языка, определяемого LR (k)-грамматикой, существует LR (1)-грамматика; более того, для любого детерминированного КС-языка существует LR (1)-грамматика.

Число LR (1)-состояний для практически интересных грамматик также весьма велико. LR (0) свойством такие грамматики обладают редко. На практике чаще используется промежуточный между LR (0) и LR (1) метод, известный под названиями и LALR (1).

1.2.2 LALR (1) — грамматики

В основе этих двух методов лежит одна и та же идея. Построим множество канонических LR (0)-состояний грамматики. Если это множество не содержит конфликтов, то можно применить LR (0)-парсер. Иначе попытаемся разрешить возникшие конфликты, рассматривая односимвольную аванцепочку. Другими словами, попробуем построить LR (1) парсер с множеством LR (0)-состояний.

LALR (1)-метод (Look Ahead — заглядывание вперед) заключается в следующем. Введем на множестве LR (1)-ситуаций отношение эквивалентности: будем считать две ситуации эквивалентными, если они различаются только аванцепочками. Например, ситуации A: Aa_Ab|e и A: Aa_Ab|a эквивалентны. Построим каноническое множество LR (1)-состояний и объединим состояния, состоящие из множества эквивалентных ситуаций.

Если полученное множество состояний не содержит LR (1) конфликтов, и, следовательно, позволяет построить LR (1)-парсер, то говорят, что грамматика обладает свойством LALR (1).

2. Разработка транслятора

2.1 Анализ требований

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

— проектирование лексического анализатора;

— проектирование магазинного автомата;

— программная реализация синтаксического анализатора;

— разработка модуля интерпретации.

Разработка будет проведена с использованием операционной системы Windows XP на персональном компьютере IBM PC с процессором Intel Pentium IV.

Исходя из тенденций развития программного обеспечения для реализации учебного транслятора выбран язык программирования С# в среде Visual Studio 2010.

2.2 Проектирование

2.1.1 Проектирование лексического анализатора

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

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

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

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

Просмотр таблицы идентификаторов выполняет две основные функции:

а) запись нового имени в таблицу при обработке описания переменных;

б) поиск имени, ранее записанного в таблицу.

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

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

Запуская лексический анализатор, мы разбиваем нашу программу на лексемы, после чего каждая лексемы проходит проверку длины (лексема не может быть больше 11 символов). Пройдя успешно этот этап, мы проверяем правильность расположения лексем (ключевых слов var, begin, end, for, to, do, end_for). Затем анализируем лексемы переменные — они не должны содержать цифр в своем описании и повторяться. На последнем этапе проверяем правильность написания лексем (ключевые слова, неизвестные идентификаторы). Если хотя бы одна из проверок выдает ошибку, лексический анализатор выводит ошибку.

Схема программы работы лексического анализатора приведена в приложении B на рисунке В.1.

2.2.2 Проектирование магазинного автомата Зададим следующую грамматику:

Г: {Vt, Va, I, R},

где Vt — это множесто терминальных символов, Va — множество нетерминальных символов, I — начальное состояние грамматики, R — множество правил грамматики.

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

Составим правила для нашей грамматики Г и приведем их в таблице 1.

Таблица 1 — Правила грамматики

Обозначения лексем, перевод лексем в коды и список обозначений грамматики приведем в таблицах 2, 3, 4 соответственно.

Таблица 2 — Обозначения лексем

Таблица 3 — Перевод лексем в коды

Таблица 4 — Список обозначений грамматики

Построим детерменированный восходящий распознаватель.

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

а)Если имеется символ группы В такой, что в некоторое правило грамматики входит цепочка АВ и существует символ хПЕРВ'(В), то будем считать, что между символами х и, А определяются отношения х ПОСЛЕ, А б) Если в заданной грамматике имеетя правило В->бАб А, ВV_a, б то между, А и х определяется отношение, А СВЕРТ х.

Вся наша грамматика остается прежней, то есть:

Г: {Vt, Va, I, R},

а правила грамматики Г приведены в таблице 5.

Таблица 5 — Правила грамматики

Где? — маркер конца цепочки.

Определим некоторые случаи:

а)Идентификатор ID состоит из множества букв латинского алфавита, то есть будем считать, что u = { a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z}

б) Константа СО состоит из цифр, то есть будем считать, что k = {0,1,2,3,4,5,6,7,8,9}

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

а) Отсутствие е — правил б) Имеются правила при которых, х ПОСЛЕ, А? А СВЕРТ х = ?

в) А -> бYг

B->г

и необходимо, чтобы В ПОСЛЕ х? В СВЕРТ х = ?

г) А ->б

B -> б

т.е в грамматике будут выполняться В ПОСЛЕ х либо, А ПОСЛЕ х, где х — символпредикат цепочки б.

а) ПЕРВ'(PG)={PG?}

ПЕРВ'(RG) = ПЕРВ (DE) = {RG, v, i,;}

ПЕРВ' (AL) = ПЕРВ (b LE e)= {AL, b, e}

ПЕРВ' (DE) = ПЕРВ (v LV: i;) = {DE, v, i,;}

ПЕРВ' (LV) = ПЕРВ (ID, LV) = { LV, ID }

ПЕРВ' (OP) ={OP, ID, CO}

ПЕРВ' (EQ) = ПЕРВ (ID = EX;) = {EQ, =,;}

ПЕРВ' (EX) = {EX, SB, -}

ПЕРВ' (BO) ={B0, +,*,-}

ПЕРВ' (SB) =ПЕРВ ((EX)SB)? ПЕРВ (OP)? ПЕРВ (ВО)={SB, (,), OP, BO};

ПЕРВ' (LE) = ПЕРВ (EQ) = {LE, (,), =,;, f, t, d, n, w, r}

ПЕРВ' (UO) = {UO,-}

ПЕРВ' (ID)= ПЕРВ' (u) = {u}

ПЕРВ' (CO) = ПЕРВ' (k) = {k}ПЕРВ' (e) ={ e}

ПЕРВ' (b) ={ b}

ПЕРВ' (e) ={ e}

ПЕРВ' (v) ={ v}

ПЕРВ' (w) ={ w}

ПЕРВ' ® ={ r}

ПЕРВ' (i) ={ i}

ПЕРВ' (f) ={ f}

ПЕРВ' (d) ={d}

ПЕРВ' (n) ={ n}

ПЕРВ' © ={ c}

ПЕРВ' (+) ={ +}

ПЕРВ' (*) ={ *}

ПЕРВ' (-) ={ -}

ПЕРВ' (,) ={,}

ПЕРВ' (;) ={;}

ПЕРВ' (:) ={:}

ПЕРВ' (=) = { = }

ПЕРВ' (() ={ (}

ПЕРВ' ()) ={) }

ПЕРВ' (u) ={u}

ПЕРВ' (k) ={k}

б) СЛЕД `(AL) = {?}?СЛЕД'(PG)={?, b, e}

СЛЕД ` (DE) = {?}?ПЕРВ'(AL)= {?, b, e }

СЛЕД ` (LV) = {?}?ПЕРВ'(:)= {?:}

СЛЕД ` (OP) = {?}?ПЕРВ'(SB)= {?,;,), d, t, +, -, *}

СЛЕД ` (EQ) = {?}?ПЕРВ'(LE)={?, (,),;, f, =, t, d, n, w, r }

СЛЕД ` (EX) = {?}?ПЕРВ'(t)?ПЕРВ'(d)?ПЕРВ'(;)?ПЕРВ'())={?, t, d,;,)}

СЛЕД ` (BO) = {?}?ПЕРВ'(SB)= {?, (,), OP, BO}

СЛЕД ` (UO) = {?}?ПЕРВ'(SB)= {?, (,), OP, BO}

СЛЕД ` (SB) = {?}?СЛЕД'(EX)= {?, t, d,;,), +, *, -}

СЛЕД ` (LE) = {?} ?ПЕРВ'(e) ?ПЕРВ'(n) = {?, e, n}

СЛЕД `(ID)= {?}? СЛЕД' (OP)? ПЕРВ' (=) ={?,;,), d, t, +, -, *, =}

СЛЕД `(CO) = {?}? СЛЕД' (OP)= {?,;,), d, t, +, -, *, =}

СЛЕД ` (b) ={?}?ПЕРВ'(LE)= {?, u, =,;}

СЛЕД ` (e) ={?}?СЛЕД'(AL)= {?, b}

СЛЕД ` (v) ={?}?ПЕРВ'(LV)= {?, u }

СЛЕД ` (w) ={?}?ПЕРВ'(()= {?, (}

СЛЕД ` ® ={?}?ПЕРВ'(() = {?, (}

СЛЕД ` (i) ={?}?ПЕРВ'(;)= {?,; }

СЛЕД ` (f) ={?}?ПЕРВ'(ID) = {?, u}

СЛЕД ` (d) ={?}?ПЕРВ'(LE)= {?, u, =,;}

СЛЕД ` (n) ={?}?ПЕРВ'(i) = {?, i }

СЛЕД ` (+) ={?}?СЛЕД'(ВО) = {?, +,*,-}

СЛЕД ` (-) ={?}?СЛЕД'(ВО) = {?, +,*,-}

СЛЕД ` (*) ={?}?СЛЕД'(ВО) = {?, +,*,-}

СЛЕД ` (;) ={?}?СЛЕД' (DE)?СЛЕД `(LE1)?СЛЕД' (EQ) = {?, b, e, l, u }

СЛЕД ` (:) ={?}?ПЕРВ'(i)= {?, i }

СЛЕД ` (=) = {?}?ПЕРВ'(EX) = {? (,), u, k, +, -, *}

СЛЕД ` (() ={?}?ПЕРВ'(DE)= {?, v, i,;}

СЛЕД ` ()) ={?}? ПЕРВ'(;) = {?,; }

СЛЕД ` (,) ={?}? ПЕРВ'(LV) = {?, u }

СЛЕД `(u) ={?}? ПЕРВ' (ID)= { u, ?}

СЛЕД `(k) ={?}? ПЕРВ (CO)= {?, k}

в) PG ->DE AL

AL ПОСЛЕ DE = {b, e} ПОСЛЕ DE = {(b DE), (e DE) }

AL -> b LE e

e ПОСЛЕ LE = {(e LE)}

LE ПОСЛЕ b = {(,), =,;, f, t, d, n, w, r} ПОСЛЕ b = {((b), ()b), (=b), (;b), (f b), (t b), (d b), (n b), (w b), (r b)}

;ПОСЛЕ i = {(; i)}

i ПОСЛЕ: = { (i:) }

: ПОСЛЕ LV = { (: LV) }

LV ПОСЛЕ v = { (ID, v) }

LV ПОСЛЕ, = {(ID,)}

ПОСЛЕ ID = {(, u)}

LE-> EQ LE

LE ПОСЛЕ EQ = {(,), =,;, f, t, d, n, w, r } ПОСЛЕ EQ = {((EQ), () EQ), (= EQ), (; EQ), (f EQ), (t EQ), (d EQ), (n EQ), (w EQ), (r EQ)}

LE -> r (DE);

; ПОСЛЕ) = {(;))}

) ПОСЛЕ DE = {((DE)}

DE ПОСЛЕ (= (= {(v)), (:)), (i)), (;)), (e))}

(ПОСЛЕ r = {(®}

LE -> w (DE);

; ПОСЛЕ) = {(;))}

) ПОСЛ DE = {((DE)}

DE ПОСЛЕ (= {(v)), (:)), (i)), (;)), (e))}

(ПОСЛЕ w = {((w)}

LE -> f ID = EX t EX d LE n;

; ПОСЛЕ n = {(;n)}

n ПОСЛЕ LE = { (n, LE)}

LE ПОСЛЕ d = { ((,), =,;, f, t, d, n, w, r)}? ПОСЛЕ d = {((d), ()d), (;d), (f d), (t d), (d d), (n d), (w d), (r d)}

d ПОСЛЕ EX = {(d, EX)}

EX ПОСЛЕ t = (BO, -)? ПОСЛЕ t = {(BO t), (- t)}

t ПОСЛЕ EX = { t EX}

EX ПОСЛЕ = = {(BO, -)? ПОСЛЕ = = {(BO =), (- =)}

= ПОСЛЕ ID = {(= ID)}

ID ПОСЛЕ f = {(ID f)}

EQ -> ID = EX;

; ПОСЛЕ EX = {(; EX }

EX ПОСЛЕ = = (BO, -)? ПОСЛЕ = = {(BO =), (- =)}

= ПОСЛЕ u = { (=u)}

EX -> UO SB

SB ПОСЛЕ UO = { (,), OP, BO } ПОСЛЕ UO = {((UO), (OP UO), (BO UO) }

SB->(EX)

) ПОСЛЕ EX = { ()EX) }

EX ПОСЛЕ (= (BO, -)? ПОСЛЕ (= {(BO (), (- ()}

SB-> SB BO SB

SB ПОСЛЕ BO = ((,), OP, BO) ПОСЛЕ BO = {((BO), ()BO), (OP BO), (BO BO)}

BO ПОСЛЕ SB = {+,*,-} ПОСЛЕ SB = {(+SB), (*SB), (-SB)}

ID -> u ID

ID ПОСЛЕ u = {(u, u)}

г) PG ->DE AL

AL СВЕРТ PG = AL СВЕРТ СЛЕД' (PG) = {(AL ?)}

AL -> b LE e

e СВЕРТ AL = e СВЕРТ СЛЕД'(AL)= {(eb), (e?)}

=; СВЕРТ СЛЕД'(DE) = {(;b), (;?)}

LV СВЕРТ LV = LV СВЕРТ СЛЕД' (LV) = {(LV:), (LV?)}

ID СВЕРТ LV = ID СВЕРТ СЛЕД' (LV) = {(ID:), (ID ?)}

LE-> w (DE);

; СВЕРТ LE =; СВЕРТ СЛЕД' (LE) = {(; e), (;?), (;n)}

LE-> r (DE);

; СВЕРТ LE =; СВЕРТ СЛЕД' (LE) = {(; e), (;?), (;n)}

LE -> f ID = EX t EX d LE n;

; СВЕРТ LE =; СВЕРТ СЛЕД' (LE) = {(; e), (;?), (;n)}

LE -> EQ

EQ СВЕРТ LE = EQ СВЕРТ СЛЕД' (LE) = {(EQ e), (EQ?), (EQ n)}

EQ -> ID = EX;

; СВЕРТ EQ =; СВЕРТ СЛЕД' (EQ) = {(; (), (;)), (;;), (;f), (;?), (;=), (;t), (;d), (;n), (;w), (;r)}

EX ->SB

SB СВЕРТ EX = SB СВЕРТ СЛЕД' (EX) = {(SB t), (SB?), (SB d), (SB)), (SB;), (SB (), (SB=), (SBf), (SBn), (SBw), (SBr) }

EX — >

SB СВЕРТ EX = SB СВЕРТ СЛЕД' (EX) = {(SB t), (SB?), (SB d), (SB)), (SB;), (SB (), (SB=), (SBf), (SBn), (SBw), (SBr) }

SB ->(EX)

) СВЕРТ SB = SB СВЕРТ СЛЕД' (SB) = {() t), ()?), () d), ())), ();)}

SB -> OP

OP СВЕРТ SB = OP СВЕРТ СЛЕД' (SB) = {(OP t), (OP ?), (OP d), (OP)), (OP;)}

SB-> SB BO SB

SB СВЕРТ SB = SB СВЕРТ СЛЕД' (SB) = {(SB, t), (SBd), (SB;). (SB)), (SB+), (SB-), (SB*), (SB?) }

UO -> ;

— СВЕРТ UO = - СВЕРТ СЛЕД' (UO) = { (-?), (—)}

BO -> +

+ СВЕРТ BO = + СВЕРТ СЛЕД' (BO) = {(++), (+?), (+*), (±)}

BO-> *

* СВЕРТ BO = * СВЕРТ СЛЕД' (BO) = {(*+), (*?), (**), (*-)}

BO -> ;

— СВЕРТ BO = - СВЕРТ СЛЕД' (BO) = {(-+), (-?), (-*), (—)}

OP ->ID

ID СВЕРТ OP = ID СВЕРТ СЛЕД' (OP) = {(ID+), (ID?), (ID*), (ID-)}

OP->CO

CO СВЕРТ OP = CO СВЕРТ СЛЕД' (OP) = {(CO+), (CO?), (CO*), (CO-), (CO;), (COd), (COt), (CO))}

ID -> u ID

ID СВЕРТ ID = ID СВЕРТ СЛЕД' (ID) = {(ID)), (ID ?), (ID k), (ID+), (ID-), (ID*), (ID=), (IDt), (IDd))}

ID->u

u СВЕРТ ID = l СВЕРТ СЛЕД' (ID) = {(u)), (u?), (uk), (u+), (u-), (u*), (u=), (ut), (ud))}

CO -> k CO

CO СВЕРТ CO = CO СВЕРТ СЛЕД' (CO) = (CO+), (CO?), (CO*), (CO-), (CO;), (COd), (COt), (CO))}

CO -> k

k СВЕРТ CO = k СВЕРТ СЛЕД' (CO) = (k+), (k?), (k*), (k-), (k;), (kd), (kt), (k))}

Обнаружена одна конфликтная ситуация при сворачивании правил

OP ->ID и ID -> u ID

Вводим ID1 -> ID, следовательно переписываем правило ID1 -> u ID

Следовательно, проведем операции свертка.

ID1 -> u ID

ID1 СВЕРТ ID = ID1 СВЕРТ СЛЕД' (ID) = {(ID1)), (ID1 ?), (ID1 k), (ID1+), (ID1-), (ID1*), (ID1=), (ID1t), (ID1d))}

Для каждой пары (х, А)? х ПОСЛЕ, А строим функцию перехода, определяющее действие перенос ??(S₀, x, A) = (S₀, A)

? (S0, b, DE) = (S0, DEb)

? (S0, e, DE) = (S0, DEe)

? (S0, e, LE) = (S0, LEe)

? (S0,), b) = (S0, b))

? (S0,;, b) = (S0, b;)

? (S0, (, b) = (S0, b ()

? (S0, =, b) = (S0, b=)

? (S0, f, b) = (S0, bf)

? (S0, t, b) = (S0, bt)

? (S0, d, b) = (S0, bd)

? (S0, n, b) = (S0, bn)

? (S0, w, b) = (S0, bw)

? (S0, r, b) = (S0, br)

? (S0,;, i) = (S0, i;)

? (S0, i:) = (S0, i:)

? (S0: LV) = (S0, LV:)

? (S0, ID, v) = (S0, vID)

? (S0, ID,) = (S0,ID)

? (S0, u) = (S0, u,)

? (S0, (, EQ)= (S0, EQ ()

? (S0,), EQ)= (S0, EQ))

? (S0, =, EQ)= (S0, EQ=)

? (S0,;, EQ)= (S0, EQ;)

? (S0, f, EQ)= (S0, EQf)

? (S0, t, EQ)= (S0, EQt)

? (S0, d, EQ)= (S0, EQd)

? (S0, n, EQ)= (S0, EQn)

? (S0, w, EQ)= (S0, EQw)

? (S0, r, EQ)= (S0, EQr)

? (S0,;,)) = (S0,);)

? (S0, (, DE) = (S0, DE ()

? (S0, v,)) = (S0,)v)

? (S0,;,)) = (S0,);)

? (S0, i,)) = (S0,)i)

? (S0,)) = (S0,):)

? (S0, e,)) = (S0,)e)

? (S0, (, r) = (S0, r ()

? (S0, (, w) = (S0, w ()

? (S0,;, n) = (S0, n;)

? (S0, n, LE) = (S0, LEn)

? (S0, (, d) = (S0, d ()

? (S0,), d) = (S0, d))

? (S0,;, d) = (S0, d;)

? (S0, f, d) = (S0, df)

? (S0, t, d) = (S0, dt)

? (S0, d, d) = (S0, dd)

? (S0, n, d) = (S0, dn)

? (S0, w, d) = (S0, dw)

? (S0, r, d) = (S0, dr)

? (S0, d, EX) = (S0, EXd)

? (S0, BO, t) = (S0, tBO)

? (S0, -, t) = (S0, t-)

? (S0, t, EX) = (S0, EXt)

? (S0, BO, =) = (S0, =BO)

? (S0, -, =) = (S0, =-)

? (S0, =, ID) = (S0, ID=)

? (S0, ID, f) = (S0, fID)

? (S0,;, EX) = (S0, EX;)

? (S0, =, u) = (S0, u=)

? (S0, (, UO) = (S0, UO ()

? (S0, OP, UO) = (S0, UO OP)

? (S0, BO, UO) = (S0, UO BO)

? (S0,), EX) = (S0, EX))

? (S0, BO, () = (S0, (BO)

? (S0, BO, -) = (S0, -BO)

? (S0, (, BO) = (S0, BO ()

? (S0,), BO) = (S0,)BO)

? (S0, OP, BO) = (S0, BOOP)

? (S0, +, SB) = (S0, SB+)

? (S0, *, SB) = (S0, SB*)

? (S0, -, SB) = (S0, SB-)

? (S0, u, u) = (S0, uu)

Для каждой пары (х, А)? А СВЕРТ х строим функцию перехода, определяющее действие свертка ??^*(S₀, x, бA) = (S₀, В), где В->бA

?^*(S₀, AL, ?) = (S₀, PG)

?^*(S₀, e, b) = (S₀, AL)

?^*(S₀, n, ?) = (S₀, AL)

?^*(S₀,;, b) = (S₀, DE)

?^*(S₀,;, ?) = (S₀, DE)

?^*(S₀,;, e) = (S₀, DE)

?^*(S₀, LV:) = (S₀, LV)

?^*(S₀, LV, ?) = (S₀, LV)

?^*(S₀, ID, ?) = (S₀, LV)

?^*(S₀, ID, e) = (S₀, LV)

?^*(S₀,;, e) = (S₀, LE)

?^*(S₀,;, ?) = (S₀, LE)

?^*(S₀,;, n) = (S₀, LE)

?^*(S₀, EQ, n) = (S₀, LE)

?^*(S₀, EQ, e) = (S₀, LE)

?^*(S₀, EQ, ?) = (S₀, LE)

?^*(S₀,;, e) = (S₀, LE)

?^*(S₀,;, ?) = (S₀, LE)

?^*(S₀,;, () = (S₀, EQ)

?^*(S₀,;,)) = (S₀, EQ)

?^*(S₀,;, f) = (S₀, EQ)

?^*(S₀,;, =) = (S₀, EQ)

?^*(S₀,;, t) = (S₀, EQ)

?^*(S₀,;, d) = (S₀, EQ)

?^*(S₀,;, n) = (S₀, EQ)

?^*(S₀,;, w) = (S₀, EQ)

?^*(S₀,;, r) = (S₀, EQ)

?^*(S₀, SB, t) = (S₀, EX)

?^*(S₀, SB, ?) = (S₀, EX)

?^*(S₀, SB, d) = (S₀, EX)

?^*(S₀, SB,)) = (S₀, EX)

?^*(S₀, SB,;) = (S₀, EX)

?^*(S₀, SB, w) = (S₀, EX)

?^*(S₀, SB, r) = (S₀, EX)

?^*(S₀, SB, f) = (S₀, EX)

?^*(S₀, SB, =) = (S₀, EX)

?^*(S₀, SB, t) = (S₀, EX)

?^*(S₀, SB, ?) = (S₀, SB)

?^*(S₀, SB, () = (S₀, SB)

?^*(S₀, SB,)) = (S₀, SB)

?^*(S₀, SB, u) = (S₀, SB)

?^*(S₀, SB, k) = (S₀, SB)

?^*(S₀, SB, +) = (S₀, SB)

?^*(S₀, SB, -) = (S₀, SB)

?^*(S₀, SB, *) = (S₀, SB)

?^*(S₀, SB, e) = (S₀, SB)

?^*(S₀,), t) = (S₀, SB)

?^*(S₀,), ?) = (S₀, SB)

?^*(S₀,), t) = (S₀, SB)

(S₀,),)) = (S₀, SB)

?^*(S₀,),;) = (S₀, SB)

?^*(S₀, -, ?) = (S₀, UO)

?^*(S₀, -, -) = (S₀, UO)

?^*(S₀, +, +) = (S₀, BO)

?^*(S₀, +, ?) = (S₀, BO)

?^*(S₀, +, *) = (S₀, BO)

?^*(S₀, -, -)) = (S₀, BO)

?^*(S₀, -, +) = (S₀, BO)

?^*(S₀, -, ?) = (S₀, BO)

?^*(S₀, -, *) = (S₀, BO)

?^*(S₀, -, -)) = (S₀, BO)

?^*(S₀, *, +) = (S₀, BO)

?^*(S₀, *, ?) = (S₀, BO)

?^*(S₀, *, *) = (S₀, BO)

?^*(S₀, *, -)) = (S₀, BO)

?^*(S₀, u, +) = (S₀, BO)

?^*(S₀, u, ?)= (S₀, BO)

?^*(S₀, u, *) = (S₀, BO)

?^*(S₀, u, -)) = (S₀, BO)

?^*(S₀, k, +) = (S₀, BO)

?^*(S₀, k, ?) = (S₀, BO)

?^*(S₀, k, *) = (S₀, BO)

?^*(S₀, k, -)) = (S₀, BO)

?^*(S₀, ID, ?) = (S₀, OP)

?^*(S₀, ID, +) = (S₀, OP)

?^*(S₀, ID, *) = (S₀, OP)

?^*(S₀, ID, -) = (S₀, OP)

?^*(S₀, CO, ?) = (S₀, OP)

?^*(S₀, CO, +) = (S₀, OP)

?^*(S₀, CO, *) = (S₀, OP)

?^*(S₀, CO, -) = (S₀, OP)

?^*(S₀, CO,;) = (S₀, OP)

?^*(S₀, CO, d) = (S₀, OP)

?^*(S₀, CO, t) = (S₀, OP)

?^*(S₀, ID, -) = (S₀, OP)

?^*(S₀, ID, *) = (S₀, OP)

?^*(S₀, ID, ?) = (S₀, OP)

?^*(S₀, ID, () = (S₀, OP)

?^*(S₀, ID,)) = (S₀, OP)

?^*(S₀, ID, u) = (S₀, OP)

?^*(S₀, ID, k) = (S₀, OP)

?^*(S₀, ID, -) = (S₀, OP)

?^*(S₀, ID, +) = (S₀, OP)

?^*(S₀, u,)) = (S₀, I OP)

?^*(S₀, ID1, *) = (S₀, ID)

?^*(S₀, ID1, ?) = (S₀, ID)

?^*(S₀, ID1, () = (S₀, ID)

?^*(S₀, ID1,)) = (S₀, ID)

?^*(S₀, ID1, u) = (S₀, ID)

?^*(S₀, ID1, k) = (S₀, ID)

?^*(S₀, ID1, -) = (S₀, ID)

?^*(S₀, ID1, +) = (S₀, ID)

?^*(S₀, u,)) = (S₀, ID)

?^*(S₀, u, ?) = (S₀, BO)

?^*(S₀, u, k) = (S₀, ID)

?^*(S₀, u, *)) = (S₀, ID)

?^*(S₀, u, -)) = (S₀, ID)

?^*(S₀, u, +)) = (S₀, ID)

?^*(S₀, u, d)) = (S₀, ID)

?^*(S₀, u, t)) = (S₀, ID)

?^*(S₀, u, =)) = (S₀, ID)

?^*(S₀, CO, ?) = (S₀, CO)

?^*(S₀, CO, +) = (S₀, CO)

?^*(S₀, CO, -) = (S₀, CO)

?^*(S₀, CO, *) = (S₀, CO)

?^*(S₀, CO,;) = (S₀, CO)

?^*(S₀, CO, d) = (S₀, CO)

?^*(S₀, CO, t) = (S₀, CO)

?^*(S₀, CO,)) = (S₀, CO)

?^*(S₀, k, +) = (S₀, CO)

?^*(S₀, k, -) = (S₀, CO)

?^*(S₀, k, *) = (S₀, CO)

?^*(S₀, k,;) = (S₀, CO)

??^*(S₀, k, d) = (S₀, CO)

?^*(S₀, k, t) = (S₀, CO)

?^*(S₀, k,)) = (S₀, CO)

?^*(S₀, k, () = (S₀, CO)

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

Для восходящего грамматического разбора для детерминированного восходящего распознавателя после приведения ее к нужному виду требуется с использованием функций ПОСЛЕ и СВЕРТ спроектировать магазинный автомат с подробным описанием всех переходов в рамках функции переходов.

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

— такт работы магазинного автомата без чтения входного символа (пустой такт);

— такт работы магазинного автомата с чтением входного символа.

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

Схема программы работы синтаксического анализатора приведена в приложении B на рисунке В.2.

2.2.4 Разработка модуля интерпретации

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

Рассмотрим основные принципы формирования и выполнения постфиксной формы записи выражений.

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

Считанные операнды добавляются к постфиксной записи, операции записываются в стек.

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

Считанная открывающая скобка заносится в стек.

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

После считывания всего выражения, оставшиеся в стеке операции добавляются к постфиксной записи.

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

Если лексема является операндом, то она записывается в стек. Если лексема является операцией, то указанная операция выполняется над последними элементами (последним элементом), записанными в стек, и эти элементы (элемент) заменяются в стеке результатом операции.

Если успешно прошли лексический и синтаксический анализы, то мы приступаем к интерпретации. Сначала делаем из слов предложения, затем переводим выражения в постфиксную запись и вычисляем.

Схема работы интерпретатора приведена в приложении B на рисунке В.3.

2.3 Кодирование Программа реализована на языке C# в среде программирования Visual Studio 2010. Текст программы представлен в приложении А.

В программе реализованно пять классов. С помощью класса MainForn реальзован пользовательский интерфейс. C помощью класса LexAnalysis реализован модуль лексического анализа, SynAnalysis — модуль синтаксического анализа, Intepreter — модуль интерпретации, ProgramisciJakPolska — вспомогательный класс перевода выражений в обратную польскую запись (постфиксную).

Назначение процедур и функций, реализованных в программе, описано в таблицах 6,7,8.

Таблица 6 — Назначение процедур и функций лексического анализа