Cтраница 1
Контекстно-свободная грамматика, с каждым нетерминальным символом которой связан набор атрибутов и для каждого правила которой указан способ вычисления атрибутов символа в левой части по атрибутам компонент правой части. Атрибуты используются для задания контекстных условий или для описания семантики языка. [1]
Контекстно-свободная грамматика, в которой применимость правила вывода к заданной подцепочке определяется ее контекстом ограниченной длины. [2]
Контекстно-свободная грамматика, на символах которой заданы отношения, позволяющие определить во входной строке возможные границы синтаксических конструкций, рассматривая лишь пары соседних символов. [3]
Контекстно-свободная грамматика Г - ( V, А, л) называется линейной, если п содержит лишь правила вида а - - ы или а - u v, где и, v А и а, р VA. Семейство З ип всех линейных языков служит примером рационального конуса, не являющегося AFL, потому что З цп не замкнуто относительно произведений ( см. упр. [4]
Контекстно-свободные грамматики были введены Хомским [1959] в качестве математической модели для грамматик естественных языков. Изложение в § 2 и 5 непосредственно инспирировано работами Нива [1968] н Боассона [1971]; например, доказательство теоремы 5.14 принадлежит Нива. [5]
Контекстно-свободные грамматики и языки обычно появляются в связи с языками программирования и, конечно, при анализе естественных языков. Непосредственно возникают две вычислительные задачи. [6]
Контекстно-свободная грамматика не может описать весь естественный язык. Вопрос, как это сделать, остается открытым. Но такая грамматика может описать большую часть языка, хотя тогда она будет очень громоздкой. Тем не менее эта грамматика настолько проста и описательна, что ее обычно берут за основу анализа. [7]
Контекстно-свободная грамматика, построенная так, чтобы вместе с цепочками порождались также деревья подчинения. [8]
Контекстно-свободная грамматика, в каждом правиле которой правая часть содержит не более одного вспомогательного символа. [9]
Контекстно-свободная грамматика, на символах которой заданы отношения, позволяющие определить во входной строке возможные границы синтаксических конструкций, рассматривая лишь пары соседних символов. [10]
Контекстно-свободная грамматика ограниченного типа, в которой правая часть продукции состоит из одного терминального либо двух нетерминальных символов. [11]
Множество контекстно-свободных грамматик, которые порождают регулярные языки ( или кофинитные множества), является 22-полным. [12]
Множество неоднозначных контекстно-свободных грамматик является Si-полным. [13]
Пусть дана контекстно-свободная грамматика, и пусть она приведена к нормальной форме. Пусть эта нормальная грамматика задана в виде двух множеств: множества упорядоченных пар, представляющих терминальные правила, и множества упорядоченных троек, представляющих двойные правила. Дана также цепочка символов в терминальном словаре языка. Необходимо узнать, входит ли эта цепочка в язык, порожденный данной грамматикой. [14]
Простым примером контекстно-свободной грамматики служит БНФ ( В. BNF), используемая для описания синтаксиса языков программирования. Сам термин является антонимом термина контекстно-зависимая грамматика ( С. [15]