Контекстно-вільні граматики, висновок,ліво- та правосторонній висновок, дерево розбору

Розглянемо граматику, що виводить усі правильні дужкові послідовності.

[math]"("[/math] і [math]")"[/math] - термінальні символи [math]S[/math] - стартовий нетермінал

  1. [math]S\rightarrow (S)S[/math]
  2. [math]S\rightarrow S(S)[/math]
  3. [math]S\rightarrow \varepsilon[/math]

[math]\boldsymbol\Rightarrow(S)\boldsymbol \Rightarrow(S)(\boldsymbol)S\Rightarrow(S)()\boldsymbol\Rightarrow(\boldsymbol)()\Rightarrow(\boldsymbol(S))() \Rightarrow(S(S)(\boldsymbol))()\Rightarrow(S(S)(\boldsymbol(S)))()\Rightarrow(S(\boldsymbol)((S)))()\Rightarrow( \boldsymbol()((S)))()\Rightarrow(()((\boldsymbol)))()\Rightarrow(()(()))()[/math]

Розглянемо лівий висновок скобкової послідовності з прикладу:

[math]\boldsymbol\Rightarrow (\boldsymbol)S \Rightarrow ((\boldsymbol)S)S\Rightarrow (()\boldsymbol)S\Rightarrow(()\boldsymbol(S))S\Rightarrow(()(\ boldsymbol))S\Rightarrow(()(\boldsymbol(S)))S\Rightarrow(()((\boldsymbol)))S\Rightarrow(()(()))\boldsymbol\Rightarrow(()(( )))(\boldsymbol)S\Rightarrow(()(()))()\boldsymbol\Rightarrow(()(()))()[/math]

Побудуємо дерево розбору дужної послідовності з прикладу.

ліво

Використовуємо індукцію на висоті дерева.

База:Базисом є висота [math]1[/math], найменша з можливих для дерева розбору з термінальною кроною.

Оскільки це дерево є деревом розбору, [math] A \rightarrow \omega[/math] має бути продукцією. Таким чином, [math]A \Rightarrow_ \omega[/math] є однокрокове ліве породження [math]\omega[/math] з [math]A[/math] .

Індукційний перехід:Існує корінь з позначкою [math]A[/math] та синами, відміченими зліва направо [math]X_1X_2 \dots X_k[/math] . Символи [math]X[/math] можутьбути як терміналами, і змінними.

  1. Якщо [math]X_i[/math] — термінал, то визначимо [math]\omega_i[/math] як ланцюжок, що складається з одного [math]X_i[/math] .
  2. Якщо [math]X_i[/math] - змінна, то вона повинна бути коренем деякого піддерева з термінальною кроною, яку позначимо [math] \ omega_i [/math]. Зауважимо, що в цьому випадку висота поддерева менше [math]n[/math], тому до нього застосовується припущення індукції. Отже, існує ліве породження [math] X_i \ Rightarrow^_ \ omega_i [/ ​​math] .

Зауважимо, що [math]\omega = \omega_1\omega_2 \dots \omega_k[/math] . Побудуємо ліве породження ланцюжка [math]\omega[/math] наступним чином:

Почнемо з кроку [math]A \Rightarrow_ X_1X_2\dots X_k[/math] . Потім для [math]i = 1, 2, \dots, k[/math] покажемо, що має місце наступне породження: [math]A \Rightarrow^_ \omega_1\omega_2\dots\omega_iX_X_\dots X_k[/math]

Цей доказ насправді використовує ще одну індукцію, цього разу по [math]i[/math] . Для базису [math]i = 0[/math] ми знаємо, що [math]A \Rightarrow_ X_1X_2\dots X_k[/math] .

Для індукції припустимо, що існує таке породження: [math]A \Rightarrow^_ \omega_1\omega_2\dots\omega_X_iX_\dots X_k[/math]

  1. Якщо [math]X_i[/math] — термінал, то не робимо нічого, але надалі розглядаємо [math]X_i[/math] як термінальний ланцюжок [math]\omega_i[/math]. Отже, приходимо до існування наступного породження. [math]A \Rightarrow^_ \omega_1\omega_2\dots\omega_iX_X_\dots X_k[/math]
  2. Якщо [math]X_i[/math] є змінною, то продовжуємо породженням [math]\omega_i[/math] з [math]X_i[/math] у контексті вже побудованого породження. Таким чином, якщо цим породженням є: [math] X_i\Rightarrow_ \alpha_1 \Rightarrow_ \alpha_2\dots \Rightarrow_ \omega_i[/math] , то продовжуємо наступні породження:
[math]\omega_1\omega_2\dots\omega_X_iX_\dots X_k \Rightarrow_[/math] [math]\omega_1\omega_2\dots\omega_\alpha_1X_\dots X_k \Rightarrow_[/math] [math]\omega_1 dots\omega_\alpha_2X_\dots X_k \Rightarrow_[/math] [math]\dots[/math] [math]\omega_1\omega_2\dots\omega_iX_X_\dots X_k[/math]

Результатом є породження [math]A \Rightarrow^_ \omega_1\omega_2\dots\omega_iX_X_\dots X_k[/math] .

Коли [math]i = k[/math] , результат є ліве породження [math]\omega[/math] з [math]A[/math] .

Уважно розглянемо побудову лівого породження по дереву розбору на доказ теореми. У будь-якому випадку, якщо у двох дерев розбору вперше з'являється вузол, в якому застосовуються різні продукції, ліві породження, що будуються, також використовують різні продукції і, отже, є різними.

[math] \Longleftarrow [/math]

Хоча ми попередньо не описали безпосередню побудову дерева розбору за лівим породженням, ідея його проста. Почнемо будову дерева з кореня, відзначеного стартовим символом. Розглянемо породження покроково. На кожному кроці замінюється змінна, і ця змінна відповідатиме побудованому крайньому ліворуч вузлу дерева, що не має синів, але відзначеному цією змінною. За продукцією, використаною на цьому кроці лівого породження, визначимо, які сини мають бути у цього вузла. Якщо є два різних породження, то першому кроці, де вони різняться, побудовані вузли отримають різні списки синів, що гарантує відмінність дерев розбору.

Вище вже було побудовано дерево розбору слова [math]"(()(()))()"[/math] . Збудуємо ще однедерево розбір для цього слова.

Наприклад, воно виглядатиме так:

правосторонній

Таким чином, існує слово, яке має більше одного дерева розбору в даній граматиці [math]\Rightarrow[/math] ця граматика не є однозначною.

Для доказу достатньо навести однозначну граматику для мови правильних дужних послідовностей (неоднозначною граматикою для цієї мови є граматика з прикладу вище).

[math]"("[/math] і [math]")"[/math] - термінальні символи [math]S[/math] - стартовий нетермінал

  1. [math]S\rightarrow (S)S[/math]
  2. [math]S\rightarrow \varepsilon[/math]

Покажемо, що це граматика однозначна. І тому, використовуючи індукцію, доведемо, що з будь-якого слова [math]\omega[/math] , є правильної скобочной послідовністю, у цій граматиці існує лише одне дерево розбору.

База:Якщо [math]\omega=\varepsilon[/math] , то воно виводиться лише за другим правилом [math]\Rightarrow[/math] для нього існує єдине дерево розбору.

Індукційний перехід:Нехай [math]\left\vert \omega \right\vert=n[/math] і [math]\forall \upsilon[/math] : [math]\left\vert \ upsilon \right\vert \lt n[/math] і [math]\upsilon[/math] - правильна скобкова послідовність, у якої [math]\exists![/math] дерево розбору.

Знайдемо у слові [math]\omega[/math] мінімальний індекс [math]i \neq 0[/math] такий, що слово [math]\omega[0..i][/math] є правильною скобковою послідовністю. Оскільки [math]i \neq 0[/math] мінімальний, то [math]\omega[0..i]=(\alpha)[/math] . З того, що [math]\omega[/math] є правильною скобковою послідовністю [math]\Rightarrow[/math] [math]\alpha[/math] і[math]\beta=\omega[i+1..n-1][/math] - правильні скобочні послідовності, при цьому [math]\left\vert \alpha \right\vert\lt n[/math] і [math]\left\vert \beta \right\vert\lt n \Rightarrow[/math] за індукційним припущенням припущенню у [math]\alpha[/math] і [math]\beta[/math] існують єдині дерева розбору . Якщо ми покажемо, що з частини [math](S)[/math] першого правила можна вивести лише слово [math](\alpha)[/math] , то твердження буде доведено (оскільки з першої частини першого правила виводиться [math] ]\alpha[/math] , та якщо з другої лише [math]\beta[/math] і кожного з них за припущенням існують єдині дерева розбору). Нехай з [math](S)[/math] було виведено частину слова [math]\omega[0..j]=(\gamma)[/math] , де [math]j \lt i[/math] , при цьому [math]\gamma[/math] є правильною скобковою послідовністю, але тоді як мінімальний індекс ми мали вибрати [math]j[/math] , а не [math]i[/math] - протиріччя. Аналогічно з [math](S)[/math] не може бути виведена частина слова [math]\omega[0..j][/math] , де [math]j \gt i[/math] , тому що тоді [math]\omega[0..i]=(\alpha)[/math] не буде правильною скобковою послідовністю, тому що в позиції [math]i-1[/math] баланс дужок буде негативний. Отже, з [math](S)[/math] було виведено частину слова [math]\omega[0..i] \Rightarrow \omega[/math] має єдине дерево розбору [math]\Rightarrow[/math] дана граматика однозначна. Таким чином, для мови правильних дужних послідовностей ми навели приклад як однозначної, так і неоднозначної граматики.

Однак є КС-мови, для яких не існує однозначних КС-граматик. Такі мови і граматики їх породжують називають істотно неоднозначними.