русс | укр

Языки программирования

ПаскальСиАссемблерJavaMatlabPhpHtmlJavaScriptCSSC#DelphiТурбо Пролог

Компьютерные сетиСистемное программное обеспечениеИнформационные технологииПрограммирование

Все о программировании


Linux Unix Алгоритмические языки Аналоговые и гибридные вычислительные устройства Архитектура микроконтроллеров Введение в разработку распределенных информационных систем Введение в численные методы Дискретная математика Информационное обслуживание пользователей Информация и моделирование в управлении производством Компьютерная графика Математическое и компьютерное моделирование Моделирование Нейрокомпьютеры Проектирование программ диагностики компьютерных систем и сетей Проектирование системных программ Системы счисления Теория статистики Теория оптимизации Уроки AutoCAD 3D Уроки базы данных Access Уроки Orcad Цифровые автоматы Шпаргалки по компьютеру Шпаргалки по программированию Экспертные системы Элементы теории информации

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

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

Формальной грамматики Г называется совокупность четырех объектов.

Va – нетерминальные символы.

R – правила грамматики. Вида: a ->b, где a принадлежим Va. В принадлежит Vt,Va.

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

Vt – терминальные символы (символы допускаемые языком. Для упрощения ключевые слова, будем считать одним терминальным символом.

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

Например:
Множество конечных цепочек выводимых изначального символа грамматики называется языком порождаемый данной грамматикой. И обозначается L(Г).

Знак доллара означает пусто($):R->$.

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

Например:

I-> iR | jR  --- это правило можно заменить на: I-> iR, I->jR
R ->; iR | ;jR | $
I->iR->I;iR->I,I,jR

Синтаксический разбор

1) I->TS;
2) T-> int | char | float
3) S-> ABCR
4) A->*|$
5) B->i|j
6) C->[]|$
7) R->,S|$

Каким образом будет выводится вывод такой строчки: int *i,j,i[];

I->TS; -> intS; -> int ABCR; ->int *BCR; -> int *iCR; -> int *iR; -> int *i,S; ->int *i,ABCR; ->
int *i, BCR; -> int *i,jCR; -> int *i,jR; -> int *i,j,ABCR; -> int *i,j,BCR; -> int *i,j,CR; ->
int *i,j,i[];.

[1, 2.1, 3, 4.1, 5.1, 6.2, 7.1…]

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

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

 

Составление правил грамматики

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

Пример 1:

main() { ………. }
main() { ………. }
То,
I -> mailA

Пример 2:

Если:

a = 10;
B = 10+ c;
D = e + k – 20;

То:

I -> A;

И так далее…

Повторение символов, называется списком. Пример: ааааааа….а.

Тогда:

I -> aR
R -> aR | $
Пример: a,a,a,a,a,a
I -> aR
R -> ,aR |$

Для построения правил грамматики необходимо:

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

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

123
2075
625310

Все цепочки начинаются от 1 до 9. И обозначим буквой А. Оставшийся список буквой R,

Правило:

1) I -> AR
2) A -> 1|2|3 .. |9
3) R -> AR | 0R | $

Проверим число 105:

I -> AR -> 1R -> 10R -> 10AR -> 105R -> 105

Пример 2:

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

1) I -> AR.BR
2) A -> 1|2|3| .. |9
3) B ->0|A
4) R ->AR | BR  | $

Пример 3: Составить правило грамматики для целых десятичных, восьмеричных и шестнадцатеричных чисел. Числа могут быть – и +.

105 - десятичное
0105 - восьмеричное
0х105 - шестнадцатеричное
-427 - десятичное                        
-055 - восьмеричное
-0хaf6 – шестнадцатеричное

Правило:

I -> AR | 0BR |0xCR
A -> 1|2|3| .. |9
B -> 1| 2| .. |7
C -> 1|2|3|..|9|A|B|C|D|E|F
R -> AR |BR| CR| $

 

Пример 4: Составить правило грамматики для описания целого и вещественного типа.

var a,b,a,b,a: integer;
var b,f:real;

Правило:

I -> var S:T;
S -> AR
R -> ,AR| $
A -> a| b
T -> integer | char

Просмотров: 3136

Вернуться в оглавление:Проектирование системных программ




Карта сайта Карта сайта укр


Уроки php mysql Программирование

Онлайн система счисления Калькулятор онлайн обычный Инженерный калькулятор онлайн Замена русских букв на английские для вебмастеров Замена русских букв на английские

Аппаратное и программное обеспечение Графика и компьютерная сфера Интегрированная геоинформационная система Интернет Компьютер Комплектующие компьютера Лекции Методы и средства измерений неэлектрических величин Обслуживание компьютерных и периферийных устройств Операционные системы Параллельное программирование Проектирование электронных средств Периферийные устройства Полезные ресурсы для программистов Программы для программистов Статьи для программистов Cтруктура и организация данных


 


Полезен материал? Поделись:

Не нашли то, что искали? Google вам в помощь!

 
 

© life-prog.ru При использовании материалов прямая ссылка на сайт обязательна.