А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 52
Текст из файла (страница 52)
1. Следующие символы являются терминалами. а) Строчные буквы из начала алфавита, такие как а, б, с. б) Символы операторов, такие как +, * и т.п. в) Символы пунктуации, такие как запятые, скобки и т.п. г) Цифры О, 1,..., 9. д) Строки, выделенные полужирным шрифтом, такие как Ы н 1Г, каждая из которых представляет терминальный символ. 2. Следующие символы являются нетерминалами. а) Прописные буквы из начала алфавита, такие как А, В, С.
б) Буква Я, которая обычно означает стартовый символ. в) Имена из строчных букв, выделенные курсивом, такие как лгтг и ехрг. г) Прн рассмотрении программных конструкций прописные буквы могут использоваться для представления нетерминалов конструкций. Например, нетерминалы для выражений, слагаемых и сомножителей часто представлены буквами Е, Т и Е соответственно.
3. Прописные буквы из конца алфавита, такие как Х, У, Я, представляют грамматические символы, т.е. либо терминалы, либо нетерминалы. 4. Строчные буквы из конца алфавита, такие как и, и,..., х, обозначают строки терминалов. 5. Строчные греческие буквы, такие как о, )3, 7, представляют (возможно, пустые) строки грамматических символов. Таким образом, в общем виде продукция может быть записана как А + о, где А — заголовок продукции, а гх — ее тело. 6. Множество продукций А — оп А — аз,..., А — гхь с общим заголовком А (называющихся А-продукциями) может быть записано как А — о1 ~ оз ~ ~ оы оы оз,..., аь называются альтернативами (а11еглабиез) А. 7.
Если иное не указано явно, заголовок первой продукции является стартовым символом. 261 4.2. Контекстно-свободные грамматики Пример 4.2. Используя указанные соглашения, грамматика из примера 4.1 может быть сокращенно записана как Š— ~ Е+Т~Š— Т)Т Т вЂ” Т*Е)Т/г ~ŠŠ— (Е)(Ы Соглашения по обозначениям говорят нам, что Е, Т и Š— нетерминалы, причем Е является стартовым символом.
Остальные символы являются терминалами. 42.3 Порождения Построение дерева разбора можно сделать совершенно точным при помощи порождений, рассматривая каждую продукцию как правило для переписывания. Начиная со стартового символа, на каждом шаге переписывания нетерминал замещается телом одной из его продукций. Описанные действия соответствуют нисходящему построению дерева разбора, но точность, достигаемая таким образом, оказывается полезной при рассмотрении восходящего синтаксического анализа. Как мы увидим, восходящий синтаксический анализ связан с классом порождений, известных как правые порождения, когда на каждом шаге переписывается крайний справа нетерминал. Рассмотрим, например, следующую грамматику с единственным нетерминалом Е, в которой к грамматике (4.3) добавлена продукция Š— — Е: Š— Е+ Е ( Е * Е ~ — Е ) (Е) ( Ы (4.5) Продукция Š— г — Е означает, что если Е обозначает выражение, то — Е также должно обозначать выражение. Замена одного Е на — Е может быть описана записью Е =ь — Е Она читается как "Е порождает — Е".
Продукция Š— — Е может быть применена для замены любого экземпляра Е в любой строке символов грамматики на (Е), например Е * Е ~ (Е) * Е или Е х Е =ь Е * (Е). Можно взять один нетермннал Е и многократно применять продукции в произвольном порядке для получения последовательности замещений, например Е ~ — Е ~ — (Е) — — (И) Такая последовательность замен называется выводом (депчабоп) или порождением' — (И) из Е. Это порождение доказывает, что строка — (И) является конкретным примером выражения.
'В оригинале — йепгаапола (аыяолы). В связи с неоднозначностью общепринятою а русскоязычной литературе термина "вывод" палее используется термин "поролщение". — Прим. лер. 262 Глава 4. Синтаксический анализ Чтобы дать общее определение порождения, рассмотрим нетерминап А в средине последовательности грамматических символов, как в случае сто), где гт и 13— произвольные строки грамматических символов. Предположим, что А — 7 является продукцией. Тогда мы записываем стА)3 =о ст717.
Символ ~ означает "порождение за один шаг". Если последовательность порождений тт1 => гтз =~ ~ и„ переписывает слы заменяя его ст„, мы говорим, что ст1 поролсдаепз ск„. Часто нам надо сказать "порождает за нуль или более шагов". Для этой цели используется символ =~. Таким образом, 1) а =ь ст для любой строки ст; 2) если тт =ь,9 и )3 =о 7, то се =~ Т.
Аналогично символ ~ используется для обозначения "порождает за один или более шагов". Если Я =~ тт, где Я вЂ” стартовый символ грамматики С, то мы говорим, что а является сентенциальной формойз С. Заметим, что сентенциальная форма может содержать как терминалы, так и нетерминалы, а также быть пустой. Предложение С представляет собой сентенциальную форму без нетерминалов. Язык, генерируемый грамматикой, представляет собой множество ее предложений. Таким образом, строка терминалов зп принадлежит генерируемому грамматикой С языку Ь (С) тогда и только тогда, когда зп является предложением С (или Я =~ зп).
Язык, который может быть сгенерирован грамматикой, называется контекстносвободнымязыком. Если две грамматики генерируют один и тот же язык, то эти грамматики называются эквивалентными. Строка — (Ы+ Ы) является предложением грамматики (4.5) ввиду наличия порождения Е =~ — Е => — (Е) ~ — (Е+ Е) ~ — (Ы+ Е) =ь — (Ы+ И) (4.6) Строки Е, — Е, — (Е),..., — (Ы + Ы) представляют собой сентенциальные формы данной грамматики. Для указания того, что — (Ы + Ы) может быть пороящено из Е, мы записываем Е ь — (Ы+ Ы). На кажцом шаге порождения осуществляется два выбора — мы должны выбрать заменяемый нетерминал, а затем продукцию, у которой данный нетерминал является заголовком.
Например, приведенное ниже альтернативное порождение для — (Ы + Ы) отличается от порождения (4.6) последними двумя шагами: Е ~ — Е ~ — (Е) =~ — (Е+ Е) ~ — (Е+ Ы) ~ — (Ы+ И) (4.7) Каждый нетерминал замещается тем же телом, что и ранее, но в другом порядке. В руссколзычной литературе также используетсл термин "цепочка": цепочка терминалов и нетерминалов. — Прим. ред. 263 4.2. Контекстно-свободные грамматики Чтобы понять, как работают синтаксические анализаторы, рассмотрим порождения, в которых замещаемый нетерминал на каждом шаге выбирается следующим образом. 1. В левых (!ейпозг) порождениях в каждом предложении всегда выбирается крайний слева нетерминал, Если а «,3 является шагом, на котором замещается крайний слева нетерминал а, то это записывается как а =~ 13.
1т 2. В правых (Пй)з1шозг) порождениях в каждом предложении всегда выбирается крайний справа нетерминал; в зтом случае мы пишем гг =~ )3. гт Порождение (4.6) левое, поскольку его можно переписать как Е =ь — Е =~ — (Е) ~ — (Е+ Е) =~ — (Ы+ Е) =ь — (н$+ н1) ьь ьь Ьп Ьп ьь Заметим, что порождение (4.7) — правое. С использованием наших соглашений по обозначениям каждый левый шаг может быть записан как юА у =ь юд.у, где ю состоит только из терминалов, А — д— 1т примененная продукция, а 7 — строка грамматических символов. Чтобы подчеркнуть, что а порождает )3 путем левого порождения, мы записываем гг =~,3.
Если Ьь Я =~ о, то мы говорим, что гг — левосентенциальная форма рассматриваемой Ьь грамматики. Аналогичные определения выполняются и для правых порождений. Правые порождения иногда называются каноническими. 4.2.4 Деревья разбора и порождения Дерево разбора может рассматриваться как графическое представление порождения, из которого удалена информация о порядке замещения нетерминалов. Каждый внутренний узел дерева разбора представляет применение продукции. Внутренний узел дерева помечен нетерминалом А из заголовка соответствующей продукции, а дочерние узлы слева направо — символами из тела продукции, использованной в порождении для замены А.
Например, дерево разбора для — (И + Ы), показанное на рис. 4.3, получается как в результате порождения (4.6), так и в результате порождения (4.7). Листья дерева разбора помечены нетерминаламн или терминалами и, будучи прочитаны слева направо, образуют сентенциальную форму, называемую кроной (у)е16) нли границей (йопйег) дерева. Для того чтобы увидеть взаимосвязь между порождением и деревьями разбора, рассмотрим произвольное приведение аг ~ ггз ~ ~ а„, где ггу— отдельный нетермннал А. Для каждой сентенциальной формы сн в приведении Глава 4. Синтаксический анализ Рис.
4.3. Дерево разбора ~я'-(И'+ И) можно построить дерево разбора, кроной которого является о,. Этот процесс представляет собой индукцию по з'. Блзис: дерево для а1 = А представляет собой единственный узел, помеченный А. Индукция: предположим, что мы уже построили дерево разбора, имеющее крону сн 1 = Х1Хз... Хь (заметим, что в соответствии с нашими соглашениями об обозначениях Х, может означать нетерминал или терминал). Предположим, что а, 1 порождает еч заменой нетерминала Х на )3 = У1Уз... У . Иначе говоря, на з-м шаге порождения к сн 1 применяется продукция Х вЂ” )3, порождая сн = = Х,Х,...Ху,ДХ,+,...Х„. Для моделирования этого шага порождения находим у-й слева не-е-лист в текущем дереве разбора, который помечен Х . Мы даем этому листу т дочерних узлов, помеченных Уы Уз,..., У слева направо.
В частном случае, если т = О, то )з = е, и у з-го листа появляется один дочерний узел, помеченный е. Пример 4.3. Последовательность деревьев разбора, построенная на основе порождения (4.6), показана на рис. 4.4. Первый шаг этого порождения — Е ~ — Е, Для моделирования этого шага мы добавляем к корню Е начального дерева два дочерних узла, помеченных — и Е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
