ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 11.04.2019
Просмотров: 5780
Скачиваний: 8
контекст, α2 – правый контекст. В общем случае они могут быть пустыми.
В неукорачивающих грамматиках при построении предложений языка
цепочка символов заменяется на цепочку не меньшей длины.
Эти два класса грамматик эквивалентны.
При построении компиляторов такие грамматики не применяются,
поскольку языки программирования имеют более простую структуру и могут
быть построены с помощью грамматик других типов.
3. Тип 2 – Контекстно-свободные (КС) грамматики V+ α β → ∈
Контекстно-свободные (КС) грамматики имеют правила вида A→ β, где
A∈VN, β∈ V+ . В правой части у них стоит всегда хотя бы один символ. Их
отличие от предыдущих типов состоит в том, что левая часть правил должна
состоять ровно из одного нетерминального символа. Такие грамматики еще
называют неукорачивающими контекстно-свободными (НКС) грамматиками.
Существует почти эквивалентный им класс укорачивающих контекстно-
свободных (УКС) грамматик, отличие которого в том, что он допускает
пустую цепочку, т.е. правила имеют вид A→ β, где A∈VN, β∈V*. В
дальнейшем, если возможность наличия в языке пустой цепочки не имеет
принципиального значения, будем говорить просто о КС-грамматиках. КС-
грамматики широко используются при описании синтаксических конструкций
языков программирования.
4. Тип 3 – Регулярные грамматики
В правой части правил грамматик этого типа может присутствовать не
более одного нетерминального символа, причём он должен быть расположен
во всех правилах одной грамматики с одной и той же стороны от цепочки
терминалов, а требования к левой части правил совпадают с предыдущим
типом. К этому типу относятся два эквивалентных класса грамматик:
леволинейные и праволинейные (их название определяется местоположением
нетерминального символа в правой части правил относительно терминальной
цепочки). Для любой праволинейной грамматики можно построить
эквивалентную ей леволинейную, задающую тот же язык, и наоборот.
Регулярные грамматики используются при описании простейших
конструкций языков программирования: идентификаторов, констант, строк,
комментариев и т.д. Они очень просты и удобны в использовании, поэтому в
компиляторах на их основе строятся функции лексического анализа входного
языка.
Из определения типов видно, что любая регулярная грамматика является
также КС-грамматикой, или любая грамматика может быть отнесена к типу 0.
В то же время существуют УКС-грамматики, которые не относятся к типу 1,
поскольку могут содержать правила вида A→λ, недопустимые в этом типе. В
общем, сложность грамматики обратно пропорциональна тому максимально
возможному номеру типа, к которому может быть отнесена эта грамматика.
Самыми простыми являются грамматики типа 3, самыми сложными – типа 0.
1.4.2 Классификация языков
Языки классифицируются согласно иерархии Хомского в соответствии с
типами грамматик, с помощью которых они заданы, причем из всех
эквивалентных грамматик, задающих один и тот же язык, выбирается
грамматика с максимально возможным номером, т.е. самая простая.
Сложность языков соответствует сложности грамматик. От
классификационного типа языка зависит и сложность распознавателя этого
языка.
1. Тип 0 – языки с фразовой структурой
Это самые сложные языки, для распознавания которых требуются
вычислители, равномощные машине Тьюринга. Для такого языка невозможно
построить компилятор, который выполнил бы разбор за ограниченное время
на основе ограниченных вычислительных ресурсов.
Практически все естественные языки относятся к этому типу. Одно и то
же слово в естественном языке может иметь различный смысл в зависимости
от контекста и играть различную роль в предложении. Такие языки далее
рассматриваться не будут.
2. Тип 1 – контекстно-зависимые (КЗ) языки
В общем случае время на распознавание языка типа 1 экспоненциально
зависит от длины исходной цепочки символов.
Языки и грамматики этого типа используются в переводе текстов на
естественных языках. Распознаватели, построенные на их основе, позволяют
анализировать тексты с учётом контекстной зависимости в предложениях
входного языка, хотя в общем случае для точного перевода всё же требуется
вмешательство человека. Такие грамматики могут использоваться в
сервисных функциях проверки орфографии в языковых процессорах.
Однако языки программирования имеют более простую структуру,
поэтому в компиляторах КЗ-языки не применяются.
3. Тип 2 – контекстно-свободные (КС) языки
КС-языки лежат в основе большинства современных языков
программирования, на их основе работают некоторые командные процессоры,
допускающие управляющие команды цикла и условия.
В общем случае время на распознавание предложений языка этого типа
полиномиально зависит от длины цепочки символов (это кубическая или
квадратичная зависимость в зависимости от класса языка). Но среди КС-
языков существует много классов, для которых эта зависимость линейна, и
многие языки программирования можно отнести к одному из таких классов.
КС-языки будут рассматриваться подробно.
4. Тип 3 – регулярные языки
Это самый простой тип языков, и они являются наиболее широко
распространенным типом, используемым в вычислительных системах. Время
на распознавание цепочек языка линейно зависит от их длины. Поэтому
иногда эти языки ещё называют линейными.
П. G ({0,1}, {S}, P, S) L={0*2n | n >=0}
P: S→00S | λ Праволинейная
P: S→S00 | λ Леволинейная
P: S→0S0 | λ Контекстносвободные
P: S→AAS | λ Контекстносвободные
A→0
2.3 Цепочки вывода (левосторонний, правосторонний)
Выводом называется процесс порождения цепочек языка на основе
правил определяющей язык грамматики.
Грамматика, в которой для любой цепочки порождаемого языка
существует единственная цепочка вывода, называется однозначной.
Вывод называется законченным, если из полученной цепочки нельзя
сделать более ни одного шага, т.е. если полученная цепочка пустая или
содержит только терминальные символы грамматики: β ∈ VT*. Цепочка,
полученная в результате законченного вывода, называется конечной цепочкой
вывода.
Цепочка символов α ∈ V* называется сентенциальной формой
грамматики G(VT,VN,P,S), если она выводима из целевого символа
грамматики S: S ⇒* α. Если цепочка получена в результате законченного
вывода, она называется конечной сентенциальной формой.
Вывод называется левосторонним, если в нём на каждом шаге вывода
правило грамматики применяется к самому левому нетерминальному символу
в цепочке. Аналогично определяется правосторонний вывод. Если символы
заменяются в произвольном порядке, вывод нельзя отнести ни к какому из
типов. Для КС - грамматик для любой сентенциальной формы всегда можно
построить левосторонний или правосторонний вывод. Для грамматик более
сложных типов это не всегда возможно (структура правил не всегда позволяет
заменять крайний левый или крайний правый нетерминальные символы в
цепочке).
Здесь (1) – (4) – конечные сентенциальные формы, поскольку цепочка в
(2) может быть получена из целевого символа грамматики (хотя в этом
примере и получена из нетерминала T); (5) – просто сентенциальная форма
(не конечная). В выводе (6) в явном виде не присутствует сентенциальная
форма, хотя цепочка 1210 и является конечной сентенциальной формой. Для
того, чтобы это подтвердить, достаточно построить другой вывод этой
цепочки из целевого символа. А цепочка TFT не является сентенциальной
формой, т.к. её невозможно получить из целевого символа. Все выводы, за
исключением (5), являются законченными. На примере (3), (4) видно, что
одна и та же цепочка может быть получена посредством разных выводов.
Выводы (2), (4), (6) – правосторонние, (1) – левосторонний, (3), (5) – ни то,
ни другое.
2.4 Проблемы однозначности и эквивалентности грамматик
Грамматика, в которой для любой цепочки порождаемого языка существует единственная цепочка вывода, называется однозначной. Грамматика также называется однозначной, если для каждой цепочки символов языка, заданного этой грамматикой, существует единственное дерево вывода. В противном случае грамматика называется неоднозначной.
Рассмотрим некоторую грамматику G ( {+, – , *, /, (, ), x, y}, {S}, P, S):
P: S → S+S | S–S | S*S | S/S | (S) | x | y
Грамматика определяет язык арифметических выражений с четырьмя основными операциями: сложение, вычитание, умножение, деление и скобками.
Для цепочки, принадлежащей данному языку, x*y+x можно построить два варианта левостороннего вывода:
S => S+S => S*S+S => x*S+S => x*y+S => x*y+x
S => S*S => x*S => x*S+S => x*y+S => x*y+S
С точки зрения формального языка, заданного грамматикой, не имеет значения, какая цепочка вывода и какое дерево вывода из возможных вариантов будут построены. Однако в реальных языках структура предложения и его значение (смысл) взаимосвязаны. Это справедливо как для естественных языков, так и для языков программирования. Для языков программирования, которые несут смысловую нагрузку, имеет принципиальное значение то, какая цепочка вывода будет построена для того или иного предложения языка.
Например, если принять во внимание, что рассмотренная здесь грамматика определяет язык арифметических выражений, то с точки зрения семантики арифметических выражений порядок построения дерева вывода соответствует порядку выполнения арифметических действий. В арифметике, как известно, при отсутствии скобок умножение всегда выполняется раньше сложения (умножение имеет более высокий приоритет), но в рассмотренной выше грамматике это ниоткуда не следует — в ней все операции равноправны. Поэтому с точки зрения арифметических операций приведенная грамматика имеет неверную семантику — в ней нет приоритета операций, а кроме того, для равноправных операций не определен порядок выполнения (в арифметике принят порядок выполнения действий слева направо), хотя синтаксическая структура построенных с ее помощью выражений будет правильной.
Такая ситуация называется неоднозначностью в грамматике. Естественно, для построения компиляторов и языков программирования нельзя использовать грамматики, допускающие неоднозначности.
Однозначность — это свойство грамматики, а не языка. Для некоторых языков, заданных неоднозначными грамматиками, иногда удается построить эквивалентную однозначную грамматику (однозначную грамматику, задающую тот же язык).
Например, для рассмотренной грамматики арифметических выражений существует эквивалентная ей однозначная грамматика вида:
G’ ( {+, – , *, /, (, ), x, y}, {S, Т, Е}, P’, S):
P’: S → S+T | S–T | T
T→ T*E | T/E | E
E→ (S) | x | y
Для арифметического выражения x*y+x в этой грамматике можно построить единственный левосторонний вывод:
S => S+T => T+T => T*E+T => E*E+T => x*E+T => x*y+T => x*y+E => x*y+x
В таком случае необходимо решить проблемe: доказать что две имеющиеся грамматики эквивалентны (задают один и тот же язык).
К сожалению, доказано, что проблема эквивалентности грамматик в общем случае с помощью алгоритма неразрешима. Это значит, что не только до сих пор не существует алгоритма, который бы позволял проверить, являются ли две заданные грамматики эквивалентными, но и доказано, что такой алгоритм в принципе не существует, а значит, он никогда не будет создан.
Точно так же неразрешима в общем виде и проблема однозначности грамматик. Это значит, что не существует (и никогда не будет существовать) алгоритм, который бы позволял для произвольной заданной грамматики G проверить, является ли она однозначной или нет. Однако, неразрешимость проблем эквивалентности и однозначности грамматик в общем случае не означает, что они не разрешимы вообще. Для многих частных случаев эти проблемы решены.
2.5 Распознаватели, общая схема распознавателей.
В числе прочих задач компилятор должен определить принадлежность некоторого текста к конкретному языку. В отношении исходной программы компилятор выступает в роли распознавателя, а человек, создавший программу – в роли генератора цепочек этого языка.
Распознаватель – это специальный алгоритм, позволяющий для
некоторой цепочки символов определить, принадлежит ли она заданному языку. Это один из способов задания языка.
Распознаватель входит в состав компилятора и является частью
программного обеспечения компьютера.
Основные компоненты распознавателя:
входная лента – линейная последовательность клеток, или ячеек, каждая из которых содержит ровно один символ входного алфавита;
входная (считывающая) головка обозревает одну входную ячейку; на каждом шаге работы может сдвигаться на одну ячейку вправо, влево или оставаться на месте;
устройство управления (УУ), которое координирует работу
распознавателя, имеет некоторое множество состояний и конечную
память;
внешняя (рабочая) память может хранить некоторую информацию в процессе работы распознавателя и может иметь неограниченный объем.
Алфавит распознавателя конечен; он включает в себя все допустимые символы входных цепочек, а также некоторый дополнительный алфавит символов, которые могут обрабатываться УУ и храниться в рабочей памяти распознавателя.
В процессе своей работы распознаватель может выполнять некоторые элементарные операции, такие как чтение входного символа, сдвиг головки, доступ к рабочей памяти для чтения или записи информации, изменение состояния УУ.
Работа распознавателя состоит из последовательности шагов, или
тактов. То, каким должен быть этот такт, определяется текущим входным символом, состоянием УУ и символом, извлеченным из памяти. Итак, Такт состоит из следующих моментов:
входная головка распознавателя сдвигается на одну ячейку вправо, влево
или остается на месте;
в память помещается некоторая информация;
изменяется состояние УУ.
В процессе работы распознавателя происходит смена конфигураций.
Конфигурация распознавателя (мгновенное описание) определяется
следующими параметрами:
состояние УУ;
содержимое входной ленты и положение считывающей головки в ней;
содержимое внешней памяти.
Конфигурация называется начальной, если УУ находится в начальном
состоянии, входная головка обозревает самый левый символ на входной ленте, а память имеет заранее установленное начальное содержимое.
Конфигурация называется заключительной, если УУ находится в одном из множества заключительных состояний, а входная головка обозревает правый концевой маркер или сошла с ленты.
Распознаватель допускает входную цепочку символов, если, находясь в начальной конфигурации, в которой данная цепочка записана на входной ленте, он может проделать конечную последовательность шагов, заканчивающуюся одной из его заключительных конфигураций.
Некоторые виды распознавателей могут из начальной конфигурации
проделать различные последовательности шагов, из которых, может быть, лишь некоторые (или даже одна) приведут к заключительной конфигурации.