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

• Автор: Зо Зон Су, 0
• Шифр специальности: 05.13.11
• Научная степень: Кандидатская
• Год защиты: 1985
• Место защиты: Ленинград
• Количество страниц: 110 c. : ил

ОГЛАВЛЕНИЕ

Введение . з

Глава 1. Контекстные условия в языках программирования

1. Определение и классификация контекстных условий

2. Неадекватность КСграмматик для описания полного

синтаксиса языков программирования .

3. Некоторые способы формального описания контекстных

условий.

4. Методы анализа контекстных условий

Глава П.ЛКУграмматики и их модификация.

1. ЛКУграмматики

2. Модифицированные ЛКУграмматшси.
3. Применение модифицированных ЛКУграмматик.
Глава Ш. Методы анализа языков, порождаемых модифицированными ЛКУграмматиками
1. Методика модификации синтаксических анализаторов
для МЖУязыков
2. Модификация ьианализатора.
3. Модификация анализатора Эрли
4. Оценка эффективности модифицированных анализаторов. 8
Заключение. до
Приложение 1.
Приложение 2.
Литература


ЛКУ-грамматики представляются в виде КС-грамматик с дополнительными условиями, которым должен удовлетворять каждый правильный вывод. Эти дополнительные условия отражают контекстные условия языков програмирования естественным образом. ЛКУ-грамматики удобнее и проще других способов описания контекстных условий. КС-грамматики, определяющие языки программирования без контекстных условий, легко преобразуются в ЛКУ-грамматики. Однако ЛКУ-грамматиками описываются только контекстные условия первого и второго типов. Поэтому представляют интерес модификация ЛКУ-грамматик, целью которой является разработать грамматики, позволяющие описать все контекстные условия языков программирования, и разработка соответствующих методов анализа. Этим вопросам посвящены главы П и Ш. Но мы не будем рассматривать проблемы, связанные с семантикой, так как нашей целью является разработка простой и практичной методики описания полного синтаксиса языков программирования и соответствующих методов их анализа. Приведем необходимые определения. Алфавитом называется непустое конечное множество символов. Пусть 2 -алфавит. Цепочкой над алфавитом называется последовательность символов этого алфавита. Цепочка, не содержащая ни одного символа, называется пустой цепочкой и обозначается через Л • Длина цепочки - это число символов в ней. Длина цепочки со обозначается через со . А| = 0. Языком над алфавитом 2 называется множество цепочек над • Пустое множество обозначается через 0 . Грамматика - это математическая система, определяющая язык. Одновременно она может являться средством, которое придает цепочкам языка полезную структуру. ЪбС/ги/А)*. Будем считать, что цепочка Сді непосредственно выводима из цепочки (0о в грамматике бг , и обозначать это отношение через со0=? Уги^)+и р содержит правило ? Ос =? В этом случае последовательность С0О} . СОп называется выводом, и говорят, что СО„ выводима из С0о • Часто вместо С => Фг и &Л> &Л? И СО© "'—г' ? Совокупность терминальных цепочек грамматики Сг , выводимых в ней из начального символа, называется языком, порождаемым этой грамматикой, и обозначается через I— ( <к ), т. Одной из основных проблем, связанных с практическим применением грамматик, является проблема распознавания* Эта проблема разрешима, если существует такой алгоритм, который за конечное число шагов дает ответ на вопрос, входит ли произвольная цепочка терминальных символов некоторой грамматики в язык, порождаемый этой грамматикой. Если такой алгоритм существует, то язык называется распознаваемым. Если число шагов алгоритма распознавания зависит от длины цепочки и может быть оценено до выполнения алгоритма, язык называется легко распознаваемым. Естественно, что представляют практический интерес лишь те грамматики, которые порождают распознаваемые языки. Сг , легко распознаваем. Рассмотрим несколько грамматик, более удобных для практического использования. Ути Уд)* А Є У* ,^6 ( УтіїУ/))+ . НС-грамматики указывает подстановку некоторой цепочки вместо нетерминального символа. Однако, возможность реализации подстановки зависит от символов, окружающих заменяемый, или, как часто говорят, от контекста, в котором находится заменяемый символ. По любой неукорачивающей грамматике можно построить НС-грамматику, порождающую тот же язык ( С3 ). Такую грамматику будем называть эквивалентной исходной. Классы грамматик будем называть эквивалентными, если порождаемые ими классы языков совпадают. Из определения очевидно, что любая КС-грамматика является одновременно и НС-грамматикой. Поэтому класс КС-грамматик входит в класс НС-грамматик. Укорачивающей контекстно-свободной грамматикой (УКС-грамма-тикой) называется грамматика, имеющая правила того же вида, что и КС-грамматика, но цепочка может быть и пустой. Таким образом, этот класс грамматик не входит в класс неукорачивающих грамматик. По любой УКС-грамматике можно построить почти эквивалентную ей КС-грамматику. Почти эквивалентной грамматикой мы будем называть такую, которая порождает тот же язык, что и исходная грамматика, за исключением пустой цепочки.