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



страница1/7
Дата30.12.2012
Размер0.89 Mb.
ТипПрограмма
  1   2   3   4   5   6   7


КАЛИНИНГРАДСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

В.Ф. Пономарев

ФОРМАЛЬНЫЕ ЯЗЫКИ И ГРАММАТИКИ


Утверждено Ученым Советом университета в качестве

учебного пособия для студентов направления 550028 -

“Информатика и вычислительная техника” по дисциплине

"Теория автоматов"

Калининград

1998
УДК 519.95

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

Учебное пособие. - Калининград: КГТУ, 1998, c.

Изложены основные понятия и методы использования теории формальных языков и грамматик. Дана классификация грамматик по Хомскому и области применения различных классов грамматик. Рассмотрены правила и алгоритмы грамматического разбора текста формального языка "сверху-вниз" и "снизу-вверх". Основные положения иллюстрируются примерами различных формальных языков, в том числе языка программирования "Паскаль". Каждому студенту предлагается выполнить индивидуальное задание на грамматический разбор арифметического выражения.

илл.- 24 ., табл.- 3 ,список лит. - 8 наименований.
Рецензент: Кафедра математической кибернетики Калининградского

государственного университета

@ Калининградский государственный технический университет,1998
Вениамин Федорович П о н о м а р е в

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

Редактор

Подписано к печати тир. формат

объем п.л. заказ Цена договорная

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

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

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

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

1.
Предварительные обсуждения

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

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

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

Для объяснения синтаксиса формального языка можно рассмотреть основные правила формирования синтаксических конструкций естественного языка. Множество слов естественного языка разбито на синтаксические группы: существительные, глаголы, прилагательные, предлоги и т.д. Представителем каждой группы является синтаксическая переменная, сохраняющая имя синтаксической группы. Для удобства изложения представим синтаксические переменные, заключенными в угловые скобки, а слова, - заключенными в кавычки. Например, <существительное>, <глагол>, <прилагательное> и "алгоритм", "подмножество", " функция" и т.д..

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

Упорядоченная последовательность выражений формирует новую синтаксическую конструкцию - предложение. Основными составными частями предложения естественного языка являются части речи: группы подлежащего, сказуемого и дополнения, которые в синтаксисе языка также могут быть представлены синтаксическими переменными: <предложение>, <подлежащее>, <сказуемое>, <дополнение> и т.д.

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

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

Введем условные обозначения:

::= - знак о том, что выражение, стоящее слева, может быть

замещено выражением, стоящим справа ( "...состоит из...") ;

< .. > - синтаксическая переменная языка ;

" .. " - слово ( лексема ) языка ;

< .. >< .. > .. - соединение синтаксических переменных союзом "и";

< .. > | < .. >| .. - разделение синтаксических переменных

разделителем "или";

" .. " < .. > .. | < .. > " .. " .. - соединение синтаксических

переменных и лексем союзом "и" и разделение

выражений и/или предложений языка разделителем "или";

" .. " " .. " .. - cоединение лексем союзом "и" ;

" .. " | " .. "| .. - разделение лексем разделителем "или";

{ .. } - многократное повторение выражения, заключенного в

фигурные скобки, включая нуль раз;

[ ... ] - одно- или нулькратное повторение выражения,

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

Тогда основная формула БНФ может быть представлена в виде

Х ::= Y1  Y2  Y3 ..., ( 1 )
где Х - выражение, определяемое только синтаксической

переменной;

Yi - выражение, определяемое набором синтаксических

переменных и/или лексем, где I = 1, 2, 3, ... .

При подстановке вместо Х выражений Yi осуществляется вывод синтаксически правильной конструкции выражения или предложения, описываемого синтаксической переменной X.

Введем знак "=>", показывающий использование одного из правил синтаксиса и выводимости синтаксически правильной цепочки.

Пусть дано некоторое множество правил и множество лексем естественного языка, описанные на языке БНФ:

<предложение> ::= <подлежащее> <сказуемое> |..;

<подлежащее> ::= <прилагательное> <существительное> |..;

<сказуемое> ::= <глагол> <дополнение> |..;

<дополнение>::=<предлог> <существительное>|

<прилагательное> |.. ;

::= "алгоритм" | "сходимость" | "кошка" | "диван"|.. ;

<глагол> ::= "иметь" | "лежать" |.. ;

<прилагательное> ::= "рыжий" | "хороший" | "высокий" |.. ;

<предлог> ::= " на " | .. ; и т.д..

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

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

Например,

<дополнение> ::= <прилагательное> <существительное>;

<дополнение> ::= <предлог> <существительное>;

<глагол> ::= "иметь";

<глагол> ::= "лежать";

и т.д.

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

Пример 1. Пусть дано предложение "хороший алгоритм имеет высокую сходимость".

Верна ли синтаксическая конструкция предложения?

<предложение> => <подлежащее><сказуемое> => <прилагательное> <существительное> <сказуемое> => "хороший" <существительное> => "хороший" "алгоритм" <сказуемое> => "хороший" "алгоритм" <глагол> <дополнение> => "хороший" "алгоритм" "имеет" <дополнение> => "хороший" "алгоритм" "имеет" <прилагательное> <существительное> => "хороший" "алгоритм" "имеет" "высокую" <существительное> => "хороший" "алгоритм" "имеет" "высокую" "cходимость".

Так доказана верность синтаксической конструкции исходного предложения.

Пример 2. Пусть дано предложение "рыжая кошка лежит на диване".

Верна ли синтаксическая конструкция предложения?

<предложение> => <подлежащее> <сказуемое> => <подлежащее> <глагол> <дополнение> => <подлежащее> <глагол> <предлог> <существительное> => <подлежащее> <глагол> <предлог> "диван" => <подлежащее> <глагол> "на" "диване" => <подлежащее> "лежит" "на" "диване" => <прилагательное> <существительное> "лежит" "на" "диване" => <прилагательное> "кошка" "лежит" "на" "диване" => "рыжая" "кошка" "лежит" "на" "диване".

Так доказана верность синтаксической конструкции исходного предложения.

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

Кстати, опираясь на вышеприведенное множество правил и лексем, можно вывести синтаксически правильные, но бессмысленные предложения. Например, "рыжий" "алгоритм" "лежит" "сходимости" или "высокая" "кошка" "имеет" "хороший" "диван"

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

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

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

Например, в понятие "аудитория" включен единственный атрибут - помещение, в котором читаются лекции и проводятся семинарские занятия, но объем его неограниченно большой ( даже в одном учебном заведении может быть очень много аудиторий ). В понятие "аудитория № 382 главного учебного корпуса КГТУ" включены четыре атрибута - помещение, в котором читаются лекции и проводятся семинарские занятия, имя помещения внутри здания, имя здания и его принадлежность учебному заведению, но объем этого понятия ограничен единственным помещением.

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

Например, выражение " 14 декабря 1997г. в 10.00 в аудитории 382 состоится лекция на тему..." может быть истинным или ложным по факту свершения этого события. Следовательно, это выражение является суждением.

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

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

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

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

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

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

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

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

Элементарными лексическими единицами большинства языков программирования являются :

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

<служебные слова>::= AND  ARRAY  BEGIN  CASE  CONS  DIV  DOWNTO  DO  ELSЕ  END  FILE  FOR  FUNCTION  GOTO  IF  IN  LABEL MOD NIL NOT OF OR PACKED PROCEDURE PROGRAM RECORD REPEAT SETTHEN TO TYPE UNTIL  VAR  WHILE  WITH ;

<специальные символы>::= +  -  *  /  =  <  >  <=  >=  [  ]  (  )  _  :=  "  '  .  ,  :  ;   $ ;

десятичные числа без знака .

В выражениях и предложениях формального языка, cодержащих лексемы и синтаксические переменные, лексемы всегда заключены в кавычки. Например, "BEGIN", "NOT", AND" и др.

Для обозначения синтаксических переменных введем прописные буквы латинского алфавита. Знаки этого множества называют нетерминальными. Обозначим множество нетерминальных символов знаком VN.

Множество VN - счетно и конечно .

Элементарными синтаксическими переменными для языка программирования являются :

<блок> :: = <блок-операторов><блок-процедуры><блок-функции>...;

<заголовок> ::= <заголовок-программы><заголовок-процедуры>

<заголовок-функции>...;

<идентификатор> ::= <идентификатор-программы><идентификатор-

переменной>...;

<оператор> ::= <оператор-присваивания><оператор-ЕСЛИ>...;

<операция> ::= <операция-сложения><операция-умножения>

<операция-отношения>...;

и другие синтаксические переменные.

В языке Паскаль всего около 240 синтаксических переменных.

В выражениях и предложениях формального языка, содержащих синтаксические переменные, их заключают в угловые скобки. Например, "PROGRAM" <идентификатор-программы> ";" "BEGIN" <блок-операторов> "END" и др.

Объединение символов двух множеств VTи VN представляет множество символов формального языка, т.е.
V = VTVN . ( 2 )
Цепочки символов формального языка могут содержать различное количество терминальных и/или нетерминальных символов. Поэтому множество правильных цепочек может быть записано так:
V* = i=0(n ) V i ( 3 )

Если каждый элемент множества V* обозначить строчной буквой греческого алфавита, то множество V* можно описать перечислением его элементов:

V* = {     

Например,

 := "PROGRAM"<идентификатор-программы>";"<блок>".";

 := "CONST" <определение-константы> "; " ;

 := "( " <идентификатор> { " , " <идентификатор> } " ) ";

где знак ":=" означает: "...присвоить значение...".Цепочка  V* содержит пять символов множества V, цепочка  V* - три символа и цепочка  V* - не менее трех символов, т.к. в языках программирования знак "{ .. }" означает многократное повторение выражения, заключенного в фигурные скобки, включая нуль раз.

Конструкция программы на любом языке программирования состоит, как правило, из двух частей: заголовка - <заголовок-программы> и тела программы - <блок>. В заголовке программы, начинающемся служебным словом "PROGRAM", ей присваивается имя (идентификатор), вслед за которым в круглых скобках задается перечень идентификаторов тех файлов, через которые программа взаимодействует с внешним миром. В теле программы должны следовать в определенном порядке разделы меток, констант, типов, переменных, процедур, функций и операторов. Так как разделы, предшествующие разделу операторов, носят описательный характер, то каждый из них может быть пустой цепочкой, а раздел операторов является основным и должен присутствовать в любой программе. Поэтому в последующих объяснениях <блок> содержит только описание операторов, т.е. исполняет функции <блока-операторов>. 

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

Продукцию или правило подстановки записывают так:

::= ( 5 )

где  - левая часть правила,

 - правая часть правила.

Если правил несколько,то их необходимо индексировать:

p i :  i::= i, где i = 1;2;3;... ( 6 )

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

 V*\ где  - пустая цепочка. ( 7 )

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

 V* или V*\ VN. ( 8 )

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

<программа> ::= <заголовок-программы> " ; "<блок>" . ";

<заголовок-программы> ::= "PROGRAM"<идентификатор-программы>;

<блок> ::= <раздел-операторов> | ...;

<раздел-операторов> ::= "BEGIN" <оператор> " END" ;

<оператор> ::= <оператор-присваивания> |...;

<оператор-присваивания> ::= <переменная> " := " <выражение>;

<выражение> ::= <терм> <операция-сложения> <терм> ;

<терм> ::= <множитель> <операция-умножения> <множитель>;

<множитель> ::= <переменная> ;

<переменная> ::= <идентификатор-переменной> ;

<операция-сложения> ::= " + " | " - " | "OR";

<операция-умножения> ::= " x " | " / " | "DIV" | "MOD" |"AND".

Синтаксической переменной <идентификатор-программы> присвоим какое-либо значение ( например, "ALGEBRA"), т.е.

<идентификатор-программы>::= "ALGEBRA".

Cинтаксической переменной <идентификатор-переменной> также присвоим какое-либо значение, начинающееся с буквы ( например," i " ), т.е.

<идентификатор-переменной> ::= " i ".

Последовательность использования правил подстановки в процессе формирования цепочки терминальных и/или нетерминальных символов называют выводом. Поэтому эти же правила часто называют правилами вывода. Для указания процесса вывода используют знак "=>".

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

Пример 4. а) Для начального символа <программа> (пример 3) исполнить левосторонний вывод :

<программа> => <заголовок-программы> ";" <блок> "." => "PROGRAM" <идентификатор-программы> ";" <блок> "." => "PROGRAM" "ALGEBRA" ";" <блок> "." => "PROGRAM" "ALGEBRA" ";" <раздел-операторов> "." => "PROGRAM" "ALGEBRA" ";" "BEGIN" <оператор> "END" "." => "PROGRAM" "ALGEBRA" ";" "BEGIN" <оператор-присваивания> "END" "." => ."PROGRAM" "ALGEBRA" ";" "BEGIN" <переменная> ":= " <выражение> "END" "." => "PROGRAM" "ALGEBRA" ";" "BEGIN" <идентификатор-переменной> ":=" <выражение> "END" "." => "PROGRAM" "ALGEBRA" ";" "BEGIN" " i " ":=" <выражение> "END" "." => ..

b) Для начального символа <программа> ( пример 3) исполнить правосторонний вывод:

<программа> => <заголовок-программы> ";" <блок> "." => <заголовок-программы> ";" <раздел-операторов> "." => <заголовок-программы> ";" "BEGIN" <оператор> "END" "." => <заголовок-программы> ";" "BEGIN" <оператор-присваивания> "END" "." => <заголовок-программы> ";" "BEGIN" <переменная> ":=" <выражение> "END" "." => ...

Cинтаксической переменной <выражение> может быть любое арифметическое, алгебраическое или логическое выражение. Так как содержание этого выражения не определено, то оба вывода остановились на этой синтаксической переменной. Остальные члены предложения <программа> представлены элементарными лексическими единицами текста программы.,

Пример 5. Для cинтаксической переменной <выражение> (пример 3) выполнить левосторонний вывод:

<выражение> => <терм><операция-сложения><терм>=> <множитель> <операция-умножения><множитель><операция-сложения><терм> => <переменная><операция-умножения><множитель><операция-сложения> <терм>=> <идентификатор-переменной><операция-умножения> <множитель> <операция-сложения><терм> => "i" <операция-умножения> <множитель><операция-сложения><терм> => "i" "x" <множитель><операция-сложения><терм> => "i" "x" <переменная><операция-сложения><терм> => "i" "x" <идентификатор-переменной><операция-сложения><терм> => "i" "x" "i" <операция-сложения><терм> => "i" "x" "i" "+" <терм> => "i" "x" "i" "+" <множитель><операция-умножения><множитель> => "i" "x" "i" "+" <переменная> <операция-умножения><множитель> => "i" "x" "i" "+" <идентификатор-переменной><операция-умножения> <множитель> => "i" "x" "i" "+" "i" <операция-умножения> <множитель> => "i" "x" "i" "+" "i" "x" <множитель> "i" "x" "i" "+" "i" "x" <переменная> => "i" "x" "i" "+" "i" "x"<идентификатор-переменной> => "i" "x" "i" "+" "i" "x" "I".

Имя начальной синтаксической переменной языка, для которой дано множество правил вывода называют начальным символом и обозначают буквой J. Роль начального символа может исполнять любая синтаксическая переменная. Для текста программы начальной синтаксической переменной является <программа>. Для части текста программы - выражения - начальной синтаксической переменной является <выражение>.

Итак, модель формальной грамматики может быть описана совокупностью четырех основных компонент:
G =  V T ; V N ;J ; P  , ( 9 )
где VT = { a;b;c;... } - терминальные символы;

VN = { A;B;C;...} - нетерминальные символы;

J Vn - начальный символ;

P = { pi |i = 1; 2; 3; ... } - синтаксические правила .

Множество правильных цепочек терминальных символов представляет выражения и предложения формального языка данной формальной грамматики L(G) :
L ( G ) = {  V *\ VN }. ( 10 )
Текст программы, ограниченный разделителем ".", называют предложением, а часть текста, ограниченную разделителем ";" , - выражением.

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

Если для начального символа не дана цепочка терминальных и/или нетерминальных символов или дана ее часть, то формальная грамматика оказывает помощь в построении синтаксически правильной цепочки терминальных символов с указанием ее состава и структуры. Такая грамматика называется порождающей.
  1   2   3   4   5   6   7

Похожие:

Формальные языки и грамматики iconРабочая программа дисциплины теория автоматов и формальных языков направление подготовки
Уметь: строить формальные грамматики, деревья вывода, распознающие автоматы; анализировать формальные языки
Формальные языки и грамматики iconЛекция 4 Исчисления. Формальные системы. Формальные грамматики. Автоматы
...
Формальные языки и грамматики iconЛекция 3 Исчисления. Формальные системы. Формальные грамматики. Автоматы
...
Формальные языки и грамматики iconМетоды представления знаний Формальные языки и формальные системы
Естественный язык: достоинства (и они же недостатки): неполнота, избыточность, неоднозначность
Формальные языки и грамматики iconИерархия Хомского
Согласно Хомскому, формальные грамматики делятся на четыре типа. Для отнесения грамматики к тому или иному типу необходимо соответствие...
Формальные языки и грамматики iconЛабораторная работа №1. Формальные грамматики и их свойства. Дана грамматика. Построить вывод заданной цепочки
Определить тип грамматики. Описать язык, порождаемый этой грамматикой. Написать для этого языка кс-грамматику
Формальные языки и грамматики icon12. Формальные грамматики и автоматы
До начала XX века существовали только естественные (разговорные языки). При этом под языком понималось средство общения между людьми....
Формальные языки и грамматики iconВопросы к зачету/экзамену по спецкурсу «Языки и автоматы»
...
Формальные языки и грамматики iconПервая часть: Формальные грамматики: К. С. грамматика
Алгоритмы синтеза абстрактного автомата на примере четырехразрядного сумматора двоичных чисел
Формальные языки и грамматики icon1. Понятие информации. Виды информации. Роль информации в живой природе и в жизни людей. Язык как способ представления информации: естественные и формальные языки
Понятие информации. Виды информации. Роль информации в живой природе и в жизни людей. Язык как способ представления информации: естественные...
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org