Грамматика с фразовой структурой

Грамматика с фразовой структурой — формальная грамматика, алгебраическая структура, состоящая из упорядоченной четвёрки G=(N, T, P, S) и определёной на ней неявно операцией конкатенации.

• N — конечное множество нетерминальных символов
• T — не пересекающееся с N конечное множество терминальных символов
• P — набор ограничивающих правил (продукций)
• S — стартовый (начальный символ)

Пример Грамматикой, порождающей язык {0ⁿ1ⁿ | n≥0}, является G: G= ({S}, {0,1}, P, S), где P = {S→0S1, S→ε}.

Понятие выводимости: Если αβγ последовательный набор символов языка G, а β→δ правило этого языка, то αβγ=>αδγ (αδγ непосредственно выводима из αβγ в G).

Цепь — последовательное присваивание нетерминальных символов. Цикл — замкнутая цепь

x (x ∈ N) — недоступный символ, если x неэквивалентен стартовому символу S (x ≠ S) и не существует выводов типа S⁺→αxβ. Символ называется непродуктивным, если не существует строки γ, такой, что нетерминальный символ не будет присвоен γ (x→γ) Символ называется бесполезным если он непродуктивен или недоступен.

Литература

• Ахо, Дж. Ульман «Теория синтаксического анализа, перевода и компиляции», Т.1 «Синтаксический анализ», М.: Мир, 1978
• Р. Хантер «Проектирование и конструирование компиляторов», ФиС, 1984

Ссылки

• [lpcs.math.msu.su/~pentus/tfyaw.htm Теория формальных языков]
• [62.76.251.125/kurses.php?part=math&kurs=003 Теория алгоритмов и математическая логика]

Отрывок, характеризующий Грамматика с фразовой структурой

– Нам лучше расстаться, – проговорил он прерывисто.
– Расстаться, извольте, только ежели вы дадите мне состояние, – сказала Элен… Расстаться, вот чем испугали!
Пьер вскочил с дивана и шатаясь бросился к ней.
– Я тебя убью! – закричал он, и схватив со стола мраморную доску, с неизвестной еще ему силой, сделал шаг к ней и замахнулся на нее.
Лицо Элен сделалось страшно: она взвизгнула и отскочила от него. Порода отца сказалась в нем. Пьер почувствовал увлечение и прелесть бешенства. Он бросил доску, разбил ее и, с раскрытыми руками подступая к Элен, закричал: «Вон!!» таким страшным голосом, что во всем доме с ужасом услыхали этот крик. Бог знает, что бы сделал Пьер в эту минуту, ежели бы
Элен не выбежала из комнаты.

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


Прошло два месяца после получения известий в Лысых Горах об Аустерлицком сражении и о погибели князя Андрея, и несмотря на все письма через посольство и на все розыски, тело его не было найдено, и его не было в числе пленных. Хуже всего для его родных было то, что оставалась всё таки надежда на то, что он был поднят жителями на поле сражения, и может быть лежал выздоравливающий или умирающий где нибудь один, среди чужих, и не в силах дать о себе вести. В газетах, из которых впервые узнал старый князь об Аустерлицком поражении, было написано, как и всегда, весьма кратко и неопределенно, о том, что русские после блестящих баталий должны были отретироваться и ретираду произвели в совершенном порядке. Старый князь понял из этого официального известия, что наши были разбиты. Через неделю после газеты, принесшей известие об Аустерлицкой битве, пришло письмо Кутузова, который извещал князя об участи, постигшей его сына.