Синтаксический анализ: разбор символьных строк по формальной грамматике.

Введение

Анализ ряда символов в соответствии с правилами формальной грамматики. Синтаксический анализ, или разбор, — это процесс анализа ряда символов, будь то в естественном языке, языках программирования или структурах данных, в соответствии с правилами формальной грамматики. Термин «разбор» происходит от латинского *pars (orationis)*, означающего «часть (речи)». В различных областях лингвистики и информатики этот термин имеет несколько отличающиеся значения. Традиционный разбор предложений часто используется как метод понимания точного значения предложения или слова, иногда с использованием таких инструментов, как схемы предложений. Обычно подчеркивается важность грамматических элементов, таких как подлежащее и сказуемое. В вычислительной лингвистике термин относится к формальному анализу компьютером предложения или другой последовательности слов на составляющие его части, результатом чего является дерево разбора, показывающее их синтаксические взаимосвязи, которое может также содержать семантическую информацию. Некоторые алгоритмы разбора генерируют лес разборов или список деревьев разбора для строки, которая является синтаксически неоднозначной. Этот термин также используется в психолингвистике при описании понимания языка. В этом контексте разбор относится к тому, как люди анализируют предложение или фразу (в устной или письменной форме) «с точки зрения грамматических составляющих, определяя части речи, синтаксические отношения и т. д.». Это во многом определяется изучением спряжений и склонений языка, которые могут быть довольно сложными для языков с развитой морфологией. Разбор фразы, такой как «man bites dog» (человек кусает собаку), включает в себя определение того, что существительное «man» в единственном числе является подлежащим предложения, глагол «bites» является формой третьего лица единственного числа настоящего времени глагола «to bite» (кусать), а существительное «dog» в единственном числе является дополнением. Такие методы, как схемы предложений, иногда используются для обозначения связей между элементами в предложении. Разбор ранее был центральным элементом обучения грамматике во всем англоязычном мире и широко рассматривался как основа для использования и понимания письменного языка. Однако общее обучение этим методам в настоящее время не практикуется.

Analysing a string of symbols, according to the rules of a formal grammar

Parsing, syntax analysis, or syntactic analysis is the process of analyzing a string of symbols, either in natural language, computer languages or data structures, conforming to the rules of a formal grammar. The term parsing comes from Latin pars (orationis), meaning part (of speech). The term has slightly different meanings in different branches of linguistics and computer science. Traditional sentence parsing is often performed as a method of understanding the exact meaning of a sentence or word, sometimes with the aid of devices such as sentence diagrams. It usually emphasizes the importance of grammatical divisions such as subject and predicate. Within computational linguistics the term is used to refer to the formal analysis by a computer of a sentence or other string of words into its constituents, resulting in a parse tree showing their syntactic relation to each other, which may also contain semantic information. Some parsing algorithms generate a parse forest or list of parse trees from a string that is syntactically ambiguous. The term is also used in psycholinguistics when describing language comprehension. In this context, parsing refers to the way that human beings analyze a sentence or phrase (in spoken language or text) "in terms of grammatical constituents, identifying the parts of speech, syntactic relations, etc." This is determined in large part from study of the language's conjugations and declensions, which can be quite intricate for heavily inflected languages. To parse a phrase such as "man bites dog" involves noting that the singular noun "man" is the subject of the sentence, the verb "bites" is the third person singular of the present tense of the verb "to bite", and the singular noun "dog" is the object of the sentence. Techniques such as sentence diagrams are sometimes used to indicate relation between elements in the sentence. Parsing was formerly central to the teaching of grammar throughout the English speaking world, and widely regarded as basic to the use and understanding of written language. However, the general teaching of such techniques is no longer current.

Вычислительные методы

В некоторых системах машинного перевода и обработки естественного языка письменные тексты на человеческих языках анализируются компьютерными программами. Человеческие предложения нелегко поддаются программному анализу из-за существенной неоднозначности структуры человеческого языка, который используется для передачи смысла (или семантики) из потенциально неограниченного множества возможностей, но лишь некоторые из них релевантны конкретному случаю. Так, высказывание «Человек кусает собаку» в отличие от «Собака кусает человека» однозначно в одном аспекте, но в другом языке может быть представлено как «Человек собаку кусает», полагаясь на более широкий контекст для различения этих двух возможностей, если вообще эта разница имеет значение. Сложно сформулировать формальные правила для описания неформального поведения, хотя очевидно, что определенные правила соблюдаются. Для анализа данных естественного языка исследователям необходимо сначала согласовать используемую грамматику. Выбор синтаксиса обусловлен как лингвистическими, так и вычислительными соображениями; например, некоторые системы анализа используют лексико-функциональную грамматику, но в целом анализ грамматик этого типа известен как NP-полная задача. Грамматика структуры фраз с головным управлением – еще один лингвистический формализм, популярный в сообществе анализаторов, однако другие исследовательские усилия сосредоточены на менее сложных формализмах, таких как тот, что используется в Penn Treebank. Поверхностный анализ направлен на определение границ основных составляющих, таких как именные группы. Еще одна распространенная стратегия для избежания лингвистических споров – анализ зависимостей. Большинство современных анализаторов в той или иной степени статистические, то есть они опираются на корпус обучающих данных, который уже был размечен (проанализирован вручную). Такой подход позволяет системе собирать информацию о частоте встречаемости различных конструкций в конкретных контекстах. (См. машинное обучение.) Используемые подходы включают простые PCFG (вероятностные контекстно-свободные грамматики), метод максимальной энтропии и нейронные сети. Большинство наиболее успешных систем используют лексическую статистику (то есть учитывают идентичность слов, а также их часть речи). Однако такие системы подвержены переобучению и требуют некоторой формы сглаживания для достижения эффективности. Алгоритмы анализа естественного языка не могут полагаться на то, что грамматика обладает «удобными» свойствами, как в случае с грамматиками, разработанными вручную для языков программирования. Как упоминалось ранее, некоторые грамматические формализмы очень сложны для вычислительного анализа; в целом, даже если желаемая структура не является контекстно-свободной, для первого прохода используется некоторое контекстно-свободное приближение к грамматике. Алгоритмы, использующие контекстно-свободные грамматики, часто опираются на один из вариантов алгоритма CYK, обычно с применением некоторых эвристик для отсечения маловероятных вариантов анализа с целью экономии времени. (См. chart parsing.) Однако некоторые системы жертвуют скоростью ради точности, используя, например, линейные версии алгоритма сдвига-восстановления. Относительно недавним развитием стал повторный ранжирование результатов анализа, когда анализатор предлагает большое количество вариантов, а более сложная система выбирает оптимальный. В приложениях для понимания естественного языка семантические анализаторы преобразуют текст в представление его значения.

In some machine translation and natural language processing systems, written texts in human languages are parsed by computer programs. Human sentences are not easily parsed by programs, as there is substantial ambiguity in the structure of human language, whose usage is to convey meaning (or semantics) amongst a potentially unlimited range of possibilities, but only some of which are germane to the particular case. So an utterance "Man bites dog" versus "Dog bites man" is definite on one detail but in another language might appear as "Man dog bites" with a reliance on the larger context to distinguish between those two possibilities, if indeed that difference was of concern. It is difficult to prepare formal rules to describe informal behaviour even though it is clear that some rules are being followed. In order to parse natural language data, researchers must first agree on the grammar to be used. The choice of syntax is affected by both linguistic and computational concerns; for instance some parsing systems use lexical functional grammar, but in general, parsing for grammars of this type is known to be NP complete. Head driven phrase structure grammar is another linguistic formalism which has been popular in the parsing community, but other research efforts have focused on less complex formalisms such as the one used in the Penn Treebank. Shallow parsing aims to find only the boundaries of major constituents such as noun phrases. Another popular strategy for avoiding linguistic controversy is dependency grammar parsing. Most modern parsers are at least partly statistical; that is, they rely on a corpus of training data which has already been annotated (parsed by hand). This approach allows the system to gather information about the frequency with which various constructions occur in specific contexts. (See machine learning.) Approaches which have been used include straightforward PCFGs (probabilistic context free grammars), maximum entropy, and neural nets. Most of the more successful systems use lexical statistics (that is, they consider the identities of the words involved, as well as their part of speech). However such systems are vulnerable to overfitting and require some kind of smoothing to be effective. Parsing algorithms for natural language cannot rely on the grammar having 'nice' properties as with manually designed grammars for programming languages. As mentioned earlier some grammar formalisms are very difficult to parse computationally; in general, even if the desired structure is not context free, some kind of context free approximation to the grammar is used to perform a first pass. Algorithms which use context free grammars often rely on some variant of the CYK algorithm, usually with some heuristic to prune away unlikely analyses to save time. (See chart parsing.) However some systems trade speed for accuracy using, e. g., linear time versions of the shift reduce algorithm. A somewhat recent development has been parse reranking in which the parser proposes some large number of analyses, and a more complex system selects the best option. In natural language understanding applications, semantic parsers convert the text into a representation of its meaning.

Психолингвистика

В психолингвистике анализ включает не только отнесение слов к категориям (формирование онтологических представлений), но и оценку значения предложения в соответствии с правилами синтаксиса, выведенными из заключений, сделанных на основе каждого слова в предложении (известного как коннотация). Обычно это происходит по мере восприятия слов на слух или при чтении. Нейролингвистика рассматривает анализ как функцию рабочей памяти, то есть анализ используется для одновременного удержания нескольких частей одного предложения в сознании, все они легко доступны для анализа по мере необходимости. Поскольку человеческая рабочая память имеет ограничения, это относится и к функции синтаксического анализа. Это подтверждается различными типами синтаксически сложных предложений, представляющих потенциальные трудности для ментального анализа. Первым и, пожалуй, наиболее известным типом предложения, затрудняющим анализ, является предложение-ловушка (garden path sentence). Такие предложения построены таким образом, что наиболее вероятная интерпретация кажется грамматически некорректной, но при более внимательном рассмотрении оказывается грамматически верной. Предложения-ловушки трудно анализировать, поскольку они содержат фразу или слово с несколькими значениями, при этом их наиболее типичное значение относится к другой части речи. Например, в предложении "the horse raced past the barn fell" ("конь, участвовавший в скачках мимо сарая, упал"), слово "raced" первоначально интерпретируется как глагол в прошедшем времени, но в данном предложении оно является частью именной группы. Поскольку анализ используется для определения частей речи, такие предложения бросают вызов аналитическим способностям читателя. Другой тип предложения, который трудно анализировать, – это неоднозначность присоединения, включающая фразу, которая потенциально может относиться к разным частям предложения, что затрудняет определение синтаксических связей (например, "The boy saw the lady with the telescope" – "Мальчик увидел леди с телескопом", где неоднозначная фраза "with the telescope" может относиться либо к мальчику, либо к леди). В нейролингвистике существует множество теорий, стремящихся описать, как происходит анализ в мозге. Одна из таких моделей – более традиционная генеративная модель обработки предложений, которая предполагает наличие в мозге отдельного модуля, предназначенного для синтаксического анализа, которому предшествует доступ к лексическому распознаванию и извлечению, а затем – синтаксическая обработка, рассматривающая единственный синтаксический результат анализа, возвращаясь к пересмотру этой интерпретации только при обнаружении потенциальной проблемы. Противоположная, более современная модель предполагает, что обработка предложения в сознании не является модульной или последовательной. Скорее, она постулирует возможность одновременного рассмотрения нескольких различных синтаксических вариантов, поскольку лексический доступ, синтаксическая обработка и определение значения происходят параллельно в мозге. Таким образом, эти процессы интегрированы. Хотя многое еще предстоит узнать о нейрологии анализа, исследования показали, что в анализе могут участвовать несколько областей мозга, включая левую переднюю височную долю, левую нижнюю лобную извилину, левую верхнюю височную извилину, левую верхнюю лобную извилину, правую заднюю поясную кору и левую угловую извилину. Хотя это и не доказано окончательно, предполагается, что эти различные структуры могут способствовать либо анализу структуры фраз, либо анализу структуры зависимостей, то есть разные типы анализа могут обрабатываться по-разному, что пока не до конца понятно.

In psycholinguistics, parsing involves not just the assignment of words to categories (formation of ontological insights), but the evaluation of the meaning of a sentence according to the rules of syntax drawn by inferences made from each word in the sentence (known as connotation). This normally occurs as words are being heard or read. Neurolinguistics generally understands parsing to be a function of working memory, meaning that parsing is used to keep several parts of one sentence at play in the mind at one time, all readily accessible to be analyzed as needed. Because the human working memory has limitations, so does the function of sentence parsing. This is evidenced by several different types of syntactically complex sentences that propose potentially issues for mental parsing of sentences. The first, and perhaps most well known, type of sentence that challenges parsing ability is the garden path sentence. These sentences are designed so that the most common interpretation of the sentence appears grammatically faulty, but upon further inspection, these sentences are grammatically sound. Garden path sentences are difficult to parse because they contain a phrase or a word with more than one meaning, often their most typical meaning being a different part of speech. For example, in the sentence, "the horse raced past the barn fell", raced is initially interpreted as a past tense verb, but in this sentence, it functions as part of an adjective phrase. Since parsing is used to identify parts of speech, these sentences challenge the parsing ability of the reader. Another type of sentence that is difficult to parse is an attachment ambiguity, which includes a phrase that could potentially modify different parts of a sentence, and therefore presents a challenge in identifying syntactic relationship (i. e. "The boy saw the lady with the telescope", in which the ambiguous phrase with the telescope could modify the boy saw or the lady.) Within neurolinguistics there are multiple theories that aim to describe how parsing takes place in the brain. One such model is a more traditional generative model of sentence processing, which theorizes that within the brain there is a distinct module designed for sentence parsing, which is preceded by access to lexical recognition and retrieval, and then followed by syntactic processing that considers a single syntactic result of the parsing, only returning to revise that syntactic interpretation if a potential problem is detected. The opposing, more contemporary model theorizes that within the mind, the processing of a sentence is not modular, or happening in strict sequence. Rather, it poses that several different syntactic possibilities can be considered at the same time, because lexical access, syntactic processing, and determination of meaning occur in parallel in the brain. In this way these processes are integrated. Although there is still much to learn about the neurology of parsing, studies have shown evidence that several areas of the brain might play a role in parsing. These include the left anterior temporal pole, the left inferior frontal gyrus, the left superior temporal gyrus, the left superior frontal gyrus, the right posterior cingulate cortex, and the left angular gyrus. Although it has not been absolutely proven, it has been suggested that these different structures might favor either phrase structure parsing or dependency structure parsing, meaning different types of parsing could be processed in different ways which have yet to be understood.

Анализ речи

Дискурсный анализ изучает способы анализа использования языка и семиотических явлений. Убедительная речь может быть названа риторикой.

Обзор процесса

Следующий пример демонстрирует типичный случай разбора компьютерного языка с двумя уровнями грамматики: лексическим и синтаксическим. Первый этап – генерация лексем, или лексический анализ, посредством которого входной поток символов разбивается на значимые символы, определяемые грамматикой регулярных выражений. Например, программа-калькулятор будет анализировать ввод, такой как "12 * (3 + 4)^2", и разбивать его на лексемы 12, *, (, 3, +, 4, ), ^, 2, каждая из которых является значимым символом в контексте арифметического выражения. Лексический анализатор будет содержать правила, указывающие, что символы *, +, ^, ( и ) обозначают начало новой лексемы, поэтому бессмысленные лексемы, такие как "12*" или "(3", не будут сгенерированы. Следующий этап – синтаксический разбор, или синтаксический анализ, который проверяет, образуют ли лексемы допустимое выражение. Обычно это делается на основе контекстно-свободной грамматики, которая рекурсивно определяет компоненты, из которых может состоять выражение, и порядок, в котором они должны располагаться. Однако не все правила, определяющие языки программирования, могут быть выражены только контекстно-свободными грамматиками, например, проверка типов и корректное объявление идентификаторов. Эти правила могут быть формально выражены с помощью атрибутных грамматик. Заключительный этап – семантический разбор, или семантический анализ, который определяет последствия только что проверенного выражения и выполняет соответствующие действия. В случае калькулятора или интерпретатора действие заключается в вычислении значения выражения или программы; компилятор же, напротив, будет генерировать какой-либо код. Атрибутные грамматики также могут быть использованы для определения этих действий.