Содержание к диссертации
Введение
Глава 1. Контекстные условия в языках программирования 72
1. Определение и классификация контекстных условий... -/2
2. Неадекватность КС-грамматик для описания полного синтаксиса языков программирования /7
3. Некоторые способы формального описания контекстных условий
4. Методы анализа контекстных условий 32
Глава II . ЛКУ-грамматики и их модификация 36
1. ЛКУ-грамматики 36
2. Модифицированные ЛКУ-грамматики 47
3. Применение модифицированных ЛКУ-грамматик вб
Глава ІІІ. Методы' анализа языков, порождаемых модифицированными ЛКУ-грамма тиками 83
1. Методика модификации синтаксических анализаторов для МЖУ-языков 53
2. Модификация і и-)-анализатора 66
3. Модификация анализатора Эрли ^
4. Оценка эффективности модифицированных анализаторов. 8 К
Заключение до
Приложение 1 92
Приложение 2 gg
Литература
- Неадекватность КС-грамматик для описания полного синтаксиса языков программирования
- Некоторые способы формального описания контекстных условий
- Модифицированные ЛКУ-грамматики
- Модификация і и-)-анализатора
Введение к работе
Формально, язык программирования - это множество текстов, записанных с помощью некоторого набора символов - алфавита языка. Содержательно, т.е. по существу, язык программирования - это средство общения между человеком и электронными вычислительными машинами (ЭВМ). К настоящему времени разработаны и реализованы сотни различных языков программирования. Хотя эти языки программирования определяются разными способами, обычно определение языка сводится к определению его внешней, текстуальной стороны и внутренней, смысловой стороны.
Система правил, определяющих внешнюю текстуальную сторону языка, называется синтаксисом, а система правил, определяющих внутреннюю, смысловую сторону языка, называется семантикой данного языка. Следует отметить, что синтаксические ошибки, т.е. нарушения синтаксических правил, мы можем обнаружить без выполнения программ, а семантические ошибки обнаруживаются только при выполнении программы на ЭВМ. Например, правило, согласно которому в каждом блоке без внутренних блоков никакой идентификатор нельзя описывать более одного раза, является синтаксическим правилом и мы можем обнаружить нарушение этого правила без выполнения.программы. Рассмотрим следующее арифметическое выражение Алгола-60: В/(А- 5). Если в момент вычисления этого выражения значение Д оказалось равным 5, то данное выражение оказалось бессмысленным, и его значение не может быть вычислено. Эта ошибка является семантической^ очевидно, что данную ошибку либо очень трудно, либо вообще невозможно обнаружить при анализе программы.
С самого начала появления сложных языков програмирования стало уделяться большое внимание проблеме их точного описания, и
-4-для этого используются разные математические средства. Среди них наибольшей популярностью пользуется аппарат форм Бэкуса - Наура (БШ). Большинство синтаксических правил языков программирования высокого уровня описывается с помощью (расширенной) БНФ, но некоторые синтаксические свойства, называемые контекстными условиями, языков программирования описываются неформально, с помощью естественных языков ((3), С4),а?),Ш),С20;],т),30),134} ). При этом трудно обеспечить их точное и единственное понимание из-за неоднозначности естественных языков. Для пояснения смысла описываемых условий приводятся примеры» То есть, контекстные условия задаются с помощью естественных языков и примеров. Этот метод обладает очевидными недостатками. Отсутствие средств формального описания контекстных условий не позволяет, в частности, предложить точный и формальный алгоритм построения синтаксических анализаторов для языков программирования. Это обстоятельство, в свою очередь, затрудняет создание синтаксически ориентированных трансляторов и метатрансляторов, т.е. программ, автоматически вырабатывающих трансляторы по информации о синтаксисе и семантике входных и выходных языков. Поэтому разработка общепринятого формализма для описания полного синтаксиса языков программирования, под которым мы будем понимать совокупность синтаксических правил, описываемых КС-средствами, и контекстных условий, и соответствующих методов их анализа имеет важное значение с практической и теоретической точки зрения. Настоящая работа посвящена этим вопросам.
Полный синтаксис языка Алгол-68 был определен так называемой ^/^грамматикой или двухуровневой грамматикой С 53, С323). W -грам, матика, по существу, состоит из двух связанных друг с другом грамматик. Комбинация этих двух грамматик позволяет вывести в
- b-принципе бесконечное множество синтаксических правил. Имея бесконечное множество КС-правил,удаєтея определить полный синтаксис языков программирования. Но W-грамматики обладают излишне большой порождающей мощностью, что затрудняет разработку анализаторов для языков, порождаемых этими грамматиками.
Для определения полного синтаксиса языков программирования были предложены и другие формализмы ((22), С24),СЗЗЛ, но каждый из них обладает определенными недостатками. Поэтому проблема разработки методов описания полного синтаксиса этих языков пока еще не решена в полной мере,
В (113 были предложены так называемые грамматики с локальными контекстными условиями (ЖУ-грамматики), учитывающие практические действия, предусмотренные для проверки контекстных условий в трансляторах. ЛКУ-грамматики представляются в виде КС-грамматик с дополнительными условиями, которым должен удовлетворять каждый правильный вывод. Эти дополнительные условия отражают контекстные условия языков програмирования естественным образом. ЛКУ-грамматики удобнее и проще других способов описания контекстных условий. КС-грамматики, определяющие языки программирования без контекстных условий, легко преобразуются в ЛКУ-грамматики. Однако ЛКУ-грамматиками описываются только контекстные условия первого и второго типов. Поэтому представляют интерес модификация ЛКУ-грамматик, целью которой является разработать грамматики, позволяющие описать все контекстные условия языков программирования, и разработка соответствующих методов анализа. Этим вопросам посвящены главы П и Ш.
Хотя контекстные условия языков программирования относятся к синтаксису языка, многие формализмы(например, w-грамматики и атрибутные грамматики), предложенные для их описания, приме-
нимы и для формального определения семантики этих языков. Но мы не будем рассматривать проблемы, связанные с семантикой, так как нашей целью является разработка простой и практичной методики описания полного синтаксиса языков программирования и соответствующих методов их анализа.
Приведем необходимые определения. Алфавитом называется непустое конечное множество символов. Пусть _ -алфавит. Цепочкой над алфавитом , называется последовательность символов этого алфавита. Цепочка, не содержащая ни одного символа, называется пустой цепочкой и обозначается через Л . Длина цепочки - это число символов в ней. Длина цепочки со обозначается через \со\ . Очевидно,что |Л|= 0.
Языком над алфавитом 2 называется множество цепочек над 21 Пустое множество обозначается через 0 . Обозначим через 2.* множество, содержащее все цепочки над алфавитом X » включая Л . Каждый язык над Z. является подмножеством множества Z* Множество всех цепочек над , за исключением Л , обозначается через Z.*
Грамматика - это математическая система, определяющая язык. Одновременно она может являться средством, которое придает цепочкам языка полезную структуру. Порождающей грамматикой называется четверка объектов
где \^~ конечное множество терминальных символов;
уА- конечное множество нетерминальных символов,VrГ) \/д =ф \ - начальный символ или аксиома грамматики, S&Va і р - конечное множество правил вида ^ -* ? , где
Причем правила из р называются правилами вывода грамматики Gr .
- * -
Будем считать, что цепочка СО-j непосредственно выводима из цепочки 0Оо в грамматике Or , и обозначать это отношение через со0=?сои если &>0 = кт1=г , у=^г, где ^г, ^,^е (\ZtVVa ), ^Є ( Vr О Va ) и Р содержит правило -*-/ . Будем писать со0 ==> оОу, , если существует последовательность цепо-чек Со01 cu1t...t (Оці 1^1) такая, что <>6 -==^(0.^ 1 для t =0, 1,..., /7 -1. В этом случае последовательность со0, , СОп называетея выводом, и говорят, что СОп выводима из С0о . Часто вместо и?о ~=^> (Of и со0 =& оо„ будем писать просто CQ0=P-Ci)
Совокупность терминальных цепочек грамматики Cr , выводимых в ней из начального символа, называется языком, порождаемым этой грамматикой, и обозначается через 1— ( <к ), т.е.
Одной из основных проблем, связанных с практическим применением грамматик, является проблема распознавания. Эта проблема разрешима, если существует такой алгоритм, который за конечное число шагов дает ответ на вопрос, входит ли произвольная цепочка терминальных символов некоторой грамматики в язык, порождаемый этой грамматикой. Если такой алгоритм существует, то язык называется распознаваемым. Если число шагов алгоритма распознавания зависит от длины цепочки и может быть оценено до выполнения алгоритма, язык называется легко распознаваемым. Естественно, что представляют практический интерес лишь те грамматики, которые порождают распознаваемые языки.
Грамматика называется неукорачивающей, если для любого ее правила вывода ^-^ справедливо неравенство |^|4 j 7\ . В 19J доказано, что язык L СйО , порождаемый неукорачивающей грамматикой Cf , легко распознаваем.
- 8 -Рассмотрим несколько грамматик, более удобных для практического использования. Грамматикой непосредственных составляющих (НС-грамматикой) называется неукорачивающая грамматика с правилами вывода вида
где %А, %ze{ VrU \JAf, AVA ,Є ( VtUVa? . Каждое правило вывода НС-грамматики указывает подстановку некоторой цепочки вместо нетерминального символа. Однако, возможность реализации подстановки зависит от символов, окружающих заменяемый, или, как часто говорят, от контекста, в котором находится заменяемый символ. По любой неукорачивающей грамматике можно построить НС-грамматику, порождающую тот же язык ( 14} ). Такую грамматику будем называть эквивалентной исходной. Классы грамматик будем называть эквивалентными, если порождаемые ими классы языков совпадают.
Контекстно-свободной или бесконтекстной грамматикой (КС-грамматикой) называется неукорачивающая грамматика с правилами вывода вида /\~>~?1 , где /\ - нетерминальный символ, а 7 - произвольная непустая цепочка над VrU\^« Из определения очевидно, что любая КС-грамматика является одновременно и НС-грамматикой. Поэтому класс КС-».грамматик входит в класс НС-грамматик.
Укорачивающей контекстно-свободной грамматикой (УКС-грамма-тикой) называется грамматика, имеющая правила того же вида, что и КС-грамматика, но цепочка может быть и пустой. Таким образом, этот класс грамматик не входит в класс неукорачивающих грамматик. По любой УКС-грамматике можно построить почти эквивалентную ей КС-грамматику. Почти эквивалентной грамматикой мы будем называть такую, которая порождает тот же язык, что и исходная грамматика, за исключением пустой цепочки. Так как определить,
- g -
входит ли пустая цепочка в язык, порождаемый УКС-грамматикой, не представляет труда, последние порождают легко распознаваемые языки. УКС-грамматики представляют интерес потому, что именно они используются для описания синтаксиса языков программирования.
Автоматной грамматикой (А-грамматикой) навивается грамматика с правилами вывода вида Д-^ЬВ и А -* b , гДе А » В 6 Va , b Vy Автоматные грамматики используются, в основном, при предварительном преобразовании программ, с целью их представления в форме, более удобной для дальнейшего анализа.
Конечный ориентированный граф (Х,И ), где X - множество его вершин, a U частичное отображение X в X і определяющее дуги, называется деревом, если
у него имеется одна вершина, в которую не входит ни одна дуга; эту вершину будем называть корнем дерева;
в каждую из его остальных вершин входит лишь одна дуга;
он не содержит контуров.
Из корня дерева в любую его вершину ведет ровно один путь. Назовем уровнем вершины дерева длину такого пути, т.е. число составляющих его дуг. Будем считать, что корень дерева имеет уровень 0. Высотой дерева называется наибольший уровень его вершин. Если в дереве существует путь из вершины ЭС'ь в вершину X.J. , то говорят, что вершина Х.0 предшествует вершине ОСф , а ЭСф. следует за ЭСЬ . При этом очевидно, что вершина уровня Y] следует ровно за одной вершимой каждого из уровней Л-1, П-2,...,0. Вершины, не предшествующие никаким вершинам дерева, т.е. не имеющие выходящих из них дуг, называются заключительными, а все остальные - незаключительными вершинами дерева.
Пусть в КС-грамматике имеется некоторый вывод &0, co1f...t CDп . По этому выводу можно однозначно построить синтаксическое
-10-дерево вывода, в котором незаключительные вершины соответствуют нетерминальным символам грамматики, а заключительные - терминальным символам.
Вывод в КС-грамматике называется левосторонним (правосторонним), если правила вывода применяются к самому левому(правому) вхождению нетерминального символа каждой цепочки вывода. Очевидно, что по любому выводу в произвольной КС-грамматике можно построить эквивалентный ему (т.е. порождающий ту же цепочку) левосторонний (правосторонний) вывод. Поэтому для любой цепочки языка существует левосторонний (правосторонний) вывод этой цепочки в порождающей язык КС-грамматике.
КС-грамматика называется неоднозначной, если в грамматике существует более чем один левосторонний вывод некоторой терминальной цепочки, а язык, порождаемый такой грамматикой, называется синтаксически неоднозначным. Язык, все порождающие КС-грамматики которого неоднозначны, называется существенно синтаксически неоднозначным.
Анализатором для некоторой грамматики мы будем называть такой алгоритм, который для любой терминальной цепочки устанавливает за конечное число шагов, принадлежит ли цепочка языку, по-рожаемому данной грамматикой, и если да, то распознает синтаксическую структуру данной терминальной цепочки в терминах порождающих правил грамматики. Говорят, что анализатор работает по принципу "снизу вверх", если он пытается сводить терминальную цепочку к начальному символу грамматики. Говорят, что анализатор работает по принципу "сверху вниз", если он пытается получить терминальную цепочку из начального символа грамматики.
Работа состоит из введения, трех глав, заключения и приложений. В главе 1 рассматриваются контекстные условия языков програм-
- л -
мирования в общем виде. Далее глава содержит обзор методов формального описания контекстных условий (программные грамматики, W -грамматики, атрибутные грамматики,V -подход и НС-грамматики). Там указаны как достоинства, так и недостатки этих методов. Потом рассматриваются практические методы анализа контекстных условий, используемые в трансляторах.
Неадекватность КС-грамматик для описания полного синтаксиса языков программирования
Как выше сказано, еще не существует общепринятого формализма для описания полного синтаксиса языков программирования, и контекстные условия обычно задаются естественными языками. Конечно, было бы удобно, чтобы все синтаксические правила языков программирования описывались средствами КС-грамматик. Но, к сожалению, это невозможно.
Теперь рассмотрим модель языка программирования и докажем, что невозможно описать ее КС-средствами. КС-частью модели может служить язык LKC={XiCt; ХгСгі Ч Х»Сп X -fL X"} На язык Lice мы будем налагать следующие ограничения: 1. Xi Хф , когда lA ф ; 2. X , Х"Є{ Ь";,Хи} 3 CirCj., когда X =Xi и X = X-j. Каждое ограничение отражает контекстные условия соответствующего типа. Ограничение 3, конечно, отражает только частный случай контекстных условий третьего типа. Таким образом, налагая ограничения 1, 2 и 3 на язык LKC t мы получаем модель языка программирования. Обозначим ее через Lpr . Очевидно, что L?yCLKC
Перейдем теперь к доказательству того, что язык Lp нельзя описывать с помощью КС-грамматик. Теорема 1. Язык Lpy не является КС-языком.
Доказательство. Используем следующуу лемму из 13} : Для каждой КС-грамматики Сг существуют числа р и $. , такие, что каждая цепочка ZeLC , где Zj p , может быть представлена в виде Z=XUlfr??-y так, что LLV- Л t\uwv-\4t 18 и для всякого }l X.UL lfrV ZyG.Ltb )
Пусть Lpr есть КС-язык, Cr -. порождающая его КС-грамматика и р , g, - числа из леммы. Возьмем цепочку Z6 L f где \Z\ Р .Ее можно представить в виде XilW-V-Ц f где LLV- \ \ииг&т Ь и Хбб г - yeLp для всех - 1. Мы докажем, что ни одна из цепочек л:, , , "2Л, У не содержит вхождения символа . , что противоречит определению языка l_p r
1) Предположим, что цепочка X содержит вхождение символа . Поскольку ULV X , цепочки ( и/или 2 содержат хотя бы одно вхождение символа из цепочки X" . При этом со = XUlz,&?-Z?-lzlУф LpY , потому что СО не удовлетворяет ограничению 2: х" / XJ при (,= 1,2,...., Л .
2) Предположим, что или V содержит вхождение символа . Тогда сразу очевидно, что XILW V Уфі-ру , так как всякая цепочка из Lpy содержит только одно вхождение символа -&.
3) Предположим, что ТО или У содержит вхождение символа &. При этом рассмотрим только цепочку \JL , потому что для цепочки If тоже можно сказать подобное. (1) Пусть цепочка it содержит только символы из цепочки X . Тогда, как в случае 1, цепочка XUIZZ02/-IZI$ не удов летворяет ограничению 2. Поэтому XUlz їО-ТГ1 Уф Lpy (2) Пусть цепочка U содержит только символы из цепочки X;, , где 1 . І П . Тогда для цепочки ze L?r, где Xi= X и \Z\ p , XUzW-V-z4$Lp y , потому что XUzZO-V-zy не удовлетворяет ограничению 2. (3) Пусть цепочка It содержит только символы из цепочки С-и, где Uu4« . Тогда для цепочки Z& L рҐ , где %= х и \Z\ p , цепочка XUz№V-Z(e$. Lpy , потому что - 19-она не удовлетворяет ограничению 3. (4)
Пусть цепочка и содержит символ ";". Если Ц = С ; или U=l X , где CQCL , XQXL » то очевидно, что X,UZ2J V-Z У L кс .Поэтому хигг 2 гв$ L Для всех остальных вариантов цепочки 66 Xtl U Lpf при - 3, так как эта цепочка не удовлетворяет ограничению 1. Итак, теорема доказано.
Впервые неадекватность КС-грамматик для полного синтаксического описания языка Алгол-60 была показана в 393 . Доказательство подобного факта содержится и в 17 и в ряде других публикаций. Однако, в связи с удобством и простотой описания языков программирования КС-грамматиками и наличием для КС-языков эффективных анализаторов, одной из основных тенденций является описание контекстных условий с помощью дополненных и обобщенных КС-грамматик ( 6} , 97, 157, 29}и др.). В следующем параграфе дается обзор некоторых способов описания контекстных условий. Большинство этих способов построено на основе КС-грамматик.
Некоторые способы формального описания контекстных условий
Представляет интерес разработка таких способов формального описания контекстных условий, которые, во-первых, базировались бы на КС-грамматиках, широко применяемых при описании языков программирования, и, во-вторых, позволяли бы при проверке контекстных условий использовать таблицы. Одним из методов такого рода является грамматика с локальными контекстными условиями (ЛКУ-грамматика). ЛКУ-грамматики представляют достаточно удобный аппарат для описания контекстных условий первого и второго типов ( С9) , C1U ).
Прежде чем перейти к определению ЛКУ-грамматик, выделим из множества нетерминальных символов КС-грамматик два подмножества - множество контекстных символов и множество локализаторов. Нетерминальный символ называется контекстным, если его терминальные порождения могут находиться в двух позициях - в позиции определяющего и в позиции использующего вхождений. Формальное задание областей действия требует отдельно рассматривать некоторые символы, имеющие смысл блока языка Алгол-60. Такие символы называются локализаторами.
Для каждого терминального порождения любого контекстного символа нужно проверять контекстное условие некоторого типа в зависимости от его позиции. Обычно такая проверка ведется отдельно после порождения терминальной цепочки с помощью КС-грамматик. Но для формализации задания контекстных условий удобнее включить действия, связанные с их проверкой, в сам процесс вывода нетерминальной цепочки. Такая идея реализована на ЛКУ-грамматиках. ЛКУ-грамматикой будем считать пятерку следующих объектов: где \у - конечное множество терминальных символов; \/. - конечное множество нетерминальных символов; V =V v U Vc U VL. , V : множество бесконтекстных символов, Vc множество контекстных символов, VLI множество локализаторов, 5 - начальный символ грамматики; р - конечное множество правил вывода вида А - в гДе AzvA, kecvTuvAy;
М0- соответствие, установленное между элементами множеств Vc и VT\"C-A} » т»е конечное (возможно, пустое) множество пар {А , X ), где AeVc » Х.Є\/т\іЛ} . Контекстные символы в правых частях правил вывода могут находиться в двух позициях. Определяющие вхождения контекстных символов будем выделять надстрочным символом . Будем считать, что из контекстных символов не выводятся цепочки, содержащие контекстные символы, а также пустые цепочки.
Пусть W Vc Через М0СЮ будем обозначать подмноже-ство множества VTVf А} , состоящее из всех образов элементов из U/
Любой обобщенный левосторонний вывод в ЛКУ-грамматике можно разбить на четыре этапа. На первом этапе правила вывода применяются к бесконтекстным символам. Затем на втором этапе правила применяются к определяющим вхождениям контекстных символов и их потомкам. На третьем этапе вывода правила применяются к исполь зующим вхождениям контекстных символов. Наконец, на четвертом этапе правила применяются к локализаторам.
Определим понятие вывода в ЖУ-грамматике, удовлетворяющего контекстным условиям. При его выполнении, кроме применений правил, на некоторых шагах требуется проверять, входят ли порожденные из контекстных символов терминальные цепочки в подмножества МОіЛіУ) » где М - некоторое переменное соответствие, а Аь -контекстные символы, 1= 1, 2,..., у\ . Поскольку ЖУ-грамма-тика предназначена для описания языков, имеющих локальные области действия, для каждой такой области нужно определить свои переменные соответствия. Каждое переменное соответствие должно задаваться в момент, когда начинается вывод подцепочки, определяющей локальную область действия, т.е. при применении правила вывода к локализатору. При проверке контекстных условий это соответствие должно учитываться до окончания вывода подцепочки, т.е. до того момента, пока не будет применено правило вывода к другому локализатору, не являющемуся потомком данного.
Переменное соответствие, которое задается при применении правила вывода к локализатору L , обозначим через Mj,. Через АпсСсО обозначим минимальную область действия, в которой находится вхождение оС . Сначала установим Мь= 0
Модифицированные ЛКУ-грамматики
Будем считать, что реализованная на третьем этапе вывода замена использующего вхождения контекстного символа А терминальной цепочкий удовлетворяет контекстным условиям, если директивы, находящиеся налево и направо от А , выполняются и в случае ПРО получается положительный результат, т.е. Ьииг . После выполнения директивы исключаются из цепочки вывода. В цепочке вывода налево от использующего вхождения контекстного символа А находится директива ЗАЛ и направо - ПРО, соответствующая этому А . При этом между А и соответствующей ему ПРО может быть находится подцепочка данной цепочки вывода. Если успешно выполняется ЗАП, то данное использующее вхождение удовлетворяет контекстному условию второго типа. Положительный реузльтат директивы ПРО означает удовлетворение контекстного условия третьего типа.
Будем считать, что обобщенный левосторонний вывод в 6гм удовлетворяет контекстным условиям, если все реализованные в нем замены определяющих и использующих вхождений контекстный символов терминальными цепочками удовлетворяют контекстным условиям и после успешного выполнения всех директив магазин К содержит только # .
Язык, порождаемый модифицированной ЛКУ-грамматикой, определим как множество терминальных цепочек, для каждой из которых существуем обобщенный левосторонний вывод из начального символа грамматики, удовлетворяющий контекстным условиям.
Приведем пример модифицированной ЛКУ-грамматики и вывода в ней. Пример.4. Рассмотрим следующую грамматику. \//у = { программа , части , :часть , описание , тип , гоператор , буква , переменная , :идент , выражение)}, Vc ={ имя ]. , \/ь={ блок ]- ,Vx={ n J-» = программа і Мо = 0 , у={ЗАП, ЗАП (U), ЗАП (/V), ИСК, ИСК(/У,М), ПРО, ПРО ( = М ) . Рассмотрим директивы с параметрами. ЗАЩ U ): объединение верхних двух элементов магазина Z , т.е. последний элемент и предпоследний элемент -9- последний элемент. Например, если до выполнения директивы ЗАП(и) в Z содержалась цепочка Хиел л гшх# то после выполнения этой директивы в Z останется jtiifajfyen и jvza Р ЗАП( /V ): запись вида А/ в магазин Z ИСК (/V ,М ): если N настоящий критерий, то он исключается и на его место в магазин записывается М (в противном случае ничего не происходит). ПРО ( =М ): проверка идентичности верхнего элемента магазина Я и М . В случае идентичности результатом выполнения является JJUAJL , а в противном случае - $ал#. . р содержит следующие правила: 1) программа .. = блок 2) блок .:= &г $і+і С части &nd 3) части ::гг части ; ічасть часть 4) часть :;= описание іоператор блок 5) іописание ::= огип имя 6) тип ::= лпЯщ&і \ лгхл 7) оператор :: = переменная?- .= :выражение ИСК {Ш іилгаі.пейН) ЗАП( jteai )ЗАП( U ) ПРО ИСК 8) гпеременная :: = ЗАП имя 9) выражение :: = выражение + переменная ПРО (=МьСё#&?:илеа) ЗАП(и)) выражение - переменная ПРО (= Jnteg iU лед) ЗАП ( U) J переменная ПРО (= Ьн&длг 10) имя -.:= :идент 11) :идент ::= г.буква 4буква идент 12) :6yKBa :.- = a/bJ---/Z
Результат операций + и « целый, если оба операнда - целого вида, и вещественный в противном случае. Переменная и выражение оператора должны быть идентичного вида, но допускается использование переменной вещественного вида с выражением целого вида. Рассмотрим процесс вывода цепочки jj qpn Jtzxx CLj яжл bj Лие%? с J CL .zzb-C &nd с помощью этой грамматики. Множества М( :имя ) и М совпадают, так как 4.имя является единственным контекстным символом. 0)0- оірограмма Щ= &&& гчасти &nd Сд= &&#( :части s :часть Є4гсІ fozF 4я% " swx @ сшк І леа/ жя ї лм&$еыи я ; ЗАП имя : = ЗАП симя ПРО (=мкг$ж и леа ) + ЗАП гимя №0{=Mfe%en. ЦУШІ) ЗАП(и ) WLQ $ i}jm)mB) ЗАП ( лахі) ЗАП ( U) ПРО ИСК
Модификация і и-)-анализатора
Сначала рассмотрим LL(-f-) -грамматики и i_LC-)-анализаторы. Пусть дана КС-грамматика т = VT. V/]J SJ Р Для С? функция PlRSTgCoO, гАе - - целое число moLeCVTUVAf , определяется следующим образом: FIflS7 oO = { 6-VT U = -{ и 1 1= или иВД} . Если oL&Vf , то будем писать FI&S7 0 = х . & называется ИбО-грамматикой, если для данной цепочки CO/J 2, где CoeV-f AeVA d6(Vr ОУдУ , и цепочки 66 Є FXR T С Ad) существует не более одного правила, которое можно применить к А , чтобы получить вывод терминальной цепочки, начинающейся с и продолжающейся цепочкой и . LL анализатор анализирует языки, порождаемые UL СЮ -грамматиками. При этом он использует входную ленту, магазин А , выходную ленту и управляющую таблицу Т . Конфигурацией LLC-&) -анализатора будем считать тройку где Х- еще непроанализированная часть первоначальной цепочки, led - цепочка в магазине А ( К - верхний символ), Л - цепочка номеров правил на выходной ленте. Исходной конфигурацией мы будем считать с со, s #j Л) , где СО" исходная терминальная цепочка, S- начальный символ грамматики, - граничный маркер магазина А .
Работой LL -анализатора руководит управляющая таблица Т , задающая отображение множества С VT U \/д U {#}) X VT " в множество, в которое входят 1) (р , и ), где L номер правила, а - правая часть -го правила, 2) ВЫБРОС, 3) ДОПУСК, 4) ОШИБКА.
Анализатор анализирует входную цепочку, проделывая последовательность тактов. На каждом такте сначала определяются Я= FIRSTgt ) и верхний символ к магазина А . Затем для определения того, что действительно надо делать, рассматривается элемент Т( К, U ) управляющей таблицы. Если в процессе работы анализатора одна конфигурация С непосредственно переходит к другой конфигурации р с помощью Т( к ,и), то мы будем обозначать отношение этих двух конфигураций через h , т.е. С -р , Опишем такты LLG&)-анализатора.
1) если TU,a)=(,i,). Здесь верхний символ К магазина А заменяется цепочкой В , и к выходу добавляется номер правила u .
2) (X, ad. ,К ) ( , d ,7V), если Т( а, и) = ВЫБРОС и х.= (XX.1. Когда верхний символ магазина А совпадает с первым символом цепочки х. , он выбрасывается из магазина А , и первый символ цепочки ос считается проанализированным.
3) Если анализатор достигает конфикурации (Л , # ,я), то его работа прекращается, и выходная цепочка X называется раз 1} VT " =f eVT 1 1« J бором первоначальной входной цепочки. Будем предполагать, что всегда Т( # , Л ) = ДОПУСК, и конфигурацию (Л , , Я) будем называть допускающей.
4) Если анализатор достигает конфикурации (X ,Ко( ,7С ) и Т{ К , U) = ОШИБКА, то его работа прекращается,и выдается сообщение об ошибке. Эту конфигурацию ( х. ,Ко1 ,я) назовем ошибочной.
Теперь рассмотрим, как модифицируется LL -анализатор. Пусть Си - символ магазина/1 . При этом ае( VTuV/\ u{ip) U{±}) , где і- символ, называемый разделителем.
Для первого этапа анализа введем понятие конфигурации анализатора, под которой будем понимать шестерку С , Ы; 71, С, Г, Ю; где Х- еще непроанализированная часть первоначальной цепочки, ltd - цепочка в магазине А , где к верхний символ магазина, 7i цепочка на входной ленте, С - содержимое регистра С » Y - содержимое регистра , У] - содержимое магазина N . Исходной конфигурацией мы будем считать {0O;S#j Л, 0, И, Я ), где СО- исходная терминальная цепочка, $ - начальный символ грамматики 6f-M , #- граничный маркер магазина А , йо- начальное содержимое магазина /V .
