Cтраница 3
СУШ алгебраический язык LA бесконечен, то L порождается некоторой связной контекстно-свободной грамматикой с циклическим символом. Обратно, если для некоторой а-связной контекстно-свободной грамматики Г с циклическим символом и без правил вида a - 1 язык L L ( Г, о) непуст, то он бесконечен. [31]
Предложение 3.5. Не существует алгоритма, позволяющего решать, допускает ли произвольная контекстно-свободная грамматика неоднозначное слово. [32]
Приблизительно в то же самое время Ноам Хомский [1959] ввел аналогичную форму - контекстно-свободную грамматику - для определения синтаксиса естественного языка. Формы НФБ и контекстно-свободная грамматика по существу эквивалентны, различия касаются только обозначений. Этим и объясняется принятая в работах по синтаксису взаимозаменяемость терминов НФБ-грамматика и контекстно-свободная грамматика. [33]
Аналогично случаю унарных схем для языка историй L ( S) можно построить задающую контекстно-свободную грамматику с управлением путем просмотра на один символ. Таким образом, для распознавания расходимости преобразователя S достаточно проверить пустоту языка, порожденного контекстно-свободной грамматикой, что разрешимо. [34]
По существу форма Бэкуса - Наура представляет собой то же самое, что и контекстно-свободная грамматика, введенная лингвистами приблизительно в это же время. [35]
Хотя существует много классов грамматик непосредственных составляющие, мы представляем здесь только один класс, а именно контекстно-свободные грамматики. Однако поскольку мы рассматриваем свойство порождения непосредственных составляющих, мы пользуемся более широким названием. [36]
В классе контекстно-свободных языков разрешимы проблемы принадлежности, пустоты и конечности, но не разрешима проблема эквивалентности контекстно-свободных грамматик. В этом параграфе рассматриваются соответствующие проблемы для введенных выше классов языков сетей Петри. [37]
Для грамматик, описываемых направленной сетью без циклов ( граф рис. 6.2), алгоритм автоматического построения контекстно-свободной грамматики системой поддержки принятия решений достаточно прост. [38]
Удобной формой кодирования иерархической структуры показателя является скобочная линейная запись, которая эквивалентна синтаксическому дереву вывода в некоторой контекстно-свободной грамматике. Выполнение операции композиции возможно только при единообразной форме представления значений единичных показателен. [39]
Как следует из приведенных правил и диаграмм, с теоретической точки зрения HTML - это простой язык программирования с контекстно-свободной грамматикой. [40]
В связи с доказательством теоремы 2.7 кажется, что вспомогательные символы, используемые в регулярно-подобных конструкциях КСЯ, играют ту же роль, что и переменные в контекстно-свободных грамматиках. Известно [7], что для всякого натурального п и любого алфавита 2 с не менее чем двумя символами существует линейный КСЯ Ln, который не может быть порожден КС-грамматикой, содержащей меньше чем п переменных. [41]
За исключением правил S - SA и A - BS, образующих представление правила S - - SBS в нормальной форме, нормальная грамматика существенно не отличается от контекстно-свободной грамматики, из которой она построена. [42]
Таким образом, компилятор компиляторов Yacc и генератор лексических анализаторов Lex позволяют: задавать лексемы и грамматику языка в формализованном виде, удобном для реализации, для внесения изменений в язык; осуществлять преобразование контекстно-свободной грамматики в набор таблиц, подготовив тем самым транслятор языка; изменять синтаксис и семантику языка на уровне входных файлов. [43]
Описываемый ниже конструктор [40] строит распознаватель на языке правил подстановки Флойда для LR ( l) грамматики. Исходная контекстно-свободная грамматика должна быть задана порождающими правилами в БНФ. Предъявляемые к ней требования описаны в следующем пункте. [44]
Область теории сложности ни в коей мере не ограничивается алгебраическими или арифметическими вычислениями. Рассмотрим контекстно-свободные грамматики, из которых в качестве примера возьмем следующую. Среди этих символов t нетерминальный, а все остальные - терминальные. [45]