Cтраница 1
Синтаксические методы часто дают более простые разрешающие алгоритмы. Так, например, для элементарной теории р-адических чисел разрешимость была установлена сначала теоретико-модельными методами. Позднее был найден примитивно-рекурсивный алгоритм распознавания выводимости для этой теории с помощью некоторой модификации синтаксического метода элиминации кванторов. Существенной является оценка сложности алгоритмов разрешения теорий. Как правило, для разрешимых теорий имеется примитивно-рекурсивный разрешающий алгоритм, и проблема состоит в том, чтобы указать более точные границы сложности. Перспективным направлением исследований является изучение разрешимости естественных фрагментов известных формальных теорий. В этом отношении особенно подробно изучено классическое исчисление предикатов, где эффективно описаны все разрешимые и неразрешимые классы формул, заданные в терминах расположения кванторов в формуле и вида предикатных символов, встречающихся в формуле. Описан ряд разрешимых фрагментов арифметического исчисления, элементарной теории множеств. [1]
Синтаксические методы трансляции основаны на переработке отдельных синтаксических конструкций Алгола. Транслятор в этом случае представляет набор подпрограмм, соответствующих отдельным операторам. Каждый оператор в исходной программе транслируется своей подпрограммой. В некоторых случаях в основу составления отдельных подпрограмм берется принцип синтаксических единиц языка, например выражение. Достоинством таких трансляторов является то, что исходная программа может задаваться в виде закодированных синтаксических правил перевода. [2]
Синтаксические методы трансляции отличаются прежде всего более или менее четко выраженным разделением этапов синтаксического и семантического анализов. Некоторые из ранних синтаксических методов, как и прямые методы, ориентированы на конкретные входные языки. Характерным примером является метод синтаксических подпрограмм, в котором каждой синтаксической единице входного языка соответствует отдельная подпрограмма. [3]
Более поздние синтаксические методы основаны на теории формальных грамматик. Каждый из этих методов ориентирован не на конкретный входной язык, а на некоторый класс входных языков точнее, на определенный способ описания синтаксиса входных языков. Поэтому эти методы называют синтаксически-ориентированными. [4]
Мы только что видели, что в таких ситуациях могут применяться формальные синтаксические методы; другим средством составления символических описаний являются графы отношений. [5]
В программировании, приближающемся по своим возможностям к мышлению, большое значение имеют синтаксические методы. Поэтому следующие два раздела главы мы посвящаем рассмотрению синтаксического анализа, в особенности в применении к переводу языков автоматического программирования. Это рассмотрение представляет собой не только более подробное исследование собственно синтаксических структур, оно по праву занимает важное место среди методов перевода языков автоматического программирования. Мы увидим в разд. [6]
Сейчас принято считать, что автоматические рассуждения на основе формальной логики относятся к слабым ( weak) методам доказательства теорем, и чисто синтаксические методы управления поиском не способны обрабатывать огромное пространство поиска при решении задач практической сложности. Поэтому альтернативой являются неформальные методы поиска, ad hoc стратегии, эвристики и рассуждения здравого смысла, которые человек использует при решении проблем. [7]
Используемая в трансляторах система правил и приемов преобразования исходных программ в объектные модули. Различают прямые и синтаксические методы трансляции. [8]
Книга представляет собой монографию по системному программированию, После краткой характеристики основных элементов современных систем программирования: библиотек, языков программирования и трансляторов - изложены принципы построения трансляторов для языков символического кодирования, макроязыков и процедурно-ориентированных языков высокого уровня. Описаны наиболее распространенные прямые и синтаксические методы тран-сляции. [9]
Дедуктивные выводы в настоящее время хорошо изучены, и автоматическое доказательство теорем является старейшей ветвью искусственного интеллекта. Конечно, формальные, синтаксические методы дедуктивного вывода не способны обрабатывать сложные прикладные области с большим пространством поиска нужной информации. Необходимо разрабатывать эвристические методы управления таким поиском, применять ad hoc стратегии, которые использует человек при решении различных проблем. Таким образом, на первый план выдвигаются рассуждения здравого смысла, рассуждения, оперирующие с неполной, противоречивой, неточной, неопределенной информацией, где главную роль играет правдоподобный вывод. Но прежде чем переходить к основным методам правдоподобного вывода - абдукции и индукции, необходимо остановиться на основных особенностях данных и знаний, применяемых в интеллектуальных системах различного назначения. [10]
Определение решающего правила в случае, когда объекты задаются цепочками, включает в себя алгебраическую структуру в большей степени чем в случае ЛЛмерных векторов. В этом разделе мы рассмотрим синтаксические методы восстановления грамматик в свете структурного подхода, изложенного в разд. [11]
Преимуществом РСП является то, что она позволяет получить компактное представление и эффективные алгоритмы для различных грамматик. Последний класс систем понимания ТЕЯ на лингвистическом уровне представляется системами анализа, включающими семантические процедуры, которые используются в дополнение к синтаксическим методам или вместо них. [12]
В книге частично представлено содержание нескольких курсов по интуиционистской математике, которые автор читал в течение ряда лет на механико-математическом факультете МГУ. Книга содержит пять частей и два дополнения. В первой части излагаются чисто синтаксические методы исследования интуиционистской логики предикатов, основанные на теореме Генцена об устранении сечения. В частности, доказана теорема Харропа о свойствах дизъюнктивности и экзистенциальности логики предикатов. Во второй части, посвященной интуиционистской арифметике, основным инструментом исследования является принадлежащий Клини метод реализуемости. [13]
А выяснять, выводима ли А в этой теории или нет. Известно, что всякая формальная теория, содержащая нек-рый фрагмент теории рекурсивных функций, необходимо неразрешима. Отсюда следует неразрешимость элементарной арифметики, системы Цермело - Френкеля и многих других теорий. Примерами могут служить элементарная теория групп, теория двух отношений эквивалентности, элементарная теория частичного порядка. С другой стороны, имеются примеры интересных разрешимых теорий, таких, как элементарная геометрия, элементарная теория действительных чисел, теория множеств натуральных чисел с единственной операцией следования. Разрешимость теорий доказывается теоретико-модельными и синтаксич. Синтаксические методы часто дают более простые разрешающие алгоритмы. Так, например, для элементарной теории р-адических чисел разрешимость была установлена сначала теоретико-модельными методами. Позднее был найден примитивно-рекурсивный алгоритм распознавания выводимости для этой теории с помощью нек-рой модификации синтаксич. Существенной является оценка сложности алгоритмов разрешения теорий. Как правило, для разрешимых теорий имеется примитивно-рекурсивный разрешающий алгоритм, и проблема состоит в том, чтобы указать более точные границы сложности. Перспективным направлением исследований является изучение разрешимости естественных фрагментов известных формальных теорий. В этом отношении особенно подробно изучено классич. [14]
Методы оптимизации различаются по типу информации, используемой при оптимизации. Наиболее распространена синтаксическая оптимизация. В этом случае при трансформации программ рассматриваются только их синтаксические особенности. В частности, различают два вида структурных свойств. Первый вид связан с анализом структуры программы, и, в частности, с типом правил, из которых она состоит. Например, некоторые методы при оптимизации используют линейность правил ( разд. Второй вид касается структуры цели и, в частности, селективности, вызванной наличием в цели констант. Эти два подхода не являются взаимно исключающими: можно разработать синтаксические методы, в которых возможны оба рассмотренных выше случая. [15]