Системное программное обеспечение: Основы трансляции. Карпушин А.Н - 20 стр.

UptoLike

ВУЗ: 

УлГТУ | Ульяновск

Составители: 

Рубрика: 

22
скольку эти языки являются однозначными, именно они представляют наи-
больший интерес для построения компиляторов.
Более того, среди всех детерминированных КС-языков существуют такие
классы языков, для которых возможно построить линейный распознаватель –
распознаватель, у которого время принятия решения о принадлежности цепоч-
ки языку имеет линейную зависимость от длины цепочки. Синтаксические кон-
струкции практически всех существующих языков программирования могут
быть отнесены к одному из таких классов языков.
Следует помнить, что только синтаксические конструкции языков про-
граммирования допускают разбор с помощью распознавателей КС-языков.
Сами языки программирования не могут быть полностью отнесены к типу
КС-языков, поскольку предполагают некоторую контекстную зависимость в
тексте исходной программы (например, такую, как необходимость предвари-
тельного описания переменных). Поэтому кроме синтаксического разбора
практически все компиляторы предполагают дополнительный семантический
анализ текста исходной программы. Этого можно было бы избежать, если по-
строить компилятор на основе контекстно-зависимого распознавателя, но ско-
рость работы такого компилятора была бы недопустимо низка, поскольку время
разбора в таком варианте будет экспоненциально зависеть от длины исходной
программы. Комбинация из распознавателя КС-языка и дополнительного се-
мантического анализатора является более эффективной с точки зрения скорости
разбора исходной программы.
Для регулярных языков (тип 3) распознавателями являются детерминиро-
ванные автоматы без внешней памяти – конечные автоматы (КА). Это очень
простой тип распознавателя, который всегда предполагает линейную зависи-
мость времени на разбор входной цепочки от ее длины. Кроме того, конечные
автоматы имеют важную особенность: любой недетерминированный КА всегда
может быть преобразован в детерминированный. Это обстоятельство су-
щественно упрощает разработку программного обеспечения, обеспечивающего
функционирование распознавателя. Простота и высокая скорость работы рас-
познавателей определяют широкую область применения регулярных языков.
В компиляторах распознаватели на основе регулярных языков использу-
ются для лексического анализа текста исходной программы. На основе распо-
знавателей регулярных языков функционируют ассемблеры – компиляторы с
языков ассемблера (мнемокода) в язык машинных команд.
Кроме компиляторов регулярные языки находят применение еще во мно-
гих областях, связанных с разработкой программного обеспечения вычисли-
тельных систем. На их основе функционируют многие командные процессоры
как в системном, так и в прикладном программном обеспечении. Для регуляр-
ных языков существуют развитые, математически обоснованные механизмы,
которые позволяют облегчить создание распознавателей.
Постановка задачи разбора
Грамматики и распознаватели – два независимых метода, которые реально
могут быть использованы для определения какого-либо языка. Однако при раз-

Страницы