Разработка синтаксических анализаторов языков программирования с учетом контекстных условий

Формально, язык программирования — это множество текстов, записанных с помощью некоторого набора символов — алфавита языка. Содержательно, т. е. по существу, язык программирования — это средство общения между человеком и электронными вычислительными машинами (ЭВМ). К настоящему времени разработаны и реализованы сотни различных языков программирования. Хотя эти языки программирования определяются разными способами, обычно определение языка сводится к определению его внешней, текстуальной стороны и внутренней, смысловой стороны.

Система правил, определяющих внешнюю текстуальную сторону языка, называется синтаксисом, а система правил, определяющих внутреннюю, смысловую сторону языка, называется семантикой данного языка. Следует отметить, что синтаксические ошибки, т. е. нарушения синтаксических правил, мы можем обнаружить без выполнения программ, а семантические ошибки обнаруживаются только при выполнении программы на ЭВМ. Например, правило, согласно которому в каздом блоке без внутренних блоков никакой идентификатор нельзя описывать более одного раза, является синтаксическим правилом и мы можем обнаружить нарушение этого правила без выполнения программы. Рассмотрим следующее арифметическое выражение Алгола-60: В/(А — 5). Если в момент вычисления этого выражения значение, А оказалось равным 5, то данное выражение оказалось бессмысленным, и его значение не может быть вычислено. Эта ошибка является семантической^ очевидно, что данную ошибку либо очень трудно, либо вообще невозможно обнаружить при анализе программы.

С самого начала появления сложных языков програмирования стало уделяться большое внимание проблеме их точного описания, и для этого используются разные математические средства. Среди них наибольшей популярностью пользуется аппарат форм Бэкуса — Наура (БНФ). Большинство синтаксических правил языков программирования высокого уровня описывается с помощью (расширенной) БНФ, но некоторые синтаксические свойства, называемые контекстными условиями, языков программирования описываются неформально, с помощью естественных языков ((3), С43,(17), а8), С2С",?21),?30),?34}). При этом трудно обеспечить их точное и единственное понимание из-за неоднозначности естественных языков. Для пояснения смысла описываемых условий приводятся примеры. То есть, контекстные условия задаются с помощью естественных языков и примеров. Этот метод обладает очевидными недостатками. Отсутствие средств формального описания контекстных условий не позволяет, в частности, предложить точный и формальный алгоритм построения синтаксических анализаторов для языков программирования. Это обстоятельство, в свою очередь, затрудняет создание синтаксически ориентированных трансляторов и метатрансляторов, т. е. программ, автоматически вырабатывающих трансляторы по информации о синтаксисе и семантике входных и выходных языков. Поэтому разработка общепринятого формализма для описания полного синтаксиса языков программирования, под которым мы будем понимать совокупность синтаксических правил, описываемых КС-средствами, и контекстных условий, и соответствующих методов их анализа имеет важное значение с практической и теоретической точки зрения. Настоящая работа посвящена этим вопросам.

Полный синтаксис языка Алгол-68 был определен так называемой и/-грамматикой или двухуровневой грамматикой С ?53, С323). IVграм. матика, по существу, состоит из двух связанных друг с другом грамматик. Комбинация этих двух грамматик позволяет вывести в принципе бесконечное множество синтаксических правил. Имея бесконечное множество КС-правил, удается определить полный синтаксис языков программирования. Но v/-грамматики обладают излишне большой порождающей мощностью, что затрудняет разработку анализаторов для языков, порождаемых этими грамматиками.

Для определения полного синтаксиса языков программирования были предложены и другие формализмы ((22), С24),£33})| но каждый из них обладает определенными недостатками. Поэтому проблема разработки методов описания полного синтаксиса этих языков пока еще не решена в полной мере,.

В (11!) были предложены так называемые грамматики с локальными контекстными условиями (ЖУ-грамматики), учитывающие практические действия, предусмотренные для проверки контекстных условий в трансляторах. ЛКУ-грамматики представляются в виде КС-грамматик с дополнительными условиями, которым должен удовлетворять каждый правильный вывод. Эти дополнительные условия отражают контекстные условия языков програмирования естественным образом. ЛКУ-грамматики удобнее и проще других способов описания контекстных условий. КС"грамматики, определяющие языки программирования без контекстных условий, легко преобразуются в ЛКУ-грамматики. Однако ЛКУ-грамматиками описываются только контекстные условия первого и второго типов. Поэтому представляют интерес модификация ЛКУ-грамматик, целью которой является разработать грамматики, позволяющие описать все контекстные условия языков программирования, и разработка соответствующих методов анализа. Этим вопросам посвящены главы П и 1.

Хотя контекстные условия языков программирования относятся к синтаксису языка, многие формализмы (например, -грамматики и атрибутные грамматики), предложенные для их описания, применимы и для формального определения семантики этих языков. Но мы не будем рассматривать проблемы, связанные с семантикой, так как нашей целью является разработка простой и практичной методики описания полного синтаксиса языков программирования и соответствующих методов их анализа.

Приведем необходимые определения. Алфавитом называется непустое конечное множество символов. Пустьалфавит. Цепочкой над алфавитом называется последовательность символов этого алфавита. Цепочка, не содержащая ни одного символа, называется пустой цепочкой и обозначается через Л. Длина цепочки — это число символов в ней. Длина цепочки со обозначается через со. Очевиднр, что |Л|= 0.

Языком над алфавитом? называется множество цепочек над 21 • Пустое множество обозначается через 0. Обозначим через 2.* множество, содержащее все цепочки над алфавитом X «включая Л. Каждый язык над? является подмножеством множества. Множество всех цепочек над? , за исключением Л, обозначается через Z.* •.

Грамматика — это математическая система, определяющая язык. Одновременно она может являться средством, которое придает цепочкам языка полезную структуру. Порождающей грамматикой называется четверка объектов где конечное множество терминальных символовуАконечное множество нетерминальных символов, VrЛ V^ =ф gначальный символ или аксиома грамматики, i р — конечное множество правил вида, где.

Причем правила из р называются правилами вывода грамматики Gr .

Будем считать, что цепочка С01 непосредственно выводима из цепочки 0до в грамматике От, и обозначать это отношение через оо0=?сои если &>0 = £71=£г, бсу^^г* Где (Ути), (Уг и) и р содержит правило?. Будем писать со0 ойу,, если существует последовательность цепочек Со01 со" ^ 1) такая, что сос для I =0, 1,., П -1. В этом случае последовательность со0, СОп называется выводом, и говорят, что СОп выводима из С0о. Часто вместо Ш0 -==> со-г и со0 -=Р оо&bdquoбудем писать просто и со0?$>соИ.

Совокупность терминальных цепочек грамматики Сг, выводимых в ней из начального символа, называется языком, порождаемым этой грамматикой, и обозначается через 1— (<к), т. е. ибо={х| хеУг*, X}.

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

Грамматика называется неукорачивающей, если для любого ее правила вывода справедливо неравенство • В С93 доказано, что язык, порождаемый неукорачивающей грамматикой С?, легко распознаваем.

Рассмотрим несколько грамматик, более удобных для практического использования. Грамматикой непосредственных составляющих (НС-грамматикой) называется неукорачивающая грамматика с правилами вывода взда где Ути УА)* A? VA >71<Ь (Уг^УрХ. Кавдое правило вывода НС-грамматики указывает подстановку некоторой цепочки вместо нетерминального символа. Однако, возможность реализации подстановки зависит от символов, окружающих заменяемый, или, как часто говорят, от контекста, в котором находится заменяемый символ. По любой неукорачивающей грамматике можно построить НС-грамматику, порождающую тот же язык (?143). Такую грамматику будем называть эквивалентной исходной. Классы грамматик будем называть эквивалентными, если порождаемые ими классы языков совпадают.

Контекстно-свободной или бесконтекстной грамматикой (КС-грамматикой) называется неукорачивающая грамматика с правилами вывода вида, где / - нетерминальный символ, а — произвольная непустая цепочка над /ти/д" Из определения очеввдно, что любая КС-грамматика является одновременно и НС-грамматикой. Поэтому класс КС^грамматик входит в класс НС-грамматик.

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

Автоматной грамматикой (А-грамматикой) называется грамматика с правилами вывода вида Д-*Ь8 и Л Ь «гДе, А «В 6 /д «Ь? Уу. Автоматные грамматики используются, в основном, при предварительном преобразовании программ, с целью их представления в форме, более удобной для дальнейшего анализа.

Конечный ориентированный граф (X, СС), где X — множество его вершин, а и частичное отображение X в X «определяющее дуги, называется деревом, если.

1) у него имеется одна вершина, в которую не входит ни одна дугаэту вершину будем называть корнем дерева;

2) в каждую из его остальных вершин входит лишь одна дуга;

3) он не содержит контуров.

Из корня дерева в любую его вершину ведет ровно один путь. Назовем уровнем вершины дерева длину такого пути, т. е. число составляющих его дуг. Будем считать, что корень дерева имеет уровень 0. Высотой дерева называется наибольший уровень его вершин. Если в дереве существует путь из вершины ЭС^ в вершину, то говорят, что вершина Х. ь предшествует вершине, а ЭСф. следует за ЭСъ • При этом очевидно, что вершина уровня У] следует ровно за одной вершимой каждого из уровней Л-1, П-2,., 0. Вершины, не предшествующие никаким вершинам дерева, т. е. не имеющие выходящих из них дуг, называются заключительными, а все остальные — незаключительными вершинами дерева.

Пусть в КС-грамматике имеется некоторый вывод (?>0, соп. По этому выводу можно однозначно построить синтаксическое дерево вывода, в котором незаключительные вершины соответствуют нетерминальным символам грамматики, а заключительные — терминальным символам.

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

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

Анализатором для некоторой грамматики мы будем называть такой алгоритм, который для любой терминальной цепочки устанавливает за конечное число шагов, принадлежит ли цепочка языку, по-рожаемому данной грамматикой, и если да, то распознает синтаксическую структуру данной терминальной цепочки в терминах порождающих правил грамматики. Говорят, что анализатор работает по принципу «снизу вверх», если он пытается сводить терминальную цепочку к начальному символу грамматики. Говорят, что анализатор работает по принципу «сверху вниз», если он пытается получить терминальную цепочку из начального символа грамматики.

Работа состоит из введения, трех глав, заключения и приложений. В главе 1 рассматриваются контекстные условия языков программирования в общем виде. Далее глава содержит обзор методов формального описания контекстных условий (программные грамматики, л/ -грамматики, атрибутные грамматики, Vподход и НС-грамматики). Там указаны как достоинства, так и недостатки этих методов. Потом рассматриваются практические методы анализа контекстных условий, используемые в трансляторах.

Глава П посвящена ЖУ-грамматикам и их модификации. Дается определение ЛКУ-грамматик и рассматривается методика формального описания контекстных условий этими грамматиками. Предлагается модификация ЛКУ-грамматик, целью которой является предложить средство формального описания полного синтаксиса языков программирования. Затем рассматриваются некоторые вопросы, связанные с практическим применением модифицированных ЛКУ-грамматик.

В главе Ш рассматриваются методы модификации КС-анализаторов для МЛКУ-языков. Сначала обсуждаются общие принципы такой модификации, а потом эти принципы применяются для модификации ЫС-?)-анализатора и анализатора Эрли. Получена оценка эффективности модифицированного МЛКУанализатора.

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

В приложениях дается полное синтаксическое описание языка Паскаль-5 в виде МЛКУ-грамматики, а также приводятся данные о реализации модифицированного 1Ь-С!>-анализатора — распечатка программы на языке Алгол-68 и результатов ее работы.

ЗАКЛЮЧЕНИЕ

.

В данной работе получены следующие основные результаты:

1) предложена модификация ЛКУ-грамматик, позволяющая формально описывать все контекстные условия языков программирования типа Алгол;

2) рассмотрена методика разработки методов анализа МЛКУ-языков;

3) предложены модифицированные Ь1(-?)-анализатор и анализатор Эрли для МЛКУ-языков;

4) получена оценка эффективности модифицированных для МЛКУ-грамматик анализаторов;

5) на основе МЛО-грамматик разработано полное синтаксическое описание языка Паскаль-5 ;

6) реализован модифицированныйанализатор.

Для описания любого языка с помощью МЛКУ-грамматики нужно определить директивы с параметрами. Вообще говоря, каждому конкретному языку соответствует некоторое множество директив. Однако, нет сомнения о той, что для многих языков программирования существует большое совместное подмножество этих директив. Поэтому представляют интерес следующие вопросы:

— разработка метода определения множества директив для конкретных языков;

— отношение между множествами директив различных языков прог раммирования.

Модифицированные для МЛКУ-языков анализаторы выполняют на втором этапе нужные директивы. При реализации таких анализаторов предусматриваются все возможные директивы. Однако, с практической точки зрения удобнее использовать такие анализаторы, после разработки которых можно автоматически дополнить или отменить возможность выполнения любой директивы.

Дальнейшие исследования применения МЛКУ-грамматик и соответствующих методов анализа должны быть направлены на полную или частичную автоматизацию разработки трансляторов.