СИНТАКСИЧЕСКИЙ АНАЛИЗАТОР ЭТО

Текущая версия страницы пока не проверялась опытными участниками и может значительно отличаться от версии, проверенной 24 июня 2020 года; проверки требуют 4 правки.

Парсер (англ. ; от  — анализ, разбор), или синтаксический анализатор, — часть программы, преобразующей входные данные (как правило, текст) в некий структурированный формат, нужный для задач последующего их (данных) анализа и использования. Технически, парсер выполняет синтаксический анализ данных (например, текста).

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

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

Как правило, результатом синтаксического анализа является синтаксическое строение предложения, представленное либо в виде дерева зависимостей, либо в виде дерева составляющих, либо в виде некоторого сочетания первого и второго способов представления.

См. также LL

Синтаксический LL-анализатор (LL parser) — в информатике нисходящий синтаксический анализатор для некоторого подмножества контекстно-свободных грамматик, известных как LL-грамматики. При этом не все контекстно-свободные грамматики являются LL-грамматиками.

Буквы L в выражении «LL-анализатор» означают, что входная строка анализируется слева направо (left to right), и при этом строится её левосторонний вывод (leftmost derivation).

LL-анализатор называется LL(k)-анализатором, если данный анализатор использует предпросмотр на k токенов (лексем) при разборе входного потока. Грамматика, которая может быть распознана LL(k)-анализатором без возвратов к предыдущим символам, называется LL(k)-грамматикой. Язык, который может быть представлен в виде LL(k)-грамматики, называется LL(k)o-языком. Существуют LL(k+n)-языки, которые не являются LL(k)-языками.

Далее описывается анализатор, в основе которого лежит построение таблиц; альтернативой может служить анализатор, построенный методом рекурсивного спуска, который обычно пишется вручную (хотя существуют и исключения, например, генератор синтаксических анализаторов ANTLR для LL(*) грамматик).

LL

-грамматики очень распространены, потому что соответствующие им LL-анализаторы просматривают поток только на один символ вперед при принятии решения о том, какое правило грамматики необходимо применить. Языки, основанные на грамматиках с большим значением k, традиционно считались трудными для распознавания, хотя при широком распространении генераторов синтаксических анализаторов, поддерживающих LL(k) грамматики с произвольным k, это замечание уже неактуально.

LL-анализатор называется LL(*)-анализатором, если нет строгого ограничения для k и анализатор может распознавать язык, если токены принадлежат какому-либо регулярному множеству (например, используя детерминированные конечные автоматы).

Существуют противоречия между так называемой «Европейской школой» построения языков, которая основывается на LL-грамматиках, и «Американской школой», которая предпочитает LR-грамматики. Такие противоречия обусловлены традициями преподавания и деталями описания различных методов и инструментов в конкретных учебниках; кроме того, своё влияние оказал Н. Вирт из ETHZ, чьи исследования описывают различные методы оптимизации LL

распознавателей и компиляторов.

Синтаксический анализ. Контекстно-свободные грамматики.
Нисходящие анализаторы. Метод рекурсивного спуска.

О методах определения языков

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

Грамматики одинаково помогают решать задачи как программистов, использующих язык, так и создателей компиляторов для данного языка:

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

Синтаксический анализ

Синтаксический — это процесс, который определяет, принадлежит ли некоторая последовательность лексем языку, порождаемому грамматикой. В принципе, по любой грамматике можно построить синтаксический анализатор, но грамматики, используемые на практике, имеют специальную форму. Например, известно, что для любой контекстно-свободной грамматики может быть построен анализатор, сложность которого не превышает для строки длины , но в большинстве случаев по заданному языку программирования мы можем построить такую грамматику, которая позволит сконструировать и более быстрый анализатор. Анализаторы реально используемых языков обычно имеют ; это достигается, например, за счет просмотра исходной программы слева направо с заглядыванием вперед на один (лексический ).

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

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

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

Классы синтаксических анализаторов

Большинство известных методов анализа принадлежат одному из двух классов, один из которых объединяет нисходящие (top-down) алгоритмы, а другой — восходящие (bottom-up) алгоритмы. Происхождение этих терминов связано с тем, каким образом строятся узлы синтаксического дерева: либо от корня (аксиомы грамматики) к листьям (терминальным символам), либо от листьев к корню.

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

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

С другой стороны, восходящие анализаторы могут анализировать большее количество грамматик, чем нисходящие, и поэтому именно для таких методов существуют программы, которые умеют автоматически строить анализаторы. С восходящими анализаторами связаны -грамматики. В этом обозначении буква L по-прежнему означает, что входная цепочка просматривается слева направо (left-to-right ), а буква R означает, что строится цепочки ( ). С помощью -грамматик можно определить большинство использующихся в настоящее время языков программирования.

Метод рекурсивного спуска

Одним из наиболее простых и потому одним из наиболее популярных методов нисходящего синтаксического анализа является метод рекурсивного спуска (recursive descent method) .

Для объяснения принципов, лежащих в основе метода рекурсивного спуска, рассмотрим задачу вычисления значения арифметической формулы. Будем рассматривать формулы, состоящие из целочисленных значений, бинарных операций сложения ( + ), вычитания ( — ), умножения ( * ) и деления нацело ( / ), а также круглых скобок. Как обычно, приоритеты операций умножения и деления равны и их приоритет больше, чем приоритеты операций сложения и вычитания, причем приоритеты этих операций также равны. Будем называть + и — операциями типа сложения, а * и / — операциями типа умножения. Круглые скобки используются для изменения стандартного порядка выполнения операций. Наша задача заключается в написании программы, вычисляющей формулы.

Изучаемые нами формулы можно представить следующим образом:

Вычисление значения формулы

Итак, мы можем разделить все формулы на следующие классы:

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

Expression (Term (Factor ())),

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

Опишем процедуру, вычисляющую простейшей формулы:

Лексический анализ

Входом компилятора служит на исходном языке программирования. С точки зрения компилятора это просто последовательность символов. Задача первой фазы компиляции, лексического анализатора (lexical analysis) , заключается в разборе цепочки и выделении некоторых более «крупных» единиц, лексем, которые удобнее для последующего разбора. Примерами лексем являются основные ключевые слова, идентификаторы, константные значения (числа, строки, логические) и т.п.

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

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

будет подробно рассмотрен в
«Лексический анализ»
.

Синтаксический анализатор (syntax analyzer, parser) получает на вход результат работы лексического анализатора и разбирает его в соответствии с некоторой грамматикой. Эта аналогична грамматике, используемой при описании входного языка. Однако входного языка обычно не уточняет, какие конструкции следует считать лексемами.

Синтаксический является одной из наиболее формализованных и хорошо изученных фаз компиляции.
«Теория языков»
посвящена математическому аппарату, используемому при описании языков и создании синтаксических анализаторов. Различные методы построения синтаксических анализаторов будут рассмотрены в
«Синтаксические анализаторы. Нисходящие анализаторы»
,
«Восходящие анализаторы»
и
«Грамматики и YACC»
.

После синтаксического анализа можно считать, что исходная преобразована в некоторое промежуточное . Некоторые распространенные формы промежуточного представления программы будут рассмотрены в
«Семантический анализ. Внутреннее представление»
. Пока же мы остановимся на одной форме промежуточного представления, которая будет использована в нашем курсе, — на дереве разбора программы (иногда его также называют синтаксическим деревом). В дереве разбора программы внутренние узлы соответствуют операциям, а представляют операнды.

Видозависимый анализ

Видозависимый анализ (type checking) , иногда также называемый семантическим анализом (semantic analysis) , обычно заключается в проверке правильности типов данных, используемых в программе. Кроме того, на этом этапе должен также проверить, соблюдаются ли определенные контекстные условия входного языка. В современных языках программирования одним из примеров контекстных условий может служить обязательность описания переменных: для каждого использующего вхождения идентификатора должно существовать единственное определяющее вхождение. Другой пример контекстного условия: число и атрибуты фактических параметров вызова процедуры должны быть согласованы с определением этой процедуры.

Такие контекстные условия не всегда могут быть проверены во время синтаксического анализа и потому обычно выделяются в отдельную фазу. Эта фаза компиляции подробно обсуждается в
«Семантический анализ. Внутреннее представление»
.

Оптимизация кода

Основная цель фазы оптимизации (code optimization) заключается в преобразовании промежуточного представления программы в целях повышения эффективности результирующей объектной программы. Отметим, что существуют различные критерии эффективности, например, скорость исполнения или объем памяти, требуемый программе. Очевидно, что все преобразования, осуществляемые на фазе оптимизации, должны приводить к программе, эквивалентной исходной.

Некоторые оптимизации тривиальны, другие требуют достаточно сложного анализа программы. В
«Оптимизация»
и
«Анализ потока управления»
мы рассмотрим потоков управления программы и анализ потоков данных. Затем в
«Анализ потоков данных»
мы рассмотрим сам этап оптимизации программ и рассмотрим наиболее распространенные оптимизации:

Синтаксический анализатор – это программное обеспечение, которое анализирует структуру текста и определяет его соответствие грамматике, что позволяет автоматически проверять и разбирать программный код, упрощая процесс разработки и отладки.

О чем статья

Введение

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

Нужна помощь в написании работы?

Написание учебной работы за 1 день от 100 рублей. Посмотрите отзывы наших клиентов и узнайте стоимость вашей работы.

Определение синтаксического анализатора

Синтаксический анализатор, также известный как парсер, является одной из ключевых компонент программного обеспечения, используемого в компиляторах и интерпретаторах. Он выполняет анализ входного текста, проверяет его на соответствие определенной грамматике и создает структуру данных, называемую синтаксическим деревом или абстрактным синтаксическим деревом (AST).

Синтаксический анализатор играет важную роль в процессе компиляции или интерпретации программного кода. Он принимает входной текст, который может быть написан на определенном языке программирования, и проверяет его на наличие синтаксических ошибок. Если текст соответствует грамматике языка, синтаксический анализатор создает структуру данных, которая представляет собой иерархическое представление программы.

Синтаксический анализатор может быть реализован с использованием различных алгоритмов, таких как рекурсивный спуск, LL(k), LR(k) и т.д. Он может работать в двух режимах: синтаксический анализ сверху вниз (top-down) и синтаксический анализ снизу вверх (bottom-up).

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

Цели и задачи разработки синтаксического анализатора

Синтаксический анализатор является одной из ключевых компонент программного обеспечения, используемого в компиляторах, интерпретаторах и других инструментах для обработки языков программирования. Его основной целью является разбор входного текста и создание структуры данных, которая будет использоваться в дальнейшем для выполнения семантического анализа и генерации исполняемого кода.

Цели разработки синтаксического анализатора

1. Разбор входного текста: Основная цель синтаксического анализатора – разбор входного текста, который представляет собой последовательность лексем или символов. Синтаксический анализатор анализирует эту последовательность и определяет, соответствует ли она грамматике языка программирования.

2. Построение синтаксического дерева: Синтаксический анализатор создает синтаксическое дерево, которое представляет структуру программы. Синтаксическое дерево является иерархическим представлением программы, где каждый узел представляет конструкцию языка программирования, а дочерние узлы представляют ее подвыражения.

3. Проверка синтаксиса: Синтаксический анализатор проверяет, соответствует ли входной текст грамматике языка программирования. Если входной текст содержит синтаксические ошибки, синтаксический анализатор обнаруживает их и генерирует сообщения об ошибках, которые помогают программисту исправить ошибки.

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

2. Выбор алгоритма синтаксического анализа: Существует множество алгоритмов синтаксического анализа, таких как рекурсивный спуск, LL(k), LR(k) и т.д. Задача разработчика – выбрать подходящий алгоритм, который обеспечит эффективный и точный разбор входного текста.

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

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

В целом, разработка синтаксического анализатора требует глубокого понимания грамматики языка программирования, алгоритмов синтаксического анализа и навыков программирования. Он играет важную роль в процессе разработки программного обеспечения, помогая программистам понять структуру программы и обнаружить возможные ошибки в синтаксисе.

Типы синтаксических анализаторов

Синтаксический анализатор, также известный как парсер, является одной из ключевых компонент программного обеспечения, которая выполняет анализ синтаксиса входного текста. Существует несколько типов синтаксических анализаторов, каждый из которых имеет свои особенности и применение.

Рекурсивный спуск

Рекурсивный спуск – это один из самых простых и понятных типов синтаксических анализаторов. Он основан на рекурсивных функциях, которые соответствуют правилам грамматики языка. Каждая функция анализирует определенное правило грамматики и вызывает другие функции для анализа подвыражений. Рекурсивный спуск легко реализовать и понять, но может быть неэффективным для больших и сложных грамматик.

Метод рекурсивного спуска с предиктивным анализом

Метод рекурсивного спуска с предиктивным анализом – это улучшенная версия рекурсивного спуска, которая использует предиктивный анализ для выбора правил грамматики на основе следующего символа входного текста. Это позволяет избежать обратной откатки и повышает производительность анализатора. Однако этот метод требует более сложной реализации и может быть ограничен в использовании для некоторых типов грамматик.

Метод восходящего анализа

Метод восходящего анализа – это тип синтаксического анализа, который строит дерево разбора, начиная с листьев и двигаясь вверх к корню. Он использует стек для отслеживания состояния анализа и применяет правила грамматики в обратном порядке. Метод восходящего анализа может быть более эффективным для больших и сложных грамматик, но требует более сложной реализации и может быть менее интуитивным для понимания.

Метод LL

Метод LL

– это метод восходящего анализа, который использует однозначные предиктивные функции для выбора правил грамматики. Он основан на следующем символе входного текста и верхнем символе стека. Метод LL

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

Метод LR

Метод LR

– это метод восходящего анализа, который использует однозначные предиктивные функции для выбора правил грамматики. Он основан на следующем символе входного текста и верхнем символе стека. Метод LR

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

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

Алгоритмы синтаксического анализа

Синтаксический анализатор (парсер) – это инструмент, который анализирует последовательность символов и определяет, соответствует ли эта последовательность заданной грамматике. Алгоритмы синтаксического анализа используются в компиляторах, интерпретаторах и других инструментах для обработки и анализа языков программирования и других формальных языков.

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

Метод рекурсивного спуска с предиктивным анализом – это улучшенная версия рекурсивного спуска, которая использует предиктивный анализ для выбора правил разбора на основе следующего символа входной последовательности. Предиктивный анализ основан на первом символе каждого правила грамматики и позволяет выбрать правило разбора без необходимости обратного отслеживания. Это улучшает производительность и эффективность алгоритма.

Метод LL

– это алгоритм синтаксического анализа, который использует предиктивный анализ для выбора правил разбора на основе следующего символа входной последовательности. Он работает слева направо и строит левосторонний вывод. Метод LL

использует таблицу предсказания, которая содержит информацию о том, какое правило грамматики следует применять в зависимости от текущего символа входной последовательности и верхнего символа стека.

Метод LR

– это алгоритм синтаксического анализа, который использует предсказание на основе следующего символа входной последовательности и верхнего символа стека. Он работает справа налево и строит правосторонний вывод. Метод LR

использует автомат со стеком (LR-автомат) и таблицу действий и переходов для определения следующего шага анализатора на основе текущего символа входной последовательности и верхнего символа стека. Метод LR

может быть использован для широкого спектра грамматик и обеспечивает быстрое и эффективное выполнение анализа.

Каждый из этих алгоритмов имеет свои преимущества и недостатки, и выбор конкретного алгоритма зависит от требований и характеристик конкретного языка программирования или грамматики.

Примеры использования синтаксического анализатора

Одним из основных примеров использования синтаксического анализатора является компиляция программного кода. Компиляторы используют синтаксический анализатор для разбора и анализа исходного кода программы, чтобы проверить его синтаксическую корректность и построить внутреннее представление программы, такое как абстрактное синтаксическое дерево (AST). Это позволяет компилятору дальше выполнять оптимизации и генерацию машинного кода.

Проверка синтаксиса в текстовых редакторах

Синтаксические анализаторы также используются в текстовых редакторах и интегрированных средах разработки (IDE) для проверки синтаксиса в реальном времени. Например, при написании кода на языке программирования, синтаксический анализатор может подсвечивать ошибки синтаксиса и предлагать автодополнение кода, чтобы помочь разработчику.

Парсинг языков разметки

Синтаксические анализаторы также широко используются для парсинга языков разметки, таких как HTML, XML и JSON. Синтаксический анализатор может разбирать входную последовательность тегов и атрибутов, чтобы проверить их корректность и построить структуру документа. Это позволяет программам обрабатывать и анализировать данные в формате разметки.

Анализ запросов в базах данных

Синтаксические анализаторы также используются для анализа запросов в базах данных. Например, SQL-запросы могут быть разобраны синтаксическим анализатором, чтобы проверить их корректность и построить структуру запроса. Это позволяет базам данных эффективно обрабатывать запросы и возвращать соответствующие результаты.

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

Преимущества и недостатки синтаксического анализатора

1. Автоматизация анализа: Синтаксический анализатор позволяет автоматизировать процесс анализа структуры текста или кода. Он может быстро и точно определить, соответствует ли текст определенным правилам и синтаксису.

2. Обнаружение ошибок: Синтаксический анализатор может обнаружить ошибки в структуре текста или кода. Он может предупредить о неправильном использовании ключевых слов, операторов или символов, что помогает разработчикам избежать ошибок и повысить качество программного обеспечения.

3. Улучшение производительности: Синтаксический анализатор может оптимизировать процесс обработки текста или кода. Он может упростить структуру и убрать ненужные элементы, что позволяет улучшить производительность и эффективность работы с данными.

4. Расширяемость: Синтаксический анализатор может быть расширен для поддержки новых языков или форматов данных. Это позволяет адаптировать его под конкретные потребности и использовать его в различных областях.

1. Сложность разработки: Разработка синтаксического анализатора может быть сложной задачей, особенно для сложных языков или форматов данных. Требуется глубокое понимание синтаксиса и грамматики языка, а также опыт в разработке алгоритмов анализа.

2. Ограничения в гибкости: Синтаксический анализатор работает на основе заданных правил и грамматики, что может ограничивать его гибкость. Если структура текста или кода не соответствует заданным правилам, анализатор может не справиться с его обработкой.

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

4. Требования к ресурсам: Синтаксический анализатор может потреблять значительные ресурсы, особенно при обработке больших объемов текста или кода. Это может замедлить процесс анализа и требовать дополнительных вычислительных мощностей.

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

Таблица сравнения типов синтаксических анализаторов

Синтаксический анализатор – это инструмент, который позволяет анализировать и понимать структуру и синтаксис программного кода. Он играет важную роль в разработке компиляторов, интерпретаторов и других инструментов для обработки кода. Существует несколько типов синтаксических анализаторов, каждый из которых имеет свои преимущества и недостатки. Алгоритмы синтаксического анализа позволяют эффективно обрабатывать и анализировать большие объемы кода. В целом, синтаксический анализатор является важным инструментом для разработчиков программного обеспечения и помогает обеспечить правильность и корректность кода.

Всё что угодно, имеющее «синтаксис», поддается автоматическому анализу.

Построение таблиц синтаксического анализа для LL(k) анализаторов

Размер таблицы синтаксического анализа в худшем случае имеет показательную сложность в зависимости от k. Однако, после выпуска набора инструментальных средств конструирования компиляторов (PCCTS, теперь известный как ANTLR) приблизительно в 1992 году было показано, что размер таблицы синтаксического анализа для большинства языков программирования не имеет тенденции к показательному росту, так как не является худшим вариантом. Кроме того, в определенных случаях было возможно создание даже LL(*)-анализаторов. Однако, несмотря на это, традиционные генераторы синтаксических анализаторов, такие как yacc/GNU bison, используют LALR

таблицы синтаксического анализа, чтобы создать ограниченный LR-анализатор.

Восстановление после ошибок

Простейший способ реагирования на некорректную входную цепочку лексем — завершить синтаксический анализ и вывести сообщение об ошибке. Однако часто оказывается полезным найти за одну попытку синтаксического анализа как можно больше ошибок. Именно так ведут себя трансляторы большинства распространённых языков программирования.

Таким образом, перед обработчиком ошибок синтаксического анализатора стоят следующие задачи:

Ниже описаны наиболее известные стратегии восстановления после ошибок.

Восстановление в режиме паники

При обнаружении ошибки синтаксический анализатор пропускает входные лексемы по одной, пока не будет найдена одна из специально определённого множества синхронизирующих лексем. Обычно такими лексемами являются разделители, например: ;, ) или }. Набор синхронизирующих лексем должен определять разработчик анализируемого языка. При такой стратегии восстановления может оказаться, что значительное количество символов будут пропущены без проверки на наличие дополнительных ошибок. Данная стратегия восстановления наиболее проста в реализации.

Восстановление на уровне фразы

Иногда при обнаружении ошибки синтаксический анализатор может выполнить локальную коррекцию входного потока так, чтобы это позволило ему продолжать работу. Например, перед точкой с запятой, отделяющей различные операторы в языке программирования, синтаксический анализатор может закрыть все ещё не закрытые круглые скобки. Это более сложный в проектировании и реализации способ, однако в некоторых ситуациях, он может работать значительно лучше восстановления в режиме паники. Естественно, данная стратегия бессильна, если настоящая ошибка произошла до точки обнаружения ошибки синтаксическим анализатором.

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

Наиболее часто встречающиеся виды парсеров:

Виды парсеров по количеству операций чтения входных данных:

Исходный код парсера может быть:

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

Эти шаги повторяются до тех пор, пока не произойдёт останов. После останова мы получим или сообщение об ошибке, или сообщение об успешном распознавании цепочки.

Таблица синтаксического анализа

Чтобы объяснить принцип работы синтаксического LL анализатора, рассмотрим следующую грамматику:

И проанализируем разбор на примере строки:

(1 + 1)

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

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

Процедура синтаксического анализа

Синтаксический анализатор просматривает первый символ ‘(‘ из входного потока, в этот момент на вершине стека находится символ ‘S’, на пересечении этих значений в таблице синтаксического разбора находится правило из списка грамматики. В данном примере это правило номер 2, которое предписывает заменить в стеке символ ‘S’ на цепочку ‘(S + F)’.
Состояние стека после применения этого правила:

На следующем шаге анализатор читает символ ‘(‘ из входного потока. Так как на вершине стека находится аналогичный символ ‘(‘, то происходит чтение данного символа с ленты и его удаление из стека.
Состояние стека после применения этого правила:

Далее на ленте находится символ ‘1’, а на вершине стека ‘S’, на пересечении этих символов в таблице находится правило 1. После применения этого правила, согласно таблице, анализатор применяет правило 3.
Состояние стека после применения правил:

Далее синтаксический анализатор читает ‘1’ и ‘+’ из входного потока и, так как они соответствуют следующим двум элементам на стеке, также удаляет их из стека.
В результате чего стек имеет вид:

В следующих трёх шагах символ ‘F’ в стеке будет заменен на ‘1’, после чего символы ‘1’ и ‘)’ будут прочитаны с ленты и удалены из стека. В результате на вершине стека и на ленте будет находиться символ ‘

В таком случае анализатор сообщит об успешном завершении и выдаст список правил, которые были применены в процессе вывода:

Данные правила действительно являются крайним левым выводом:

LL генераторы синтаксических анализаторов

Современные генераторы синтаксических анализаторов, для LL грамматик с мультиэстафетным предвидением, включают:

Построение LL

таблицы синтаксического анализа

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

грамматикой.

Синтаксический анализатор предназначен для разрешения проблемы принадлежности строки заданной грамматике и построения дерева вывода в случае принадлежности.

Синтаксический анализатор состоит из:

В строках таблицы располагаются символы магазинного алфавита, а в столбцах — символы терминального алфавита.

При запуске синтаксического анализа, стек уже содержит два символа:

Где ‘

Синтаксический анализатор пытается при помощи правил грамматики заменить в стеке аксиому на цепочку символов, аналогичную цепочке, находящейся на входной ленте, и затем полностью прочитать ленту, опустошая стек.

Средства разработки анализаторов

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

, согласно определению это означает успешный разбор цепочки.

В таком случае анализатор сообщит об успешном завершении и выдаст список правил, которые были применены в процессе вывода:

Данные правила действительно являются крайним левым выводом:

LL генераторы синтаксических анализаторов

Современные генераторы синтаксических анализаторов, для LL грамматик с мультиэстафетным предвидением, включают:

Построение LL

таблицы синтаксического анализа

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

грамматикой.

Синтаксический анализатор предназначен для разрешения проблемы принадлежности строки заданной грамматике и построения дерева вывода в случае принадлежности.

Синтаксический анализатор состоит из:

В строках таблицы располагаются символы магазинного алфавита, а в столбцах — символы терминального алфавита.

При запуске синтаксического анализа, стек уже содержит два символа:

Где ‘$’ — специальный терминал, служащий для указания конца стека, а ‘S’ — аксиома грамматики.

Синтаксический анализатор пытается при помощи правил грамматики заменить в стеке аксиому на цепочку символов, аналогичную цепочке, находящейся на входной ленте, и затем полностью прочитать ленту, опустошая стек.

Средства разработки анализаторов

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

 — специальный терминал, служащий для указания конца стека, а ‘S’ — аксиома грамматики.

Синтаксический анализатор пытается при помощи правил грамматики заменить в стеке аксиому на цепочку символов, аналогичную цепочке, находящейся на входной ленте, и затем полностью прочитать ленту, опустошая стек.

Средства разработки анализаторов

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

, согласно определению это означает успешный разбор цепочки.

В таком случае анализатор сообщит об успешном завершении и выдаст список правил, которые были применены в процессе вывода:

Данные правила действительно являются крайним левым выводом:

LL генераторы синтаксических анализаторов

Современные генераторы синтаксических анализаторов, для LL грамматик с мультиэстафетным предвидением, включают:

Построение LL

таблицы синтаксического анализа

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

грамматикой.

Синтаксический анализатор предназначен для разрешения проблемы принадлежности строки заданной грамматике и построения дерева вывода в случае принадлежности.

Синтаксический анализатор состоит из:

В строках таблицы располагаются символы магазинного алфавита, а в столбцах — символы терминального алфавита.

При запуске синтаксического анализа, стек уже содержит два символа:

Где ‘$’ — специальный терминал, служащий для указания конца стека, а ‘S’ — аксиома грамматики.

Синтаксический анализатор пытается при помощи правил грамматики заменить в стеке аксиому на цепочку символов, аналогичную цепочке, находящейся на входной ленте, и затем полностью прочитать ленту, опустошая стек.

Средства разработки анализаторов

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