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

Большинство этих методов решения задачи соответствует конкретным методам разбора. Методы разбора обычно бывают нисходящими, т.е. начинают с начального символа и идут к предложению, или восходящими, т.е. начинают с предложения и идут к начальному символу. Разрешается смешивать эти два метода. Предложение, разбираемое слева направо, читается нормально, хотя с точки зрения разбора читать его справа налево может оказаться так же просто (или еще проще). Принцип никогда не поднимать уже положенную пластинку в игре такого типа соответствует принципу никогда не отказываться от решения применять конкретное порождающее правило в процессе разбора. Отказ от решения в разборе иногда называют возвратом. Методы разбора могут быть недетерминированными или детерминированными в зависимости от того, возможен возврат или нет. Недетерминированные методы разбора весьма дорогие с точки зрения памяти и времени и крайне затрудняют включение в синтаксический анализатор действий, выполняемых во время компиляции, результаты которых позднее должны быть аннулированы (например, построение таблицы символов и т.п.). В настоящей книге мы имеем дело почти исключительно с детерминированными методами разбора. В гл. 4 описывается метод LL, который осуществляет разбор сверху вниз и использует левосторонние выводы, а в гл. 5 - метод LR, который осуществляет разбор снизу вверх и использует правосторонние выводы. Мы в основном рассматриваем контекстно-свободный

разбор, но эти методы можно распространить и на определенные классы универсальных грамматик, таких, как атрибутивные [57] и аффиксные [40]. W-грамматики менее удобны для разбора из-за своего более общего характера.

Упражнения

2.1. Приведите грамматику для следующих языков:

2.2. Является ли какой-либо из этих языков регулярным? Обоснуйте свой вывод.

2.3. Найдите регулярную грамматику, генерирующую тот же язык, что и грамматика со следующими порождающими правилами (S - начальный символ):

SAB A-XIY

Yy\yY В-*Ь\ЬВ

2.4. Выпишите регулярное выражение, генерированное грамматикой из упражнения 2.3.

2.5. Покажите, что грамматика со следующими порождающими правилами является не однозначной:

2.6. В некоторой грамматике S является начальным символом, а порождающие правила следующие:

S->real 1DL1ST IDLIST->IDLIST, ID 1DLIST->ID

ID->a ID->b ID->c

Составьте дерево разбора для предложения

real a, b, с

2.7.Выведите грамматику, генерирующую все строки (включая пустую) по алфавиту {0, 1}.

2.8.Рассмотрите следующую грамматику с начальным символом PROGRAM:

РRОGRAM- begin DECS; STATS end DECS->d; DECS d

STATS->s; STATS s

Дайте левосторонний и правосторонний выводы

begin s; s; d; d end

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

а) регулярное выражение для идентификатора;

б) грамматику типа 3, генерирующую все без исключения идентификаторы Фортрана.

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

описанному в упражнении 2.5. Объясните, как в некоторых знакомых вам языках

избегают потенциальной неоднозначности или как там разрешается этот вопрос. Глава 3

ЛЕКСИЧЕСКИЙ АНАЛИЗ

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

3.1. РАСПОЗНАВАНИЕ СИМВОЛОВ

Характер распознаваемых строк может намного упростить процесс лексического анализа. К примеру, возьмем такие идентификаторы, как

first datel no1234.

вещественные числа

1.23 6.0 34.291(-20,

слова языка

begin for case

Все эти строки можно генерировать с помощью регулярных выражений. Например, вещественные числа можно генерировать посредством регулярного выражения

(+-) digit*.digit digit* (l0(+-D digit digit*D