Общий вид цепочек КС-языков

Прежде чем рассматривать теорему о разрастании КС-языков, примем без доказательств следующую теорему.

Теорема 5.2. Для любой КС-грамматики, которая не допускает вывода вида

А Þ⁺ aАb,

где ½a½> 0 и ½b½> 0 можно построить эквивалентную А-грамматику. š

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

Теорема 5.3. Для любого КС-языка L существует постоянная p такая, что если y Î L и ½y½ > p, то y = abgjl, где b¹e, j¹e и ab ⁱgj ⁱl Î L для любого i ³0.

Доказательство. Аналогично с теоремой 5.1 рассмотрим только случай бесконечных языков.

Рассмотрим в бесконечном КС-языке L бесповторные деревья вывода, то есть такие, у которых ни на одной ветви нет повторяющихся нетерминалов. Таких деревьев конечное число. Максимальная высота бесповторного дерева v - равна количеству нетерминалов грамматики. Если максимальная длина правых частей правил грамматики равна b, то максимальная длина цепочки, выводимой бесповторными деревьями, будет не более b^v. Положим p = b^v. Рассмотрим цепочку с длиной больше p и ту ветвь ее дерева вывода, в которой нетерминалы повторяются.

Рассмотрим поддеревья D₁ и D₂, начинающиеся с повторяющегося нетерминала A. Если D₁ заменить на D₂, то получим дерево вывода цепочки agl. Подвеска дерева D₂ к корню D₁ возможна, так как после нее корень дерева D₁ соответствует применению того же правила, что и корень дерева D₂. Таким образом, полученное дерево вывода является деревом вывода в той же грамматике.

Если D₂ заменить на D₁, то получим дерево вывода цепочки ab ²gj ²l. Дерево D₁, которым заменяется D₂ содержит в себе D₂ в качестве поддерева. Заменив его на D₁, получим дерево вывода цепочки ab ³gj ³l. Продолжая такие замены, можно получить любую из цепочек ab ⁱgj ⁱl. š

Пример 5.1. Пусть дана КС-грамматика с правилами:

S ® aAp

A ® cAc ½ cbAb ½ d

Максимальная высота бесповторного дерева здесь равна 2, а максимальная длина цепочки выводимая бесповторным деревом равна 3 (бесповторно выводится только цепочка adp). На рис. 5.1 (а) показано дерево вывода цепочки acbdbp. Здесь принято следующее: a = a, b = cb, g = d, j = b, l = p. На рис. 5.1 (б) показана замена поддерева D₁ на D₂, а на рис. 5.1 (в) замена D₂ на D₁. †

Теорема 5.3, как и теорема 5.1, чаще всего используется для доказательства того, что некоторые цепочки не принадлежат КС-языкам.

Следствие 5.3. Язык L, состоящий из цепочек x ⁿy ⁿz ⁿ, не является КС-языком.

Действительно, разделяя эту цепочку на пять частей abgjl, любым возможным способом, мы увидим, что либо agl Ï L, из-за неравного количества символов x, y и z; либо ab ²gj ²l Ï L, из-за перемешивания символов внутри цепочки.

Следствие 5.4. Языки программирования в общем случае не являются КС-языками.

Например, в языках программирования каждая конкретная процедура имеет одно и то же число аргументов в каждом месте, где она упоминается. Можно показать, что такой язык не контекстно-свободен, отобразив множество программ с тремя вызовами одной и той же процедуры на не КС-язык { 0 ⁿ 10 ⁿ 10 ⁿ | n³0 }.

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

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

Дата добавления: 2015-06-27