Глава 14 синтаксический разбор слева направо (lr)


Содержание

Глава 14 синтаксический разбор слева направо (lr)

После того, как построена грамматика, порождающая язык для описания рассматриваемого образа, необходимо построить устройство, распознающее объекты представленные цепочками, порождёнными этой грамматикой. Прямой подход к решению этой задачи состоит в создании отдельной грамматики для каждого класса объектов. Распознающее устройство для данной грамматики будет выделять только те объекты, которые принадлежат соответствующему этой грамматике классу. Например, для m классов объектов C1, C2, …, Cm можно построить m соответствующих грамматик G1, G2, …, Gm, таких, что цепочки, порождённые грамматикой Gi, будут представлять объекты из класса Ci. [4] Тогда для произвольного объекта, описываемого цепочкой x, проблема распознавания сводится к вопросу: верно ли, что

xL (Gi) для i = 1, …, m? (2.32)

Процесс, приводящий к ответу на этот вопрос для одной заданной грамматики, обычно называют «синтаксическим анализом» или «грамматическим разбором». Этот процесс, кроме ответа на вопрос — «да» или «нет», может также давать дерево вывода, т.е. информацию о структуре соответствующего объекта. Блок-схема распознающего алгоритма приведена на рисунке 9.

Будем считать, что если объекты представляются единственным образом, то среди ответов на вопросы «верно ли, что xL (Gi) для i = 1, …, m?» может быть один только один положительный ответ, а все остальные — отрицательными. При ответе «xL (Gj)» считается, что x принадлежит классу Cj. Если же все ответы отрицательны, то считается, что x не принадлежит ни одному из классов.

Простой способ распознавания состоит в сопоставлении входной цепочки с прототипом или эталоном каждого класса. Эталонная цепочка задаётся в терминах непроизводных элементов. Сопоставление непроизводных элементов может осуществляться параллельно или последовательно. Цепочка x относится к тому классу, из которого взята эталонная цепочка, наилучшим образом согласующаяся с x. В этом случае требуется либо точное совпадение x с эталоном, либо выполнение подходящего критерия согласования. Конечно, не менее важен и выбор эталонных цепочек [4]. Этот подход, хотя и выглядит менее гибким, может быть реализован быстродействующей программой. Однако в действительности иерархическая структурная информация используется недостаточно, и этот подход полезен только тогда, можно определить соответствующие эталонные цепочки и имеющий смысл критерий согласования.

Если грамматика Gi регулярна, то можно построить детерминированный конечный автомат для распознавания цепочек, порождённых Gi. Если Gi — бесконтекстная или программная грамматика, то обычно требуется недетерминированный автомат. В процессе распознавания используется, вообще говоря, некоторая недетерминированная процедура. Задача синтаксического анализа может быть поставлена следующим образом: для заданного предложения x и грамматики G построить треугольник

и попытаться заполнить его внутреннюю часть деревом вывода x, правильным для грамматики G [4]. Если попытка успешна, то xL (G), в противном случае xL (G). В принципе не важно, как мы пытаемся заполнить треугольник. Это можно делать, начиная с корня дерева (грамматический разбор сверху вниз) или снизу к вершине (разбор снизу вверх). Оба способа называются разборами слева направо, так как там, где это возможно, символы в предложении обрабатываются слева направо. Какой бы способ не использовался, отдельные шаги состоят из попыток найти правило подстановки, подходящее для рассматриваемого участка предложения. Тот факт, что приходится делать пробные попытки, которые впоследствии оказываются ошибочными, делает синтаксический анализ, вообще говоря, неэффективной процедурой. Правило подстановки выбирается только в том случае, если оно удовлетворяет некоторым априорным тестам. Например, выбираются только такие правила подстановки, которые подходят только для данного участка цепочки. Априорные тесты могут быть и более сложными. Правило подстановки может отбрасываться из-за того, что его применение приводит к большему количеству основных символов, чем содержится в исходной цепочке, либо к появлению основного символа, которого в цепочке нет. Быстрота синтаксического анализа зависит от того, насколько удаётся избежать ошибочных проб, которые и приводят к лишним затратам времени. Если порядок выбора шагов и априорные тесты таковы, что на каждом шаге применимо только одно правило подстановки, метод синтаксического анализа не может быть существенно улучшен (при условии, что проверка априорных тестов не слишком длинна). Однако если на каждом шаге есть несколько возможностей, то общее число возможных грамматических разборов растёт экспоненциально. Поэтому выбор априорных тестов и порядок действий становятся чрезвычайно важными [4].

Грамматический разбор сверху вниз.

Синтаксический анализ сверху вниз начинается с символа S, обозначающего всё предложение, и состоит из последовательных пробных подстановок правил, которые порождают подходящие для этого предложения вспомогательные символы. Чистый синтаксический анализ сверху вниз — полностью целенаправленный процесс. Главной целью является вывод из S данного предложения x. Делается предположение, что анализируемая цепочка действительно есть предложение в языке данной грамматики G. Поэтому первый шаг — выяснить, можно ли свести цепочку к правой части некоторого правила подстановки

S>X1X2…XN. (2.33)

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

Точно также решаются подзадачи для всех AVN, проверяется применимость правила подстановки A>X1X2…Xl и ставится и решается новая подзадача. Если подзадачу решить не удаётся, то на предыдущем уровне надо попытаться применить другое правило.

При анализе слева направо и сверху вниз иногда вызывает затруднение повторение слева вспомогательного символа: правила подстановки вида A1>A1б могут приводить к бесконечным петлям при анализе. Это происходит, когда сведение части цепочки к символу A1 ставится как подзадача, и первым шагом в её решении оказывается решение той же задачи, т.е. сведение части цепочки к A1. Проблема повторения слева иногда решается путём какого-либо преобразования грамматики или изменения порядка разбора. Большую роль здесь также может сыграть порядок, в котором проверяются различные правые части правил подстановки при одной и той же левой части. Если только одна правая часть содержит повторение слева, то она должна проверяться в последнюю очередь. Однако такая последовательность действий может вступать в противоречие с другими условиями на порядок проверки, например, с требованием, что кратчайшая правая часть проверяется последней.

Грамматический разбор снизу вверх.

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

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

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

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

Один из таких классов называется классом LR (k)-грамматик. Запись LR(k) означает, что при грамматическом разборе слева направо и снизу вверх достаточен просмотр цепочки вперёд на k символов. Неформально будем относить бесконтекстную грамматику G = (VN, VT, P, S) к LR (k)-грамматикам, если для любой выводимой цепочки s верно следующее: s единственным способом записывается в виде вгд, так что существует единственный правый вывод S * вAдвгд, причём A заменено на г на последнем шаге вывода, и если, кроме того, A и г определяются однозначно при просмотре цепочки s слева направо не более, чем на k символов после г. Если часть этих k символов расположена правее конца цепочки, то будем считать, что цепочка s выводима из S$ k , где $VN.

Если на предпоследнем шаге вывода получена цепочка бAx1x2 так, что

то г = б, A = B и x = x1x3. Другими словами, в правом выводе двух цепочек, у которых совпадают k символов правее места последней подстановки, в цепочках, полученных на предпоследнем шаге этого вывода, должны также совпадать k символов правее места последней подстановки.

Важные свойства LR (k)-грамматик.

1) Каждая LR (k)-грамматика однозначна.

2) Каждый язык, порождаемый LR (k)-грамматикой, допускается детерминированным магазинным автоматом. Такой язык называется детерминированным бесконтекстным языком.

3) Каждый язык, допускаемый некоторым детерминированным магазинным автоматом, порождается LR (1)-грамматикой. Таким образом, язык принадлежит классу LR (1) тогда и только тогда, когда он принадлежит классу LR (k) для некоторого k.

4) Если язык L1 допускается некоторым детерминированным магазинным автоматом, то существует такая LR (0)-грамматика G, что L (G) = L1$.

синтаксический анализ слева направо

1 left-to-right parsing

2 left-to-right parsing

См. также в других словарях:

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

LL-анализатор — Стиль этой статьи неэнциклопедичен или нарушает нормы русского языка. Статью следует исправить согласно стилистическим правилам Википедии … Википедия

LR-анализатор — LR Parser LR анализатор (англ. LR parser) синтаксический анализатор для исходных кодов программ, написанных на некотором языке программирования, который читает входной поток слева (Left) направо и произв … Википедия

Информация — (Information) Информация это сведения о чем либо Понятие и виды информации, передача и обработка, поиск и хранение информации Содержание >>>>>>>>>>>> … Энциклопедия инвестора

Регулярные выражения — (англ. regular expressions, сокр. RegExp, RegEx, жарг. регэкспы или регексы) это формальный язык поиска и осуществления манипуляций с подстроками в тексте, основанный на использовании метасимволов (символов джокеров,… … Википедия

Метод рекурсивного спуска — Для улучшения этой статьи желательно?: Найти и оформить в виде сносок ссылки на авторитетные источники, подтверждающие написанное. Метод реку … Википедия

Рекурсивный нисходящий парсер — (англ. Recursive descent parser) алгоритм синтаксического анализа, реализуемый путём взаимного вызова парсящих процедур, соответствующих правилам контекстно свободной грамматики или БНФ. Применения правил последовательно, слева направо … Википедия

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

Схема синтаксического разбора предложения (разбор под цифрой 4)

  1. Разобрать предложение по членам (подлежащее а – тот кто действует, о ком или о чем идет речь; сказуемое б – что о нем говорится, что он делает, сделал; определение в – от существительного к нему можно задать вопрос какой, чей; дополнение г – от глагола к нему можно задать вопрос косвенного падежа; обстоятельство д — от глагола к нему можно задать вопросы как? когда? почему? с какой целью? и т.п.).
  2. Разделить предложение (если предложение сложное) на части, пронумеровать части по порядку.

III. Сделать описательный разбор (всего предложения) по следующей схеме:


– повествовательное (.),
– вопросительное (?),
– побудительное (глагол стоит в повелительном наклонении, выражает просьбу, приказ).

  1. По количеству грамматических основ:

1) простое (одна грамматическая основа – одно подл.+ сказ),
2) сложное:
– сложносочинённое (предложения с разными грамматическими основами соединены сочинительными союзами*),
– сложноподчинённое (предложения с разными грамматическими основами соединены подчинительными союзами**),
– бессоюзное***,
– с разными видами связи (одни блоки предложения связаны сочинительным союзом, другие — подчинительным).

  1. По наличию одного или обоих главных членов (в сложном предложении каждого простого предложения):

1) двусоставное (есть и подлежащее, и сказуемое).
2) односоставное (есть только один главный член предложения) с главным членом
а) подлежащим – назывное (Весна.);
б) сказуемым****
– определённо-личное,
– неопределённо-личное,
– обобщённо-личное,
– безличное.

  1. По наличию второстепенных членов:

– распространённое (кроме главных членов есть второстепенные),
– нераспространённое (только главные члены).

  1. По наличию пропущенных членов:

– полное,
– неполное (указать, какой член / члены предложения пропущен).

  1. По наличию осложняющих членов:

1) неосложнённое,
2) осложнённое:
– однородными членами предложения (указать какими);
– обособленными второстепенными членами предложения – определениями (в том числе и приложениями), дополнениями, обстоятельствами (выраженными причастным, деепричастным, сравнительным и др. оборотами);
– вводными словами, вводными и вставными конструкциями,
– прямой речью;
– обращением.

Образец синтаксического разбора

Предложение повествовательное, невосклицательное, сложное, с разными видами связи.
1 часть: двусоставное (подлежащее шкап, сказуемое был, ПГС), распространённое, полное, осложнено однородными обстоятельствами;
2 часть: двусоставное (подлежащее сырость, сказуемое была, ПГС), распространённое, полное, неосложненное;
3 часть: односоставное – неопределённо-личное (сказуемое открывали, ПГС), распространённое, полное, неосложненное;
4 часть: односоставное – безличное (сказуемое невозможно было сказать), нераспространённое, полное, неосложненное; (другой вариант разбора: двусоставное, неполное – место подлежащего занято придаточным изъяснительным, нераспространённое, неосложненное);
5 часть: двусоставное (подлежащее ель, сказуемое кончается, ПГС), распространённое, полное, неосложненное;
6 часть: двусоставное (подлежащее ель, опущено, сказуемое начинается, ПГС), распространённое, неполное (опущено подлежащее), неосложненное;
7 часть: двусоставное (подлежащее мальчик, сказуемое стоял, ПГС), распространённое, полное, неосложненное;
8 часть: двусоставное (подлежащее тома, сказуемое были, ПГС, опущено), распространённое, неполное (опущено сказуемое), неосложненное.

Примечания:
а) ТИПЫ ПОДЛЕЖАЩЕГО
Подлежащее – одно слово:

  1. Имя существительное: Старший сынуехал в столицу.
  2. Местоимение: Онуехал в столицу.
  3. Имя прилагательное: Старшийуехал в столицу.
  4. Причастие: Поднявшиймеч от меча и погибнет.
  5. Имя числительное: Двоеуехали в столицу.
  6. Инфинитив (неопределённая форма глагола): Любить– это прекрасно.
  7. Наречие: Настало и роковое послезавтра .
  8. Предлог: « В »является предлогом.
  9. Союз: « А »противительный союз.
  10. Частица: « Не »с глаголами пишется отдельно.
  11. Междометие: Неслось со всех сторон « ау ».
  12. Косвенная форма имени, спрягаемая форма глагола, предложение в значении имени существительного: « Не забывай себя, не волнуйся, умеренно трудись »было его девизом.

Подлежащее – цельное, то есть синтаксически неделимое словосочетание:

  1. Имя в именительном падеже (наречие) + имя в родительном падеже: Пять стульев стояло у стены. Часть стульев стояла у стены.
  2. Имя в именительном падеже + имя в родительном падеже с предлогом из:Многие из наспоедут в столицу.
  3. Имя в именительном падеже + имя в творительном падеже с предлогом с(только при сказуемом – во множественном числе!): Мать с сыном поедут (мн. ч.) отдыхать. НО! Мать с сыном поедет отдыхать.
  4. Существительные начало, середина, конец+ существительное в родительном падеже: Стоял конец сентября .
  5. Существительное + согласуемое имя (фразеологизм, словосочетание с метафорическим значением): Шапка русых кудрей колыхалась на его голове.
  6. Неопределённое местоимение (от основ кто, что) + согласуемое имя: Что-то неприятное было во всем его облике.

б) ТИПЫ СКАЗУЕМОГО (подробнее на стр. «Члены предложения»)

в) ОПРЕДЕЛЕНИЕ

Определение — второстепенный член предложения, обозначающий признак лица или предмета и отвечающий на вопрос какой? чей?

Согласованные определения согласуются с определяемым словом в формах числа, падежа. Согласованные определения выражаются:
-прилагательным (Я надену к а к у ю? белую рубашку.);
-местоименным прилагательным (Дай мне ч ь ю? твою руку.);
-порядковым числительным (Принеси к а к о й? пятый том.);
-причастием (На столе лежит к а к о е? нераспечатанное письмо.)
Согласованные определения обычно стоят перед определяемым словом.

Несогласованные определения связаны с определяемым словом управлением или примыканием и выражаются:
-существительным в косвенном падеже с предлогом или без предлога (Я люблю пьесы к а к и е? Чехова. На ней была юбка к а к а я? в клетку.);
-существительным в И. п. (Я побывал на озере к а к о м? Байкал.);
-притяжательным местоимением его, её, их (Это ч е й? его дом.)
-наречием (Нам подали яйца к а к и е? всмятку и кофе к а к о й? по-варшавски.);
-глаголом в форме инфинитива (У него было желание к а к о е? учиться.)
Несогласованные определения обычно стоят после определяемого слова.

Приложения — определения, выраженные существительными и связанные с определяемым словом согласованием или примыканием. Приложения имеют следующие значения:
-качество, свойство предмета (Мороз-воевода дозором обходит владенья свои.);
-возраст, звание, род занятий и т.п. (Сестра Лиза приехала на каникулы.)
-пояснение, более точное название (В саду растёт шиповник — кустарник с крупными, похожими на розу цветами.);
— название литературных произведений, предприятий, торговых марок и т. д. (Я читаю роман «Евгений Онегин».)

г) ДОПОЛНЕНИЕ

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

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

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

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

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

Дополнения, выраженные инфинитивом, обозначают действие как объект, на который направлено другое действие:Он уговорил меня пойти на дискотеку. Запомнить:
— инфинитив-дополнение и инфинитив-сказуемое обозначают действия разных лиц,
— инфинитив-дополнение зависит от сказуемых с определенным значением — значением волеизъявления: просить, приказать, уговорить, умолять и т.п.

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

д) ОБСТОЯТЕЛЬСТВО

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

Обстоятельства Вопросы Примеры
образа действия как? каким образом? Мы пошли пешком.
времени когда? с каких пор? до каких пор? Мы приехали вчера.
места (где? куда? откуда?): Я побежал вперёд.
причины почему? От усталости у меня кружится голова.
цели зачем? Я пришла мириться.
меры и степени в какой мере, степени? Он был очень внимателен и всё сделал совершенно правильно.
условия при каком условии? Без звонка туда идти нельзя.
уступки несмотря на что? Несмотря на дождь, мы всё же вышли из дома.

Обстоятельства бывают выражены

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

Сочинительные союзы*

  1. Соединительные: и, да (в значении «и»), да и, ни-ни, тоже, также
    2. Разделительные: или, либо, то-то, не то-не то, то ли-то ли. Функцию разделительных союзов могут выполнять их аналоги, сохраняющие семантические связи с соответствующими вводными словами или наречиями: может быть … может быть; возможно … возможно; иногда … иногда … а иногда. Эти последние могут употребляться совместно с союзами (может быть … или, может быть; то ли … то ли … а может быть; иногда … а то и).
    3. Противительные: а, но, да (=но), зато, однако
    4. Сопоставительные (двойные или составные):
    как…, так и
    не только…, но и
    не столько…, сколько
    не так…, как
    хотя и…, но
    не то что(бы)…, но (а)
    если не…, то


Значение соединительных союзов можно условно обозначить фразой: «И ЭТО, И ТО». Они соединяют два однородных члена между собой. Значение разделительных союзов можно определить так: «ИЛИ ТО, ИЛИ ЭТО». Такие союзы указывают на возможность только одного однородного члена из нескольких или на их чередование. Значение противительных союзов выражается иначе: «НЕ ТО, А ЭТО».

Подчинительные союзы**
Подчинительные союзы объединяют неравноправные компоненты и указывают на зависимость одного из этих компонентов от другого. Они связывают главным образом части сложного предложения, но могут быть использованы и в простом предложении для связи однородных и неоднородных членов.
Выделяют следующие разряды подчинительных союзов по значению:
1) временные: когда, пока, едва, лишь, с тех пор как, лишь только;
2) причинные: так как, потому что, ввиду того что, ибо (устар. / книжн.);
3) условные: если, кабы (устар.), коли (устар.), раз;
4) целевые: чтобы, для того чтобы, дабы (устар.), с тем чтобы;
5) уступительные: хотя, несмотря на то что, вопреки тому что;
6) следствия: так что;
7) сравнительные: как, как будто, словно, будто, точно, чем, подобно тому как;
8) изъяснительные: что, как, чтобы, ли (частица в роли союза).

Бессоюзное сложное предложение***
В бессоюзном сложном предложении его части связаны между собой:
1)по смыслу (Наступил вечер, шел дождь, с севера прерывисто дул ветер.);
2)интонационно
— интонация перечисления (Заунывный ветер гонит стаю туч на край небес, ель надломленная стонет, глухо шепчет темный лес .),
— противопоставления (Служить бы рад — прислуживаться тошно),
— пояснения (Страшная мысль мелькнула в уме моем: я вообразил ее в руках разбойников),
— предупреждения (Вдруг я чувствую: кто-то берет меня за плечо и толкает),
— обусловленности (Любишь кататься — люби и саночки возить);
3)порядком расположения частей (Наступил вечер — стало прохладно. Стало прохладно: наступил вечер),
4)видо-временными формами глаголов-сказуемых (однородные глагольные формы, например: По дереву лодки неугомонно стучал дождь, мягкий шум его наводил на грустные мысли).

Односоставные предложения с главным членом сказуемым****
1) В определенно-личных предложениях сказуемое выражено в такой форме, которая имеет значение 1-го или 2-го лица единственного числа или множественного (действие производят: я, ты, мы, вы), т.е. в форме настоящего или будущего времени, а также повелительного наклонения (остальные формы глагола значения лица не имеют). Примеры: Хочу спать. Хотим спать. Хочешь спать? Хотите спать? Спи! Спите!
2) В неопределенно-личных предложениях сказуемое выражено глаголом обязательно в форме множественного числа, это может быть форма 3-го лица настоящего или будущего времени или же форма прошедшего времени, а также условного наклонения (действие производят Они). Пример: В киоске продают (продавали) газеты.
3) В обобщенно-личных предложениях сказуемое по форме совпадает со сказуемым в определенно-личном или неопределенно-личном предложении, однако значение предложения — обобщенное, т.е. действие совершает любой, каждый из нас, все. Примеры: Без труда не вытащишь и рыбку из пруда. Цыплят по осени считают.
4) В безличных предложениях единственный главный член — сказуемое, которое может быть выражено наречием (На улице холодно. Можно простудиться.); безличным глаголом (Хочется стать.); личным глаголом в безличном значении (Из окна дует.); глаголом в неопределенной форме (Молчать!).

Синтаксический разбор предложения.

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

1) Каково данное предложение по цели высказывания? (Повествовательное, побудительное или вопросительное).

2) Какова эмоциональная окраска предложения ? (Восклицательное или невосклицательное).

3) Сколько грамматических основ есть у данного предложения? (Простое – одна основа, сложное – две и более).

Далее, если предложение простое:

4) Односоставное предложение или двусоставное? (Если имеется и подлежащее, и сказуемое – то двусоставное, если только один главные член – то односоставное).

5) Распространенное предложение или нераспространенное? (Есть ли второстепенные члены предложения?).

6) Осложненное предложение или неосложненное?(Имеются ли однородные члены, вводное слово, причастный/деепричастный оборот, обращение?)

7) Какими частями речи выражены все члены предложения? Подчеркните все члены предложения.

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

Если предложение сложное, то следуем следующей схеме.

4) Какая связь имеется в сложном предложении: союзная или бессоюзная?

5) Какой именно способ связи используется в предложении: подчинительная, сочинительная или интонация?

6) На основе ответа на предыдущий пункт, обозначить, к какому типу сложного предложения относится данное: сложносочиненное, сложноподчиненное или бессоюзное?

7) Следуя инструкции разбора простого предложение, разобрать каждую из частей сложного предложения.

Пример синтаксического разбора простого предложения.

В букете были розы и лилии.

Устный разбор простого предложения.

Предложение повествовательное, невосклицательное, простое, двусоставное; грамматическая основа: розы и лилии были; распространенное, осложнено однородными подлежащими.

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

Повест., невоскл., прост., двусост., г/о розы и лилии были, распростр., осложн. однород. подл.

Пример разбора сложного предложения.

В букете были розы и лилии, но ей больше нравились тюльпаны.

Устный разбор сложного предложения.

Предложение повествовательное, невосклицательное, сложное, связь союзная, предложения связываются сочинительным союзом «но», сложносочиненное предложение. Первое предложение двусоставное, грамматическая основа розы и лилии были; распространенное, осложнено однородными подлежащими. Второе предложение двусоставное, грамматическая основа: тюльпаны нравились, распространенное, не осложнено.

Письменный разбор сложного предложения.

Повеств., невоскл., сложн., сложносоч., с союзом но. 1-е ПП: двусост., г/о розы и лилии были, распр., осложн. однор. подл. 2-е ПП: двусост., г/о: тюльпаны нравились, распростр., не осложн.

Синтаксический разбор предложения.

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

1) Каково данное предложение по цели высказывания? (Повествовательное, побудительное или вопросительное).

2) Какова эмоциональная окраска предложения ? (Восклицательное или невосклицательное).

3) Сколько грамматических основ есть у данного предложения? (Простое – одна основа, сложное – две и более).

Далее, если предложение простое:

4) Односоставное предложение или двусоставное? (Если имеется и подлежащее, и сказуемое – то двусоставное, если только один главные член – то односоставное).

5) Распространенное предложение или нераспространенное? (Есть ли второстепенные члены предложения?).

6) Осложненное предложение или неосложненное?(Имеются ли однородные члены, вводное слово, причастный/деепричастный оборот, обращение?)


7) Какими частями речи выражены все члены предложения? Подчеркните все члены предложения.

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

Если предложение сложное, то следуем следующей схеме.

4) Какая связь имеется в сложном предложении: союзная или бессоюзная?

5) Какой именно способ связи используется в предложении: подчинительная, сочинительная или интонация?

6) На основе ответа на предыдущий пункт, обозначить, к какому типу сложного предложения относится данное: сложносочиненное, сложноподчиненное или бессоюзное?

7) Следуя инструкции разбора простого предложение, разобрать каждую из частей сложного предложения.

Пример синтаксического разбора простого предложения.

В букете были розы и лилии.

Устный разбор простого предложения.

Предложение повествовательное, невосклицательное, простое, двусоставное; грамматическая основа: розы и лилии были; распространенное, осложнено однородными подлежащими.

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

Повест., невоскл., прост., двусост., г/о розы и лилии были, распростр., осложн. однород. подл.

Пример разбора сложного предложения.

В букете были розы и лилии, но ей больше нравились тюльпаны.

Устный разбор сложного предложения.

Предложение повествовательное, невосклицательное, сложное, связь союзная, предложения связываются сочинительным союзом «но», сложносочиненное предложение. Первое предложение двусоставное, грамматическая основа розы и лилии были; распространенное, осложнено однородными подлежащими. Второе предложение двусоставное, грамматическая основа: тюльпаны нравились, распространенное, не осложнено.

Письменный разбор сложного предложения.

Повеств., невоскл., сложн., сложносоч., с союзом но. 1-е ПП: двусост., г/о розы и лилии были, распр., осложн. однор. подл. 2-е ПП: двусост., г/о: тюльпаны нравились, распростр., не осложн.

Глава 14 синтаксический разбор слева направо (lr)

После того, как построена грамматика, порождающая язык для описания рассматриваемого образа, необходимо построить устройство, распознающее объекты представленные цепочками, порождёнными этой грамматикой. Прямой подход к решению этой задачи состоит в создании отдельной грамматики для каждого класса объектов. Распознающее устройство для данной грамматики будет выделять только те объекты, которые принадлежат соответствующему этой грамматике классу. Например, для m классов объектов C1, C2, …, Cm можно построить m соответствующих грамматик G1, G2, …, Gm, таких, что цепочки, порождённые грамматикой Gi, будут представлять объекты из класса Ci. [4] Тогда для произвольного объекта, описываемого цепочкой x, проблема распознавания сводится к вопросу: верно ли, что

xL (Gi) для i = 1, …, m? (2.32)

Процесс, приводящий к ответу на этот вопрос для одной заданной грамматики, обычно называют «синтаксическим анализом» или «грамматическим разбором». Этот процесс, кроме ответа на вопрос — «да» или «нет», может также давать дерево вывода, т.е. информацию о структуре соответствующего объекта. Блок-схема распознающего алгоритма приведена на рисунке 9.

Будем считать, что если объекты представляются единственным образом, то среди ответов на вопросы «верно ли, что xL (Gi) для i = 1, …, m?» может быть один только один положительный ответ, а все остальные — отрицательными. При ответе «xL (Gj)» считается, что x принадлежит классу Cj. Если же все ответы отрицательны, то считается, что x не принадлежит ни одному из классов.

Простой способ распознавания состоит в сопоставлении входной цепочки с прототипом или эталоном каждого класса. Эталонная цепочка задаётся в терминах непроизводных элементов. Сопоставление непроизводных элементов может осуществляться параллельно или последовательно. Цепочка x относится к тому классу, из которого взята эталонная цепочка, наилучшим образом согласующаяся с x. В этом случае требуется либо точное совпадение x с эталоном, либо выполнение подходящего критерия согласования. Конечно, не менее важен и выбор эталонных цепочек [4]. Этот подход, хотя и выглядит менее гибким, может быть реализован быстродействующей программой. Однако в действительности иерархическая структурная информация используется недостаточно, и этот подход полезен только тогда, можно определить соответствующие эталонные цепочки и имеющий смысл критерий согласования.

Если грамматика Gi регулярна, то можно построить детерминированный конечный автомат для распознавания цепочек, порождённых Gi. Если Gi — бесконтекстная или программная грамматика, то обычно требуется недетерминированный автомат. В процессе распознавания используется, вообще говоря, некоторая недетерминированная процедура. Задача синтаксического анализа может быть поставлена следующим образом: для заданного предложения x и грамматики G построить треугольник

и попытаться заполнить его внутреннюю часть деревом вывода x, правильным для грамматики G [4]. Если попытка успешна, то xL (G), в противном случае xL (G). В принципе не важно, как мы пытаемся заполнить треугольник. Это можно делать, начиная с корня дерева (грамматический разбор сверху вниз) или снизу к вершине (разбор снизу вверх). Оба способа называются разборами слева направо, так как там, где это возможно, символы в предложении обрабатываются слева направо. Какой бы способ не использовался, отдельные шаги состоят из попыток найти правило подстановки, подходящее для рассматриваемого участка предложения. Тот факт, что приходится делать пробные попытки, которые впоследствии оказываются ошибочными, делает синтаксический анализ, вообще говоря, неэффективной процедурой. Правило подстановки выбирается только в том случае, если оно удовлетворяет некоторым априорным тестам. Например, выбираются только такие правила подстановки, которые подходят только для данного участка цепочки. Априорные тесты могут быть и более сложными. Правило подстановки может отбрасываться из-за того, что его применение приводит к большему количеству основных символов, чем содержится в исходной цепочке, либо к появлению основного символа, которого в цепочке нет. Быстрота синтаксического анализа зависит от того, насколько удаётся избежать ошибочных проб, которые и приводят к лишним затратам времени. Если порядок выбора шагов и априорные тесты таковы, что на каждом шаге применимо только одно правило подстановки, метод синтаксического анализа не может быть существенно улучшен (при условии, что проверка априорных тестов не слишком длинна). Однако если на каждом шаге есть несколько возможностей, то общее число возможных грамматических разборов растёт экспоненциально. Поэтому выбор априорных тестов и порядок действий становятся чрезвычайно важными [4].

Грамматический разбор сверху вниз.

Синтаксический анализ сверху вниз начинается с символа S, обозначающего всё предложение, и состоит из последовательных пробных подстановок правил, которые порождают подходящие для этого предложения вспомогательные символы. Чистый синтаксический анализ сверху вниз — полностью целенаправленный процесс. Главной целью является вывод из S данного предложения x. Делается предположение, что анализируемая цепочка действительно есть предложение в языке данной грамматики G. Поэтому первый шаг — выяснить, можно ли свести цепочку к правой части некоторого правила подстановки

S>X1X2…XN. (2.33)

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

Точно также решаются подзадачи для всех AVN, проверяется применимость правила подстановки A>X1X2…Xl и ставится и решается новая подзадача. Если подзадачу решить не удаётся, то на предыдущем уровне надо попытаться применить другое правило.

При анализе слева направо и сверху вниз иногда вызывает затруднение повторение слева вспомогательного символа: правила подстановки вида A1>A1б могут приводить к бесконечным петлям при анализе. Это происходит, когда сведение части цепочки к символу A1 ставится как подзадача, и первым шагом в её решении оказывается решение той же задачи, т.е. сведение части цепочки к A1. Проблема повторения слева иногда решается путём какого-либо преобразования грамматики или изменения порядка разбора. Большую роль здесь также может сыграть порядок, в котором проверяются различные правые части правил подстановки при одной и той же левой части. Если только одна правая часть содержит повторение слева, то она должна проверяться в последнюю очередь. Однако такая последовательность действий может вступать в противоречие с другими условиями на порядок проверки, например, с требованием, что кратчайшая правая часть проверяется последней.

Грамматический разбор снизу вверх.

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

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

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

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

Один из таких классов называется классом LR (k)-грамматик. Запись LR(k) означает, что при грамматическом разборе слева направо и снизу вверх достаточен просмотр цепочки вперёд на k символов. Неформально будем относить бесконтекстную грамматику G = (VN, VT, P, S) к LR (k)-грамматикам, если для любой выводимой цепочки s верно следующее: s единственным способом записывается в виде вгд, так что существует единственный правый вывод S * вAдвгд, причём A заменено на г на последнем шаге вывода, и если, кроме того, A и г определяются однозначно при просмотре цепочки s слева направо не более, чем на k символов после г. Если часть этих k символов расположена правее конца цепочки, то будем считать, что цепочка s выводима из S$ k , где $VN.

Если на предпоследнем шаге вывода получена цепочка бAx1x2 так, что

то г = б, A = B и x = x1x3. Другими словами, в правом выводе двух цепочек, у которых совпадают k символов правее места последней подстановки, в цепочках, полученных на предпоследнем шаге этого вывода, должны также совпадать k символов правее места последней подстановки.

Важные свойства LR (k)-грамматик.

1) Каждая LR (k)-грамматика однозначна.


2) Каждый язык, порождаемый LR (k)-грамматикой, допускается детерминированным магазинным автоматом. Такой язык называется детерминированным бесконтекстным языком.

3) Каждый язык, допускаемый некоторым детерминированным магазинным автоматом, порождается LR (1)-грамматикой. Таким образом, язык принадлежит классу LR (1) тогда и только тогда, когда он принадлежит классу LR (k) для некоторого k.

4) Если язык L1 допускается некоторым детерминированным магазинным автоматом, то существует такая LR (0)-грамматика G, что L (G) = L1$.

синтаксический анализ слева направо

Универсальный русско-английский словарь . Академик.ру . 2011 .

Смотреть что такое «синтаксический анализ слева направо» в других словарях:

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

LL-анализатор — Стиль этой статьи неэнциклопедичен или нарушает нормы русского языка. Статью следует исправить согласно стилистическим правилам Википедии … Википедия

LR-анализатор — LR Parser LR анализатор (англ. LR parser) синтаксический анализатор для исходных кодов программ, написанных на некотором языке программирования, который читает входной поток слева (Left) направо и произв … Википедия

Информация — (Information) Информация это сведения о чем либо Понятие и виды информации, передача и обработка, поиск и хранение информации Содержание >>>>>>>>>>>> … Энциклопедия инвестора

Регулярные выражения — (англ. regular expressions, сокр. RegExp, RegEx, жарг. регэкспы или регексы) это формальный язык поиска и осуществления манипуляций с подстроками в тексте, основанный на использовании метасимволов (символов джокеров,… … Википедия

Метод рекурсивного спуска — Для улучшения этой статьи желательно?: Найти и оформить в виде сносок ссылки на авторитетные источники, подтверждающие написанное. Метод реку … Википедия

Рекурсивный нисходящий парсер — (англ. Recursive descent parser) алгоритм синтаксического анализа, реализуемый путём взаимного вызова парсящих процедур, соответствующих правилам контекстно свободной грамматики или БНФ. Применения правил последовательно, слева направо … Википедия

Зачем нужен AST

AST — это Abstract Syntax Tree, то есть дерево, которое в абстрактном виде представляет структуру программы. AST создаётся парсером по мере синтаксического разбора программы. В современных компиляторах AST и список диагностик (ошибок, предупреждений) — это два результата вызова модуля синтаксического разбора.

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

Типовой императивный язык программирования (такой как C, C++, PASCAL, Java, JavaScript, C#) состоит из трёх синтаксических элементов:

  • Выражения (expressions)
  • Инструкции (statements)
  • Объявления (declarations)

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

Выражения

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

  • Доступ к переменной (variable access): например, x
  • Литерал (literal): например, 5.18 или «some meaningful string»
  • Унарный оператор (unary operator): например, -x
  • Бинарный оператор (binary operator): например, x + 5.18 или x == 5.18
    • Разные бинарные операторы обычно имеют разный приоритет и могут группироваться скобками, но в функциональных языках (LISP, Haskell) операторы бывают неотличимы от функций
    • Типовой набор операторов: арифметические, логические, сравнения; такой набор уже позволяет создавать полноценные программы
  • Вызов функции (function call): например, sqrt(pow(a, 2.0) + pow(b, 2.0))

Инструкции

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

Примеры инструкций, характерных для процедурных языков:

  • Объявление переменной с опциональной/обязательной инициализацией, например, let value = . ; или int x = 500;
    • В языке Python объявлений переменных нет
  • Присвоение переменной, например, velocity = velocity + acceleration * dt;
  • Специальные инструкции, например, печать print x+1 или проверка контракта assert isinstance(x, int) в языке Python
  • Условные инструкции, такие как if , switch
  • Циклы, такие как while , do/while , repeat/until , for , foreach
  • Инструкции потока управления, например, возвраты из функций return x+5; или прерывания циклов break;
    • Возвраты требуются не во всех языках — иногда функция просто возвращает последнее вычисленное выражение
  • Блоки кода, такие как

Объявление


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

Спорные вопросы

Некоторые сущности трудно отнести к той или иной категории. Например:

  • Объявление анонимной функции (лямбды) можно считать объявлением без имени либо выражением
  • Объявление переменной можно считать как просто инструкцией, так и полноценным объявлением

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

Что такое AST?

AST — это Abstract Syntax Tree, т.е. представление структуры программы в виде дерева объявлений, инструкций и выражений.

  • AST не является бинарным деревом: например, у унарного оператора будет один дочерний узел
  • AST является гетерогенным деревом, состоящим из узлов разного типа
    • В этом AST похож на DOM-представление документа HTML/XML
  • В каждом поддереве дочерними узлами становятся лексически вложенные сущности: например, для узла объявления функции дочерними узлами являются инструкции, составляющие тело функции, а также объявления параметров функции (если они выделены в отдельные узлы AST волей автора компилятора)

Удобный способ реализовать AST в коде — это иерархия классов и интерфейсов. Например, можно ввести три базовых интерфейса:

  • ExpressionAST — интерфейс, который реализуется всеми выражениями
  • StatementAST — интерфейс, который реализуется всеми инструкциями
  • DeclarationAST — аналогичный интерфейс для объявлений функций и типов
    • В компилируемых языках всю программу целиком можно считать списком DeclarationAST , в скриптовых — списком StatementAST
    • Альтернативно, можно ввести специальный узел ProgramAST или ModuleAST

Если в языке нет типов, то DeclarationAST можно для удобства превратить в FunctionAST и считать программу списком FunctionAST .

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

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

  • Можно избежать проблемы: например, добавляем полиморфный метод Evaluate в интерфейс ExpressionAST и реализуем его по-разному в классах LiteralAST , VariableAST , BinaryOperatorAST , CallAST — на выходе получаем возможность вычислить выражение
  • Можно решить проблему с помощью шаблона проектирования Visitor (Посетитель)
  • Можно решить проблему с помощью сопоставления шаблона (pattern matching) по типу, если язык это поддерживает
    • Например, в Go можно использовать type switch
    • В C++ можно было бы использовать std::variant , но он не поддерживает рекурсию в собственном определении

Конструирование AST в парсере

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

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

Если вы используете рекурсивный спуск, то вы скорее всего

  • Пишете по одной функции/методу парсинга на каждое правило формальной грамматики: например, методы Parser::parseExpr , Parser::parseCallExpr , Parser::parseAssignment
  • В случае ошибки разбора бросаете исключение или добавляете объект, описывающий ошибку, в возвращаемое значение каждой функции парсера

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

Для добавления конструирования AST следуйте простым правилам:

  • на каждое правило грамматики создавайте узлы AST с помощью оператора new , а в языке C++ — с помощью std::make_unique
  • сохраняйте указатели на узлы в локальные переменные
  • возвращайте из каждой функции парсинга указатель на узел AST, полученный при разборе по соответствующему правилу грамматики
    • в случае ошибки — бросайте исключение

Восходящий разбор методом свёртки (LL, LR, SLR, LALR)

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

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

Пример декларативного описания правила грамматики с конструированием AST (для генератора парсеров Lemon):

Обработка готового AST


Путём обработки готового AST можно

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

Глава 14 синтаксический разбор слева направо (lr)

. ь в грамматике имеются два правила с нетермииналом
K в левой части, имеющих вид
K -» LK
K -«
по которым K-слово представляет собой конечную последовательность
L-слов, причем множества Посл(L) и Нач(K) (в данном
случае равное Нач(L)) не пересекаются. Используя корректную для
L процедуру ReadL, написать корректную для K процедуру ReadK, не
используя рекурсии. Предполагается, что пустое слово не выводимо
из L.

Решение. По нашим правилам следовало бы написать

procedure ReadK;
begin
| if (Next принадлежит Нач (L)) then begin
| | ReadL;
| | if b then begin ReadK; end;
| end else begin
| | b := true;
| end;
end;

завершение работы гарантируется тем, что пустое слово не выводимо
из L (и, следовательно, перед рекурсивным вызовом длина непрочитанной
части уменьшается).
Эта рекурсивная процедура эквивалентна нерекурсивной:

procedure ReadK;
begin
| b := true;
| while b and (Next принадлежит Нач (L)) do begin
| | ReadL;
| end;
end;

Формально можно проверить эту эквивалентность так. Завершаемость
в обоих случаях ясна. Достаточно проверить поэтому, что тело рекурсивной
процедуры эквивалентно нерекурсивной в предположении,
что ее рекурсивный вызов эквивалентен вызову нерекурсивной процедуры.
Подставим:

if (Next принадлежит Нач (K)) then begin
| ReadL;
| if b then begin
| | b := true;
| | while b and (Next принадлежит Нач (L)) do begin
| | | ReadL;
| | end;
| end;
end else begin
| b := true;
end;

Первую команду b := true можно выкинуть (в этом месте и так b
истинно). Вторую команду можно перенести в начало:

b := true;
if (Next принадлежит Нач (K)) then begin
| ReadL;
| if b then begin
| | while b and (Next принадлежит Нач (L)) do begin
| | | ReadL;
| | end;
| end;
end;

Теперь внутренний if можно выкинуть (если b ложно, цикл while
все равно не выполняется) и добавить в условие внешнего if условие
b (которое все равно истинно).

b := true;
if b and (Next принадлежит Нач (L)) then begin
| ReadL;
| while b and (Next принадлежит Нач (A)) do begin
| | ReadL;
| end;
end;

что эквивалентно приведенной выше нерекурсивной процедуре (из
которой вынесена первая итерация цикла).

13.2.7. Доказать корректность приведенной выше нерекурсивной
программы непосредственно, без ссылок на рекурсивную.

Решение. Рассмотрим наибольшее начало входа, являющееся
K-началом. Оно представляется в виде конкатенации (последовательного
приписывания) нескольких непустых L-слов и, возможно,
одного непустого L-начала, не являющегося L-словом. Инвариант
цикла: прочитано несколько из них; b «=» (последнее прочитанное
является L-словом).
Сохранение инварианта: если осталось последнее слово, это
очевидно; если осталось несколько, то за первым B-словом (из
числа оставшихся) идет символ из Нач(B), и потому это слово —
максимальным началом входа, являющееся B-началом.

На практике при записи грамматики используют сокращения.
Если правила для какого-то нетерминала K имеют вид
K -» L K
K -«
(т.е. K-слова — это последовательности L-слов), то этих правил
не пишут, а вместо K пишут L в фигурных скобках. Несколько правил
с одной левой частью и разными правыми записывают как одно
правило, разделяя альтернативные правые части вертикальной чертой.

Например, рассмотренная выше грамматика для «выр» может
быть записана так:

13.2.8. Написать процедуру, корректно для «выр», следуя
этой грамматике и используя цикл вместо рекурсии, где можно.

procedure ReadSymb (c: Symbol);
| b := (Next = c);
| if b then begin Move; end;
end;

procedure ReadExpr;
begin
| ReadAdd;
| while b and (Next = ‘+’) do begin
| | Move;
| | ReadAdd;
| end;
end;

procedure ReadAdd;
begin
| ReadMult;
| while b and (Next = ‘*’) do begin
| | Move;
| | ReadMult;
| end;
end;

procedure ReadMult;
begin
| if Next = ‘x’ do begin
| | Move;
| end else if Next = ‘(‘ then begin
| | Move;
| | ReadExpr;
| | if b then begin ReadSymb (‘)’); end;
| end else begin
| | b := false;
| end;
end;

13.3. Алгоритм разбора для LL(1)-грамматик.

В этом разделе мы рассморим еще один метод проверки выводимости
в КС-грамматике, называемый по традиции LL(1)-разбором.
Вот его идея в одной фразе: можно считать, что в процессе вывода
мы всегда заменяем самый левый нетерминал и нужно лишь выбрать
одно из правил; если нам повезет с грамматикой, то выбрать правило
можно, глядя на первый символ выводимого из этого нетерминала
слова. Говоря более формально, дадим такое
Определение. Левым выводом (слова в грамматике) называется
вывод, в котором на каждом шаге замене подвергается самый левый
из нетерминалов.

13.3.1. Для каждого выводимого слова (из терминалов) существует
его левый вывод.

Решение. Различные нетерминалы заменяются независимо; если
в процессе вывода появилось слово ..K..L. где K, L — нетерминалы,
то замены K и L можно производить в любом порядке. Поэтому
можно перестроить вывод так, чтобы стоящий левее нетерминал заменялся
раньше. (Формально говоря, надо доказывать индукцией по
длине вывода такой факт: если из некоторого нетерминала K выводится
некоторое
слово A, то существует левый вывод A из K.)

13.3.2. В грамматике с 4 правилами

(1) E -»
(2) E -» T E
(3) T -» ( E )
(4) T -» [ E ]

найти левый вывод слова A = [()([])] и доказать, что он
единствен.

Решение. На первом шаге можно применить только правило (2):
E -» TE
Что будет дальше с T? Так как слово A начинается на «[«, то может
примениться только правило (4):
E -» TE -» [E]E
Первое E должно замениться на TE (иначе вторым символом была бы
скобка «]»):
E -» TE -» [E]E -» [TE]E
и T должно заменяться по (3):
E -» TE -» [E]E -» [TE]E -» [(E)E]E
Далее первое E должно замениться на пустое слово (иначе третьей
буквой слова будет «(» или «[» — только на эти символы может начинаться
слово, выводимое из T):
E -» TE -» [E]E -» [TE]E -» [(E)E]E -» [()E]E
и далее
. -» [()TE]E -» [()(E)E]E -» [()(TE)E]E -» [()([E]E)E]E -»
-» [()([]E)E]E -» [()([])E]E -» [()([])]E -» [()([])].

Что требуется от грамматики, чтобы такой метод поиска левого
вывода был применим? Пусть, например, на очередном шаге самым
левым нетерминалом оказался нетерминал K, т.е. мы имеем слово
вида AKU, где A — слово из терминалов, а U — слово из терминалов
и нетерминалов. Пусть в грамматике есть правила
K -» L M N
K -» P Q
K -» R
Нам надо выбрать одно из них. Мы будем пытаться сделать этот выбор,
глядя на первый символ той части входного слова, которая
выводится из KU.
Рассмотрим множество Нач(LMN) тех терминалов, с которых начинаются
непустые слова, выводимые из LMN. (Это множество равно
Нач(L), объединенному с Нач(M), если из L выводится пустое слово,
а также с Нач(N), если из L и из M выводится пустое слово.)
Чтобы описанный метод был применим, надо, чтобы Нач(LMN),
Нач(PQ) и Нач(R) не пересекались. Но этого мало. Ведь может быть
так, например, что из LMN будет выведено пустое слово, а из слова
U будет выведено слово, начинающееся на букву из Нач(PQ).
Следующие определения учитывают эту проблему.

Напомним, что определение выводимости в КС-грамматике было
дано только для слова из терминалов. Оно очевидным образом обобщается
на случай слов из терминалов и нетерминалов. Можно также
говорить о выводимости одного слова (содержащего терминалы и нетерминалы)
из другого. (Если говорится о выводимости слова без
указания того, откуда оно выводится, то всегда подразумевается
выводимость в грамматике, т.е. выводимость из начального нетерминала.)

Для каждого слова X из терминалов и нетерминалов через
Нач(X) обозначаем множество всех терминалов, с которых начинаются
непустые слова из терминалов, выводимые из X. (В случае, если
из любого нетерминала выводится хоть одно слово из терминалов,
не играет роли, рассматриваем ли мы при определении Нач(X) слова
только из терминалов или любые слова. Мы будем предполагать далее,
что это условие выполнено.)
Для каждого нетерминала K через Послед(K) обозначим множество
терминалов, которые встречаются в выводимых словах сразу
же за K. Кроме того, в Послед(K) включается символ EOI, если существует
выводимое слово, оканчивающееся на K.
Для каждого правила
K -» V
(где K — нетерминал, V — слово, содержащее терминалы и нетерминалы)
определим множество «направляющих терминалов», обозначаемое
Напр(K-«V). По определению оно равно Нач(V), к которому добавлено
Послед(K), если из V выводится пустое слово.

Определение. Грамматика называется LL(1)-грамматикой, если
для любых правил K-«V и K-«W с одинаковыми левыми частями множества
Напр(K-«V) и Напр(K-«W) не пересекаются.

13.3.3. Является ли грамматика
K -» K #
K -«
(выводимыми словами являются последовательности диезов)
LL(1)-грамматикой?

Решение. Нет: символ # принадлежит множествам направляющих
символов для обоих правил (для второго — поскольку # принадлежит
Послед(K)).

13.3.4. Написать LL(1)-грамматику для того же языка.

Решение.
K -» # K
K -«
Как говорят, «леворекурсивное правило» заменено на «праворекурсивное».

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


13.3.5. Пусть дано выводимое в LL(1)-грамматике слово X, в
котором выделен самый левый нетерминал К: X=AKS, где A — слово
из терминалов, S — слово из терминалов и нетерминалов. Пусть существуют
два различных правила грамматики с нетерминалом K в левой
части, и мы применили их к выделенному в X нетерминалу K,
затем продолжили вывод и в конце концов получили два слова из
терминалов, начинающихся на A. Доказать, что в этих словах за
началом A идут разные буквы.

Решение. Эти буквы принадлежат направляющим множествам различных
правил.

13.3.6. Доказать, что если слово выводимо в LL(1)-грамматике,
то его левый вывод единствен.

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

13.3.7. Грамматика называется леворекурсивной, если из некоторого
нетерминала K выводится слово, начинающееся с K, но не
совпадающее с ним. Доказать, что леворекурсивная грамматика, в
которой из каждого нетерминала выводится хотя бы одно непустое
слово из терминалов и для каждого нетерминала существует вывод
(начинающийся с начального нетерминала), в котором он встречается,
не является LL(1)-грамматикой.

Решение. Пусть из K выводится KU, где K — нетерминал, а U —
непустое слово. Можно считать, что это левый вывод (другие нетерминалы
можно не заменять). Рассмотрим вывод K —» KU —» KUU
-«. (знак —» обозначает несколько шагов вывода) и левый вывод
K -» A, где A — непустое слово из терминалов. На каком-то шаге
второй вывод отклоняется от первого, а между тем по обоим путям
может быть получено слово, начинающееся на A (в первом случае
это возможно, так как сохраняется нетерминал K, который может
впоследствии быть заменен на A). Это противоречит возможности
однозначного определения правила, применяемого на очередном шаге
поиска левого вывода. (Oднозначность выполняется для выводов из
начального нетерманала, и надо воспользоваться тем, что K по
предположению встречается в таком выводе.)

Таким образом, к леворекурсивным грамматикам (кроме тривиальных
случаев) LL(1)-наука неприменима. Их приходится преобразовывать
к эквивалентным LL(1)-грамматикам — или пользоваться
другими методами распознавания.

13.3.8. Используя сказанное, построить алгоритм проверки
выводимости слова из терминалов в LL(1)-грамматике, не являющейся
леворекурсивной.

Решение. Мы следуем описанному выше методу поиска левого
вывода, храня лишь часть слова, находящуюся правее уже прочитанной
части входного слова. Другими словами, мы храним слово S из
терминалов и нетерминалов, обладающее таким свойством (прочитанную
часть входа обозначаем через A):

| (1) слово AS выводимо в грамматике;
(И) | (2) любой левый вывод входного слова проходит через стадию
| AS

Вначале A пусто, а S состоит из единственного символа — начального
нетерминала.
Если в некоторый момент S начинается на терминал t и t =
Next, то можно выполнить команду Move и удалить символ t, являющийся
начальным в S, поскольку при этом AS не меняется.
Если S начинается на терминал t и t не равно Next, то входное
слово невыводимо — ибо по условию любой его вывод должен
проходить через AS. (Это же справедливо и в случае Next = EOI.)
Если S пусто, то из условия (И) следует, что входное слово
выводимо тогда и только тогда, когда Next = EOI.
Остается случай, когда S начинается с некоторого нетерминала
K. По доказанному выше все левые выводы из S слов, начинающихся
на символ Next, начинаются с применения к T одного и того
же правила — того, для которого Next принадлежит направляющему
множеству. Если таких правил нет, то входное слово невыводимо.
Если такое правило есть, то нужно применить его к первому символу
слова S — при этом свойство (И) не нарушится. Приходим к такому
алгоритму:

S := пустое слово;
error := false;


Наша цель — построение алгоритма, распознающего принадлежность
произвольного слова к Лев(K). Рассмотрим функцию, сопоставляющую
с каждым словом S (из терминалов и нетерминалов) множество
всех согласованных с ним ситуаций. Это множество называют
состоянием, соответствующим слову S. Будем обозначать его
Сост(S). Достаточно показать, что функция Сост(S) индуктивна,
т.е. что значение Сост(SJ), где J — терминал или нетерминал, может
быть вычислено, если известно Сост(S) и символ J. (Мы видели
ранее, как принадлежность к Лев(К) выражается в терминах этой
функции.) Значение Сост(SJ) вычисляется по таким правилам:
(1) Если слово S было согласовано с ситуацией K-«U_V, причем
слово V начиналось на букву J, то есть V=JW, то теперь слово
SJ будет согласовано с ситуацией K-«UJ_W.
Это правило полностью определяет все ситуации с непустой
левой половиной (то есть не начинающиеся с подчеркивания), согласованные
с SJ. Осталось определить, для каких нетерминалов K
слово SJ принадлежит Лев(K). Это делается по двум правилам:
(2) Если уже выяснено, что ситуация L-«U_V согласована с SJ
(по правилу (1)), а V начинается на нетерминал К, то SJ принадлежит
Лев(K).
(3) Если уже выяснено, что SJ входит в Лев(L) для некоторого
L, L-«V — правило грамматики и V начинается на нетерминал K,
то SJ принадлежит Лев(K).
Заметим, что правило (3) можно рассматривать как аналог
правила (2): в указанных в (3) предположениях ситуация L-«_V
согласована с SJ, а V начинается на нетерминал K.
Корректность этих правил в общем-то очевидна, если хорошенько
подумать. Единственное, что требует некоторых пояснений —
это то, почему с помощью правил (2) и (3) обнаружатся ВСЕ терминалы
K, для которых SJ принадлежит Лев(K). Попытаемся это объяснить.
Рассмотрим правый вывод, в котором SJ стоит слева от K.
Откуда мог взяться в нем нетерминал K? Если правило, которое его
породило, породило также и конец слова SJ, то принадлежность SJ
к Лев(K) будет обнаружена по правилу (2). Если же K было первой
буквой слова, порожденного каким-то другим нетерминалом L, то —
благодаря правилу (3) — достаточно установить принадлежность SJ
к Лев(L). Осталось применить те же рассуждения к L и т.д.
В терминах LR-процесса то же самое можно сказать так. Сначала
нетерминал K может участвовать в нескольких свертках, не
затрагивающих SJ (они соответствуют применению правила (3)), но
затем он обязан подвергнуться свертке, затрагивающей SJ (что соответствует
применению правила (2)).
Осталось выяснить, какие ситуации согласованы с пустым словом,
то есть для каких нетерминалов K пустое слово принадлежит
Лев(K). Это определяется по следующим правилам: (1) начальный
нетерминал таков; (2) если K таков и K -» V — правило грамматики,
причем слово V начинается с нетерминала L, то и L таков.

Глава 14 синтаксический разбор слева направо (lr)

. ь в грамматике имеются два правила с нетермииналом
K в левой части, имеющих вид
K -» LK
K -«
по которым K-слово представляет собой конечную последовательность
L-слов, причем множества Посл(L) и Нач(K) (в данном
случае равное Нач(L)) не пересекаются. Используя корректную для
L процедуру ReadL, написать корректную для K процедуру ReadK, не
используя рекурсии. Предполагается, что пустое слово не выводимо
из L.

Решение. По нашим правилам следовало бы написать

procedure ReadK;
begin
| if (Next принадлежит Нач (L)) then begin
| | ReadL;
| | if b then begin ReadK; end;
| end else begin
| | b := true;
| end;
end;

завершение работы гарантируется тем, что пустое слово не выводимо
из L (и, следовательно, перед рекурсивным вызовом длина непрочитанной
части уменьшается).
Эта рекурсивная процедура эквивалентна нерекурсивной:

procedure ReadK;
begin
| b := true;
| while b and (Next принадлежит Нач (L)) do begin
| | ReadL;
| end;
end;

Формально можно проверить эту эквивалентность так. Завершаемость
в обоих случаях ясна. Достаточно проверить поэтому, что тело рекурсивной
процедуры эквивалентно нерекурсивной в предположении,
что ее рекурсивный вызов эквивалентен вызову нерекурсивной процедуры.
Подставим:

if (Next принадлежит Нач (K)) then begin
| ReadL;
| if b then begin
| | b := true;
| | while b and (Next принадлежит Нач (L)) do begin
| | | ReadL;
| | end;
| end;
end else begin
| b := true;
end;

Первую команду b := true можно выкинуть (в этом месте и так b
истинно). Вторую команду можно перенести в начало:

b := true;
if (Next принадлежит Нач (K)) then begin
| ReadL;
| if b then begin
| | while b and (Next принадлежит Нач (L)) do begin
| | | ReadL;
| | end;
| end;
end;

Теперь внутренний if можно выкинуть (если b ложно, цикл while
все равно не выполняется) и добавить в условие внешнего if условие
b (которое все равно истинно).

b := true;
if b and (Next принадлежит Нач (L)) then begin
| ReadL;
| while b and (Next принадлежит Нач (A)) do begin
| | ReadL;
| end;
end;

что эквивалентно приведенной выше нерекурсивной процедуре (из
которой вынесена первая итерация цикла).

13.2.7. Доказать корректность приведенной выше нерекурсивной
программы непосредственно, без ссылок на рекурсивную.

Решение. Рассмотрим наибольшее начало входа, являющееся
K-началом. Оно представляется в виде конкатенации (последовательного
приписывания) нескольких непустых L-слов и, возможно,
одного непустого L-начала, не являющегося L-словом. Инвариант
цикла: прочитано несколько из них; b «=» (последнее прочитанное
является L-словом).
Сохранение инварианта: если осталось последнее слово, это
очевидно; если осталось несколько, то за первым B-словом (из
числа оставшихся) идет символ из Нач(B), и потому это слово —
максимальным началом входа, являющееся B-началом.

На практике при записи грамматики используют сокращения.
Если правила для какого-то нетерминала K имеют вид
K -» L K
K -«
(т.е. K-слова — это последовательности L-слов), то этих правил
не пишут, а вместо K пишут L в фигурных скобках. Несколько правил
с одной левой частью и разными правыми записывают как одно
правило, разделяя альтернативные правые части вертикальной чертой.

Например, рассмотренная выше грамматика для «выр» может
быть записана так:

13.2.8. Написать процедуру, корректно для «выр», следуя
этой грамматике и используя цикл вместо рекурсии, где можно.

procedure ReadSymb (c: Symbol);
| b := (Next = c);
| if b then begin Move; end;
end;

procedure ReadExpr;
begin
| ReadAdd;
| while b and (Next = ‘+’) do begin
| | Move;
| | ReadAdd;
| end;
end;

procedure ReadAdd;
begin
| ReadMult;
| while b and (Next = ‘*’) do begin
| | Move;
| | ReadMult;
| end;
end;

procedure ReadMult;
begin
| if Next = ‘x’ do begin
| | Move;
| end else if Next = ‘(‘ then begin
| | Move;
| | ReadExpr;
| | if b then begin ReadSymb (‘)’); end;
| end else begin
| | b := false;
| end;
end;

13.3. Алгоритм разбора для LL(1)-грамматик.

В этом разделе мы рассморим еще один метод проверки выводимости
в КС-грамматике, называемый по традиции LL(1)-разбором.
Вот его идея в одной фразе: можно считать, что в процессе вывода
мы всегда заменяем самый левый нетерминал и нужно лишь выбрать
одно из правил; если нам повезет с грамматикой, то выбрать правило
можно, глядя на первый символ выводимого из этого нетерминала
слова. Говоря более формально, дадим такое
Определение. Левым выводом (слова в грамматике) называется
вывод, в котором на каждом шаге замене подвергается самый левый
из нетерминалов.

13.3.1. Для каждого выводимого слова (из терминалов) существует
его левый вывод.

Решение. Различные нетерминалы заменяются независимо; если
в процессе вывода появилось слово ..K..L. где K, L — нетерминалы,
то замены K и L можно производить в любом порядке. Поэтому
можно перестроить вывод так, чтобы стоящий левее нетерминал заменялся
раньше. (Формально говоря, надо доказывать индукцией по
длине вывода такой факт: если из некоторого нетерминала K выводится
некоторое
слово A, то существует левый вывод A из K.)

13.3.2. В грамматике с 4 правилами

(1) E -»
(2) E -» T E
(3) T -» ( E )
(4) T -» [ E ]

найти левый вывод слова A = [()([])] и доказать, что он
единствен.

Решение. На первом шаге можно применить только правило (2):
E -» TE
Что будет дальше с T? Так как слово A начинается на «[«, то может
примениться только правило (4):
E -» TE -» [E]E
Первое E должно замениться на TE (иначе вторым символом была бы
скобка «]»):
E -» TE -» [E]E -» [TE]E
и T должно заменяться по (3):
E -» TE -» [E]E -» [TE]E -» [(E)E]E
Далее первое E должно замениться на пустое слово (иначе третьей
буквой слова будет «(» или «[» — только на эти символы может начинаться
слово, выводимое из T):
E -» TE -» [E]E -» [TE]E -» [(E)E]E -» [()E]E
и далее
. -» [()TE]E -» [()(E)E]E -» [()(TE)E]E -» [()([E]E)E]E -»
-» [()([]E)E]E -» [()([])E]E -» [()([])]E -» [()([])].

Что требуется от грамматики, чтобы такой метод поиска левого
вывода был применим? Пусть, например, на очередном шаге самым
левым нетерминалом оказался нетерминал K, т.е. мы имеем слово
вида AKU, где A — слово из терминалов, а U — слово из терминалов
и нетерминалов. Пусть в грамматике есть правила
K -» L M N
K -» P Q
K -» R
Нам надо выбрать одно из них. Мы будем пытаться сделать этот выбор,
глядя на первый символ той части входного слова, которая
выводится из KU.
Рассмотрим множество Нач(LMN) тех терминалов, с которых начинаются
непустые слова, выводимые из LMN. (Это множество равно
Нач(L), объединенному с Нач(M), если из L выводится пустое слово,
а также с Нач(N), если из L и из M выводится пустое слово.)
Чтобы описанный метод был применим, надо, чтобы Нач(LMN),
Нач(PQ) и Нач(R) не пересекались. Но этого мало. Ведь может быть
так, например, что из LMN будет выведено пустое слово, а из слова
U будет выведено слово, начинающееся на букву из Нач(PQ).
Следующие определения учитывают эту проблему.

Напомним, что определение выводимости в КС-грамматике было
дано только для слова из терминалов. Оно очевидным образом обобщается
на случай слов из терминалов и нетерминалов. Можно также
говорить о выводимости одного слова (содержащего терминалы и нетерминалы)
из другого. (Если говорится о выводимости слова без
указания того, откуда оно выводится, то всегда подразумевается
выводимость в грамматике, т.е. выводимость из начального нетерминала.)

Для каждого слова X из терминалов и нетерминалов через
Нач(X) обозначаем множество всех терминалов, с которых начинаются
непустые слова из терминалов, выводимые из X. (В случае, если
из любого нетерминала выводится хоть одно слово из терминалов,
не играет роли, рассматриваем ли мы при определении Нач(X) слова
только из терминалов или любые слова. Мы будем предполагать далее,
что это условие выполнено.)
Для каждого нетерминала K через Послед(K) обозначим множество
терминалов, которые встречаются в выводимых словах сразу
же за K. Кроме того, в Послед(K) включается символ EOI, если существует
выводимое слово, оканчивающееся на K.
Для каждого правила
K -» V
(где K — нетерминал, V — слово, содержащее терминалы и нетерминалы)
определим множество «направляющих терминалов», обозначаемое
Напр(K-«V). По определению оно равно Нач(V), к которому добавлено
Послед(K), если из V выводится пустое слово.

Определение. Грамматика называется LL(1)-грамматикой, если
для любых правил K-«V и K-«W с одинаковыми левыми частями множества
Напр(K-«V) и Напр(K-«W) не пересекаются.

13.3.3. Является ли грамматика
K -» K #
K -«
(выводимыми словами являются последовательности диезов)
LL(1)-грамматикой?

Решение. Нет: символ # принадлежит множествам направляющих
символов для обоих правил (для второго — поскольку # принадлежит
Послед(K)).

13.3.4. Написать LL(1)-грамматику для того же языка.

Решение.
K -» # K
K -«
Как говорят, «леворекурсивное правило» заменено на «праворекурсивное».

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

13.3.5. Пусть дано выводимое в LL(1)-грамматике слово X, в
котором выделен самый левый нетерминал К: X=AKS, где A — слово
из терминалов, S — слово из терминалов и нетерминалов. Пусть существуют
два различных правила грамматики с нетерминалом K в левой
части, и мы применили их к выделенному в X нетерминалу K,
затем продолжили вывод и в конце концов получили два слова из
терминалов, начинающихся на A. Доказать, что в этих словах за
началом A идут разные буквы.

Решение. Эти буквы принадлежат направляющим множествам различных
правил.


13.3.6. Доказать, что если слово выводимо в LL(1)-грамматике,
то его левый вывод единствен.

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

13.3.7. Грамматика называется леворекурсивной, если из некоторого
нетерминала K выводится слово, начинающееся с K, но не
совпадающее с ним. Доказать, что леворекурсивная грамматика, в
которой из каждого нетерминала выводится хотя бы одно непустое
слово из терминалов и для каждого нетерминала существует вывод
(начинающийся с начального нетерминала), в котором он встречается,
не является LL(1)-грамматикой.

Решение. Пусть из K выводится KU, где K — нетерминал, а U —
непустое слово. Можно считать, что это левый вывод (другие нетерминалы
можно не заменять). Рассмотрим вывод K —» KU —» KUU
-«. (знак —» обозначает несколько шагов вывода) и левый вывод
K -» A, где A — непустое слово из терминалов. На каком-то шаге
второй вывод отклоняется от первого, а между тем по обоим путям
может быть получено слово, начинающееся на A (в первом случае
это возможно, так как сохраняется нетерминал K, который может
впоследствии быть заменен на A). Это противоречит возможности
однозначного определения правила, применяемого на очередном шаге
поиска левого вывода. (Oднозначность выполняется для выводов из
начального нетерманала, и надо воспользоваться тем, что K по
предположению встречается в таком выводе.)

Таким образом, к леворекурсивным грамматикам (кроме тривиальных
случаев) LL(1)-наука неприменима. Их приходится преобразовывать
к эквивалентным LL(1)-грамматикам — или пользоваться
другими методами распознавания.

13.3.8. Используя сказанное, построить алгоритм проверки
выводимости слова из терминалов в LL(1)-грамматике, не являющейся
леворекурсивной.

Решение. Мы следуем описанному выше методу поиска левого
вывода, храня лишь часть слова, находящуюся правее уже прочитанной
части входного слова. Другими словами, мы храним слово S из
терминалов и нетерминалов, обладающее таким свойством (прочитанную
часть входа обозначаем через A):

| (1) слово AS выводимо в грамматике;
(И) | (2) любой левый вывод входного слова проходит через стадию
| AS

Вначале A пусто, а S состоит из единственного символа — начального
нетерминала.
Если в некоторый момент S начинается на терминал t и t =
Next, то можно выполнить команду Move и удалить символ t, являющийся
начальным в S, поскольку при этом AS не меняется.
Если S начинается на терминал t и t не равно Next, то входное
слово невыводимо — ибо по условию любой его вывод должен
проходить через AS. (Это же справедливо и в случае Next = EOI.)
Если S пусто, то из условия (И) следует, что входное слово
выводимо тогда и только тогда, когда Next = EOI.
Остается случай, когда S начинается с некоторого нетерминала
K. По доказанному выше все левые выводы из S слов, начинающихся
на символ Next, начинаются с применения к T одного и того
же правила — того, для которого Next принадлежит направляющему
множеству. Если таких правил нет, то входное слово невыводимо.
Если такое правило есть, то нужно применить его к первому символу
слова S — при этом свойство (И) не нарушится. Приходим к такому
алгоритму:

S := пустое слово;
error := false;

Илон Маск рекомендует:  Что такое код hw_api_attribute
Понравилась статья? Поделиться с друзьями:
Кодинг, CSS и SQL