Построение распознователя грамматик. Построение распознавателя для заданной грамматики и реализация е. Курсовая работа по дисциплине "Основы дискретной математики"

Название	Курсовая работа по дисциплине "Основы дискретной математики"
Анкор	Построение распознователя грамматик
Дата	28.04.2022
Размер	227 Kb.
Формат файла
Имя файла	Построение распознавателя для заданной грамматики и реализация е.doc
Тип	Курсовая #502707
страница	2 из 6

1 2 3 4 5 6

1. Теоретические основы разрабатываемой темы

1.1 Общие сведения о грамматиках

В расширенном представлении под термином "язык" понимают всякое средство общения, состоящее из:

- знаковой системы, т.е. множества допустимых последовательностей знаков;

- множества смыслов этой системы;

- соответствия между последовательностями знаков и смыслами, делающими осмысленными допустимые последовательности знаков.

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

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

Пусть задан алфавит V, в котором можно построить множество V* (читается - итерация алфавита V) цепочек. Формальный язык L в алфавите V - это подмножество цепочек из V* (L  V*). Описание формальных языков осуществляется с помощью формальных порождающих грамматик (формальных грамматик).

Формальная порождающая грамматика G (в дальнейшем - грамматика G) - это формальная система, определяемая четверкой объектов:
G [Z] = (VN, VT, Z, P),
где VN - алфавит нетерминалов (вспомогательных символов);

VT - алфавит терминалов (основных символов);

Z - начальный символ (аксиома) грамматики;

P - конечное множество правил.

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

Каждое правило из множества P имеет вид x  y, - где x, y цепочки, состоящие из терминальных и нетерминальных символов. В дальнейшем будем рассматривать грамматики, содержащие только правила, левые части которых состоят из одного нетерминального символа (контекстно-свободные грамматики). При этом должно быть хотя бы одно правило, левая часть которого - начальный символ грамматики.

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

Пример: Задана грамматика G [Z]: VN = {Z,A,B}; VT = {a,b,c}; Z-начальный символ.
P = { Z  ABc; (1)

A  aB; (2)

B  b }. (3)

С помощью грамматики G можно продуцировать (получать) цепочки в алфавите терминалов.

Порядок вывода можно записать в следующем виде:

(1) (2) (3) (3) (номера примененных правил)
Z  AВc  aBВc  aBbc  abbc.
Вывод продолжается до тех пор, пока на очередном шаге не получится цепочка, состоящая только из терминальных символов (т.е. нельзя применить ни одно из правил вывода).

Сокращенно вывод можно записать, пропустив промежуточные результаты, так Z+  abbc (цепочка abbc выводима из начального символа Z в заданной грамматике).

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

- начинать обход с самого левого узла;

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

Фраза - часть сентенциальной формы, выводимая из одного нетерминала за несколько шагов. Для простой фразы шаг вывода равен 1.

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

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

1. Каждой цепочке выводимой в заданной грамматике соответствует одно или несколько деревьев вывода.

2. Каждому дереву соответствует один или больше выводов.

3. Каждому дереву соответствует единственный правый и единственный левый выводы.

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

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

В процессе функционирования грамматики возможны два варианта:

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

а) вывод цепочки из начального символа грамматики (построить дерево вывода или вывод начиная с корня) - нисходящий вывод;

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

В обоих вариантах строится дерево вывода.

2. Получать цепочки, которые принадлежат к языку, порождаемому заданной грамматикой.

1 2 3 4 5 6