Задача разбора (постановка задачи)

Грамматики и распознаватели — два независимых метода, которые реально могут быть использованы для определения какого-либо языка. Однако при разработке компилятора для некоторого языка программирования возникает задача, которая требует связать между собой эти методы задания языков.

Разработчики компилятора всегда имеют дело с уже определенным языком программирования. Грамматика для синтаксических конструкций этого языка известна. Она, как правило, четко описана в стандарте языка, и хотя форма описания может быть произвольной, ее всегда можно преобразовать к требуемому виду (например, к форме Бэкуса—Наура или к форме описания с использованием метасимволов). Задача разработчиков заключается в том, чтобы построить распознаватель для заданного языка, который затем будет основой синтаксического анализатора в компиляторе.

Таким образом, задача разбора в общем виде заключается в следующем: на основе имеющейся грамматики некоторого языка построить распознаватель для это-

го языка. Заданная грамматика и распознаватель должны быть эквивалентны, то есть определять один и тот же язык (часто допускается, чтобы они были почти эквивалентны, поскольку пустая цепочка во внимание обычно не принимается).

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

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

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

Контрольные вопросы и задачи

Вопросы

1. Дайте определение цепочки, языка. Какие операции можно выполнять над цепочками символов? Что такое синтаксис и семантика языка?

2. Какие из перечисленных ниже тождеств являются истинными для двух произвольных цепочек символов а и (3, а какие нет?

3. Какие существуют методы задания языков? Почему метод перечисления всех допустимых цепочек языка не находит практического применения?

4. Какие дополнительные вопросы необходимо решить при задании языка программирования? Почему любой язык программирования не является чисто формальным языком?

5. Как решается вопрос о смысле исходной программы в современных компиляторах?

6. Что такое грамматика языка? Дайте определения грамматики.

7. Как выглядит описание грамматики в форме Бэкуса—Наура? Какие еще формы описания грамматик существуют?

8. Почему в форме Бэкуса—Наура практически невозможно построить грамматику для реального языка так, чтобы она не содержала рекурсивных правил?

9. Какие типы грамматик выделяют по классификации Хомского? Как они между собой соотносятся?

10. Какие типы языков выделяют по классификации Хомского? Как классификация языков соотносится с классификацией грамматик?

11. Дайте определения выводимости цепочки, непосредственной выводимости, нетривиальной выводимости, длины вывода.

12. Что такое сентенциальная форма грамматики? Если язык, заданный грамматикой, представляет собой множество ее конечных сентенциальных форм, то что представляет собой множество всех сентенциальных форм грамматики?

13. Что такое левосторонний и правосторонний выводы? Можно ли построить еще какие-нибудь варианты цепочек вывода?

14. Как классифицируются распознаватели? Как их классификация соотносится с классификацией языков и грамматик?

15. Кто (или что) для любого языка программирования выступает в роли генератора цепочек языка? Кто (или что) выступает в роли распознавателя цепочек? Как решается задача разбора?

Задачи

1. Ниже даны различные варианты грамматик, определяющие язык десятичных чисел с фиксированной точкой. Укажите, к какому типу относится каждая из этих грамматик. К какому типу относится сам язык десятичных чисел с фиксированной точкой?

2. Докажите, что если для некоторой цепочки языка, заданного грамматикой, существует единственный левосторонний вывод, то для нее существует и единственное дерево вывода.

3. Язык десятичных чисел с фиксированной точкой, рассмотренный в задаче №1, содержит цепочки «-22», «239», «19.4». Постройте цепочки вывода для каждой из этих трех цепочек символов на основе предложенных в задаче № 1 грамматик. Какие из предложенных пяти грамматик являются неоднозначными?

4. Язык десятичных чисел с фиксированной точкой, рассмотренный выше в задаче № 1, не содержит цепочек вида «.29» или «.104». Перестройте любую из предложенных в задаче № 1 пяти грамматик так, чтобы заданный ею новый язык допускал такого рода цепочки.

5. Поездом называется произвольная последовательность локомотивов и вагонов, начинающаяся с локомотива. Постройте грамматику для понятия «<поезд>» в форме Бэкуса—Наура, считая что понятия «<локомотив>» и «<вагон>» являются терминальными символами. Модернизируйте грамматику для любого из следующих условий:

О все локомотивы должны быть сосредоточены в начале поезда;

О поезд начинается с локомотива и заканчивается локомотивом (попробуйте построить регулярную грамматику);

О поезд не должен содержать два локомотива либо два вагона подряд.

6. Насколько сложно построить в форме Бэкуса—Наура определение поезда (согласно задаче номер № 5), содержащего не более 60 вагонов? Постройте такое определение в форме грамматики с метасимволами. Распространите его на одно из предложенных в задаче № 5 дополнительных условий.

7. Дана грамматика условных выражений G({" ",i,f,t,h,e,n,l ,s,b,a}, {Е}, Р, Е) с правилами:

Не строя цепочек вывода, покажите, что эта грамматика является неоднозначной. Проверьте это, построив некоторую цепочку вывода. Попробуйте построить эквивалентную ей однозначную грамматику.