Грамматика языка. Грамматический (синтаксический) разбор предложения
Выбери формат для чтения
Загружаем конспект в формате pdf
Это займет всего пару минут! А пока ты можешь прочитать работу в формате Word 👇
Синтаксический
анализ
Тема 4
Содержание
1. Основные определения и предпосылки
2. Грамматика языка
3. Грамматический (синтаксический) разбор
предложения
4. Грамматический разбор сверху-вниз
5. LL(1) - грамматики
2
Основные
определения и
предпосылки
3
Основные определения
• Синтаксис (грамматика) – четкие и
однозначные грамматические правила,
которые должны соблюдаться при
написании программы:
• if (ab;
4
Синтаксический анализатор
• Синтаксический анализатор (парсер) – программа
для проверки правильности грамматического
построения конструкций предложений исходного
текста программы
5
1я задача синтаксического
анализатора
распознать предложения исходной программы
как языковые конструкции, полностью
соответствующие используемой грамматике.
• A=a+b;
• A=a+;
• IF a<0 THEN a=-a; {Pascal}
• If (a<0) a=-a; //C++
6
2я задача синтаксического
анализатора
• заполнение таблицы идентификаторов
семантической информацией.
Парсер является первой фазой компилятора,
которая должна определить не только
корректность синтаксиса предложения, но и его
смысл.
Кроме этого, многие компиляторы интегрируют в
парсер и процедуры семантического анализа,
которые создают промежуточный код программы.
7
Пример
Парсер проверяет синтаксис инструкции описания типа
например такого вида:
short integer a, b, c;
После успешной проверки синтаксиса парсер должен
• найти в таблице идентификаторов идентификаторы
переменных a, b, c
• заполнить данные дескрипторов этих величин, а именно
записать длину переменной и ее тип в соответствующие
поля.
8
• Все конструкции
современных языков
программирования
имеют четкие и
однозначные
грамматические
правила (синтаксис),
которые должны
соблюдаться при
написании программы.
9
Для выявления возможных ошибок и контроля
правильности построения предложений языка в
исходном тексте необходимо иметь:
• Предложение языка, представленное в виде
таблицы стандартных символов
• Грамматику языка, расположенную в памяти (в
некоторых методах грамматического разбора
это требование может отсутствовать)
• Алгоритм грамматического разбора,
реализованный в виде синтаксического
анализатора (PARSER)
10
Объекты синтаксического
анализа
• могут быть все формальные системы, чьи
компоненты имеют «синтаксическое
описание».
11
Области применения
синтаксического анализа (1)
• Языки программирования — разбор исходного
кода языков программирования, в процессе
трансляции (компиляции или интерпретации);
• Структурированные данные — данные, языки
их описания, оформления и т. д. Например, XML,
HTML, CSS, ini-файлы, специализированные
конфигурационные файлы и т. п.;
• Построение индекса в поисковой системе;
• SQL-запросы (DSL-язык);
12
Области применения
синтаксического анализа (2)
• Математические выражения;
• Регулярные выражения (которые, в свою очередь,
могут использоваться для автоматизации
лексического анализа);
• Формальные грамматики;
• Лингвистика — человеческие языки. Например,
машинный перевод и другие генераторы текстов.
• Например: технология ABBYY Compreno использует
ABBYY Syntactic and Semantic Parser (ASSP) и
построена на базе полного синтаксического анализа
текста и иерархии универсальных семантических
значений и отношений между ними.
13
Томита-парсер
это инструмент для извлечения
структурированных данных (фактов) из
текста на естественном языке.
Извлечение фактов происходит при
помощи контекстно-свободных грамматик
и словарей ключевых слов.
В 1984 году Масару Томита описал
имплементацию алгоритма GLRпарсинга (Generalized left-to-right
algorithm), поставив перед собой задачу
эффективно и точно производить анализ
текстов на естественном языке.
14
15
Как работает Томита-парсер
16
17
К примеру на сегодняшний
день Томита-парсер
используется в четырех
сервисах Яндекса:
• Почта. Если вам придет письмо, в котором вам в
произвольной форме предлагают встретиться, Томита
определит, где и когда будет проходить эта встреча, и
предложит внести ее в календарь. Примерно так же
обстоит дело с авиабилетами.
• Новости. В этом сервисе Томита помогает автоматически
осуществлять географическую привязку и группировку
новостных сюжетов. Если в заметке упоминается название
страны, города или полный адрес места, где произошло
описываемое событие, Томита выделит эту информацию и
привяжет заметку к точке на карте.
18
• Авто. Сервис Яндекс. Авто агрегирует отзывы об автомобилях с
различных площадок, там же можно оставить свой отзыв.
Томита анализирует эти отзывы, оценивает эмоциональную
окраску
высказываний
о
различных
характеристиках
автомобилей. На основе этих данных составляется рейтинг
характеристик: внешний вид, ходовые качества, салон и комфорт,
эксплуатация, впечатления.
• Работа. Сервис Яндекс. Работа собирает с разных площадок
объявления о поиске работников. Они также обычно
составляются в произвольной форме. Томита анализирует эти
тексты и выделяет требования к кандидатам и условия работы,
формализует из, благодаря чему при поиске работы пользователи
могут фильтровать вакансии.
19
GLR-алгоритм
• В некотором роде GLR-алгоритм — это расширенная
версия алгоритма LR-парсинга.
• Но LR-алгоритм предназначен для анализа текстов,
написанных на достаточно строго детерминированных
языках программирования, и с естественным языком
работать не может.
• Томита решил эту проблему путем параллелизации
стеков, что позволило рассматривать различные
трактовки тех или иных участков текста: как только
возникает возможность различной трактовки, стек
разветвляется. Таких последовательных разветвлений
может быть несколько, но в процессе анализа
ошибочные ветви отбрасываются, и результатом
становится наиболее длинная цепочка.
• При этом алгоритм выдает результаты своей работы в
режиме реального времени, по мере продвижения
вглубь текста, другие алгоритмы обработки
естественного языка такой особенностью не обладают.
20
Инструменты для автоматического создания
парсеров
• Существует особый класс программного обеспечения
предназначенного для автоматического создания
парсеров - генераторы парсеров.
•
•
•
•
•
•
•
ANTLR — генератор парсеров
gppg — генератор парсеров для языка C#
JavaCC — генератор парсеров для языка Java
PEG.js — генератор парсеров для Javascript
Jison — генератор парсеров для Javascript
Xerces — генератор XML-парсеров
AGFL — генератор парсеров естественного языка
21
Пример дерева синтаксического
разбора
• Грамматика:
::= READ ( )
::=word | , word
Дерево разбора:
• Исходное предложение:
READ (VALUE)
READ (
word
)
{VALUE}
22
Входные данные для парсера
• После того как лексический анализатор
распознал лексемы предложения, каждой
лексеме ставится в соответствие числовой код
(стандартный символ), представляющий собой
индекс таблицы местонахождения лексемы.
• Входной строкой парсера является исходное
предложение в виде строки кодов.
23
Таблица служебных слов.
Пример
Индекс
Служебное слово
05
:=
…
15
IF
…
20
THEN
…
25
;
…
30
>
…
24
ПРИМЕР
IF A > 2.5 THEN B:=0;
• Служебное слово IF (пусть его индекс в таблице служебных слов равен, например, 15)
• Идентификатор A (код - 01)
• Однопозиционный разделитель > (индекс в таблице служебных слов равен,
например, 30)
• Константа 2.5 (код 02)
• Служебное слово THEN (индекс в таблице служебных слов равен, например, 20)
• Идентификатор B (код - 01)
• Двухпозиционный разделитель := (код – 05)
• Константа 0 (код 02)
• Однопозиционный разделитель ; (индекс в таблице служебных слов равен,
например, 25)
25
Представление конструкций языка в виде
таблиц стандартных символов
IF A > 2.5 THEN B := 0 ;
| | | |
|
-- исходный текст
| | | |
[15] [1][30] [2] [20] [1] [5] [2][25] – строка кодов
(таблица стандартных символов).
26
Грамматика языка
27
Грамматика языка
• Для описания правил построения предложений
большинства языков программирования применяется
контекстно-независимая грамматика в ее различных
модификациях, записанная в форме Бэкуса-Наура.
• В этой нотации метасимволы (символы, описывающие
структуру предложения) заключаются в так
называемые метаскобки (угловые скобки), например:
<предложение>
• Терминальные символы записываются
непосредственно в том виде, как мы их видим в тексте
программы
28
:
Пример: Описание
оператора if языка PASCAL
в расширенной БНФ
29
Пример грамматики для
русского языка
• <предложение>::=<подлежащее> <сказуемое>
• <подлежащее>::=<существительное>| <местоимение>
• <существительное>::=дом | слон | … | компьютер
• <местоимение> :=я | он
• ::=идет | стоит | бежит
• дом, слон, компьютер, я, он, идет, стоит, бежит – лексемы
объектного языка
30
•
•
•
•
•
дом стоит
он идет
компьютер бежит
я идет
И т.д.
• О семантике (смысловом содержании
предложения) речь пока не идет, хотя
понятно, что при переводе с одного языка
на другой мы должны заменить алфавит,
лексику (слова), синтаксис (грамматику)
одного языка на алфавит, лексику и
синтаксис другого языка, но при этом
смысл (семантика) должен остаться без
изменения! – это классическая задача
любого перевода.
31
Пример грамматики для
арифметических выражений
• E ::= E+T | E-T | T
• T ::= T/F | T*F | F
• F ::= (E) | i
• E- Expression (выражение) – начальный символ
• T – Term (член)
• F – Factor (коэффициет)
• Терминальные символы: +, -, *, /, круглые скобки и символ i (любой
идентификатор)
32
Грамматический
(синтаксический)
разбор
предложения
33
Классификация методов синтаксического
разбора
По направлению разбора
• Нисходящие методы (сверху-вниз или
Top-to-down)
• Восходящие методы (снизу-вверх или
Down-to-top)
• Смешанные методы (сочетают в себе
черты восходящих и нисходящих методов)
• Другие (например: алгоритм Early)
34
По последовательности разбора
Последовательность разбора определяет, каким
образом осуществляется формирование фрагмента
дерева разбора на каждом шаге подстановки.
• Слева-направо LL parser (Left-to-Left, Leftmost
derivation parser)
• Справа-налево LR(k)-парсер (Left-to-Right, Rightmost
derivation parser)
• Произвольное
35
Классы синтаксических анализаторов
• Большинство известных методов анализа принадлежат
одному из двух классов, один из которых объединяет
нисходящие (top-down) алгоритмы, а другой –
восходящие (bottom-up) алгоритмы.
• Нисходящим анализаторам соответствуют LL-грамматики,
а восходящим анализаторам - LR-грамматики.
• Происхождение этих терминов связано с тем, каким
образом строятся узлы синтаксического дерева: либо от
корня (начального символа грамматики) к листьям
(терминальным символам), либо от листьев к корню.
36
• Популярность нисходящих анализаторов связана с тем,
что эффективный нисходящий анализатор достаточно
легко может быть построен вручную, например, методом
рекурсивного спуска. Кроме того, LL-грамматики легко
обобщаются:
грамматики,
не являющиеся LLграмматиками, обычно могут быть проанализированы
методом рекурсивного спуска с возвратами.
• Восходящие анализаторы могут анализировать большее
количество грамматик, чем нисходящие, и поэтому
именно для таких методов существуют программы,
которые умеют автоматически строить анализаторы. С
восходящими анализаторами связаны LR-грамматики
• С помощью LR-грамматик можно определить
большинство использующихся в настоящее время
языков программирования.
37
Left (LL) and Right (LR) most Derivation
(левосторонний и правосторонний вывод)
Пусть имеем предложение присваивания:
A=B+C*A
Грамматика для этого предложения:
::= =
::= + |
::= * |
::= ( expr ) |
38
Левосторонний вывод
39
Правосторонний вывод
40
По просмотру «вперед» (с предпросмотром)
Языки программирования бывают различными по
сложности. Ряд из них практически невозможно описать с
помощью простых грамматик. Поэтому, в грамматиках
могут встречаться альтернативные правила, начинающиеся с
одинаковых
цепочек
символов.
Возникающая
неоднозначность
может
быть
разрешена
путем
предварительного просмотра правила на n символов
вперед до той границы, начиная с которой данное правило
можно будет отличить от других.
• На один символ вперед
• ……………….
• На К символов вперед
41
Методы
Сверху вниз LL
Снизу вверх LR
Непрямые методы
Распознаватель Унгера Распознаватель
Кок-Янгер-Касами
Прямые методы
predict/match
- shift/reduce
- Earley
ЛинейноЕдинственный метод:
направленные методы: - LL(k)
сначала в ширину с
шириной,
ограниченной 1
- Предшествования
- Контекстно-связанные
- LR(k)
- LALR(1)
- SLR(1)
Эффективные методы (нет известных
общей направленности: методов)
максимально
ограниченный поиск
сначала в ширину
Распознаватель Томита
(GLR парсер)
42
Грамматический
разбор сверхувниз
43
Грамматический разбор сверхувниз
• Разбор – попытка получить, исходя из
начального символа грамматики,
выражение, применяя правила
подстановки (замены), определенный
грамматикой.
• Операция замены некоторого
метасимвола на соответствующую ему
правую часть правила обозначаем =>
44
• Нисходящие анализаторы строят вывод, начиная
от аксиомы грамматики и заканчивая цепочкой
терминальных символов.
• С нисходящими анализаторами связаны LLграмматики.
45
Пример
Разбор выражения i – i * (i+ i)
• E ::= E+T | E-T | T
• T ::= T/F | T*F | F
• F ::= (E) | i
• E – Expression (выражение) –
начальный символ
• T – Term (член)
• F – Factor (коэффициет)
• Терминальные символы: +, -,
*, /, круглые скобки и
символ i (любой
идентификатор)
E => E – T => E – T * F => T – T * F => T – T * (E) => T – T * (E + T)=>
T – T * (T + T) => i – T * ( T + T) => i – i * (T + T) => i – i * (i + T) =>
i – i * ( i + i)
46
• Пример демонстрирует один из двух основных
методов грамматического разбора, который
называется «Разбор сверху-вниз» (TOP-DOWN).
• Основной идеей этого метода является попытка
сгенерировать разбираемое предложение,
начиная с начального символа грамматики Z
47
48
Недостатки алгоритма разбора
сверху-вниз
• Большая вероятность того, что при выборе
какой-либо правой части правила (при наличии
альтернатив) программа забора произведет
«тупиковую» замену, после чего ей придется
«вернуться назад» и выбрать другую
альтернативу из правой части правила
• В результате большого количества возвратов
усложняется сам алгоритм
• Время разбора существенно увеличивается
49
Возвраты
• Программа разбора не должна прибегать к
возвратам или должна минимизировать их!
• Это необходимо еще и потому, что во время
грамматического разбора необходимо связать
семантику с синтаксисом, и по мере того, как
происходить прогнозирование и находятся цели
эти символы будут обрабатываться
семантически.
50
Некоторые примеры
«обработки»
1. При обработке описаний переменных их
характеристики помещаются в дескрипторную
часть таблицы идентификаторов
2. При обработке арифметических выражений
проверяют, совместимы ли типы операндов.
Если возврат произошел из-за того, что
прогнозируемая цель неверна, придется уничтожить
результаты семантической обработки, проделанной
во время поисков этой цели. Сделать это не так-то
просто, поэтому следует постараться провести
грамматический разбор без возвратов.
51
«Незакрытый» символ
• Для того, чтобы избавиться от возвратов, в
компиляторах в качестве контекста обычно
используется следующий «незакрытый» символ
исходного предложения.
• Тогда на грамматику налагается следующее
требование: если есть альтернативы x | y | … | k, то
множества символов, которыми могут начинаться
выводимые из x, y, … k слова, должны быть попарно
различны.
• То есть если x=> Au и у=> Bv, то A≠B
• Если это требование выполнено, можно довольно
просто определить, какая из альтернатив x, y или v –
являются нашей целью
52
• Факторизация оказывает здесь большую
помощь.
• Если есть правило U::=xy | xv, то преобразование
этого правила с помощью приема
«факторизация» к виду U::=x(y|v) помогает
сделать множества первых символов для разных
альтернатив непересекающимися.
53
Основные особенности методов
разбора сверху-вниз
• Простота программирования
• Низкое быстродействие
• Возможность отката, если существует
несколько правил с одинаковой левой
частью (решается с помощью
предпросмотра)
• Возможность зацикливания в случае левой
рекурсии правил (решается с помощью
модификации грамматики)
54
Пример (1)
Дана грамматика
Исходная строка для
разбора
S ::= T + S | T
T ::= i * T | i
a+b*c
Ожидаемый результат
55
Пример (2)
1
a+b*c
S
2
a+b*c
T+S
3
a+b*c
i*T+S
4
+b*c
*T+S
Символы «+» и «*» не согласуются, следовательно
надо вернуться на какое-то количество шагов назад
5 (3)
a+b*c
i+S
Возвращаемся на ближайшую замену. Выбирается
альтернативный вариант для Т
6
+b*с
+S
7
b*c
S
8
b *c
T
9
b*c
i*T
10
*c
*T
11
c
T
12
c
i
56
Пример (3)
a + b *c
S
Дерево
S
a+b *c
T+S
T +
S
S
a+b *c
i*T+S
T
i * T +S
+b*c
В последней строке
таблицы символы
«+» и «*» не
согласуются,
следовательно надо
вернуться на какое-то
количество шагов
назад.
*T+S
57
• Распознаватели с возвратом — это самый
примитивный тип распознавателей для КС-языков.
• Логика их работы основана на моделировании
недетерминированного МП-автомата. (автомата с
Магазинной Памятью, или стековым механизмом
памяти)
• Поскольку моделируется недетерминированный
МП-автомат, то на некотором шаге работы
моделирующего
алгоритма
возможно
возникновение
нескольких
допустимых
следующих состояний автомата. В таком случае
существуют два варианта реализации алгоритма.
58
Вариант с возвратом
• На каждом шаге работы алгоритм должен запоминать
все возможные следующие состояния МП-автомата,
выбирать одно из них, переходить в это состояние и
действовать так до тех пор, пока либо не будет
достигнуто конечное состояние автомата, либо автомат
не перейдет в такую конфигурацию, когда следующее
состояние будет не определено.
• Если достигнуто одно из конечных состояний — входная
цепочка принята, работа алгоритма завершается.
• В противном случае алгоритм должен вернуть автомат
на несколько шагов назад, когда еще был возможен
выбор одного из набора следующих состояний, выбрать
другой вариант и промоделировать поведение автомата с
этим условием.
59
Вариант с распараллеливанием
• алгоритм должен на каждом шаге работы при
возникновении неоднозначности с несколькими
возможными следующими состояниями
автомата запускать новую свою копию
(процесс/поток) для обработки каждого из этих
состояний.
• Алгоритм завершается, если хотя бы одна из
выполняющихся его копий достигнет одно из
конечных состояний. При этом работа всех
остальных копий алгоритма прекращается.
• Если ни одна из копий алгоритма не достигла
конечного состояния МП-автомата, то алгоритм
завершается с ошибкой.
60
LL(1) грамматики
61
Методы нисходящего синтаксического
анализа с одним символом предпросмотра
• Для каждого терминала, который находится в
левой части нескольких правил, необходимо
найти такие непересекающиеся множества
символов предпросмотра, чтобы каждое
множество содержало символы,
соответствующие точно одной возможной
правой части.
• Выбор конкретного правила для замены
данного тереминала будет определяться
символом предпросмотра и множеством, к
которому принадлежит данный символ.
62
Множество первых
порождаемых символов
• Множество символов предпросмотра,
соотнесенных с применением определенного
правила, называется ее множеством первых
порождаемых символов(director symbol set).
63
Важные категории символов
• Стартовый символ для данного нетерминала
определяется как любой символ (например,
терминал), который может появиться в начале
строки, генерируемой нетерминалом.
• Символ-последователь для данного
нетерминала определяется как любой символ
(терминал или нетерминал), который может
следовать за нетерминалом в любой
сентенциальной форме.
64
• Вычисление множества стартовых символов
может быть достаточно трудоемким и
вычислительно сложным процессом, и оно
всегда выполняется в процессе генерации
программы синтаксического анализа, а не при
каждом запуске этой программы.
65
Пример
• Пусть, например, для нетерминала Т грамматика
содержит только два правила:
• T::=aG | bG
• В этом случае имеем следующие множества
стартовых символов:
Правило
T=:: aG
T=::bG
Множество
стартовых символов
{a}
{b}
66
• В общем случае, если правило начинается с
терминала, множество стартовых символов
просто состоит из этого терминала.
• Если правило не начинается с терминала, то для
него все равно нужно вычислить множество
стартовых символов
67
ПРИМЕР (продолжение)
• Имеются следующие правила для нетерминала R:
R::=BG |CH
• Множество стартовых символов нельзя определить
«с ходу»
• Пусть имеются следующие правила для
нетерминала B:
• B=:: cD |TV
• Тогда можно заключить, что множеством стартовых
символов для правила R=:: BG будет {a,b,c},
состоящих из всех стартовых для B
68
Нетерминалы, которые
генерируют пустые строки
• Множество первых порождаемых символов правила
выбираются как множество всех терминалов, которые,
выступая как символы предпросмотра, указывают на
использование данного правила.
• A ::= BC
• B::=ε
• Множество первых порождаемых символов будет
включать
• Все символы-последователи А
• Стартовые символы B и C
• Если и B и C будут генерировать пустые строки, то на
использование данной продукции будут указывать символы
предпросмотра, являющие последователям А и B и С
69
• Множестве первых порождаемых символов
продукции выбирается как множество всех
терминалов, которые, выступая как символы
предпросмотра, указывают на использование
данного правила.
• Таким образом, множество первых
порождаемых символов для продукции
• A ::= BC
• Будут включать в себя все символыпоследовательности А, а также стартовые
символы BC
70
ПРИМЕР
Правило
S=:: Ty
T=::AB
T=::sT
A=::aA
A=::ε
B=::bB
B=::ε
Множество первых порождаемых
символов
S – начальный символ грамматики
{a, b, y}
{s}
{a}
{b, y}
{b}
{y}
B=::ε равно {y} поскольку y может следовать за B
b и y могут следовать за А, если B генерирует пустую строку
71
LL(1)-грамматика
• Можно определить как грамматику, в которой
для каждого нетерминала, появляющегося в
левой части нескольких правил, множества
первых порождаемых символов всех правил, в
которых появляется этот нетерминал, являются
непересекающимися.
• L (left – чтение слева направо) L (Leftmost)
использование левых порождений, а 1 – один
символ предпросмотра.
72
Детерминированный анализ
• Если вычислены все множества первых порождаемых
символов для всех возможных правых частей правил, то
языки, которые описываются LL(1)-грамматикой всегда
анализируются детерминировано, т.е. без
необходимости отменять правило после его применения
(возврат)
• Существуют более распространенные классы грамматик,
которые могут использоваться для детерминированного
нисходящего анализа, но обычно используются именно
LL(1)-грамматики
73
Недетерминированный анализ
• Недетерминированных нисходящий анализ,
основанный на откате (backtracking), уже не
считается эффективной процедурой, хотя в
начале эры компиляторов он широко
использовался в языках подобных FORTRAN
74
Грамматика LL(k)
• Грамматики LL(k), требующие k символов
предпросмотра для различения альтернативных
правых частей, также уже не считаются
практичными с точки зрения синтаксического
анализа
75
LL(1)-языки и LL(1)-грамматики
• LL(1)-язык – это язык, который можно сгенерировать
посредством LL(1)-грамматики.
• Для любого LL(1)-языка возможен нисходящий
синтаксический анализ с одним символом
предпросмотра.
• Существует алгоритм определения, относится ли
грамматика к классу LL(1), поэтому грамматику можно
проверить на “LL(1)-ность», прежде чем создавать на ее
основе программу синтаксического анализа.
• Но не существует алгоритма определения, относится ли
данный язык к классу LL(1), то есть имеет ли он LL(1)грамматику.
76
• Не LL(1)-грамматика может иметь или не иметь
эквивалентную LL(1)-грамматику, генерирующую тот
же язык, и не существует алгоритма, который для
данной произвольной грамматики определит,
являются ли генерируемы ею язык LL(1) или нет.
• Имеются грамматики, не являющиеся LL(1), которые
генерируют LL(1)-языки, т.е. грамматики имеют
эквивалентные LL(1)-грамматики.
• Грамматики часто нужно преобразовывать, прежде
чем использовать с методами нисходящего
синтаксического анализа.
77
Спасибо за внимание!
78
