Реферат: LL (k) (-грамматики)

[AK1] <span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">LL(k) —

<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»">Грамматики<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»">.

<span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US">

<span Arial CYR",«sans-serif»;mso-bidi-font-family:«Times New Roman»">Определение

<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">LL(k)<span Arial CYR",«sans-serif»;mso-bidi-font-family:«Times New Roman»">-грамматик.

<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»">Для начала предположим, что

<span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US">G<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">=(N,E,P,S)- <span Arial CYR",«sans-serif»;mso-bidi-font-family:«Times New Roman»">однозначнаяграмматика и <span Arial CYR",«sans-serif»;mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US">w=a<span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US">1<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">,a<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">2...<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">a<span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US">n<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US"> — <span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»">цепочка из <span Arial CYR",«sans-serif»;mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US">L<span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US">(G).<span Arial CYR",«sans-serif»;mso-bidi-font-family:«Times New Roman»">Тогда существует единственная последовательность левовыводимых цепочек <span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">b<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">0<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">,b<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">1<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">..b<span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US">m<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">, <span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»">для которой <span Arial CYR",«sans-serif»;mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US">S<span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US">=b<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">0<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">,b<span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US">i<span Arial CYR",«sans-serif»;mso-bidi-font-family:«Times New Roman»">,<span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US">pi<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US"> Þ<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US"> b<span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US">i<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">+1<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»"> при <span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">0<=i<m<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US"> <span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»">и <span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">a<span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US">m<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">=w. <span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»">Последовательность <span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">p<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»">0<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">p<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">1<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">..p<span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US">m<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">-1<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US"> — <span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»">левый разбор цепочки <span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">w.

<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US"> 

<span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»">Допустим, что мы хотим найти этот левый разбор, просматривая<span Arial CYR",«sans-serif»;mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US">w <span Arial CYR",«sans-serif»;mso-bidi-font-family:«Times New Roman»">одинраз слева направо. Можно попытаться сделать это, строя последовательностьлевовыводимых цепочек <span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US">b<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">0<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">,b<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">1<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">..b<span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US">m<span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»">. Если <span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US">b<span Arial CYR",«sans-serif»;mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US">i<span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US">=a<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">1<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">,a<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">2...<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">a<span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US">j<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">AB, <span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»">то к данному моменту анализа мы ужепрочли первые <span Arial CYR",«sans-serif»;mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US">j <span Arial CYR",«sans-serif»;mso-bidi-font-family:«Times New Roman»">входныхсимволов и сравнили их с первыми <span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US">j<span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»"> символами цепочки <span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">b<span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US">i<span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»">. Было бы желательно определить <span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">b<span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US">i<span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»">+1<span Arial CYR",«sans-serif»;mso-bidi-font-family:«Times New Roman»">,зная только <span Arial CYR",«sans-serif»;mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US">a<span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US">1<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">,a<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">2...<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">a<span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US">j<span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»"> (часть входной цепочки, считанную к данному моменту), несколькоследующих входных символов (<span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US">a<span Arial CYR",«sans-serif»;mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US">j<span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US">+1<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">a<span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US">j<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">+2<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">...a<span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US">j<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">+<span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US">k<span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»"> для некоторого фиксированного <span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">k<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»">)<span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US"> <span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»">и нетерминал <span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US">A<span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»">. <span Arial CYR",«sans-serif»;mso-bidi-font-family:«Times New Roman»">Еслиэти три фактора однозначно определяют, какое правило надо применить дляразвертки нетерминала <span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US">A<span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»">, то<span Arial",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US"> a<span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US">i<span Arial",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US">+1<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»"> точно определяется по <span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">a<span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US">i<span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»"> и <span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US">k<span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»"> входным символам <span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">a<span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US">j<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">+1<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">a<span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US">j<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">+2<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">...a<span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US">j<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">+<span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US">k<span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»"> .<span Arial CYR",«sans-serif»;mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US"> <span Arial CYR",«sans-serif»;mso-bidi-font-family:«Times New Roman»">

<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»">Грамматика, в которой каждый левыйвывод обладает этим свойством, называется

<span Arial CYR",«sans-serif»;mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US">LL<span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US">(k)<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»">-грамматикой. Мы увидим, что для каждой<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">LL<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">(k)-<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»"> грамматики можно построитьдетерминированный левый анализатор, работающий линейное время. Дадим несколькоопределений <span Arial CYR",«sans-serif»;mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US">:

<span Arial CYR",«sans-serif»;mso-bidi-font-family:«Times New Roman»">ОПР

<span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US">:<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US"> <span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»">Пусть <span Arial CYR",«sans-serif»;mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US">a<span Arial CYR",«sans-serif»;mso-bidi-font-family:«Times New Roman»">=<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">xb <span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»">такая левовыводимая цепочка вграмматике <span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">G<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">=(N,E,P,S),<span Arial CYR",«sans-serif»;mso-bidi-font-family:«Times New Roman»">что <span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">xÎ<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">E*, <span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»">а <span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">b<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»"> либо начинается нетерминалом, либопустая цепочка. Будем называть <span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US">x <span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»">законченной частью цепочки <span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">a, <span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»">а <span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">b — <span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»">незаконченной частью частью. Границумежду <span Arial CYR",«sans-serif»;mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US">x <span Arial CYR",«sans-serif»;mso-bidi-font-family:«Times New Roman»">и<span Arial CYR",«sans-serif»;mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US">b <span Arial CYR",«sans-serif»;mso-bidi-font-family:«Times New Roman»">будемназывать рубежом.

<span Arial CYR",«sans-serif»;mso-bidi-font-family:«Times New Roman»">ПРМ

<span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US">:<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US"> <span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»">Пусть <span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">x=abacAaB<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»">, тогда <span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">abac — <span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»">законченная часть цепочки <span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">x, AaB — <span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»">незаконченная часть цепочки. Если <span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">x=abc, <span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»">то <span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">abc — <span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»">законченная часть и е — незаконченная и рубежом служит конеццепочки.

<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»">Иными словами идею

<span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US">LL<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">(k) — <span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»">грамматики можно объяснить так<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">: <span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»">если имеется уже разобранная частьцепочки, то на основании этого и еще нескольких неразобранных символов мы можемсделать вывод о том, какое правило неоюходимо применить. Таким образомграмматика посуществу не зависит (не считая <span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">k <span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»">последующих символов) от того, чтовыводится из незаконченной части цепочки. В терминах деревьев этот процессвыглядит следующим образом<span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US">:<span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»"> дерево вывода цепочки строится начиная с корня идетерминировано сверху вниз.

<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»">Вводят функцию

<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">FIRST(x) — <span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»">возвращающую первых <span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">k<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»"> символов. Обычно приписывают вкачестве индексов <span Arial CYR",«sans-serif»;mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US">k <span Arial CYR",«sans-serif»;mso-bidi-font-family:«Times New Roman»">и<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">G<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US"> — <span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»">количество символов и грамматикасоответственно, но их возможно опускать, если это не вызовет недоразумений.

<span Arial CYR",«sans-serif»;mso-bidi-font-family:«Times New Roman»">ОПР

<span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US">:<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US"> KC-<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»"> грамматика <span Arial CYR",«sans-serif»;mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US">G<span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US">=(N,E,P,S) <span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»">называется <span Arial CYR",«sans-serif»;mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US">LL<span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US">(k)<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»">-грамматикой для некоторогофиксированного <span Arial CYR",«sans-serif»;mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US">k<span Arial CYR",«sans-serif»;mso-bidi-font-family:«Times New Roman»">,если из существования двух левых выводов

<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»">(1)

<span Arial CYR",«sans-serif»;mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US">SÞ<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">wAa`Þ<span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US">wb`a`Þ<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">wx

(2) <span Times New Roman""> 

<span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US">SÞ<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">wAa`Þ<span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US">wc`a`Þ<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">wy

<span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»">для которых

<span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US">FIRST(x)=FIRST(y), <span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»">вытекает что <span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US">b`<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">=c`.

<span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»">Иначе это определение выражает то, что для имеющейся цепочкии зная следующие

<span Arial CYR",«sans-serif»;mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US">k <span Arial CYR",«sans-serif»;mso-bidi-font-family:«Times New Roman»">символовможно применить не более одного правила вывода. Грамматика называется <span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US">LL<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">-<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»"> грамматикой, если она <span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US">LL<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">(k)-<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»"> грамматика для некоторого <span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">k.<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»">

<span Arial CYR",«sans-serif»;mso-bidi-font-family:«Times New Roman»">ПРМ

<span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US">:<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US"> <span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»">Пусть <span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">G<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US"> <span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»">состоит из правил <span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US">S®<span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US">aAS<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">|b, A®<span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US">a<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">|bSA. <span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»">Интуитивно <span Arial CYR",«sans-serif»;mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US">G<span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US"> <span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»">является <span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">LL<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">(1)-<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»"> грамматикой, потому что, коль скородан самый левый нетерминал С влевовыводимой цепочке и следующий входной символ с, существует не более одного правила, применимого к С и приводящего к терминальной цепочке,начинающейся символом с. Переходя копределению <span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">LL<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">(1)-<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»"> грамматики, мы видим,<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US"> <span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»">что<span Arial",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US"> <span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»">если<span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US"> <span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">SÞ<span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US">wSa`Þ<span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US">wb`a`Þ<span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US">wx<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US"> <span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»">и <span Arial CYR",«sans-serif»;mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US">SÞ<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">wSa`Þ<span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US">wc`a`Þ<span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US">wy<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US"> <span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»">и цепочки <span Arial CYR",«sans-serif»;mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US">x<span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US"> <span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»">и <span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">y<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US"> <span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»">начинаются одним и тем же символом, тодолжно быть <span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">b`<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">=c`<span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»">. В данном случае если <span Arial CYR",«sans-serif»;mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US">x<span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US"> <span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»">и <span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">y<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US"> <span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»">начинаются символом <span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US">a<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">, <span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»"> то в выводе участвовало правило <span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US">S®<span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US">aAS<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US"> <span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»">и <span Arial CYR",«sans-serif»;mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US">b`<span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US">=c`=aAS. <span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»">Альтернатива <span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US">S®<span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US">b<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US"> <span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»">здесь невозможна. С другой стороны,если <span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">x<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US"> <span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»">и <span Arial CYR",«sans-serif»;mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US">y<span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US"> <span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»">начинаются с <span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">b<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»">, то должно применяться правило <span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US">S®<span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US">b<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US"> <span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»">и <span Arial CYR",«sans-serif»;mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US">b`<span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US">=c`=b. <span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»">Заметим, что случай <span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US">x<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">=y=e<span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»"> <span Arial CYR",«sans-serif»;mso-bidi-font-family:«Times New Roman»">здесьневозможен, так как из <span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">S<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US"> <span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»">в грамматике <span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US">G<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US"> <span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»">не выводится <span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US">e<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">.

<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»">Когда рассматриваются два вывода

<span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US">SÞ<span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US">wAa`Þ<span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US">wc`a`Þ<span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US">wy<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US"> <span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»">рассуждение аналогично. Грамматика <span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US">G<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»"> служит примером так называемой простой<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">LL<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">(1)-<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»"> <span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»">грамматики (или разделенной грамматики)<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">.

<span Arial CYR",«sans-serif»;mso-bidi-font-family:«Times New Roman»">ОПР

<span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US">:<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US"> <span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»">КС-грамматика <span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US">G<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">=(N,E,P,S)<span Arial CYR",«sans-serif»;mso-bidi-font-family:«Times New Roman»"> без <span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">e<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»">-правил называется простой <span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">LL<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">(k) <span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»">-<span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US"> <span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»">грамматикой (<span Arial",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US"> <span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»">или разделенной грамматикой<span Arial",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US"> <span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»">), если для каждого <span Arial CYR",«sans-serif»;mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US">AÎ<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">N<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»"> все его альтернативы начинаютсяразличными терминальными символами.      <span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">

<span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US">

<span Arial CYR",«sans-serif»;mso-bidi-font-family:«Times New Roman»">Предсказывающиеалгоритмы разбора.

<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»">Разбор для

<span Arial CYR",«sans-serif»;mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US">LL<span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US">(k)<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»">-грамматики очень удобно осуществлять спомощью так называемого <span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">k- <span Arial CYR",«sans-serif»;mso-bidi-font-family:«Times New Roman»">предсказывающего<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»"> алгоритма разбора. <span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">k<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»">-предсказывающий алгоритм используетвходную ленту, магазин и выходную ленту. Алгоритм пытается проследить выводцепочки, записанной на его входной ленте. При чтении анализируемой цепочкивходная головка может <span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US">«<span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»">заглядывать<span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US">»<span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»"> вперед на очередные <span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">k<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»"> символа. Эти символы называют аванцепочкой. Алгоритм имеет конфигурацию представляемую тройкой<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">  (x,Xa,n), <span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»">где

<span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US">x    

<span Arial CYR",«sans-serif»;mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US">- <span Arial CYR",«sans-serif»;mso-bidi-font-family:«Times New Roman»">неиспользованнаячасть входной цепочки<span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US">

<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">Xa  —

<span Arial CYR",«sans-serif»;mso-bidi-font-family:«Times New Roman»">цепочка вмагазине и Х — верхний символ<span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US">

<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">n

<span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US"> <span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»">  <span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">   — <span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»">цепочка на выходной ленте<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">

<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»">Работой

<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">k- <span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»">предсказывающего алгоритма руководитуправляющая таблица, которая задает соответствие между множеством

<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">{

<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»">(верхний символ магазина)Х(аванцепочка)<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">}<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»">

<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»">и множеством

<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">{(

<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»">правая часть правила  и его номер<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">)<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">|<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»">ошибка<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">|<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»">выброс<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">|<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»">допуск<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">}<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»">.

<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»">Алгоритм является корректным дляграмматики, если для любой цепочки из этой грамматики алгоритм позволяетполучить упорядоченный список правил для ее разбора. Если работой некоегоалгоритма руководит какая-то таблица и этот алгоритм оказывается корректным длярассматриваемой грамматики, то таблицу называют корректной.

<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">

<span Arial CYR",«sans-serif»;mso-bidi-font-family:«Times New Roman»">ПРМ

<span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US">:<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">

<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»">Пусть дана грамматика с правилами

<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">:

(1) <span Times New Roman""> 

<span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US">S®<span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US">aAS<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">

(2) <span Times New Roman""> 

<span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US">S®<span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US">b<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">

(3) <span Times New Roman""> 

<span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US">A®<span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US">a<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">

(4) <span Times New Roman""> 

<span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US">A®<span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US">bSA<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">

<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»">Для такой грамматики будет построенатаблица

<span Arial CYR",«sans-serif»;mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US">:

<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">

<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»">аванцепочка

<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">

<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">                            

<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»">            <span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US">a<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">                      b                      e

<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»">верхний                        

<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">S         aAS,1             b,2<span Arial CYR",«sans-serif»;mso-bidi-font-family:«Times New Roman»">                  <span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»">ошибка

<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»">символ

<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">   <span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»">            <span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US">A<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">         a,3                   bSA,4<span Arial CYR",«sans-serif»;mso-bidi-font-family:«Times New Roman»">             <span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»">ошибка<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">

<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»">магазина

<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">            a          <span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»">выброс          ошибка          ошибка<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">

<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">                

<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»">            <span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US">b<span Arial CYR",«sans-serif»;mso-bidi-font-family:«Times New Roman»">          <span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»">ошибка          выброс          ошибка<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">

<span Arial CYR",«sans-serif»;mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US">           

<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»">            <span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US">$<span Arial CYR",«sans-serif»;mso-bidi-font-family:«Times New Roman»">          <span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»">ошибка          ошибка          допуск

<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»">По такой таблице будет проведен анализ

<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">:<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»">

<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">(abbab,S$,e)     |-(abbab,aAS$,1)

<span Arial CYR",«sans-serif»;mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US">|-( bbab,AS$,1)

<span Arial CYR",«sans-serif»;mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US">|-( bbab,bSAS$,14)

<span Arial CYR",«sans-serif»;mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US">|-( bab,SAS$,14)

<span Arial CYR",«sans-serif»;mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US">|-( bab,bAS$,142)

<span Arial CYR",«sans-serif»;mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US">|-( ab,AS$,142)

<span Arial CYR",«sans-serif»;mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US">|-( ab,aS$,1423)

<span Arial CYR",«sans-serif»;mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US">|-( b,S$,1423)

<span Arial CYR",«sans-serif»;mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US">|-( b,b$,14232)

<span Arial CYR",«sans-serif»;mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US">|-( e,$,14232)

<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">k-

<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»">предсказывающий алгоритм разбораКС-грамматики <span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">G<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»"> можно моделировать надетерминированном МП- преобразователе с концевым маркером на входной ленте. Таккак входная головка МП- преобразователя может обозреть только один входнойсимвол, аванцепочка должна храниться в конечной памяти управляющего устройства.Остальные детали моделирования очевидны.<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">

<span Arial CYR",«sans-serif»;mso-bidi-font-family:«Times New Roman»">ТРМ

<span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US">:<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US"> <span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»">Пусть А — <span Arial CYR",«sans-serif»;mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US">k-<span Arial CYR",«sans-serif»;mso-bidi-font-family:«Times New Roman»">предсказывающий алгоритм разбора для КС-грамматики <span Arial CYR",«sans-serif»;mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US">G<span Arial CYR",«sans-serif»;mso-bidi-font-family:«Times New Roman»">.Тогда существует такой детерминированный МП- преобразователь, который позволяетразобрать любую цепочку из этой грамматики. Иначе говоря можно промоделироватьлюбой алгоритм на указанном преобразователе.

<span Arial CYR",«sans-serif»;mso-bidi-font-family:«Times New Roman»">СЛВ

<span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US">:<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US"> <span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»">Пусть А — <span Arial CYR",«sans-serif»;mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US">k-<span Arial CYR",«sans-serif»;mso-bidi-font-family:«Times New Roman»">предсказывающий алгоритм разбора для КС-грамматики <span Arial CYR",«sans-serif»;mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US">G<span Arial CYR",«sans-serif»;mso-bidi-font-family:«Times New Roman»">.Тогда для <span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US">G<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US"> <span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»">существует детерминированный левыйанализатор.<span Arial CYR",«sans-serif»;mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US">

<span Arial CYR",«sans-serif»;mso-bidi-font-family:«Times New Roman»">

<span Arial CYR",«sans-serif»;mso-bidi-font-family:«Times New Roman»">Следствияопределения

<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">LL(k)<span Arial CYR",«sans-serif»;mso-bidi-font-family:«Times New Roman»">-грамматики.

<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»">Покажем что для каждой

<span Arial",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US">LL(k)<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»"> грамматики можно механически построитькорректный <span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US">k-<span Arial CYR",«sans-serif»;mso-bidi-font-family:«Times New Roman»">предсказывающий алгоритм разбора. Так как ядром алгоритма является управляющаятаблица, надо показать, как строить по грамматике такую таблицу. Для этоговыведем некоторые следствия определения <span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US">LL<span Arial",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US">(k)-<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»"> грамматики.

<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»">В определении

<span Arial",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US">LL<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">(k)-<span Arial CYR",«sans-serif»; mso-bidi-font-family:«Times New Roman»"> грамматики утверждается, что дляданной выводимой цепочки <span Arial",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US">wAa <span Arial CYR",«sans-serif»;mso-bidi-font-family:«Times New Roman»">цепочка<span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US">w <span Arial CYR",«sans-serif»;mso-bidi-font-family:«Times New Roman»">инепосредственно следующие за ней <span Arial",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US">k<span Arial CYR",«sans-serif»;mso-bidi-font-family: «Times New Roman»"> входных
еще рефераты
Еще работы по программированию, базе данных