Грамматика формальная

Грамматика формального языка есть упорядоченная четверка О = Р, а) V — основной (терминальный) словарь — набор исходных элементов, из которых строятся цепочки 2 — вспомогательный (нетерминальный) словарь — набор символов, которыми обозначаются группы или цепочки исходных элементов Р — правила грамматики — конечное множество упорядоченных пар А В, где А, В — цепочки, составленные из множества Ки 2 5 означает заменить А на В или подставить В вместо Л а — начальный символ, с которого выводится любая фраза это выделенный нетерминальный символ, обозначающий совокупность всех тех объектов языка, для описания которых предназначена данная грамматика. [c.265]

Генератор кода 261 Глубина диагностирования ПО Грамматика формальная 262 Граф И-ИЛИ 81 [c.329]

Заметим, что V - множество бесконечное. Выше отмечалось, что грамматика формальных языков в настоящее время подразделяется на две части синтаксис и семантику. [c.114]

Пользователь САПР должен также знать, что явления зацикливания вычислений или переполнения разрядной сетки могут происходить не только из-за недостатков выбранного численного метода, но и из-за ошибок в задании исходных данных. Некоторые ошибки, связанные с нарушением формальных правил грамматики входного языка, распознаются автоматически. Однако ряд ошибок не может быть выявлен формальными средствами без участия [c.224]

Пусть имеется непустое множество U, называемое базой. Элементы множества назовем базовыми элементами. Формальным языком, определенным на базовом множестве U, называется любое множество цепочек из элементов U. В большинстве формальных языков можно использовать не все множество цепочек, а некоторое подмножество, каждому элементу которого соответствует определенное смысловое содержание. Конечное множество правил, определяющих структуру и содержание множества допустимых цепочек из элементов U, образует в совокупности формальную грамматику языка. Грамматику можно рассматривать как теорию структуры этого языка, выражаемую совокупностью закономерностей построения синтаксических единиц. [c.132]

Между обычными грамматиками естественных языков и формальными грамматиками имеется существенное различие. Все правила формальной грамматики строго формулируются на основе относительно небольшого числа определенных символов и операций. Это дает возможность создать стройную логическую структуру формальной грамматики и автоматизировать операции анализа языковых конструкций в ЭВМ. [c.132]

Формальная грамматика называется порождающей, если она создает только правильные цепочки элементов из U, давая указания о их строении, и не создает ни одной неправильной цепочки. [c.132]

Входной текст программы, написанный на языке программирования с помощью формальной грамматики, должен быть транслирован (переведен) в рабочую программу ЭВМ. Иногда используют поэтапную трансляцию с введением промежуточных языков программа Па на языке А транслируется в программу на языке В, затем в программу Пс и последней в процессе трансляции формируется рабочая программа Яр. [c.134]

Наиболее сложная фаза при трансляции — синтаксический анализ. Математическим аппаратом, используемым при построении синтаксических анализаторов, является аппарат формальных грамматик. [c.262]

Формальные грамматики. Аппарат формальных грамматик близок к теории автоматов и искусственного интеллекта. Известны попытки его использования для разработки алгоритмов структурного синтеза. [c.262]

В САПР применяются порождающие формальные грамматики. Порождающая грамматика— это четверка объектов Г=<Ут, Ун, Р, 5>, где Ут, Ун — множества соответственно терминальных и нетерминальных символов Р—правила грамматики, называемые продукциями 5 — начальный нетерминальный символ. Множество Ут включает все слова языка, из которых строятся предложения. Множество Ун включает символы, которые играют вспомогательную роль нетерминальные символы используются при [c.262]

Формальные грамматики можно рассматривать как частный случай дедуктивных систем, в которых исходный символ 5 заменяет систему аксиом А—множество априорно заданных совокупностей элементов, а в множество правил наряду с подмножеством Р синтаксических правил подстановки входит подмножество О семантических правил, представляющих собой правила трансформации одних совокупностей элементов в другие. Системы формального синтеза (см. 3.1) можно описать как дедуктивные системы. [c.263]

Непосредственному применению формальных грамматик как систем структурного синтеза препятствуют затруднения, обусловленные многомерностью, контекстной зависимостью синтезируемых систем и их частей, большой мощностью множеств V, Р и О. Многомерность связана с большим числом типов отношений, которые возможны между элементами синтезируемых объектов, что приводит к различным множествам правил при наращивании элементов. Так, могут быть правила для различных координатных осей трехмерного пространства, правила топологические по отношению к разным по- [c.264]

Определенный интерес представляет рассмотрение лингвистических моделей, к которым относятся модели, построенные иа основе формализаций, применяемых для строгого описания тех или иных свойств естественного языка. В качестве формализаций наиболее часто используются семантические сети и формальные грамматики. [c.27]

Формальное определение синтаксиса языка программирования называется грамматикой. Она представляет собой набор правил, определяющих форму, которую может иметь программа. Формальная грамматика—это грамматика, использующая строго определенные нотации. Наиболее известным типом формальной языковой грамматики является нормальная форма Бэкуса [2, 31. [c.229]

Формальные языки и порождающие грамматики. [c.65]

Задача генерации всех возможных сценариев, в частности, в примерах А, В, и С, может быть решена различными методами. Все они, так или иначе, сводятся к перебору дуг графа, описывающего создавшуюся проблему. Поэтому решение задачи могло бы быть дано и в терминах теории графов. Однако с точки зрения перспектив решения подобных задач для графов со значительно более сложной структурой (например, когда на элементы графа накладываются различные условия) более перспективным кажется использование аппарата формальных грамматик [2.29]. [c.110]

Интуитивно, язык - это множество предложений или последовательностей слов. Каждое предложение формируется из словаря языка в соответствии с заданными правилами формирования. Правила формирования называются грамматикой языка и определяют его структуру. Однако такое интуитивное определение языка и его грамматики для формального анализа и генерации совершенно недостаточно. [c.111]

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

Формальной грамматикой назовем упорядоченную четверку G=(Vn,Vt,P,S). [c.115]

Формальная грамматика, которая для любой предъявленной цепочки умеет решать, является эта цепочка правильной или нет, называется распознающей. [c.115]

Формальная грамматика, которая умеет строить любую правильную цепочку, давая указания о ее строении, не генерируя при этом ни одной неправильной цепочки, называется порождающей. [c.115]

Пример. Формальную грамматику G = (Vn, vt, Р, S), описывающую упрощенное арифметическое выражение, можно задать следующими правилами [c.116]

Подчеркнем, что формальная грамматика не является алгоритмом. Множество синтаксических правил Р - не последовательность предписаний, а совокупность разрешений выполнять заданные подстановки. [c.116]

Теперь можно ввести формальное определение языка, порождаемого грамматикой. Язык Lg, порождаемый грамматикой G=(Vn, Vt, Р, S), - это совокупность всех терминальных цепочек, выводимых из начального символа S в грамматике G, т.е. язык определяется следующим множеством [c.116]

В предыдущем разделе было показано, как, используя знаковые графы или таблицы типа 2.9 и 2.10, построить формальную грамматику и порожденный ей язык, описывающий последовательность операций в допустимых сценариях. [c.122]

Как обычно в формальных грамматиках, под символом понимается минимальная по числу знаков строка, используемая в данной грамматике или в описываемом ей языке, которая имеет самостоятельное значение. [c.123]

По четвертому признаку различают формальные и неформальные языки. Принадлежность к классу формальных языков определяется наличием формальной грамматики языка в соответствии, например, с определением Хомского [60] [c.127]

Различают распознающие, порождающие и преобразующие формальные грамматики. Грамматика называется распознающей, если для любой рассматриваемой цепочки элементов из U она может решить, является ли эта цепочка правильной (допустимой) или нет, и в случае положительного ответа распознать структуру цепочки. [c.132]

Формальная грамматика называется преобразующей, если для любой правильной цепочки она умеет строить ее отображения тоже в форме правильной цепочки, задавая при этом указания [c.132]

Формальной грамматикой Хомского называется упорядоченная система [c.133]

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

Любой формальный язык можно представить в виде множества цепочек, составленных из элементов некоторого алфавита [2]. Цепочки языка выделяют с помощью конечного множества правил, называемого грамматикой . В данном случае множеством цепочек является множество грамматически правильных предложений , составленных из отдельных слов алфавита системы распознавания. [c.265]

Детерминистские методы. Спектр этих методов достаточно широк. Если описание образов производится с помощью непроизводных элементов (подобразов) и их отношений, то для построения распознающих систем применяются лингвистические (синтаксические) методы. Образ описывается с помощью иерархической структуры подобразов, аналогичной синтаксической структуре языка. Это позволяет применять при решении задач распознавания образов теорию формальных языков. Предполагается, что грамматика образов содержит конечные множества элементов, называемые переменными, непроизводными элементами и правилами подстановки. Характер правил подстановки определяет тип грамматики. [c.114]

Эта задача принципиальЕ э ничем не отличается от предыдущей. Выходные документы также имеют определенный синтаксис ш семантику и могут быть оаисаны формальными средствами грамматики. [c.63]

Для задания контекстных ограничений в формальное описани КС-грамматики на БНФ вставляются соответствующие семантические правила и ограничения, следующие непосредственно за определяющим их понятием и отделенные с двух сторон семантическими скобками — символом ). Каждому семантическому правш у ставится в соответствие, кроме текста записи данного правила на специальном языке, ссылка на его имя с начальным символом 8 и номером. Это дает возможность формулировать само правило вне синтаксического описания и вызывать его по наименованию. [c.92]

Для решения первой проблемы в гл. 2 рассмотрены формальные средства для декларации семантических объектов модели предметной области комплексной САПР на основе языка технологии базы и средства описания синтаксиса и семантики на основе атрибутных грамматик с применением МБНФ для входных языков. В 3.1, 3.2 предложены алгоритмы трансляции и конвертирования единый) входной язык комплексной САПР — входной язык ППП в терминах отображений. Это позволяет конкретизировать структуру-системы генерации трансляторов комплексной САПР МЭА, состав необходимого программного обеспечения и перечень решаемых им [c.118]

Алгоритм трансляции с помощью атомарных грамматик [67, 81 ] заключается в последовательном выполнении транслирующих действий с помощью базового набора программ-атомов. Запись, алгоритма состоит в перечислении в тексте имен процедур-атомов-в том порядке, в каком они выполняются в алгоритме трансляции. Чтение атомов производится слева направо . Любой атод мол ет-содержать список формальных параметров, который при применении атома заменяется списком фактических параметров, т. е. тех данных, над которыми выполняются предусмотренные этим атомол операции обработки (трансляции). На основе искользова-ния именованных множеств данных в качестве фактических параметров могут быть указаны имена любых агрегатов данных, к которым атом имеет доступ и поиск которых по имени он может осуществлять в памяти ЭВМ. [c.132]

Автоматическая технология синтеза конверторов предпо тагает наличие обязательных этапов формального описания синтаксиса и семантики входных языков всех используемых в составе комплексной САПР МЭА ППП, для которых нужен этап конвертирования. Это достигается применением для описания входных языков ППП атрибутных грамматик и использованием предложенного вида МБНФ [23, 25]. [c.137]

Как видно из вышесказанного, истинный язык программирования предполагает строгую математическую формулировку, то есть он может быть определен с помощью формальной грамматики. С другой стороны, язык програ ммирования может и не иметь формальной синтаксической спецификации. Обратимся теперь к языку L-A-S и покажем, как нотации Бэкуса могут б ть использованы для определения его синтаксиса. [c.229]

Ясно, что не все высказывания/предположения на принятом формальном языке будут характерными для разных кпассов состояний технической системы. Значит, на основе использования возможностей анализа представителей классов состояний требуется установить, какие из этих высказываний являются типичными и достаточными при описаниях априорно заданных классов состояний. Эта задача решается в два этапа (по числу этапов выбора правил грамматики языка). [c.16]

Формальное определение языка позволило ввести их классификацию в соответствии с теми ограничениями, которые наложены на множество Р грамматики языка. Наибольшее распространение получила классификация Хомского [2.32], который разделил языки в соответствии с описывающими их грамматиками на четыре типа. [c.118]

Энциклопедия по машиностроению XXL

Оборудование, материаловедение, механика и ...