Студопедия  
Главная страница | Контакты | Случайная страница

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Постановка задачи. Синтаксический анализатор

Читайте также:
  1. E) задачи на вычисление боковой поверхности геометрических фигур
  2. E)задачина вычисление боковой поверхности геометрических фигур 1 страница
  3. E)задачина вычисление боковой поверхности геометрических фигур 2 страница
  4. E)задачина вычисление боковой поверхности геометрических фигур 3 страница
  5. E)задачина вычисление боковой поверхности геометрических фигур 4 страница
  6. I Задачи научно-исследовательской деятельности учащихся.
  7. I Цели и задачи изучения дисциплины
  8. I этап. Постановка задачи
  9. I. Диагностика: понятие, цели, задачи, требования, параметры
  10. I. ЗАДАЧИ ДЛЯ САМОСТОЯТЕЛЬНОГО РЕШЕНИЯ

Техническое задание

Название

Синтаксический анализатор. Метод простого предшествования.

Функциональные характеристики

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

Пользовательский интерфейс – консоль Windows.

Язык реализации – С++.

Программа должна быть простой и удобной в использовании;

Входная информация: символьная строка по образцу

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

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

Структура входных и выходных данных

Входные данные – строка символов (вводится из файла); выходные данные – матрица простого предшествования и последовательность редукций основ. (выводится в файл).

Требования к среде разработки

Требование к аппаратной части

1. ЭВМ с архитектурой IBM PC;

2. Процессор Pentium 600 и выше;

3. Не менее 256 Мб оперативной памяти;

4. 200 Mб свободного места на логическом диске.

Требование к программной части

1. Операционная система Microsoft Windows XP, Windows 7;

2. Среда разработки Microsoft Visual Studio 2010.

Постановка задачи

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

Этот метод основан на том, что между двумя соседними символами Si и Si+1 приводимой строки могут существовать только три отношения:

1. Si <. Si+1 - отношение верно, если символ Si+1 - самый левый символ некоторой основы.

2. Si. > Si+1 - отношение верно, когда Si - символ, являющийся самым правым в некоторой основе.

3. Si.= Si+1 - верно, если Si и Si+1 принадлежат одной основе.

Отношения <., .>, .= называются отношениями предшествования.

Отношения предшествования являются отношениями, которые зависят от порядка следования символов Si и Si+1.

Если имеется отношение Si.> Si+1 - это не означает, что Si+1 <. Si. Или, если выполняется отношение Si.= Si+1, то это не означает, что выполняется Si+1.= Si.

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

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

# <· S1 <· S2 ·= S3 ·= S4 ·> S5 ·= S6 ·> #

Символы S2, S3, S4 составляют основу, тогда по определению должно существовать правило U1::= S2S3S4. Следовательно, можно произвести редукцию входной строки. Она примет вид:

# <· S1 ·= U1 ·> S5 ·= S6 ·> #

Здесь основой являются S1 и U1, следовательно, должно существовать правило U2 ::= S1 U1:

# <· U2 ·= S5 ·= S6 ·> #

Продолжив процесс, в итоге получим:

# U3 #,

и, если существует правило <начальный символ>::= # U3 #, то прямая редукция приводит к завершению разбора предложения.

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

Z::=#E

E::=T+E|T

T::=F*T|F

F::=(E)|id

 

Данная грамматика не является грамматикой простого предшествования, так как между некоторыми символами существует неоднозначные отношения. В данном случае неоднозначность отношений предшествования вытекает из того, что, например, символы (и Е встречаются рядом в правой части правила, а, с другой стороны, Е принадлежит L(E), то есть множество L(E) рекурсивно для символа Е.

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

Z::=#E

E::=E+P|P

P::=T

T::=F*T|F

F::=(Z)|id

Таким образом, грамматика будет выглядеть следующим образом:

Grammar="$Z=E|$E=E+P|P|$P=T|$T=T*F|F|$F=(Z)|i|$";

Построим матрицу предшествования для данной грамматики:

 

  Z E # + P T * F ( ) id
Z . . > . . . . . . = .
  . . > = . . . . . > .
E < < > < < < < < < < <
+ . . > . = < . < < . <
P . . > > . . . . . > .
T . . > > . . = . . > .
* . . > . . . . = < . <
F . . > > . . > . . > .
( = < > . < < . < < . <
) . . > > .   > . . > .
id . . > > . . > . . > .

.

= – отношение(1) ·=; < – отношение(2) ·; > – отношение(3) ·>




Дата добавления: 2015-01-12; просмотров: 15 | Поможем написать вашу работу | Нарушение авторских прав

<== предыдущая лекция | следующая лекция ==>
Изменение балльности на Санкт-Петербург Финляндской дистанции пути.| Термины и определения

lektsii.net - Лекции.Нет - 2014-2024 год. (0.008 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав